두 테이블을 만나는 세 가지 방법: 조인 알고리즘
조인은 서로 관련된 튜플을 연결하여 새로운 결과를 만드는 연산이다. 논리적으로 학생 ID가 같은 학생 행과 수강 행을 연결한다고 표현할 수 있지만, 실제 DBMS에는 그 일치를 찾는 여러 알고리즘이 있다. 중첩 루프, 해시 조인과 정렬 병합 조인은 입력 크기, 조건, 메모리와 정렬 상태에 따라 서로 다른 장점을 보인다.
해시 조인은 빌드한 키 구조를 이용해 다른 입력의 매칭 후보를 찾는다.
하나씩 비교하거나 이미 있는 경로를 쓴다
단순한 중첩 루프는 바깥 입력의 행 하나마다 안쪽 입력의 행들을 살피며 조건을 확인한다. 두 입력이 m개와 n개이고 매번 전부 비교하면 비교 수가 m×n에 이를 수 있다. 구조는 단순하고 다양한 조건에 적용할 수 있지만 큰 입력 두 개를 무조건 이렇게 처리하면 비싸다.
안쪽의 조인 키에 인덱스가 있다면 바깥 행마다 그 인덱스로 후보를 찾는 방법을 사용할 수 있다. 바깥 입력이 작은 경우에는 효과적일 수 있다. 그러나 바깥 행이 많으면 반복 탐색과 흩어진 행 접근 비용이 커진다. 중첩 루프라는 이름만으로 항상 느리다고 판단하거나, 인덱스가 있으면 항상 빠르다고 판단하는 것은 모두 성급하다.
해시로 같은 키를 가까이 모은다
해시 조인은 보통 한 입력으로 해시 테이블을 만드는 빌드 단계와, 다른 입력을 읽어 같은 키의 후보를 찾는 프로브 단계로 나눈다. 작은 학생 목록으로 테이블을 만들고 큰 수강 목록을 한 번 훑는 예를 생각할 수 있다. 적절한 메모리와 데이터 조건에서는 두 입력을 대체로 선형적으로 처리하는 접근이 가능하다.
해시 값이 같다고 키 값도 반드시 같은 것은 아니므로 충돌을 처리하고 실제 조건을 확인해야 한다. 같은 키의 행이 여러 개면 가능한 매칭 결과를 모두 고려해야 한다. 입력에 같은 키가 많이 몰리면 해시 버킷과 결과가 커질 수 있고, 빌드 자료가 메모리에 들어가지 않으면 파티셔닝과 추가 디스크 I/O가 필요할 수 있다.
정렬 병합 조인은 두 입력을 조인 키 순서로 정렬한 뒤 함께 진행하면서 일치하는 구간을 찾는다. 이미 정렬된 입력이나 그 순서를 제공하는 인덱스가 있다면 유리할 수 있다. 새 정렬이 필요하면 그 비용까지 포함해야 한다. 중복 키 그룹을 연결할 때는 단순히 양쪽에서 한 행씩만 내보내는 것으로 끝나지 않는다.
입력보다 결과가 더 클 수도 있다
한쪽에 키 7의 행이 세 개, 다른 쪽에 같은 키의 행이 네 개 있으면 해당 키의 등가 조인 결과는 열두 조합이 될 수 있다. 어떤 알고리즘도 실제로 요구되는 출력의 크기를 없애지 못한다. 조인이 폭발하는 원인은 알고리즘뿐 아니라 데이터의 다대다 관계나 잘못된 조건일 수 있다.
해시 조인은 대표적으로 등가 조건에 적합하고, 모든 비등가 조건을 같은 방식으로 해결하지는 않는다. 정렬 병합과 중첩 루프의 적용 범위도 구현과 조건에 따라 달라진다. 내부 조인과 외부 조인은 매칭되지 않은 행을 남기는 규칙이 다르므로 결과 생성에도 추가 처리가 필요하다.
알고리즘을 비교할 때는 행 개수뿐 아니라 행 폭, 필요한 메모리, 기존 정렬과 인덱스, 키 분포를 함께 적는 것이 좋다. 아주 작은 입력에는 단순한 방법이 더 저렴할 수 있고, 큰 입력에는 한 번씩 읽는 전략이 유리할 수 있다. 같은 JOIN 구문 뒤에 어떤 물리적인 작업이 선택되었는지 이해하면 실행 계획의 속도 차이를 설명할 수 있다.