👣 개요
하나 이상의 테이블을 특정 기준을 이용해서 합치는 연산이다.
👣 Join 원리
👣 중첩 루프 조인 - Nested Loops Join, O(n^2)
2중 for문 원리로 두 테이블을 합치는 방법.
너무 큰 Cost를 지불해야 하기 때문에 대용량 테이블에서 사용하지 않는다.
👣 정렬 병합 조인 - Sort-Merge Join, O(n log n)
정렬 후, 각 테이블에 포인터를 설정하고 포인터의 칼럼값이 같으면 조인하고 다르면 포인터를 움직이는 방식이다.
정렬 병합 조인은 다음과 같은 절차로 동작한다
- 두 데이터 집합 정렬
먼저 조인을 수행할 두 개의 데이터 집합을 조인 키를 기준으로 오름차순으로 정렬.
이때, 정렬은 병합 정렬(Merge Sort)을 사용. - 정렬된 데이터 병합
정렬된 두 개의 데이터 집합을 조인 키를 기준으로 병합.
병합은 각 데이터 집합에서 현재 위치의 조인 키 값을 비교하여 동일한 값을 가지면 조인을 수행하고,
다음 조인 키를 비교.
만약 조인 키 값이 같지 않다면 더 작은 값을 가진 데이터의 위치를 증가시키며 비교.
👣 해시 조인 - Hash Join, O(n)
조인 키를 기준으로 '테이블 A'의 데이터를 해시 테이블로 변환하고
'테이블 B'를 선형 순회하면서 해시함수로 '테이블 A'의 데이터를 조회.
'테이블 A'가 온전히 메모리 위에 올라갈 수 있을 정도면 Nested Loops Join보다 훨씬 효율적이다.
또한 동등 조인에서만 사용가능하다는 단점이 있다.
해시 조인은 다음과 같은 절차로 동작한다
- '내부 데이터 집합' 해시 테이블 생성 [빌드 단계]
먼저 조인 키를 기준으로 '내부 데이터 집합'을 해시 테이블로 변환.
해시 테이블은 조인 키를 해시 함수를 사용하여 해시 값으로 변환하고 테이블에 저장. - '외부 데이터' 집합과 조인 [프로브 단계]
다음으로 '외부 데이터 집합'을 스캔하면서 조인 키를 해시 함수를 사용하여 해시 값으로 변환한 뒤,
'내부 데이터 집합'에서 생성한 해시 테이블에 해당 해시 값과 일치하는 데이터를 검색.