4383 words
22 minutes
[SQL]분산 조인: Broadcast vs Shuffle
단일 노드(PostgreSQL)의 조인 알고리즘이 분산 환경(Spark 기준) 에서 어떻게 확장되는지 정리
실행 계획은 Spark 3.5.1
local[4]에서 직접 실행한 결과.orders500만 행(spark.range로 생성),customers10만 행(AQE 예제는 500만 행),small_c1천 행. 가독성을 위해Project/Range등 일부 노드는...로 생략
0. 분산 조인의 핵심 문제
- 단일 노드: 두 테이블이 같은 머신에 있으므로 어떤 알고리즘으로 매칭할지만 결정
- 분산 환경: 같은 키를 가진 행이 서로 다른 노드에 흩어져 있음 → 매칭 전에 같은 키를 같은 노드로 모으는 작업이 먼저 필요
- 모으는 방법은 두 가지
- Broadcast: 작은 테이블 전체를 모든 노드에 복사
- Shuffle: 양쪽 테이블을 조인 키 해시로 재분배
- 이후 각 노드 안에서는 앞 글의 Hash Join / Sort Merge Join / Nested Loop가 그대로 수행됨
분산 조인 전략 = [데이터 이동 방식: Broadcast | Shuffle] + [노드 내 알고리즘: Hash | Sort Merge | Nested Loop]| Spark 전략 | 데이터 이동 | 노드 내 알고리즘 | 조건 |
|---|---|---|---|
| Broadcast Hash Join (BHJ) | 작은 쪽 broadcast | Hash | 등가 조인, 한쪽이 작음 |
| Shuffle Hash Join (SHJ) | 양쪽 shuffle | Hash | 등가 조인, 파티션별 해시가 메모리에 들어감 |
| Sort Merge Join (SMJ) | 양쪽 shuffle | 정렬 후 Merge | 등가 조인, 대량 vs 대량의 기본값 |
| Broadcast Nested Loop Join (BNLJ) | 한쪽 broadcast | Nested Loop | 비등가 조인, 한쪽이 작음 |
| Cartesian Product | 양쪽 복제 | Nested Loop | 비등가 조인, 양쪽 다 큼 (최악) |
Concept
- 분산 조인(Distributed Join) : 여러 노드에 파티션된 테이블을 조인하는 연산. 같은 조인 키의 행을 같은 노드로 모으는 데이터 이동 단계가 노드 내 매칭 알고리즘보다 먼저 필요
- Co-location : 조인할 두 테이블의 같은 키 행이 같은 노드·파티션에 놓여 있는 상태. Co-location이 이미 성립하면 데이터 이동 없이 바로 조인 가능
- 데이터 이동 비용(Data Movement Cost) : 네트워크 전송·직렬화·디스크 쓰기 비용. 분산 조인 성능은 노드 내 알고리즘보다 이동량에 좌우됨
1. Broadcast Join
1.1 개념
┌──────── small (dim) 전체 복사 ────────┐ ▼ ▼ ▼ [Executor 1] [Executor 2] [Executor 3] large 파티션 1 large 파티션 2 large 파티션 3 → Hash Join → Hash Join → Hash Join- 작은 테이블을 드라이버로 모은 뒤 모든 executor에 복사, 큰 테이블은 움직이지 않음
- 각 executor는 복사본으로 해시 테이블을 만들고 자기 파티션으로 probe → 단일 노드 Hash Join과 동일
- 큰 테이블의 shuffle이 사라지므로 가장 빠른 분산 조인
- 대가: 작은 테이블 크기 × executor 수만큼 메모리·네트워크 사용, 드라이버 메모리 부담
1.2 사용 상황
- Fact ⋈ Dimension: 수억 행 이벤트에 수천~수백만 행 코드/사용자 테이블을 붙일 때
- 필터 후 결과가 작아지는 서브쿼리를 조인할 때
- 자동 선택 기준: 통계상 크기가
spark.sql.autoBroadcastJoinThreshold(기본 10MB) 이하-1이면 자동 broadcast 비활성화
- OUTER JOIN 제약: 보존되는 쪽은 broadcast(build)할 수 없음
large LEFT JOIN small→ small broadcast 가능small LEFT JOIN large→ small을 broadcast할 수 없음FULL OUTER JOIN→ Broadcast Hash Join 불가
1.3 힌트와 실행 계획 확인
SELECT /*+ BROADCAST(c) */ c.name, sum(o.amount)FROM orders oJOIN customers c ON o.customer_id = c.customer_idGROUP BY c.name;from pyspark.sql.functions import broadcastorders.join(broadcast(customers), "customer_id")EXPLAIN(또는df.explain())에서 확인할 노드 (자동 broadcast를 끈 상태에서 힌트로 강제)
*(3) HashAggregate(keys=[name#3], functions=[sum(amount#10L)])+- Exchange hashpartitioning(name#3, 200), ENSURE_REQUIREMENTS ← GROUP BY용 shuffle (조인과 무관) +- *(2) HashAggregate(keys=[name#3], functions=[partial_sum(amount#10L)]) +- *(2) Project [amount#10L, name#3] +- *(2) BroadcastHashJoin [customer_id#9L], [customer_id#2L], Inner, BuildRight, false :- *(2) Project [...] ← orders: Exchange 없음 : +- *(2) Range (0, 5000000, step=1, splits=4) +- BroadcastExchange HashedRelationBroadcastMode(List(input[0, bigint, false]),false) ← customers 복사 +- *(1) Project [...] +- *(1) Range (0, 100000, step=1, splits=4)BuildRight/BuildLeft: 어느 쪽을 해시 테이블(build)로 만들었는지- 큰 테이블(orders) 쪽에
Exchange hashpartitioning이 없어야 의도대로 동작한 것 - 힌트 없이 기본 설정(10MB, AQE on)으로 돌려도
customers10만 행이 임계값 아래로 추정되어 같은 BHJ가 선택됨
OUTER JOIN 제약 확인: 보존되는 쪽에 BROADCAST 힌트를 주면 무시되고 SMJ로 실행됨
SELECT /*+ BROADCAST(c) */ * FROM orders o LEFT JOIN small_c c ON o.customer_id = c.customer_id; -- c는 보존 대상 아님SELECT /*+ BROADCAST(c) */ * FROM small_c c LEFT JOIN orders o ON o.customer_id = c.customer_id; -- c가 보존 대상SELECT /*+ BROADCAST(c) */ * FROM orders o FULL OUTER JOIN small_c c ON o.customer_id = c.customer_id;-- large LEFT JOIN small+- BroadcastHashJoin [customer_id#9L], [customer_id#16L], LeftOuter, BuildRight, false
-- small LEFT JOIN large → 힌트 무시+- SortMergeJoin [customer_id#16L], [customer_id#9L], LeftOuter
-- FULL OUTER → 힌트 무시+- SortMergeJoin [customer_id#9L], [customer_id#16L], FullOuter- 1천 행짜리
small_c라도 보존 방향이면 broadcast 불가. 힌트가 적용됐다고 가정하지 말고 반드시 EXPLAIN으로 확인
Concept
- Broadcast Join : 작은 테이블 전체를 모든 executor에 복사해 큰 테이블을 이동시키지 않고 조인하는 전략. Fact-Dimension 조인의 1순위 최적화
- autoBroadcastJoinThreshold : Spark가 테이블을 자동으로 broadcast할 크기 상한(기본 10MB, -1이면 비활성화). 통계 기반 추정 크기로 판단
- Build Side 제약 : OUTER JOIN에서 보존되는 쪽은 build(broadcast)할 수 없다는 규칙. LEFT JOIN은 오른쪽만, FULL OUTER는 broadcast hash 불가
- BroadcastExchange : 실행 계획에서 테이블을 모든 노드로 복사하는 연산자. 이 노드가 보이고 큰 쪽에 Exchange가 없으면 broadcast 성공
2. Shuffle Join
2.1 개념
orders 파티션들 ──hash(customer_id) % N──┐ ├──▶ 파티션 0: key%N=0 인 orders + customers → 조인 customers 파티션들 ─hash(customer_id) % N─┤──▶ 파티션 1: key%N=1 인 orders + customers → 조인 └──▶ ...- 양쪽 테이블을 같은 해시 함수·같은 파티션 수로 재분배 → 같은 키가 같은 파티션에 모임 (Co-location 생성)
- 재분배 = Shuffle: map 단계에서 디스크에 쓰고 reduce 단계에서 네트워크로 읽음 → 분산 처리에서 가장 비싼 연산
- 파티션 수:
spark.sql.shuffle.partitions(기본 200, AQE가 런타임에 병합 가능) - Shuffle 이후 파티션 안에서의 매칭 방식에 따라 두 가지로 나뉨
2.2 Sort Merge Join (SMJ) — 기본값
- 각 파티션을 조인 키로 정렬한 뒤 Merge
- 정렬은 메모리가 모자라면 디스크로 spill하며 계속 진행 → 어떤 크기에서도 OOM 없이 안정적
spark.sql.join.preferSortMergeJoin = true(기본)라서 대량 vs 대량 등가 조인의 기본 전략
# 자동 broadcast와 AQE를 끄면 대량 등가 조인의 기본값인 SMJ가 나옴spark.conf.set("spark.sql.autoBroadcastJoinThreshold", "-1")spark.conf.set("spark.sql.adaptive.enabled", "false")+- *(5) SortMergeJoin [customer_id#9L], [customer_id#2L], Inner :- *(2) Sort [customer_id#9L ASC NULLS FIRST], false, 0 : +- Exchange hashpartitioning(customer_id#9L, 200), ENSURE_REQUIREMENTS ← orders shuffle : +- *(1) Project [...] : +- *(1) Range (0, 5000000, step=1, splits=4) +- *(4) Sort [customer_id#2L ASC NULLS FIRST], false, 0 +- Exchange hashpartitioning(customer_id#2L, 200), ENSURE_REQUIREMENTS ← customers shuffle +- *(3) Project [...] +- *(3) Range (0, 100000, step=1, splits=4)- 양쪽에
Exchange hashpartitioning+Sort가 붙는 모양이 SMJ의 표시 *(n): Whole-Stage Codegen 단위.Exchange를 경계로 stage가 끊김
2.3 Shuffle Hash Join (SHJ)
- shuffle 후 각 파티션에서 작은 쪽으로 해시 테이블을 만들어 probe → 정렬 비용 없음
- 파티션 하나의 build 쪽이 메모리에 들어가야 함 → 스큐가 있으면 OOM 위험
- 사용 상황: 한쪽이 broadcast하기엔 크지만 파티션 단위로는 충분히 작고, 정렬 비용을 아끼고 싶을 때
SELECT /*+ SHUFFLE_HASH(c) */ c.name, sum(o.amount) FROM orders o JOIN customers c ON ... GROUP BY c.name;+- *(3) ShuffledHashJoin [customer_id#9L], [customer_id#2L], Inner, BuildRight :- Exchange hashpartitioning(customer_id#9L, 200), ENSURE_REQUIREMENTS ← Sort 노드 없음 : +- *(1) Project [...] +- Exchange hashpartitioning(customer_id#2L, 200), ENSURE_REQUIREMENTS +- *(2) Project [...]2.4 힌트
| 힌트 | 강제 전략 |
|---|---|
BROADCAST(t) (= BROADCASTJOIN, MAPJOIN) | Broadcast Hash Join |
MERGE(t) (= SHUFFLE_MERGE, MERGEJOIN) | Sort Merge Join |
SHUFFLE_HASH(t) | Shuffle Hash Join (t를 build) |
SHUFFLE_REPLICATE_NL(t) | Cartesian Product 계열 Nested Loop |
- 양쪽에 서로 다른 힌트가 있으면 우선순위 BROADCAST > MERGE > SHUFFLE_HASH > SHUFFLE_REPLICATE_NL
- 조인 타입상 불가능한 힌트(예: FULL OUTER에 BROADCAST)는 무시됨 (1.3의 실측 참고)
2.5 비등가 조인
- Hash·Merge는 등가 조인 전용 → 비등가 조건은 Nested Loop 계열만 가능
- 한쪽이 작으면 broadcast, 아니면 양쪽 전체 조합(Cartesian)
SELECT * FROM orders o JOIN small_c c ON o.amount > c.customer_id; -- small_c 1천 행+- BroadcastNestedLoopJoin BuildRight, Inner, (amount#10L > customer_id#16L) :- Project [...] : +- Range (0, 5000000, step=1, splits=4) +- BroadcastExchange IdentityBroadcastMode ← 해시 테이블이 아니라 행 그대로 복사 +- Project [...] +- Range (0, 1000, step=1, splits=4)자동 broadcast를 끄면 (양쪽이 큰 상황과 동일)
CartesianProduct (amount#10L > customer_id#2L) ← 500만 × 10만 조합을 모두 평가:- *(1) Project [...]+- *(2) Project [...]CartesianProduct가 보이면 조건을 등가 조인으로 바꿀 수 있는지(범위 버킷팅 등) 먼저 검토
Concept
- Shuffle : 데이터를 키 해시 기준으로 모든 노드에 재분배하는 연산. 디스크 쓰기·네트워크 전송·직렬화가 동반되어 분산 처리에서 가장 비싼 단계
- Hash Partitioning :
hash(key) % N으로 행의 목적지 파티션을 정하는 방식. 양쪽을 같은 함수·같은 N으로 나누면 같은 키가 같은 파티션에 모임 - Sort Merge Join(분산) : 양쪽을 shuffle한 뒤 파티션별로 정렬·병합하는 Spark의 기본 대량 조인 전략. 정렬이 디스크로 spill 가능해 크기에 관계없이 안정적
- Shuffle Hash Join : shuffle 후 파티션별로 해시 테이블을 만들어 조인하는 전략. 정렬 비용이 없지만 파티션 build 쪽이 메모리에 들어가야 함
- spark.sql.shuffle.partitions : shuffle 후 파티션 수(기본 200). 너무 적으면 파티션당 데이터가 커져 spill·OOM, 너무 많으면 작은 태스크 오버헤드
3. 런타임 최적화와 함정
3.1 AQE(Adaptive Query Execution)
- Spark 3.2+ 기본 활성화(
spark.sql.adaptive.enabled = true) - 실행 계획을 shuffle 단계 사이에 실제 통계로 다시 최적화
- SMJ → BHJ 전환: 필터 후 실제 크기가 작아졌으면 런타임에 broadcast로 바꿈
- 파티션 병합: 작은 shuffle 파티션을 합쳐 태스크 수를 줄임
- Skew Join 분할: 너무 큰 파티션을 쪼개 여러 태스크로 처리
- 확인:
EXPLAIN결과 맨 위AdaptiveSparkPlan isFinalPlan=false는 실행 전 계획- 실제로 쓰인 계획은 실행 후 Spark UI SQL 탭 또는
isFinalPlan=true인 계획에서 확인 EXPLAIN만 보고 “SMJ로 돌았다”고 판단하면 틀릴 수 있음 — PostgreSQL의EXPLAINvsEXPLAIN ANALYZE차이와 같은 맥락
- 실제로 쓰인 계획은 실행 후 Spark UI SQL 탭 또는
SMJ → BHJ 런타임 전환 실측 (customers 500만 행, 기본 설정)
SELECT c.name, sum(o.amount)FROM orders oJOIN (SELECT * FROM customers WHERE customer_id % 1000 = 0) c -- 실제로는 5천 행 ON o.customer_id = c.customer_idGROUP BY c.name;df = spark.sql(q)df.explain() # 실행 전: isFinalPlan=falsedf.collect()print(df._jdf.queryExecution().executedPlan().toString()) # 실행 후: isFinalPlan=true실행 전 (EXPLAIN)
AdaptiveSparkPlan isFinalPlan=false+- ... +- SortMergeJoin [customer_id#9L], [customer_id#2L], Inner :- Sort [...] : +- Exchange hashpartitioning(customer_id#9L, 200), ENSURE_REQUIREMENTS : +- Filter ((((id#6L % 90000) % 1000) = 0) AND ...) +- Sort [...] +- Exchange hashpartitioning(customer_id#2L, 200), ENSURE_REQUIREMENTS +- Filter ((id#0L % 1000) = 0)실행 후
AdaptiveSparkPlan isFinalPlan=true+- == Final Plan == ... +- *(3) BroadcastHashJoin [customer_id#9L], [customer_id#2L], Inner, BuildLeft, false :- BroadcastQueryStage 2 : +- BroadcastExchange HashedRelationBroadcastMode(...) : +- AQEShuffleRead local : +- ShuffleQueryStage 0 : +- Exchange hashpartitioning(customer_id#9L, 200), ENSURE_REQUIREMENTS +- AQEShuffleRead local +- ShuffleQueryStage 1 +- Exchange hashpartitioning(customer_id#2L, 200), ENSURE_REQUIREMENTS- 필터 없는 원본 크기(500만 행)로 추정해 정적으로는 SMJ, shuffle 후 실제 크기가 작다는 걸 보고 런타임에 BHJ로 전환
AQEShuffleRead local: 이미 shuffle로 써둔 파일을 reducer 간 재분배 없이 로컬에서 읽음 → 정렬과 두 번째 네트워크 이동을 생략AQEShuffleRead coalesced: 비어 있거나 작은 shuffle 파티션 200개를 병합해 태스크 수를 줄인 흔적
전환되지 않는 경우도 있음
- 같은 쿼리를
customer_id < 100조건(키 11개)으로 돌렸을 때는 결과가 훨씬 작은데도 SMJ가 유지됨 - Spark는 shuffle 파티션 중 데이터가 있는 비율이 낮으면(
spark.sql.adaptive.nonEmptyPartitionRatioForBroadcastJoin, 기본 0.2) broadcast 전환을 하지 않음 — 빈 파티션은 SMJ에서도 비용이 거의 없기 때문- 키 11개 → 200개 파티션 중 많아야 11개(5.5%)만 데이터가 있어 이 조건에 걸린 것으로 판단 (키를 고르게 퍼뜨린 위 실험에서는 전환됨)
- 또한
autoBroadcastJoinThreshold = -1로 자동 broadcast를 끄면 AQE의 런타임 전환 기준(spark.sql.adaptive.autoBroadcastJoinThreshold, 미설정 시 같은 값 사용)도 함께 꺼짐
3.2 Data Skew
- 특정 키(예:
customer_id = NULL, 대형 고객사)에 행이 몰리면 그 키가 간 파티션 하나만 오래 걸림 - 증상: Spark UI에서 태스크 대부분은 수 초, 몇 개만 수십 분 (stage 시간 = 가장 느린 태스크)
- 대응
- AQE skew join:
spark.sql.adaptive.skewJoin.enabled = true(기본) — 중앙값의 5배 이상 그리고 256MB 이상인 파티션을 분할 - NULL 키는 조인 전에 분리 처리 (NULL은 어차피 매칭되지 않음)
- Salting: 스큐 키에 랜덤 접미사를 붙여 여러 파티션으로 분산, 반대쪽은 그만큼 복제
- AQE skew join:
3.3 Shuffle 자체를 없애는 방법
- Broadcast: 한쪽이 작으면 가장 간단
- Bucketing: 양쪽 테이블을 같은 조인 키·같은 버킷 수로 미리 나눠 저장 → 조인 시
Exchange없음 (쓰기 시점에 shuffle 비용을 한 번만 지불) - Storage-Partitioned Join: Iceberg 등 테이블 포맷의 파티션 정보를 이용해 shuffle을 생략 (Spark 3.3+)
- 단일 노드 대응 개념: PostgreSQL의
enable_partitionwise_join— 같은 방식으로 파티션된 테이블을 파티션끼리 조인
Concept
- AQE(Adaptive Query Execution) : shuffle 경계에서 수집한 실제 통계로 남은 실행 계획을 재최적화하는 Spark 기능. SMJ→BHJ 전환, 파티션 병합, 스큐 분할을 런타임에 수행
- isFinalPlan : AQE 계획이 실행 후 확정된 최종 계획인지 표시하는 플래그.
EXPLAIN만으로는 false이므로 실제 전략은 실행 후 확인해야 함 - AQEShuffleRead local / coalesced : AQE가 shuffle 결과를 읽는 방식을 바꾼 흔적. local은 BHJ 전환 후 재분배 없이 로컬에서 읽기, coalesced는 작은 파티션 병합
- Non-empty Partition Ratio 조건 : shuffle 파티션 중 데이터가 있는 비율이 낮으면 AQE가 BHJ 전환을 하지 않는 규칙(기본 0.2). 결과가 작아도 키 종류가 적으면 SMJ가 유지될 수 있음
- Data Skew : 특정 키에 데이터가 몰려 일부 파티션만 비대해지는 현상. 가장 느린 태스크가 stage 전체 시간을 결정하므로 분산 조인 성능 저하의 주원인
- Salting : 스큐 키에 랜덤 값을 덧붙여 여러 파티션으로 분산시키고 반대쪽 테이블을 그만큼 복제하는 기법. AQE로 해결되지 않는 극단적 스큐에 사용
- Bucketing : 테이블을 조인 키 해시로 고정된 개수의 파일 그룹에 나눠 저장하는 방식. 같은 키·같은 버킷 수로 저장된 테이블끼리는 shuffle 없이 조인
4. 언제 무엇을 쓰는가
조인 조건이 등가(=)인가?├─ 아니오│ ├─ 한쪽이 작음 ─────────────────────────▶ Broadcast Nested Loop Join│ └─ 양쪽이 큼 ───────────────────────────▶ Cartesian Product (피해야 함: 조건 재설계, 범위 버킷팅)└─ 예 ├─ 한쪽이 작음(≈ 수십~수백 MB 이하) + 조인 타입상 broadcast 가능 │ ─────────────────────────────────────▶ Broadcast Hash Join ├─ 양쪽이 이미 같은 키로 bucket/partition ──▶ Shuffle 없는 SMJ (Bucketing / SPJ) ├─ 한쪽이 파티션 단위로 충분히 작고 정렬 비용이 아까움 │ ─────────────────────────────────────▶ Shuffle Hash Join └─ 그 외 대량 vs 대량 ───────────────────▶ Sort Merge Join (기본값, 스큐 확인)| 단일 노드(PostgreSQL) | 분산(Spark) | 공통 원리 |
|---|---|---|
| Nested Loop | Broadcast Nested Loop / Cartesian | 비등가 조인의 유일한 선택지 |
| Hash Join | Broadcast Hash Join / Shuffle Hash Join | 작은 쪽을 해시 테이블로 |
| Merge Join | Sort Merge Join | 정렬 후 병합, 메모리 부족에 강함 |
work_mem 초과 → batch spill | executor 메모리 초과 → spill / OOM | 메모리 한도가 전략을 바꿈 |
EXPLAIN ANALYZE | Spark UI / isFinalPlan=true | 추정 계획이 아닌 실제 계획을 볼 것 |
pg_hint_plan | /*+ BROADCAST(t) */ 등 | 힌트는 통계로 해결 안 될 때만 |
Concept
- 분산 조인 선택 기준 : 등가 여부, 작은 쪽의 크기, 조인 타입(보존 방향), 기존 파티셔닝 상태, 스큐 유무. 이 다섯 가지로 BHJ·SHJ·SMJ·BNLJ 중 하나가 결정됨
- 작은 쪽 있음 → Broadcast : shuffle을 통째로 없애는 가장 효과적인 최적화. OUTER JOIN의 보존 방향과 executor 메모리만 확인
- 대량 vs 대량 → Sort Merge : 메모리 부족에도 spill로 버티는 안정적인 기본값. 성능 문제는 대개 스큐나 과도한 shuffle 파티션에서 발생
- Shuffle 회피 → Bucketing / Partitioned Join : 반복되는 대량 조인은 저장 시점에 같은 키로 나눠 두면 매번의 shuffle 비용을 제거할 수 있음
관련 글
- [spark]Spark Shuffling 최적화
- [SQL]Semi Join과 Anti Join — Spark에서는
LEFT SEMI JOIN,LEFT ANTI JOIN으로 명시적으로 작성 가능
추가적으로 공부하면 좋은 컨셉, 주제들
- Dynamic Partition Pruning : 조인 상대의 필터 결과로 큰 테이블의 읽을 파티션을 런타임에 줄이는 Spark 최적화
- Bloom Filter Join : 작은 쪽 키로 블룸 필터를 만들어 큰 쪽을 shuffle 전에 미리 걸러내는 기법
- Trino 조인 분산 방식 :
join_distribution_type(BROADCAST / PARTITIONED / AUTOMATIC)으로 같은 문제를 다루는 방식 - Spark CBO와 테이블 통계 :
ANALYZE TABLE ... COMPUTE STATISTICS로 크기·행 수 통계를 수집해 조인 전략 선택 정확도를 높이는 방법 - Range Join 최적화 : 시간 구간 같은 비등가 조인을 버킷으로 나눠 등가 조인으로 바꾸는 기법
[SQL]분산 조인: Broadcast vs Shuffle
https://yjinheon.netlify.app/posts/02de/06-sql/de-sql-distributed-join/