[DB] 조인의 원리와 종류

서론

※ 아래 내용을 다룹니다.

• 조인 원리
• 종류

 

https://github.com/SangBeom-Hahn/boost-interview

GitHub - SangBeom-Hahn/boost-interview: Naver BoostCamp 6기, AI 엔지니어 기반을 다지는 공간 🎇

 

본론

- 조인의 원리

이너 조인, 아우터 조인 등 조인의 기반이 되는 원리를 알아보자.

 

1. 중첩 루프 조인

1) 선행 테이블의 모든 행을 순차적으로 조회
2) 각 행마다 두 번째 테이블의 모든 행을 읽어서 조인 조건을 확인

중첩 반복문처럼 동작하며, 외부 테이블의 행을 추출하여, 후행 테이블을 읽으면서 조인을 수행한다.

 

1) 결과 행의 수가 적은 테이블을 선행 테이블로 선택하는 것이 전체 일량을 줄일 수 있다.
2) Join 열에 해당하는 컬럼들은 인덱스를 가지고 있어야 하며, 없으면 성능이 매우 떨어질 수 있다.
3) 선행 테이블을 기준으로 한 레코드씩 순차적으로 진행하며 적절한 인덱스가 없으면 후행 테이블을 탐색할 때 반복적으로 풀 스캔을 하므로 매우 비효율적이다.
4) 대용량 테이블에서는 사용하지 않는게 좋다.
5) 선행은 순차적으로 접근하지만, 후행은 인덱스 사용으로 인한 랜덤 접근 방식이다.

위와 같은 상황에서 사용할 수 있다.

 

-> 동작 순서

1) 선행 테이블에서 조건을 만족하는 첫 번째 행을 찾음
2) 선택한 행의 조인 기준이 되는 컬럼으로 후행 테이블의 인덱스를 검색
3) 검색 결과 두 테이블의 조인 조건을 만족하면 조인
4) 위 과정을 선행 테이블의 모든 행에 대해 반복

따라서, 선행 테이블에는 순차적이지만, 후행 테이블에는 인덱스를 사용한 랜덤 접근이다.

 

2. 정렬 병합 조인

1) 각각의 테이블을 조인할 필드 기준으로 정렬하고 조인
2) 조인할 때 적절한 인덱스가 없고 대용량 테이블들을 조인할 때 사용
3) 조인 조건으로 범위 비교 연산자(<, >)가 있을 때 사용

 

-> 동작 순서

select /**USER_MERGE(A B) */ A.Color, B.SIZE,...
from TABLE_A A,TABLE_B B
where a.joinkey_a = b.joinkey_b -- join key에 대한 인덱스가 테이블 둘 모두 다 없음
and a.color = 'RED' --인덱스 있음
and b.size = 'MED'; --인덱스 없음

위와 같은 쿼리 예시에서 동작 순서를 알아보자.

 

1) TABLE_A와 TABLE_B를 동시에 ACCESS
2) TABLE_A의 color에 인덱스가 걸려있으므로 TABLE_A는 인덱스 스캔, TABLE_B는 테이블 풀스캔
3) TABLE_A에서 조회한 데이터는 joinkey_a를 기준으로 , TABLE_B에서 읽은 데이터는 JOINKEY_B를 통해 별도의 공간에서 테이블 각각 SORT
4) 두 개 데이터의 정렬이 모두 완료되면 정렬한 결과를 차례로 스캔하여 조인 키로 merge하여 리턴

 

-> 정리

각 테이블에 동시에 독립적으로 where 데이터를 먼저 읽고 읽은 데이터에 조인 키로 정렬을 하고 정렬이 모두 끝난 후 조인한다.

 

3. 해시 조인

https://eehoeskrap.tistory.com/84

 

조인 컬럼을 기준으로 해시 함수를 수행하여, 서로 동일한 해시값(해시 함수는 동일 입력에 대해 동일 해시값)을 갖는 것들 사이에서 실제 값이 같은지 비교하면서 조인한다. NL Join의 랜덤 엑세스 문제와 정렬 머지 조인의 정렬 작업 부담을 해결한다.

 

1) 조인 컬럼의 인덱스가 존재하지 않을 경우 사용
2) = 비교인 동등 조인에서만 사용 가능
3) 해쉬 테이블을 메모리에 생성해야 해서, 결과 행의 수가 적은 테이블을 선행 테이블로 사용

 

-> 동작 원리

1. 빌드 단계

1) 바이트 수가 더 적은 테이블로 해시 테이블을 만듦 
2) 조인 기준의 컬럼값을 전부 해시 함수에 넣어 버킷 위치를 찾고 버킷 주소에 접근하여 해시 체인에 엔트리 연결
3) 번 작업을 선행 테이블의 조건을 만족하는 모든 행에 대해 반복 수행

 

2. 프로브 단계

1) 후행 테이블에서 where 조건을 만족하는 행을 찾음
2) 후행 테이블의 조인 기준의 컬럼을 해시 함수에 넣고 버킷 주소 검색
3) 해시 체인을 스캔하면서 데이터를 찾고 조인 수행
4) 2 ~ 4를 반복