지난 글에서는 LSM 트리와 B-tree로 데이터가 디스크에 어떻게 쓰이는지를 봤습니다. 이번 글에서는 그렇게 저장된 두 테이블을 하나로 붙이는 방법, 조인 알고리즘을 알아보려고 합니다. BigQuery 시리즈에서 broadcast와 shuffle은 분산 관점으로 한 줄씩 지나갔는데, 이번에는 한 노드 안에서 행과 행이 실제로 어떻게 짝지어지는지까지 내려갑니다.
1. 조인은 짝을 찾는 일이다
1-1. 예시 데이터
두 테이블을 가정해 보겠습니다.
users (작은 쪽) orders (큰 쪽)
id | name order_id | user_id | amount
1 | Alice 101 | 1 | 30
2 | Bob 102 | 3 | 15
3 | Carol 103 | 1 | 50
104 | 2 | 20SELECT u.name, o.amount
FROM orders o
JOIN users u ON o.user_id = u.id;orders의 각 행마다 user_id가 같은 users 행을 찾아 붙이는 것이 전부입니다. 방법은 크게 세 가지입니다. 하나씩 다 비교해 보는 Nested Loop, 한쪽을 해시 테이블로 만들어 찾는 Hash Join, 양쪽을 정렬해 두고 나란히 훑는 Sort-Merge Join입니다.
1-2. 옵티마이저의 선택
어느 방법을 쓸지는 사용자가 아니라 옵티마이저가 정합니다. PostgreSQL 문서에 따르면 옵티마이저는 조인 쌍마다 가능한 계획을 모두 만들어 보고, 추정 비용이 가장 싼 것을 고릅니다. 따라서 세 알고리즘에 우열이 있다기보다, 테이블 크기와 인덱스와 메모리에 따라 비용이 뒤집히는 지점이 있습니다.
2. Nested Loop
2-1. 이중 for문
가장 단순한 방법입니다. 바깥 테이블의 행을 하나 꺼내고, 안쪽 테이블을 처음부터 끝까지 훑으며 조건이 맞는 행을 찾습니다.
for o in orders: # 바깥 (outer)
for u in users: # 안쪽 (inner)
if o.user_id == u.id:
emit(o, u)바깥이 N행, 안쪽이 M행이면 비교 횟수는 N × M입니다. 위 예시라면 4 × 3 = 12번이지만, 1억 행 × 100만 행이면 10¹⁴번이 됩니다. 안쪽 테이블을 바깥 행 수만큼 반복해서 읽는 것이 이 방식의 비용입니다.
2-2. 인덱스가 있으면 이야기가 달라진다
안쪽 테이블의 조인 키에 B-tree 인덱스가 있으면 사정이 바뀝니다. 안쪽을 매번 전부 훑는 대신, 바깥 행의 user_id로 인덱스를 타고 내려가 해당 행만 바로 꺼냅니다. 지난 글에서 본 B+ tree의 점 조회가 바깥 행 수만큼 반복되는 구조입니다.
PostgreSQL 문서도 이 경우를 따로 짚습니다. 안쪽 관계를 인덱스 스캔으로 읽을 수 있으면 nested loop가 좋은 전략이 될 수 있다는 것입니다. 바깥이 수십 행이고 안쪽이 큰 테이블이면, 해시 테이블을 만드는 것보다 인덱스를 수십 번 타는 쪽이 훨씬 쌉니다.
PostgreSQL 14부터는 여기에 Memoize 노드가 붙었습니다. 바깥에서 같은 키가 반복해서 나오면, 안쪽 조회 결과를 캐시해 두고 재사용합니다. enable_memoize로 끌 수 있습니다.
2-3. MySQL의 Block Nested Loop
8.0.20 이전 MySQL은 여기에 버퍼를 하나 끼워 넣었습니다. 바깥 행을 하나씩이 아니라 join buffer에 여러 개 모아 두고, 안쪽 테이블을 한 번 훑을 때 버퍼 안의 행 전부와 비교합니다. 안쪽 테이블을 읽는 횟수가 바깥 행 수에서 버퍼 채운 횟수로 줄어듭니다. 이것이 Block Nested Loop(BNL)입니다.
다만 BNL은 이제 MySQL에 없습니다. 8.0.18에서 hash join이 들어왔고, 8.0.20에서 BNL 지원이 제거되면서 예전에 BNL을 쓰던 자리는 전부 hash join으로 바뀌었습니다. 버퍼 크기를 정하던 join_buffer_size(기본 256KB)는 8.0.18부터 hash join이 쓰는 메모리 양도 함께 정합니다.
3. Hash Join은 메모리가 버틸 때까지 이긴다
3-1. Build와 Probe
hash join은 두 단계로 나뉩니다.
[Build] 작은 쪽(users)을 읽어 해시 테이블을 만듭니다
hash(1) → Alice
hash(2) → Bob
hash(3) → Carol
[Probe] 큰 쪽(orders)을 한 번 훑으며 해시 테이블을 조회합니다
order 101 (user_id 1) → hash(1) → Alice ✓
order 102 (user_id 3) → hash(3) → Carol ✓
...PostgreSQL 문서의 설명도 같습니다. 오른쪽 관계를 먼저 읽어 해시 테이블에 올리고, 왼쪽 관계를 읽으며 해시 테이블에서 짝을 찾습니다.
여기서 좌우는 SQL에 적은 순서가 아니라 플래너가 정한 inner/outer입니다. 보통 작은 쪽이 inner(오른쪽)가 되어 build를 맡습니다. 소스 코드에서도 단계 이름이 PHJ_BUILD_HASH_INNER, 그리고 "building done, probing can begin"으로 나뉩니다.
해시 테이블이 메모리에 들어가는 한, 양쪽을 각각 한 번씩만 읽으므로 비용은 대략 N + M에 비례합니다. nested loop의 N × M과 비교하면 큰 테이블끼리 붙일 때 차이가 큽니다. 대신 조건이 붙습니다. 해시는 같은지만 판단할 수 있어서, PostgreSQL의 hash join은 = 조건(equi-join)에서만 쓸 수 있습니다. MySQL은 8.0.20부터 등호가 아닌 조건에도 hash join을 쓰지만, 해시로 짝을 바로 찾는 이점은 등호 조건에서만 생깁니다.
3-2. 해시 테이블이 메모리를 넘으면
build 쪽이 작다는 전제가 깨지면 문제가 생깁니다. 해시 테이블이 메모리에 다 안 들어가는 경우입니다.
PostgreSQL은 이때 입력을 batch로 나눕니다. 키의 해시값으로 양쪽 입력을 여러 batch로 쪼개 디스크 임시 파일에 써 두고, batch 하나씩 메모리에 올려 build와 probe를 반복합니다. 같은 키는 같은 batch로 가므로 batch끼리만 맞춰 보면 됩니다. 소스 주석에 따르면 batch 수는 항상 2의 거듭제곱이고, 늘릴 때는 두 배씩 늘립니다. PostgreSQL 소스는 이 구조를 hybrid hash join 알고리즘에 기반한다고 적고, 주석에서는 Zeller와 Gray의 1990년 논문을 인용합니다.
해시 테이블에 쓸 수 있는 메모리는 work_mem(기본 4MB)에 hash_mem_multiplier를 곱한 값입니다. 이 배수는 13에서 1.0으로 도입됐고, 15부터 기본 2.0입니다. 같은 쿼리라도 PostgreSQL 버전에 따라 batch가 1개로 끝나기도, 디스크로 나가기도 합니다.
MySQL도 같은 상황에서 디스크를 씁니다. MySQL 블로그의 설명으로는, build 입력 중 메모리를 넘는 나머지를 디스크의 chunk 파일로 내보내고, 입력당 chunk 파일은 최대 128개로 제한합니다. chunk를 나누는 해시 함수와 메모리 해시 테이블용 해시 함수는 서로 다른 것을 씁니다. 같은 함수를 쓰면 한 chunk 안의 행이 모두 같은 해시값을 가져서, 그 chunk를 해시 테이블에 올렸을 때 행이 한 버킷에 몰려 해시 테이블이 제 역할을 못 하기 때문입니다. 공식 문서에는 생성하는 파일 수가 open_files_limit를 넘으면 조인이 실패할 수 있다고 적혀 있습니다.
3-3. 병렬 hash join
PostgreSQL 11부터는 여러 워커가 공유 해시 테이블 하나를 같이 만들어 쓰는 parallel hash join이 들어왔습니다. 소스 주석에 따르면 그 전에는 워커마다 안쪽 계획을 복사해 해시 테이블도 각자 만들었기 때문에, build 쪽이 큰 경우 같은 작업을 워커 수만큼 반복했습니다.
4. Sort-Merge Join
4-1. 정렬된 두 줄을 나란히 걷는다
양쪽을 조인 키로 정렬해 두면, 포인터 두 개를 나란히 움직이는 것만으로 짝을 찾을 수 있습니다.
orders (user_id 정렬) users (id 정렬)
1 (101) ←─────────────→ 1 Alice ✓
1 (103) ←─────────────→ 1 Alice ✓
2 (104) ←─────────────→ 2 Bob ✓
3 (102) ←─────────────→ 3 Carol ✓한쪽 포인터의 값이 작으면 그쪽을 한 칸 전진시키고, 같으면 짝으로 내보냅니다. 정렬만 되어 있으면 양쪽을 한 번씩 훑는 것으로 끝납니다.
4-2. 정렬 비용과 인덱스
문제는 정렬입니다. PostgreSQL 문서에 따르면 merge join은 조인 전에 양쪽을 조인 속성으로 정렬하는데, 이 정렬은 명시적인 정렬 단계로 할 수도 있고 조인 키 인덱스를 순서대로 읽어서 대신할 수도 있습니다.
지난 글에서 B+ tree가 리프 노드를 따라 범위 스캔에 강하다고 했는데, 이것이 그대로 정렬된 입력이 됩니다. 양쪽에 조인 키 인덱스가 있으면 정렬 비용이 사라지고, merge join은 유력한 후보가 됩니다.
정렬이 work_mem을 넘으면 디스크로 나갑니다. EXPLAIN ANALYZE에는 이렇게 찍힙니다.
Sort Method: quicksort Memory: 74kB -- 메모리 안에서 끝남
Sort Method: external merge Disk: 51200kB -- 디스크로 넘침디스크 정렬은 external merge와 external sort 두 가지 이름으로 나올 수 있습니다. 어느 쪽이든 Disk:가 보이면 work_mem이 모자랐다는 뜻입니다. PostgreSQL 15부터는 메모리를 넘었을 때 더 많은 출력 스트림을 쓰는 batch 정렬로 바뀌었고, 병합 방식도 이전의 polyphase merge에서 balanced k-way merge로 바뀌었습니다.
4-3. 정렬 결과가 공짜로 따라온다
merge join의 출력은 조인 키 순으로 정렬되어 있습니다. 쿼리에 ORDER BY user_id가 붙어 있다면 따로 정렬할 필요가 없습니다. hash join의 출력은 순서가 없으므로 같은 쿼리라도 정렬 단계가 하나 더 붙습니다.
5. 분산 엔진에서는 한 층이 더 있다
지금까지는 한 노드 안의 이야기였습니다. Spark나 BigQuery 같은 분산 엔진은 그 위에 데이터를 어떻게 노드에 나눠 줄지라는 층이 하나 더 있습니다.
방법은 둘입니다. Broadcast는 작은 쪽을 모든 노드에 통째로 복사합니다. 큰 쪽은 움직이지 않고, 등호 조건이면 각 노드가 받은 작은 테이블로 hash join을 합니다. Spark는 등호 키가 없으면 broadcast nested loop join을 씁니다. 반면 Shuffle은 양쪽을 조인 키 해시로 재분배해서 같은 키가 같은 노드에 모이게 하고, 그다음 노드마다 hash join이나 sort-merge join을 합니다.
Spark는 한쪽이 spark.sql.autoBroadcastJoinThreshold(기본 10MB)보다 작으면 broadcast를 씁니다. -1로 두면 broadcast를 끕니다. 둘 다 크면 기본은 sort-merge join인데, 내부 설정 spark.sql.join.preferSortMergeJoin(기본 true)의 설명에 sort merge join이 메모리를 덜 쓴다는 이유가 적혀 있습니다. AQE(기본 켜짐)는 실행 중 통계를 보고 한쪽이 충분히 작아졌다고 판단하면 sort-merge join을 broadcast hash join으로 바꿉니다.
BigQuery 실행 계획에서는 조인 단계에 이 구분이 그대로 보입니다. JOIN EACH WITH ALL이면 broadcast입니다. JOIN EACH WITH EACH는 문서에서 hash join이라고 부르는데, 양쪽을 해시로 셔플해 같은 키를 같은 슬롯에 모은 뒤 슬롯 안에서 조인하는 방식입니다. BigQuery 시리즈 4편에서 큰 테이블끼리 셔플 조인되면 stage 사이 데이터 이동이 폭발한다고 했는데, 실행 계획에서 EACH WITH EACH를 찾으면 그 지점입니다.
6. 언제 무엇이 이기는가
표의 '이기는 경우'는 대략적인 경향입니다. MySQL 문서는 hash join이 block nested loop보다 보통 빠르다고 쓰고, PostgreSQL 14가 추가한 Memoize처럼 nested loop의 반복 조회 비용을 줄이는 장치도 있습니다.
6-1. enable_nestloop은 꺼도 남는다
PostgreSQL에서는 enable_hashjoin, enable_mergejoin을 꺼서 다른 계획을 강제로 비교해 볼 수 있습니다. 다만 enable_nestloop은 꺼도 nested loop가 완전히 사라지지 않습니다. 문서 표현대로 플래너가 쓰지 않도록 억제할 뿐이고, 다른 방법이 없으면 여전히 nested loop를 씁니다.
마무리
조인 알고리즘은 결국 짝을 찾기 전에 무엇을 준비해 두느냐의 차이입니다. 아무것도 준비하지 않으면 nested loop, 한쪽을 해시 테이블로 만들어 두면 hash join, 양쪽을 정렬해 두면 sort-merge입니다. 옵티마이저는 그 준비 비용을 추정해서 고르기 때문에, 실행 계획에서 예상과 다른 조인이 보인다면 대개 행 수나 크기 추정이 틀린 것입니다.
다음 글에서는 지난 글에서 잠깐 등장한 Bloom filter를 알아보겠습니다. LSM 트리가 왜 이것 없이는 읽기를 감당할 수 없는지, 그리고 min/max 통계가 못 잡는 점 조회를 어떻게 걸러 내는지까지 뜯어보겠습니다.