Theory
Database
조인 종류

NL 조인(Nested Loops Join)

image

  1. 선행 테이블에서 조건을 만족하는 첫 번째 행을 찾는다. → 조건에 만족하지 않은 데이터는 필터링 된다.
  2. 조인 키를 가지고 후행 테이블에 조인 키가 존재하는지 찾는다. → 조인 시도
  3. 후행 테이블의 인덱스에 선행 테이블의 조인키가 존재하는지 확인한다. → 조인 값이 후행 테이블에 없으면 선행 테이블 데이터는 필터링
  4. 인덱스에서 추출한 레코드 식별자를 이용하여 후행 테이블을 액세스한다. → 후행 테이블에 주어진 조건까지 모두 만족하면 해당 행을 추출버퍼에 넣
  5. 위의 과정을 반복
  • NL 조인은 프로그래밍 언어에서 사용하는 중첩된 반복문과 유사한 방식으로 조인을 수행한다.
    • 조인을 한 레코드씩 순차적으로 진행한다.
  • NL 조인의 큰 특징은 랜덤 액세스(Random Access) 방식으로 데이터를 읽는 것이다. 랜덤 액세스의 예로 인덱스 스캔(Index Scan)이 있다. 인덱스 스캔은 NL Join 방식으로 조인을 수행한다. 대량의 데이터를 랜덤 액세스로 접근하면 많은 I/O 가 발생하여 성능상 종지 않다.
  • NL 조인은 조인이 성공하면 바로 결과를 사용자에게 보여준다.
  • NL 조인 이외의 Sort Merge 조인과 Hash 조인은 조인 컬럼의 인덱스가 없어도 사용 가능하며 메모리에 적재할 수 있는 크기보다 더 커지면 임시 영역(디스크)을 사용한다.

특징

  1. 선행 테이블이 작아야한다.
  2. 이중 반복문이다.
  3. 인덱스를 쓸 수 있다.

Sort Merge 조인

image

  1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾는다.
  2. 해당 행들에 대해서 선행 테이블의 조인 키를 기준으로 데이터를 정렬
  3. 후행 테이블에서 주어진 조건을 만족하는 행을 찾는다.
  4. 해당 행들에 대해서 후행 테이블의 조인 키를 기준으로 데이터를 정렬
  5. 조인을 수행
  6. 조인에 성공하면 추출 버퍼에 넣는다.
  • Sort Merge 조인은 nL 조인에서의 랜덤 액세스로 부담이 되던 넓은 범위의 데이터를 처리할 때 이용되던 조인기법이다. 주로 Full Table 스캔 방식으로 데이터를 읽는다. Sort Merge 조인은 조인 컬럼의 인덱스가 존재하지 않은 경우에도 사용할 수 있다.
  • Sort Merge 조인은 조인 컬럼을 기준으로 데이터를 정렬한 후 조인을 수행할 수 있지만 조인 작업을 위해 항상 정렬 작업이 발생하지는 않는다. 조인할 테이블 중에서 이미 앞단계의 작업을 수행하는 도중에 정렬작업이 미리 수행되었다면 조인을 위한 정렬 작업은 발생하지 않을 수 있다.
  • 정렬할 데이터가 많은 경우에 메모리에서 모든 정렬 작업을 수행하기 어려운 경우 임시 영역(디스크)를 사용하기 때문에 성능이 떨어질 수 있다. 대량의 조인 작업을 필요로 하는 Sort Merge 조인보다는 CPU 작업 위주로 처리하는 Hash 조인이 성능상 유리하다..
  • Sort Merge 조인은 Hash 조인과는 달리 동등 조인(Equi Join) 뿐만 아니라 Non-Equi 조인에 대해서도 조인 작업이 가능하다.

특징

  1. 조인 컬럼에 인덱스가 없을 때 사용
  2. 대량 데이터 조인이어서 인덱스가 효과적이지 않을 때
  3. 옵티마이저는 nl 조인 대신 소트머지 조인이나 해시조인을 선택한다.
  4. 등치 조건이 아닐 때 사용할 수 없다.
  5. 조인 조건식이 없는 조인(카테시안 곱)

해시 조인

image

  • 해시 조인
    1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾는다.
    2. 해당 행들에 대해서 선행 테이블의 조인 키를 기준으로 Hash 함수를 적용하여 해시 테이블을 생성한다. (N번 반복)
    3. 후행 테이블에서 주어진 조건을 만족하는 행을 찾는다. (M번 반복)
    4. 해당 해들에 대해서 후행 테이블에 Hash 함수를 적용하여 선행 테이블의 해시 테이블에서 맞는 버킷을 찾는다.
    5. 조인을 수행 & 조인에 성공하면 추출 버퍼에 넣는다.
    6. 반복
    • 해시조인을 수행할 테이블의 조인 컬럼을 기준으로 해시함수를 적용하여 서로 동일한 해시 값을 갖는 것들 사이에서 실제 값이 같은지를 비교하면서 조인을 수행한다. 해시함수를 적용한 실제 값은 어떤 값으로 해싱될지 예측할 수 없다. 하지만 해시 함수가 적용될 때 동일한 값은 항상 같은 값으로 해싱됨이 보장된다. 하지만 해시 함수를 적용할 때 큰 값이 항상 큰 값이 되거나 작은 값이 항상 작은값으로 해싱된다는 보장이 없다. 그렇기 때문에 해시 조인은 동등 조인(Equi join)에서만 사용할 수 있다.
    • CPU 작업 위주로 데이터 처리하는 해시 조인은 NL 조인의 랜덤 엑세스 문제점과 Sort Merge 조인의 몬제점인 정렬 작업의 부담을 해결하기 위한 대안으로 등장했다.
    • 해시 조인은 조인 작업전 해시 테이블을 메모리에 생성한다. 다만 크기가 메모리에 적재할 수 있는 크기보다 더 커지면 임시 영역(디스크)에 해시 테이블을 저장한다. 그렇기 때문에 해시 조인을 할 때는 결과 행의 수가 적은 테이블을 선행 테이블로 사용하는 것이 좋다. 선행 테이블의 결과를 완전히 메모리에 저장할 수 있다면 임시 영역에 저장하는 작업이 발생하지 않기도하고 cPU 연산을 조금 덜 수행할 수 있다.
    • 해시 조인에서는 선행 테이블을 이용해서 해시 테이블을 생성한다고 하여 해시 선행 테이블을 Build Input이라고도 하며 후행 테이블은 만들어진 해시 테이블에 대해 해시값의 존재여부를 검사한다고 해서 Prove Input이라고도 한다.

특징

  1. 수행빈도가 낮고 쿼리시간이 오래걸리는 대량 데이터 조인할 때 좋다.

소량 데이터 조인 → NL 조인

대량 데이터 조인 → 해시 조인

대량 데이터 조인인데 해시 조인으로 처리할 수 없을때(조인 조건식이 등치 조건이 아닐때 → 소트머지 조인)

시간 복잡도 예시

1. Nested Loop Join (NLJ)

  • 시간복잡도: O(M × N)
  • 예시 설명:
    • 테이블 A의 행 수 = 4
    • 테이블 B의 행 수 = 5
    • 모든 행을 비교: 
      A: {1, 2, 3, 4}
B: {2, 3, 4, 5, 6}
      비교 과정:
      • 1과 {2, 3, 4, 5, 6} 비교 (5번 비교)
      • 2와 {2, 3, 4, 5, 6} 비교 (5번 비교)
      • 3과 {2, 3, 4, 5, 6} 비교 (5번 비교)
      • 4와 {2, 3, 4, 5, 6} 비교 (5번 비교)
  • 총 비교 횟수: 4 × 5 = 20

2. Sort Merge Join (SMJ)

  • 시간복잡도: O(M log M + N log N + M + N)

  • 예시 설명:

    • 테이블 A = {4, 1, 3, 2} (4개 요소)
    • 테이블 B = {6, 5, 4, 3, 2} (5개 요소)

    정렬 과정:

    • A_sorted = {1, 2, 3, 4}: O(4 log 4) = 4 × 2 = 8
    • B_sorted = {2, 3, 4, 5, 6}: O(5 log 5) ≈ 5 × 2 = 10 병합 과정:
    • 순차적으로 병합: 4 + 5 = 9

  • 총 시간: O(4 log 4 + 5 log 5 + 4 + 5) = 27

3. Hash Join

  • 시간복잡도: O(M + N)
  • 예시 설명:
    • 테이블 A = {1, 2, 3, 4} (작은 테이블)
    • 테이블 B = {2, 3, 4, 5, 6} 해시 테이블 생성:
    • A 해시 테이블 빌드: O(4) 탐색 과정:
    • B의 각 요소를 해시 테이블에서 찾기: O(5)
  • 총 시간: O(4 + 5) = 9

MySQL과 PostgreSQL의 조인 알고리즘 및 튜닝 방법

MySQL의 조인 방법 및 기본 설정

  • 기본 조인 방법:

    • MySQL은 기본적으로 Nested Loop Join을 사용한다. 이는 프로그래밍 언어에서 사용하는 중첩된 반복문과 유사한 방식으로 조인을 수행한다.
    • 인덱스를 사용할 수 있는 경우 Index Nested Loop Join을 통해 성능을 최적화할 수 있다.
    • 최신 버전에서는 Hash Join도 지원하지만, 기본적으로 사용되지 않고 특정 조건에서만 사용된다.

  • 조인 알고리즘 튜닝 방법:

    1. 인덱스 최적화:

      • 조인 컬럼에 인덱스를 추가하여 조인 속도를 높일 수 있다. 특히 Nested Loop Join에서 인덱스를 사용하면 대량의 데이터를 처리할 때 성능이 향상될 수 있다.

    2. 쿼리 리팩토링:

      • 조인 순서를 바꾸거나, 서브쿼리를 조인으로 변경하여 효율적인 조인 순서를 찾을 수 있다. 이를 통해 쿼리 성능을 최적화할 수 있다.

    3. 힌트 사용:

      • STRAIGHT_JOIN을 사용하여 조인 순서를 강제하거나 USE INDEX를 통해 특정 인덱스를 사용하도록 힌트를 줄 수 있다.

    4. 조인 알고리즘 변경:

      • 필요에 따라 조인 알고리즘을 변경하는 힌트 (JOIN_ALGORITHM)를 사용하여 Hash Join 등을 시도할 수 있다. 하지만 기본적으로 MySQL에서는 Nested Loop Join이 많이 사용된다.

PostgreSQL의 조인 방법 및 기본 설정

  • 기본 조인 방법:
    • PostgreSQL은 Nested Loop Join, Sort Merge Join, Hash Join 중 상황에 따라 가장 적합한 조인 방법을 자동으로 선택한다.
    • 쿼리 플래너가 테이블의 통계 정보를 바탕으로 조인 방법을 선택하며, 인덱스 여부, 데이터​

Reference

복제Multiplexing & Demultiplexing