Engine Atlas

MySQL 조인 알고리즘

Indexed Nested Loop와 Hash Join의 plan, row flow, evidence

MySQL 8.4.10captured

English

학습 안내

이 Lab에서 답할 질문

같은 join 결과를 만들 때 nested-loop와 hash join은 어느 input을 반복 탐색하고 어느 input을 build/probe하나요?

실행 엔진: MySQL 8.4.10

누가 실행하나요?

하나의 Session이 같은 join SELECT를 nested-loop와 hash join capture variant에서 실행합니다.

무엇을 고정하나요?

동일한 두 input table, SQL, 반환 rows와 checksum을 고정하되 indexed variant에만 idx_join_orders_customer_status가 있는 capture condition을 비교합니다.

실행 SQL

SELECT
  c.id AS customer_id,
  c.segment,
  o.id AS order_id,
  o.status,
  o.total_cents
FROM join_customers AS c
JOIN join_orders AS o
  ON o.customer_code = c.customer_code
WHERE c.region_code = 'KR'
  AND o.status = 'PAID';

무엇이 달라지나요?

idx_join_orders_customer_status availability, operator 구조, outer/inner 반복, hash build/probe 단계와 관련 statement counters가 달라집니다.

무엇이 그대로인가요?

join predicate와 matched result rows 및 checksum은 두 algorithm variant에서 동일합니다.

먼저 예측해 보세요

hash join을 선택한 variant에서 새로 추적할 두 역할은 무엇인가요?

sort input과 LIMIT outputhash table을 만드는 build input과 match를 찾는 probe inputlock holder와 waiting transaction

증거 미션

hash join variant의 match flow 단계를 열어 어느 input이 build고 어느 input이 probe인지 확인하세요.

어디를 보나요?: Join lens에서 build side와 probe side 표시를, plan 쪽에서는 Hash operator와 Inner hash join operator를 함께 봅니다.
이동할 화면: Hash Join · match flow

무엇이 보여야 하나요?

확인할 관찰

hash-join capture에는 Hash operator가 join의 직접 child로 있고 index lookup operator는 없습니다. idx_join_orders_customer_status는 indexed-nested-loop capture 조건에만 존재하며, 두 variant 모두 join output 257행을 기록합니다.

근거 경계

Captured: hash-join plan의 Hash child와 Inner hash join operator 구조, 그리고 parent join output 257행
Derived · fixture: customer_code로 연결한 JOIN_PAIRS membership

Checkpoint · evidence로 설명하기두 variant의 captured completion time만으로 한 algorithm이 일반적으로 우월하다고 결론내릴 수 있나요?답과 근거 확인

아닙니다. 이 capture는 해당 fixture와 server state의 실행 evidence입니다. algorithm 구조와 row flow를 설명할 수 있지만 모든 workload의 성능 순위를 일반화할 수는 없습니다.

근거 경계

Captured: plan 구조, row flow, counters와 completion time

이번 Lab의 핵심

join algorithm 비교는 이름이 아니라 어떤 input이 반복되고, build되며, probe되는지와 동일 결과가 어떻게 조립되는지로 읽어야 합니다.

다음 연결

다음 Lab에서는 join이나 aggregation 뒤의 중간 rows가 internal temporary table과 sort storage로 어떻게 이어지는지 봅니다.

용어 확인

nested-loop join처음 다루는 Lab 04: outer input의 row마다 inner input에서 match를 찾는 join 실행 방식입니다.
hash build / probe처음 다루는 Lab 04: 한쪽 join input으로 hash table을 build하고 다른 input의 join key로 probe해 match를 찾는 두 단계입니다.

01 · SOURCE

두 variant가 공유하는 SQL

1 active fragmentMySQLJOIN · no ORDER BY

SELECT c.id AS customer_id, c.segment, o.id AS order_id, o.status, o.total_cents
FROM join_customers AS c
JOIN join_orders AS o ON o.customer_code = c.customer_code
WHERE c.region_code = 'KR'
  AND o.status = 'PAID';

02 · FLOW

Native plan과 actual iterator

01 / 12

STEP 01 · query shape

같은 SQL에서 두 필터와 join 조건을 읽습니다

join_customers의 KR 조건과 join_orders의 PAID 조건을 적용한 뒤 customer_code로 결합합니다. 이 SQL byte는 두 variant에서 같습니다.

Active plan operators

hash-joinhash-join-join

-> Inner hash join (o.customer_code = c.customer_code) (cost=25825 rows=1341)line:1

Frame metrics

조인 출력 행: 257
일치한 pair 수: 257

Active evidence

fixture-join-pairsevidence:join-algorithms-hash-join-result-tsv

Derived · fixture

hash-join-explain-tree-txtevidence:join-algorithms-hash-join-explain-tree-txt

Captured

hash-join-normalized-operator-metricsevidence:join-algorithms-hash-join-explain-analyze-txt

Derived · capture

hash-join-normalized-planevidence:join-algorithms-hash-join-explain-json

Derived · capture

Capturednative TREE, ANALYZE, statement, and session evidence

Derived · fixtureexact rows, join membership, stable result order, and checksum

Modelactive key position used only for the animated explanation

.join-algorithms-page { overflow: auto !important; } .join-algorithms-page main { height: auto !important; min-height: 100dvh; } .join-workbench-shell { display: none !important; } .join-noscript { display: block !important; }

SQL과 캡처 범위 · MySQL 8.4.10 · Captured

MySQL 조인 알고리즘 - 인덱스 Nested Loop와 Hash Join

동일한 SQL과 fixture에서 MySQL 8.4.10 Hash Join과 Indexed Nested Loop의 native plan, build/probe 및 outer/inner row 흐름, actual rows와 loops, 정확한 matched pair를 비교합니다.

Query SHA-256: 11ffd828e9f211040949ec56dbdc117b3dfb3b29377d7208528a7647f8ec7558
Variants: 2
Frames: 12 per variant

SQL

SELECT
  c.id AS customer_id,
  c.segment,
  o.id AS order_id,
  o.status,
  o.total_cents
FROM join_customers AS c
JOIN join_orders AS o
  ON o.customer_code = c.customer_code
WHERE c.region_code = 'KR'
  AND o.status = 'PAID';

두 실행 계획

Hash Join

Algorithm: hash-join
selectedKey: NULL
Captured join output: 257 rows
Captured join loops: 1

operator	access_type	cost	estimated rows	actual rows / loop	loops	native
`hash-join-join`	`not applicable`	25825	1341	—	1	`-> Inner hash join (o.customer_code = c.customer_code) (cost=25825 rows=1341)`line:1
`hash-join-order-filter`	`not applicable`	121	1310	2008	1	-> Filter: (o.`status` = 'PAID') (cost=121 rows=1310) (actual time=0.374..60.2 rows=2008 loops=1)line:2
`hash-join-order-scan`	`ALL`	121	130995	131072	1	`-> Table scan on o (cost=121 rows=130995) (actual time=0.365..47.7 rows=131072 loops=1)`line:3
`hash-join-hash`	`not applicable`	—	—	—	—	`-> Hash`line:4
`hash-join-customer-filter`	`not applicable`	104	102	126	1	`-> Filter: (c.region_code = 'KR') (cost=104 rows=102) (actual time=0.0629..0.47 rows=126 loops=1)`line:5
`hash-join-customer-scan`	`ALL`	104	1024	1024	1	`-> Table scan on c (cost=104 rows=1024) (actual time=0.0565..0.38 rows=1024 loops=1)`line:6

Indexed Nested Loop

Algorithm: indexed-nested-loop
selectedKey: idx_join_orders_customer_status
Captured join output: 257 rows
Captured join loops: 1

operator	access_type	cost	estimated rows	actual rows / loop	loops	native
`indexed-nested-loop-join`	`not applicable`	1282	3367	—	1	`-> Nested loop inner join (cost=1282 rows=3367)`line:1
`indexed-nested-loop-customer-filter`	`not applicable`	104	102	126	1	`-> Filter: (c.region_code = 'KR') (cost=104 rows=102) (actual time=0.0722..0.486 rows=126 loops=1)`line:2
`indexed-nested-loop-customer-scan`	`ALL`	104	1024	1024	1	`-> Table scan on c (cost=104 rows=1024) (actual time=0.0636..0.388 rows=1024 loops=1)`line:3
`indexed-nested-loop-order-lookup`	`ref`	8.25	32.9	2.04	126	`-> Index lookup on o using idx_join_orders_customer_status (customer_code=c.customer_code, status='PAID') (cost=8.25 rows=32.9) (actual time=0.0121..0.0126 rows=2.04 loops=126)`line:4

Operator와 Row 흐름

Hash Join

role	table	Actual rows / loop	Loops	Source
build	`join_customers`	126	1	Captured
probe	`join_orders`	2008	1	Captured

Captured join output: 257 rows Captured
Matched pairs: 257 pairs Derived · fixture

Indexed Nested Loop

role	table	Actual rows / loop	Loops	Source
outer	`join_customers`	126	1	Captured
inner	`join_orders`	2.04	126	Captured

Captured join output: 257 rows Captured
Matched pairs: 257 pairs Derived · fixture

결과 집합의 동일성

총 257행 · 20행 표시 · 237행 생략

customer_id, order_id로 정렬한 Derived · fixture 표시이며 MySQL native 방문 순서가 아닙니다.

SHA-256 edecce27bda10f840f1d54bda755b283368dd2703fa1bdbc3e6952dfa9a40048

총 257행 · 20행 표시 · 237행 생략
#	customer_id	segment	order_id	status	total_cents
1	5	SMB	83485	PAID	478418
2	23	PUBLIC	21263	PAID	418593
3	31	PUBLIC	62103	PAID	411640
4	31	PUBLIC	78487	PAID	38259
5	31	PUBLIC	104087	PAID	65809
6	31	PUBLIC	127639	PAID	58142
7	31	PUBLIC	130711	PAID	134844
8	37	SMB	12349	PAID	223286
9	37	SMB	17469	PAID	396245
10	37	SMB	39997	PAID	491616
11	37	SMB	66621	PAID	397863
12	39	ENTERPRISE	5663	PAID	113291
13	39	ENTERPRISE	12831	PAID	484591
14	39	ENTERPRISE	53791	PAID	64324
15	55	ENTERPRISE	31023	PAID	389822
16	55	ENTERPRISE	43311	PAID	10988
17	55	ENTERPRISE	78127	PAID	373331
18	60	STARTUP	17892	PAID	152430
19	60	STARTUP	79332	PAID	128047
20	83	PUBLIC	21387	PAID	180575

237행 생략 · Derived · fixture

12단계 실행 설명

Hash Join

같은 SQL에서 두 필터와 join 조건을 읽습니다
join_customers의 KR 조건과 join_orders의 PAID 조건을 적용한 뒤 customer_code로 결합합니다. 이 SQL byte는 두 variant에서 같습니다.
캡처된 Inner hash join 구조를 펼칩니다
native TREE에는 Inner hash join과 Hash child가 있으며 join key 보조 index는 없습니다. build와 probe 역할은 이 캡처의 plan 구조에서 가져옵니다.
customer table 1,024행을 build 입력 쪽에서 읽습니다
Table scan on c는 캡처에서 1,024행을 한 번 반환했습니다. 화면의 안정된 row sample은 고정 fixture에서 선택합니다.
KR customer 126행을 build side에 남깁니다
c.region_code = 'KR' Filter는 캡처에서 루프당 126행, 반복 횟수 1을 기록했습니다. 정확한 membership은 fixture 집합과 대조합니다.
customer_code를 hash build key로 놓습니다
선택한 customer_code의 화면 위치는 Model입니다. active key는 논리적 이동만 보여 주며 MySQL 내부 저장 위치를 뜻하지 않습니다.
order table 131,072행을 probe 입력 쪽에서 읽습니다
Table scan on o는 캡처에서 131,072행을 한 번 반환했습니다. 표시 sample은 order ID 기준으로 안정되게 고른 fixture row입니다.
PAID order 2,008행을 probe side에 남깁니다
o.status = 'PAID' Filter는 캡처에서 루프당 2,008행, 반복 횟수 1을 기록했습니다. 정확한 PAID membership은 fixture에서 계산됩니다.
probe key와 같은 customer_code의 pair를 연결합니다
보이는 pair는 JOIN_PAIRS의 안정된 앞부분이며 각 membership은 Derived · fixture입니다. 이 배열은 MySQL native 방문 순서가 아닙니다.
captured join output 257행을 확인합니다
parent Inner hash join은 캡처에서 조인 출력 행 257을 기록했습니다. 일치한 pair 수 257은 별도의 Derived · fixture 사실입니다.
257개 SELECT 결과를 안정된 순서로 표시합니다
customer_id와 order_id로 정렬한 전체 결과와 checksum은 Derived · fixture입니다. 표시 순서는 MySQL native 방문 순서가 아닙니다.
한 캡처 실행의 statement와 session delta를 읽습니다
이 captured execution은 join 완료 시각 61.2ms, statement 단위 rowsExamined 132,096을 기록했습니다. Handler_read_rnd_next 132,098은 session 단위 delta이며 operator나 row에 배분하지 않습니다.
native plan, normalized metric, fixture 결과를 대조합니다
TREE와 ANALYZE에서 읽은 normalized plan 구조를 capture-normalized operator·statement metric과 대조합니다. customers와 orders, 일치한 pair, 정렬된 전체 result rows, checksum은 각각 Derived · fixture source로 확인합니다.

Indexed Nested Loop

같은 SQL에서 두 필터와 join 조건을 읽습니다
join_customers의 KR 조건과 join_orders의 PAID 조건을 적용한 뒤 customer_code로 결합합니다. query byte와 결과 checksum은 Hash variant와 같습니다.
캡처된 Nested loop와 선택 index를 펼칩니다
native TREE는 Nested loop inner join과 idx_join_orders_customer_status lookup을 기록했습니다. outer와 inner 역할은 이 캡처의 plan 구조에서 가져옵니다.
customer table 1,024행을 outer 입력에서 읽습니다
Table scan on c는 캡처에서 1,024행을 한 번 반환했습니다. 화면의 안정된 row sample은 고정 fixture에서 선택합니다.
KR customer 126행을 outer side에 남깁니다
c.region_code = 'KR' Filter는 캡처에서 루프당 126행, 반복 횟수 1을 기록했습니다. 이 126행이 inner lookup 반복 횟수와 일치합니다.
outer customer 한 행이 inner lookup을 시작합니다
선택한 customer_code의 이동은 Model입니다. active key는 논리적 lookup 위치만 나타내며 storage 배치를 주장하지 않습니다.
선택 index에서 customer별 order 후보를 찾습니다
inner side는 idx_join_orders_customer_status를 customer_code와 PAID 값으로 조회합니다. selected index 이름과 lookup 문구는 native plan에서 가져옵니다.
inner lookup의 captured 평균과 loop를 그대로 읽습니다
inner operator는 루프당 실제 행 2.04와 반복 횟수 126을 기록했습니다. 이 값은 곱하거나 반올림해 다른 count로 바꾸지 않습니다.
outer key와 같은 customer_code의 pair를 연결합니다
보이는 pair는 JOIN_PAIRS의 안정된 앞부분이며 각 membership은 Derived · fixture입니다. 이 배열은 MySQL native 방문 순서가 아닙니다.
captured parent output 257행을 확인합니다
parent Nested loop은 조인 출력 행 257을 기록했습니다. 일치한 pair 수 257은 별도의 Derived · fixture 사실이며 2.04와 126으로 재계산하지 않습니다.
257개 SELECT 결과를 안정된 순서로 표시합니다
customer_id와 order_id로 정렬한 전체 결과와 checksum은 Derived · fixture입니다. 표시 순서는 MySQL native 방문 순서가 아닙니다.
한 캡처 실행의 statement와 session delta를 읽습니다
이 captured execution은 join 완료 시각 2.1ms, statement 단위 rowsExamined 1,281을 기록했습니다. Handler_read_key 127과 Handler_read_next 257은 session 단위 delta이며 operator나 row에 배분하지 않습니다.
native plan, normalized metric, fixture 결과를 대조합니다
TREE와 ANALYZE에서 읽은 normalized plan 구조를 capture-normalized operator·statement metric과 대조합니다. customers와 orders, 일치한 pair, 정렬된 전체 result rows, checksum은 각각 Derived · fixture source로 확인합니다.

근거와 출처 구분

Captured: MySQL 8.4.10의 native TREE, EXPLAIN ANALYZE, JSON plan, statement 및 session counter에서 읽은 값
Derived · fixture: 동일 SQL predicate를 deterministic fixture에 적용해 얻은 exact membership, canonical result, checksum
Model: active customer_code의 논리적 이동 위치. MySQL 내부 저장 위치를 나타내지 않음

Hash Join · 12 frames · 13 published evidence records

Indexed Nested Loop · 12 frames · 13 published evidence records