1. 중첩 루프 조인 (NLJ, Nested Loop Join)


  • 중첩 for 문과 같은 원리로 조건에 맞는 조인을 하는 방법을 말합니다.
  • Index에 의한 Random Access 비용이 많이 증가하기 때문에 대용량 데이터를 다루기에는 적절하지 않습니다.

 

중첩 루프 조인의 작동

# CS 전공지식 노트 226 page

for each row in t1 matching reference key {
    for each row in t2 matching reference key {
        if row satisfies join conditions, send to client
    }
}
  • 위에 있는 코드는 중첩 루프 조인을 사용하여 t1 테이블과 t2 테이블을 조인하는 의사 코드입니다.
  • t1 테이블에서 행을 한 번에 하나씩 읽고, t2 테이블에서도 행을 하나씩 읽으며 조건에 맞는 데이터를 찾아서 반환하게 됩니다.
  • 여기서 t1을 Driving Table이라고 하며, t2를 Driven Table이라고 합니다. 
  • 중첩 루프 조인에서는 Driving Table을 적절하게 선택해야 합니다. 처음 Driving Table에 해당되는 row가 너무 많다면, 그만큼의 반복을 해줘야하기 때문에 Driving Table에서 Where절로 row 수를 최대한 줄일 수 있어야 합니다.
  • Driving Table의 Join Column에 index가 존재하는지도 확인해봐야 합니다. 존재하지 않는다면 Random Access가 아닌 Full Table Scan을 통해서 모두 비교해야 하기 때문에 index를 생성하는 것이 좋습니다.

 

[출처] https://dataonair.or.kr/db-tech-reference/d-guide/sql/?mod=document&uid=356

 

* Driving Table : Join 할 때, 먼저 Access되어 Access Path를 주도하는 테이블
* Driven Table : Join 할 때, 나중에 Access되는 테이블

 

 

 

2. 정렬 병합 조인 (Sort Merge Join)


  • 각각의 테이블을 조인할 필드 기준으로 정렬한 후 조인 작업을 수행하는 조인 방법입니다.
  • 조인할 때 사용할 적절한 인덱스가 존재하지 않고, 대용량 테이블을 조인하는 데 사용됩니다.
  • 조인 조건으로 비교 연산자(>, <, >=, <=)가 있을 때도 사용됩니다.
  • 조회 범위가 좁을 때 유리했던 Nested Loop Join과는 다르게 조회 범위가 많을 때 주로 선택되어 사용합니다.

 

정렬 병합 조인의 작동

  • 각 테이블에 대해서 독립적으로 데이터를 읽어옵니다. 인덱스가 존재하는 컬럼의 테이블은 Random Access, 인덱스가 존재하지 않는 컬럼의 테이블은 Full Table Scan을 사용합니다.
  • 읽힌 각 테이블의 데이터를 조인을 위한 연결고리에 대하여 정렬을 수행합니다.
  • 정렬이 모두 끝난 뒤 정렬된 데이터를 차례로 Scan 하면서 연결고리의 조건으로 Merge하여 데이터를 반환합니다.

 

[출처]&nbsp;https://dataonair.or.kr/db-tech-reference/d-guide/sql/?mod=document&uid=356

 

 

 

3. 해시 조인 (Hash Join)


  • 조인할 두 테이블 중 하나를 해시 테이블로 선정하여 조인에 사용되는 컬럼 값을 해시 알고리즘으로 비교하여 조인하는 방법입니다.
  • 동등(=) 조인에서만 사용할 수 있습니다.
  • Sort Merge Join을 할 때, 테이블 크기가 너무 커서 Sort에 드는 부하가 너무 클 때 해시 조인가 사용됩니다.
  • 조인에 사용되는 컬럼에 적절한 index가 존재하지 않아서 Nested Loop Join을 사용하기에 효율적이지 못할 때 사용됩니다.

 

해시 조인의 작동

  • A 테이블과 B 테이블을 조인할 때, 둘 중 바이트가 더 작은 테이블을 읽어서 Hash Area에 해시 테이블을 생성합니다. 이때 해시 테이블의 Key는 조인에 사용되는 필드가 됩니다.
  • 만약 A 테이블이 해시 테이블로 생성되었다면, A 테이블은 Build Input이라고 하고, B 테이블은 Probe Input이라고 합니다.
  • B 테이블을 스캔하며 조인 컬럼을 해시 함수에 넣고, 반환되는 버킷 주소로 찾아가 해시 체인을 스캔하며 Join 할 데이터를 찾아서 반환합니다.

 

[출처]&nbsp;https://dataonair.or.kr/db-tech-reference/d-guide/sql/?mod=document&uid=356

 

 

 

💡 나올 수 있는 질문

  1. 중첩 루프 조인(Nested Loop Join)에 대해서 설명해보세요.

 

1. 관계형 데이터베이스 (RDBMS)


  • 행과 열로 구성된 표 형식 데이터를 저장하는 데이터베이스입니다.
  • SQL이라는 언어를 써서 조작할 수 있습니다.
  • 관계형 데이터베이스의 종류에는 MySQL, Oracle, PostgreSQL, MSSQL 등이 있습니다.
  • 관계형 데이터베이스는 표준 SQL을 지키기는 하지만 각 제품에서 특화시킨 SQL을 사용합니다.

 

(1) MySQL

  • 세계에서 가장 많이 사용되고 있는 오픈소스 관계형 데이터베이스입니다.
  • MySQL의 최고 장점은 오픈소스이기 때문에 무료라는 것입니다.
  • 문자열 비교에 있어서 대소문자를 구분하지 않습니다. BINARY 설정 등을 이용하면 추가 설정이 가능합니다.
  • nested loop join만을 제공한다는 단점이 있습니다. MySQL 8.0.18 릴리스 버전 이후로는 hash join도 제공하게 되었습니다.
nested loop join (중첩 루프 조인)
: 바깥 테이블의 처리 범위를 하나씩 접근하며 추출된 값으로 안쪽 테이블을 조인하는 방법입니다.
중첩 for문과 비슷한 동일한 원리라고 생각하면 됩니다. 비용이 많이 들어서 대용량 테이블에서는 사용하지 않습니다.

hash Join (해시 조인)
: 해시 테이블을 기반으로 조인하는 방법을 말합니다. 2개의 테이블을 조인할 때, 하나의 테이블을 해시 테이블로서 사용합니다.
동등(=) 조인에서만 사용이 가능하고, 테이블의 크기가 너무 크다면 디스크를 사용하는 비용이 증가할 수 있습니다.

 

 

(2) Oracle DB

  • Oracle 사에서 만든 관계형 데이터베이스입니다.
  • MySQL, MSSQL 보다 대용량 정보를 관리할 때 성능이 좋습니다.
  • 고성능 트랜잭션 처리를 제공하여 속도가 빠릅니다.
  • SQL문을 실행하는 가장 효율적인 방법을 제공합니다. 쿼리비용 최소화를 위해서 테이블 인덱싱 분석을 합니다.
  • 과거 시점의 데이터 조회도 가능하고, 커밋 이전의 상태로 되돌릴 수 있는 기능이 존재합니다.
  • 메모리를 너무 많이 차지하기 때문에 고사양 장비가 요구된다는 단점이 있습니다.

 

 

(3) PostgreSQL

  • 다양한 Join 방법을 제공합니다. (nested loop join, hash join, sort merge join)
  • update 시에는 기존에 있던 행을 지우고, 변경된 데이터를 가지는 새로운 행을 추가하는 방식을 사용하여 update 성능은 비교적 좋지 않습니다.
  • 데이터베이스 클러스터 백업 기능을 제공합니다.
  • hot backup과 wal replay를 활용하여 원하는 시점의 데이터 복구가 가능합니다.
  • SQL 뿐만 아니라 JSON을 이용해서도 데이터에 접근할 수 있습니다.
sort merge join (정렬 병합 조인)
: 각각의 테이블에서 조인할 필드 기준으로 정렬한 후 조인 작업을 수행하는 조인방법입니다.

hot backup
: 데이터베이스가 실행 중인 상태에서 데이터를 백업받는 방식입니다. 

 

(4) MSSQL

  • 마이크로소프트 사에서 사이베이스(Sybase)를 기반으로 개발한 관계형 데이터베이스입니다.
  • 윈도우 개발환경에서 DB가 필요할 경우 MSSQL을 사용합니다.
  • windows 기반 서버에서만 작동되도록 설계되어 있고, 라이센스 비용이 비싸다는 단점이 있습니다.
  • 하지만 우수한 데이터 복구 지원을 제공한다는 장점이 존재합니다.

 

 

 

2. NoSQL 데이터베이스


  • SQL를 사용하지 않는 데이터베이스를 말합니다.
  • 대표적으로 알려진 NoSQL 데이터베이스는 MongoDB와 Redis가 존재합니다.

 

(1) MongoDB

  • JSON을 통해서 데이터에 접근할 수 있습니다.
  • 데이터가 저장될 때는 Binary JSON 형태로 데이터가 저장되며 도큐먼트 기반의 데이터베이스입니다.
  • 확장성이 뛰어나고, 빅데이터를 저장할 때 성능이 좋습니다.
  • 스키마를 정해 놓지 않고 데이터를 삽입하기 때문에 다양한 도메인의 데이터베이스를 기반으로 분석할 수 있습니다.
  • 도큐먼트를 생성할 때마다 다른 컬렉션과 구별하기 위해서 유니크한 ObjectId가 생성됩니다.

[출처] CS 전공지식 노트 p.216

 

(2) Redis

  • 인메모리 데이터베이스이며, Key-Value 데이터 모델 기반의 데이터베이스입니다.
  • 다른 데이터베이스를 앞단에 두어 사용하는 캐싱 계층으로 사용됩니다.
  • 기본적인 데이터 타입은 문자열이며 최대 512MB까지 저장할 수 있습니다. 이외에도 Set과 Hash 등을 지원합니다.

 

 

 

🔗 참고 자료

주요 RDBMS의 종류

면접을 위한 CS 전공지식 노트

1. 관계


  • 하나의 데이터 베이스에는 여러 개의 테이블이 존재합니다. 
  • 여러 개의 테이블들은 서로 관계를 가지고 있고, 이런 관계를 '관계 화살표'를 이용하여 표현합니다.

 

[그림 1] 관계화살표 예시

 

 

여러 가지 관계의 종류에 대해서 알아봅시다.

 

(1) 1 : 1 관계

  • 유저 한 명에게는 하나의 유저 이메일이 존재한다고 해봅시다.
  • 그럼 유저와 유저 이메일은 1 : 1 관계를 가지게 됩니다.
  • 1 : 1 관계를 사용하면 두 개의 테이블로 나누어 테이블 구조를 더 쉽게 이해할 수 있도록 해준다는 장점이 있습니다.

[그림 2] 1 : 1 관계의 관계 화살표

 

 

(2) 1 : N 관계

  • 위에서 만들었던 유저 테이블이 존재하고, 만약 이 유저가 구매할 상품들을 장바구니에 담는다고 해봅시다.
  • 한 명의 유저는 여러 개의 상품을 장바구니에 담을 수 있습니다.
  • 이때는 유저와 상품이 1 : N 관계를 가지게 됩니다.
  • 여기서 주의해야 할 점은 유저가 장바구니에 어떠한 상품도 안 담을 수도 있기 때문에 0이라는 값도 생각해야 합니다.

[그림 3] 1 : N 관계의 관계 화살표

 

 

(3) N : M 관계

  • 만약 학생과 학생들이 듣는 강의가 여러 개 있다고 생각해 봅시다.
  • 한 명의 학생은 여러 개의 강의를 가질 수 있고, 하나의 강의도 여러 명의 학생을 가질 수 있습니다.
  • 이때는 관계 테이블을 하나 형성해서 학생과 강의가 N : M 관계를 가질 수 있도록 해줍니다.

[그림 4] N : M 관계의 관계 화살표

 

 

 

 

2. 키


  • 테이블 사이의 관계를 명확하게 구분할 수 있게 해 주고, 테이블 자체의 인덱스를 위해서 존재하는 개념이 '키(Key)'입니다.
  • 키의 종류에는 슈퍼키, 후보키, 기본키, 대체키, 외래키가 존재합니다.

[그림 5] 슈퍼키, 후보키, 기본키, 대체키의 관계

 

 

(1) 유일성과 최소성

  • 유일성은 말 그대로 중복되는 값이 없이 유일한 값이어야 하는 성질을 말합니다.
  • 최소성은 해당 키를 구성하는 모든 부분 집합들이 유일성을 가지지 않는 성질을 말합니다.
  • 다시 말해서 유일성은 하나의 Key로 하나의 Tuple을 유일하게 구별할 수 있는 성질을 말하고, 최소성은 꼭 필요한 속성들만을 가지고 구성되어 있는 성질을 말합니다.

[그림 6] 속성 A, B, C에 대한 표

 

[그림 6]을 예시로 들면서 유일성과 최소성을 이해해 봅시다.

[그림 7] 그림 6을 분석해본 표

 

[그림 7]은 키가 될 수 있는 요소의 부분 집합을 알아보고, 유일성과 최소성 그리고 키로 사용할 수 있는지의 여부를 분석해 본 표입니다.

  • (A), (B), (C)는 각각 겹치는 값들이 존재하기 때문에 유일성을 만족하지 않습니다. 유일성을 만족하지 않기 때문에 최소성은 볼 필요도 없이 존재하지 않고, 키로 사용할 수 없습니다.
  • (A, B), (B, C), (A, C)는 각각 겹치는 값들이 없기 때문에 유일성을 만족합니다. 최소성을 보기 위해서 각 요소의 부분 집합을 확인해 보면 각 부분 집합의 요소들이 모두 유일성을 가지고 있지 않기 때문에 키로 사용할 수 있습니다.
  • (A, B, C)는 겹치는 값들이 없기 떄문에 유일성을 만족합니다. 하지만 부분 집합 중 {A, B}, {B, C}, {A, C}는 이미 유일성을 가지고 있기 때문에 키로 사용할 수 없는 슈퍼키입니다.

 

 

(2) 기본키 (Primary Key, PK)

  • 기본키는 유일성과 최소성을 모두 만족하는 키를 말합니다.
  • 기본키를 사용하면 테이블에서 어떤 요소를 유일하게 구분해 낼 수 있습니다.
  • 기본키는 자연키와 인조키 중에서 골라서 설정하게 됩니다.

 

# 자연키

이름 그대로 속성 중 자연스럽게 중복되지 않는 것들을 뽑다가 나오는 키를 말합니다. "이름", "성별", "주민등록번호"가 있을 때, 이름과 성별을 중복된 값이 들어올 가능성이 매우 높습니다. 그에 반해 주민등록번호는 중복될 가능성이 매우 희박하기 때문에 자연스럽게 주민등록번호를 키로 사용하게 됩니다.

 

# 인조키

요소마다 인위적으로 어떤 Id 값을 부여하는 것을 말합니다. 대표적으로 MySQL의 auto-increment가 인조키의 예시에 속합니다. 사용해 봤다면 알겠지만, MySQL에서 데이터를 추가하게 되면 순차적으로 Id 값이 증가하는 것을 볼 수 있습니다.

 

 

(3) 외래키 (Foreign Key, FK)

  • 다른 테이블의 기본키를 그래도 참조하는 값으로서 개체와의 관계를 식별하는 데 사용하는 키입니다.
  • 외래키는 중복되어도 상관없습니다.
  • 앞서 설명했던 관계 그래프에서 유저와 상품의 사이를 예시로 들어봅시다.

[그림 8] Product 테이블에 있는 외래키 user_id

 

Product와 User는 N : 1 관계를 가지고 있기 때문에 Product에서 자신을 주문한 User에 대한 정보를 가지고 있어야 합니다. 이때 관계를 연결시켜 주기 위해서 Product 테이블에 자신을 주문한 User의 Id 값을 외래키로 넣어줍니다.

 

 

(4) 후보키 (Candidate Key)

  • 기본키(PK)가 될 수 있는 후보들의 집합입니다.
  • 후보키도 유일성과 최소성을 모두 만족합니다.

 

 

(5) 대체키 (Alternate Key)

  • 기본키로 대체될 수 있는 키를 말합니다.
  • 후보키가 여러 개인 경우 1개를 기본키(PK)로 지정하고, 기본키가 되지 못한 나머지 후보키들을 모두 대체키라고 할 수 있습니다.

 

 

(6) 슈퍼키 (Super Key)

  • 유일성을 만족하는 키를 말합니다.

 

 

💡 면접에서 나올 수 있는 질문들

  1. 키의 종류와 특징에 대해서 설명해 보세요.
  2. 유일성과 최소성에 대해서 설명해 보세요.

 

+ Recent posts