MySQL 조인 알고리즘

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

MySQL 8.4.10captured

01 · SOURCE

두 variant가 공유하는 SQL

1 active fragmentsMySQLJOIN · 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