4383 words
22 minutes
[SQL]분산 조인: Broadcast vs Shuffle

단일 노드(PostgreSQL)의 조인 알고리즘이 분산 환경(Spark 기준) 에서 어떻게 확장되는지 정리

실행 계획은 Spark 3.5.1 local[4]에서 직접 실행한 결과. orders 500만 행(spark.range로 생성), customers 10만 행(AQE 예제는 500만 행), small_c 1천 행. 가독성을 위해 Project/Range 등 일부 노드는 ...로 생략

0. 분산 조인의 핵심 문제#

  • 단일 노드: 두 테이블이 같은 머신에 있으므로 어떤 알고리즘으로 매칭할지만 결정
  • 분산 환경: 같은 키를 가진 행이 서로 다른 노드에 흩어져 있음 → 매칭 전에 같은 키를 같은 노드로 모으는 작업이 먼저 필요
  • 모으는 방법은 두 가지
    1. Broadcast: 작은 테이블 전체를 모든 노드에 복사
    2. Shuffle: 양쪽 테이블을 조인 키 해시로 재분배
  • 이후 각 노드 안에서는 앞 글의 Hash Join / Sort Merge Join / Nested Loop가 그대로 수행됨
분산 조인 전략 = [데이터 이동 방식: Broadcast | Shuffle] + [노드 내 알고리즘: Hash | Sort Merge | Nested Loop]
Spark 전략데이터 이동노드 내 알고리즘조건
Broadcast Hash Join (BHJ)작은 쪽 broadcastHash등가 조인, 한쪽이 작음
Shuffle Hash Join (SHJ)양쪽 shuffleHash등가 조인, 파티션별 해시가 메모리에 들어감
Sort Merge Join (SMJ)양쪽 shuffle정렬 후 Merge등가 조인, 대량 vs 대량의 기본값
Broadcast Nested Loop Join (BNLJ)한쪽 broadcastNested 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 o
JOIN customers c ON o.customer_id = c.customer_id
GROUP BY c.name;
from pyspark.sql.functions import broadcast
orders.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)으로 돌려도 customers 10만 행이 임계값 아래로 추정되어 같은 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의 EXPLAIN vs EXPLAIN ANALYZE 차이와 같은 맥락

SMJ → BHJ 런타임 전환 실측 (customers 500만 행, 기본 설정)

SELECT c.name, sum(o.amount)
FROM orders o
JOIN (SELECT * FROM customers WHERE customer_id % 1000 = 0) c -- 실제로는 5천 행
ON o.customer_id = c.customer_id
GROUP BY c.name;
df = spark.sql(q)
df.explain() # 실행 전: isFinalPlan=false
df.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 시간 = 가장 느린 태스크)
  • 대응
    1. AQE skew join: spark.sql.adaptive.skewJoin.enabled = true(기본) — 중앙값의 5배 이상 그리고 256MB 이상인 파티션을 분할
    2. NULL 키는 조인 전에 분리 처리 (NULL은 어차피 매칭되지 않음)
    3. Salting: 스큐 키에 랜덤 접미사를 붙여 여러 파티션으로 분산, 반대쪽은 그만큼 복제

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 LoopBroadcast Nested Loop / Cartesian비등가 조인의 유일한 선택지
Hash JoinBroadcast Hash Join / Shuffle Hash Join작은 쪽을 해시 테이블로
Merge JoinSort Merge Join정렬 후 병합, 메모리 부족에 강함
work_mem 초과 → batch spillexecutor 메모리 초과 → spill / OOM메모리 한도가 전략을 바꿈
EXPLAIN ANALYZESpark 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 비용을 제거할 수 있음

관련 글#

추가적으로 공부하면 좋은 컨셉, 주제들#

  • 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/
Author
Datamind
Published at
2026-10-24
License
CC BY-NC-SA 4.0