[MySQL] Join 동작 원리
Join이란
조인(Join)은 정규화된 테이블들을 엮어 하나의 결과로 만드는 연산이다.
Join의 동작 원리
중첩 루프 조인
중첩 루프 조인은 이중 반복문이다. 드라이빙 테이블에서 WHERE를 통과한 행을 하나 꺼내면, 드리븐 테이블에서 짝이 맞는 행을 찾아 결합한다.
여기서 비용은 드리븐의 조인 컬럼에 인덱스가 없으면 드라이빙 행 하나마다 드리븐 전체를 처음부터 스캔한다. 1만 건씩인 두 테이블이면 드리븐 풀스캔이 1만 번, 비교가 1억 번이다.
sequenceDiagram autonumber participant D as 드라이빙 테이블(orders) participant R as 드리븐 테이블 PRIMARY(customers, 클러스터 인덱스) loop 드라이빙 테이블의 각 행마다 D->>D: 조인 컬럼 값 추출(customer_id) D->>R: customer_id로 PRIMARY 탐색 R-->>D: 행 데이터 반환(클러스터 인덱스라 탐색 자체가 곧 데이터) D->>D: 두 행을 결합해 결과 한 건 방출 end
- 드라이빙 테이블에서 WHERE 조건을 통과한 행을 하나 꺼낸다.
- 조인 컬럼 값을 추출한다.
- 드리븐 테이블의 PRIMARY를 그 값으로 탐색해 행 데이터를 얻는다.
- 두 행을 결합하고, 남은 행이 있으면 반복한다.
세컨더리 인덱스가 조인 조건이라면, 세컨더리 인덱스의 리프에는 키 컬럼과 PK만 있어 조회할 컬럼이 인덱스에 없으면 그 PK로 클러스터 인덱스를 한 번 더 탐색한다. 드라이빙 행마다 PK가 달라 페이지를 무작위 순서로 읽는 랜덤 I/O가 된다. 만약 조회할 컬럼이 전부 세컨더리 인덱스에 있으면(커버링 인덱스) 디스크까지의 재탐색을 하진 않는다.
중첩 루프 조인의 비용은 드라이빙 행 수와 드리븐을 한 번 찾는 비용의 곱이다. 인덱스는 이 곱의 뒤쪽 값을 테이블 크기에서 인덱스 높이로 줄이므로, 조인 성능을 볼 때 먼저 확인할 것은 드리븐의 조인 컬럼에 인덱스가 있는가를 살펴 봐야 한다.
배치 키 액세스
인덱스를 이용하여 탐색 횟수는 줄었지만 탐색 순서는 드라이빙 행 순서를 그대로 따른다. 드라이빙 행의 조인 키가 뒤섞여 있으면, 세컨더리 인덱스에서 얻은 PK로 클러스터 인덱스를 다시 읽는 랜덤 I/O가 행 수만큼 생긴다.
배치 키 액세스는 탐색을 한 건씩 보내지 않고 모아서 보낸다. 드라이빙 행에서 조인에 필요한 컬럼만 조인 버퍼(join_buffer_size, 기본 256KB)에 쌓고, 버퍼가 차면 그 키들을 다중 범위 읽기(Multi-Range Read, MRR) 인터페이스로 스토리지 엔진에 한꺼번에 넘긴다.
- 드라이빙 테이블에서 행을 읽어 조인에 필요한 컬럼을 조인 버퍼에 쌓는다.
- 버퍼가 차면 버퍼 안의 행마다 드리븐 인덱스를 탐색할 키를 만들어 MRR에 한꺼번에 넘긴다.
- MRR이 키마다 인덱스를 탐색해 row ID(InnoDB에서는 PK)를 모으고, PK 순서로 정렬한다.
- 정렬된 PK 순서로 행을 읽어 버퍼 속 드라이빙 행과 결합하고, 버퍼를 비운 뒤 1번으로 돌아간다.
배치 키 액세스는 탐색 순서를 바꾸는 최적화다. PK 순서로 읽으면 같은 16KB 페이지에 있는 행을 연달아 처리하고, 페이지를 디스크 위치 순서로 읽게 된다. 버퍼가 클수록 한 번에 정렬하는 키가 많아져 순차 접근에 가까워진다. 이 정렬 이점은 세컨더리 인덱스로 얻은 PK로 행을 다시 읽을 때 생기므로, 다시 읽을 행이 없는 커버링 인덱스에서는 MRR을 쓰지 않는다.
블록 중첩 루프 조인
블록 중첩 루프 조인은 인덱스 없는 중첩 루프 조인의 드리븐을 1만 번 다시 읽는 문제를 조인 버퍼로 푼다. 드라이빙 행을 한 건씩 넘기지 않고 버퍼에 묶음으로 쌓은 뒤, 드리븐을 한 번 훑으면서 버퍼 안의 행 전부와 대조한다
- 드라이빙 테이블에서 행을 읽어 조인에 필요한 컬럼만 조인 버퍼에 쌓는다.
- 버퍼가 차거나 드라이빙 행을 다 읽으면 드리븐 테이블을 처음부터 끝까지 한 번 스캔한다.
- 스캔한 드리븐 행을 버퍼 안의 드라이빙 행 전부와 비교해, 조건이 맞는 쌍을 결합해 내보낸다.
- 스캔이 끝나면 버퍼를 비우고, 드라이빙 행이 남아 있으면 1번으로 돌아간다.
해시 조인
해시 조인은 빌드 단계에서 더 작다고 추정되는 테이블을 끝까지 읽어 조인 키 기준으로 해시 테이블을 만든다. 프로브 단계에서는 나머지 큰 테이블을 한 행씩 읽으며 조인 키로 해시 테이블을 조회해, 짝을 찾는 비용을 행 수와 무관한 상수 시간으로 낮춘다.
sequenceDiagram autonumber participant B as Build 입력(작다고 추정된 쪽) participant H as 해시 테이블(join_buffer_size) participant P as Probe 입력(나머지) B->>H: 입력 전체를 읽어 조인 키로 해시 테이블 생성 Note over H: 빌드가 끝나기 전에는 결과 행이 하나도 나가지 않는다 loop Probe 입력의 각 행마다 P->>H: 조인 키로 해시 테이블 조회 H-->>P: 일치하는 Build 행 P->>P: 두 행을 결합해 결과 한 건 방출 end
1만 건씩인 두 테이블이면 빌드에서 1만 번 넣고 프로브에서 1만 번 조회하므로, 블록 중첩 루프의 비교 1억 번이 해시 연산 2만 번 수준으로 줄어든다.
해시 테이블은 join_buffer_size 안에서 만들어진다. 빌드 입력이 이 크기를 넘으면, 넘친 빌드 행과 프로브 행을 조인 키 해시값에 따라 디스크의 청크 파일로 나눠 쓰고, 같은 해시값 범위의 빌드 청크와 프로브 청크를 한 쌍씩 다시 읽어 조인한다.
알고리즘별 비용
| 알고리즘 | 드리븐을 읽는 방식 (1만 건씩 기준) | 비교 횟수 | 첫 결과가 나오는 시점 |
|---|---|---|---|
| 중첩 루프 조인, 인덱스 없음 | 풀스캔 1만 번 | 1억 번 | 첫 짝을 찾은 직후 |
| 중첩 루프 조인, 인덱스 있음 | 인덱스 탐색 1만 번(높이 3이면 페이지 접근 3만 번) | 조인 키가 일치하는 행만 | 첫 짝을 찾은 직후 |
| 배치 키 액세스 | 버퍼가 찰 때마다 PK 순서로 일괄 탐색 | 조인 키가 일치하는 행만 | 첫 버퍼가 찬 뒤 |
| 블록 중첩 루프 | 풀스캔 4번(행당 100바이트, 버퍼 256KB) | 1억 번 | 첫 버퍼가 찬 뒤 |
| 해시 조인, 동등 조건 | 두 입력을 한 번씩 | 해시 조회 1만 번 | 빌드가 끝난 뒤 |
드라이빙 테이블과 드리븐 테이블
Join시 가장 먼저 접근하는 테이블을 드라이빙 테이블, 후에 접근 하는 테이블을 드리븐 테이블이라 한다. 어느 테이블을 드라이빙으로 둘지는 옵티마이저가 정하고, 정하는 방식은 두 가지다. 미리 매겨 둔 우선순위를 따르는 규칙 기반 옵티마이저(Rule-Based Optimizer, RBO)와, 후보마다 비용을 계산해 가장 싼 쪽을 고르는 비용 기반 옵티마이저(Cost-Based Optimizer, CBO)다.
| 구분 | 규칙 기반 옵티마이저 | 비용 기반 옵티마이저 |
|---|---|---|
| 판단 근거 | 접근 방식에 매긴 고정 순위 | 통계 정보와 비용 상수로 계산한 비용 |
| 행 수와 값 분포 | 보지 않는다 | 추정해서 비용에 반영한다 |
| 같은 쿼리의 실행 계획 | 데이터가 바뀌어도 같다 | 통계가 바뀌면 달라질 수 있다 |
규칙 기반 옵티마이저
규칙 기반 옵티마이저는 접근 방식마다 순위를 매겨 두고, 더 높은 순위로 읽을 수 있는 계획을 고른다.
조인 순서도 같은 순위로 정한다. 드라이빙 후보마다 접근 순위를 비교하고, 순위로 가려지지 않으면 FROM 절에 적힌 순서를 따른다.
SELECT c.name, o.amount FROM orders o JOIN customers c ON c.id = o.customer_id WHERE o.status = 'PAID'- status에는 인덱스가 없어 어느 쪽을 드라이빙으로 두든 풀스캔이기 때문에 규칙의 효과가 없음
- 드리븐도 customers는 PK로, orders는
idx_customer_id로 찾는 인덱스 탐색
결국 뒤에 적힌 customers가 드라이빙이 되고, FROM 절을 customers c JOIN orders o로 바꿔 적기만 해도 계획이 바뀐다. 이는 SQL의 작성 순서, 조건문 등 수동적으로 사람이 고려해야할 부분이 많으므로 현재는 비용 기반 옵티마이저가 많이 쓰인다.
비용 기반 옵티마이저
MySQL은 비용 기반 옵티마이저를 쓴다. 옵티마이저는 WHERE로 걸러진 뒤 남는 행 수와 인덱스로 순서 후보마다 비용을 계산하고, 가장 비용이 낮은 것을 고른다.
-- 옵티마이저가 고른 순서: orders가 드라이빙
-> Nested loop inner join (cost=678 rows=498)
-> Filter: ((o.`status` = 'PAID') and (o.customer_id is not null)) (cost=503 rows=498)
-> Table scan on o (cost=503 rows=4980)
-> Single-row index lookup on c using PRIMARY (id=o.customer_id) (cost=0.25 rows=1)
-- STRAIGHT_JOIN으로 강제한 순서: customers가 드라이빙
-> Nested loop inner join (cost=1851 rows=500)
-> Table scan on c (cost=101 rows=1000)
-> Filter: (o.`status` = 'PAID') (cost=1.25 rows=0.5)
-> Index lookup on o using idx_customer_id (customer_id=c.id) (cost=1.25 rows=5)explain analyze의 cost는 이 비용 기만 옵티마이저가 어떻게 결정을 했는지 과정을 보여준다.
- orders를 드라이빙으로 두면 풀스캔 비용 503에서 시작한다(4980행 × 행 평가 0.1 = 498에 페이지 읽기 5.25를 더한 값).
- status에는 인덱스도 히스토그램도 없어, 옵티마이저는 선택도를 기본값 10%로 두고(
EXPLAIN의filtered가 10.00) WHERE 통과 행을 498로 추정한다. - 498행마다 customers의 PRIMARY 탐색 0.35(페이지 읽기 0.25 + 행 평가 0.1)가 붙어 174가 더해지고, 합계는 678이다.
- customers를 드라이빙으로 두면 1000행마다
idx_customer_id로 평균 5행을 찾는 1.75(읽기 1.25 + 행 평가 0.5)가 붙어, 101 + 1750 = 1851이다.
FROM 절을 customers c JOIN orders o로 바꿔 적어도 옵티마이저의 비용 계산이 정하므로 결과는 동일하다. 때문에 WHERE 절의 순서라든지, Join의 순서라든지는 크게 의미가 없다.
다만 비용 기반 옵티마이저에도 비용을 따지기 전에 적용되는 규칙이 있다. PK나 유니크 키를 상수로 찾는 테이블은 한 행만 나오므로 최적화 단계에서 미리 읽어 상수(const)로 바꾸고, 조인 순서의 맨 앞에 둔다. FROM orders o JOIN customers c ON c.id = o.customer_id WHERE c.id = 100은 orders를 먼저 적어도 customers가 const로 첫 행에 오고, STRAIGHT_JOIN으로 순서를 고정할 때만 적힌 순서를 따른다.
Join과 인덱스
customers 1000건, orders 5000건, payments 8000건, order_logs 9800건
CREATE TABLE customers (
id BIGINT PRIMARY KEY,
name VARCHAR(100)
);
CREATE TABLE orders (
id BIGINT PRIMARY KEY,
customer_id BIGINT,
amount DECIMAL(10,2),
status VARCHAR(20),
created_at DATETIME,
warehouse_code VARCHAR(20),
INDEX idx_customer_id (customer_id)
);
CREATE TABLE payments (
id BIGINT PRIMARY KEY,
order_id BIGINT,
amount DECIMAL(10,2),
paid_at DATETIME
-- order_id에 인덱스 없음. 한 테이블 인덱스 컬럼으로 조회 절에서 의도적으로 비워 둔다
);
CREATE TABLE order_logs (
id BIGINT PRIMARY KEY,
warehouse_code VARCHAR(20),
message VARCHAR(200)
-- warehouse_code에 인덱스 없음. 인덱스 컬럼 없이 조회 절에서 사용한다
);두 테이블 인덱스 컬럼으로 조회
양쪽에 인덱스가 있으면 둘 다 드리븐이 될 수 있다. 옵티마이저는 전체 비용으로 드라이빙을 정하며, 대개 필터 후 행 수가 적은 쪽을 고른다.
EXPLAIN
SELECT c.name, o.amount
FROM customers c
JOIN orders o ON c.id = o.customer_id
WHERE c.id = 100;| id | select_type | table | type | possible_keys | key | key_len | ref | rows |
|---|---|---|---|---|---|---|---|---|
| 1 | SIMPLE | c | const | PRIMARY | PRIMARY | 8 | const | 1 |
| 1 | SIMPLE | o | ref | idx_customer_id | idx_customer_id | 9 | const | 13 |
c는 PK 등치 조건이라 const, o는 idx_customer_id로 ref다(고객 100번의 실제 주문 13건과 일치). 둘 다 인덱스로 좁혀져 건당 비용이 크게 늘지 않는다.
한 테이블 인덱스 컬럼으로 조회
한쪽에만 인덱스가 있으면 옵티마이저는 인덱스 있는 쪽을 드리븐으로 두려 한다.
EXPLAIN
SELECT o.id, p.paid_at
FROM orders o
JOIN payments p ON o.id = p.order_id
WHERE o.customer_id = 100;| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|---|---|---|---|---|---|---|---|---|---|
| 1 | SIMPLE | p | ALL | NULL | NULL | NULL | NULL | 8116 | Using where |
| 1 | SIMPLE | o | eq_ref | PRIMARY,idx_customer_id | PRIMARY | 8 | joindemo.p.order_id | 1 | Using where |
인덱스가 없는 p가 드라이빙(전체 스캔, 추정 8116건), o가 드리븐(PK eq_ref)으로 선택됐다. orders를 먼저 13건으로 좁히는 것보다, payments 한 행마다 orders를 PK로 즉시 찾는 쪽을 옵티마이저가 더 싸다고 봤다. 옵티마이저 선택은 데이터 분포와 통계에 따라 달라질 수 있다.
인덱스 컬럼 없이 조회
양쪽 다 인덱스가 없어도 중첩 루프 조인은 성립하지만 비효율적이다. orders.warehouse_code와 order_logs.warehouse_code는 둘 다 인덱스 없는 같은 타입(VARCHAR) 컬럼이다. o JOIN l ON o.warehouse_code = l.warehouse_code는 다음처럼 처리된다.
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|---|---|---|---|---|---|---|---|---|---|
| 1 | SIMPLE | o | ALL | NULL | NULL | NULL | NULL | 4980 | NULL |
| 1 | SIMPLE | l | ALL | NULL | NULL | NULL | NULL | 9675 | Using where; Using join buffer (hash join) |
o, l 모두 ALL이지만 두 테이블의 컬럼에 인덱스가 없기 때문에 옵티마이저가 비용을 비교해보고, 해시 조인을 만들었다. 그 결과 l의 Extra에 있는 Using join buffer (hash join)이 사용되었다고 표시된다.
-- 같은 쿼리의 TREE
-> Inner hash join (l.warehouse_code = o.warehouse_code) (cost=4.82e+6 rows=4.82e+6)
-> Table scan on l (cost=0.0326 rows=9675)
-> Hash
-> Table scan on o (cost=503 rows=4980)Hash 아래 Table scan on o가 있어, 더 작다고 추정된 orders(4980건)가 빌드 입력이고 order_logs(9675건)가 프로브 입력이다. 빌드가 join_buffer_size(기본 256KB)를 넘으면 디스크로 나눠 처리한다.
-- block_nested_loop=off 상태에서 같은 쿼리의 TREE
-> Nested loop inner join (cost=4.96e+6 rows=4.84e+6)
-> Table scan on o (cost=519 rows=5000)
-> Filter: (l.warehouse_code = o.warehouse_code) (cost=24.3 rows=968)
-> Table scan on l (cost=24.3 rows=9675)Join의 실행 계획
| type | 의미 | 조인에서 흔한 위치 |
|---|---|---|
| const | PK 또는 UNIQUE NOT NULL 인덱스 전체를 등치 조건으로 사용(일치 행이 없어도 나올 수 있음) | WHERE에 상수 조건이 걸린 드라이빙 테이블 |
| eq_ref | 드라이빙 행마다 PK 또는 UNIQUE NOT NULL 인덱스 전체를 등치 조건으로 사용(일치 행 없을 수도 있음) | 드리븐 테이블이 PK로 조인될 때 |
| ref | 드라이빙 행마다 비유니크 인덱스로 여러 행 가능 | 드리븐 테이블이 일반 인덱스로 조인될 때 |
| range | 인덱스 범위 스캔 | 조인 컬럼에 범위 조건이 있을 때 |
| ALL | 풀스캔 | 인덱스 없는 드라이빙 또는 드리븐 테이블 |
Extra는 그 테이블에 쓴 전략을 보여준다.
| Extra 값 | 의미 |
|---|---|
| Using join buffer (Batched Key Access) | BKA로 키를 모아 MRR로 일괄 탐색 |
| Using join buffer (Block Nested Loop) | 8.0.20 미만, 인덱스 없어 조인 버퍼 묶음마다 드리븐 재스캔 |
| Using join buffer (hash join) | 8.0.20부터 전통적 EXPLAIN에 표시(8.0.18~19는 TREE로 확인) |
| Using where | 잔여 조건 적용(조인 전후 모두 가능). 정확한 위치는 TREE의 Filter 노드 |
| Using index | 커버링 인덱스만으로 해결, 테이블 접근 없음 |
아래는 orders를 status로 거른 뒤 customers와 PK로 조인하는 쿼리의 TREE와 ANALYZE다.
EXPLAIN FORMAT=TREE
SELECT c.name, o.amount
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.status = 'PAID';
-- TREE
-> Nested loop inner join (cost=678 rows=498)
-> Filter: ((o.`status` = 'PAID') and (o.customer_id is not null)) (cost=503 rows=498)
-> Table scan on o (cost=503 rows=4980)
-> Single-row index lookup on c using PRIMARY (id=o.customer_id) (cost=0.25 rows=1)
-- 같은 쿼리의 EXPLAIN ANALYZE
-> Nested loop inner join (cost=678 rows=498) (actual time=0.213..1.51 rows=138 loops=1)
-> Filter: ((o.`status` = 'PAID') and (o.customer_id is not null)) (cost=503 rows=498) (actual time=0.171..1.18 rows=138 loops=1)
-> Table scan on o (cost=503 rows=4980) (actual time=0.15..0.901 rows=5000 loops=1)
-> Single-row index lookup on c using PRIMARY (id=o.customer_id) (cost=0.25 rows=1) (actual time=0.00216..0.00218 rows=1 loops=138)Filter 노드가 Using where의 정확한 위치다. status='PAID'와 함께 customer_id IS NOT NULL도 자동으로 걸린다.
loops=138은 필터를 통과한 138개 orders 행마다 PRIMARY 탐색이 한 번씩, 총 138회 일어났다는 뜻이다. 여러 loops의 시간과 rows는 반복 1회 평균이다. 추정 rows(498)와 실제(138)의 차이만으로 통계 노후화가 증명되지는 않으며, 데이터 분포나 조건 간 상관관계가 원인일 수도 있다.
Join 성능과 주의사항
조인 컬럼 타입이 다르면 변환 방향에 따라 한쪽 인덱스만 무효가 될 수 있다. customers(1000건)를 드라이빙에 두고 orders.customer_id_text(VARCHAR, idx_cust_text)로 조인하면, 같은 타입 BIGINT 대조군과 이렇게 갈린다.
| 구분 | table | type | key | key_len | rows | Extra |
|---|---|---|---|---|---|---|
| VARCHAR 비교 | o | index | idx_cust_text | 83 | 5000 | Using where; Using index; Using join buffer (hash join) |
| BIGINT 대조군 | o | ref | idx_customer_id | 9 | 12 | Using index |
-- VARCHAR 비교의 TREE
-> Inner hash join (cast(c.id as double) = cast(o.customer_id_text as double)) (cost=500151 rows=500000)
-> Index scan on o using idx_cust_text (cost=0.0993 rows=5000)
-> Hash
-> Table scan on c (cost=101 rows=1000)cast(c.id as double) = cast(o.customer_id_text as double)가 TREE에 그대로 찍힌다. 인덱스가 있어도 ref 대신 index 풀스캔이 됐다. 조인 컬럼은 처음부터 같은 타입, 같은 문자셋으로 두어야 풀스캔을 피할 수 있다.
카디널리티가 안 맞으면 결과가 불어난다. 1대다인 줄 알았던 조인이 실제로는 다대다면, 드라이빙 한 행이 드리븐 여러 행과 겹쳐 결과가 예상보다 커진다. COUNT(DISTINCT ...)로 중간 검증하면 초반에 잡아낼 수 있다.
참여 테이블이 늘면 탐색 비용도 커진다(optimizer_prune_level과 optimizer_search_depth는 앞서 다룬 것과 같다). 고정된 테이블 수 경계는 없으므로, EXPLAIN으로 순서를 확인하고 필요하면 STRAIGHT_JOIN이나 JOIN_ORDER로 고정한다.
상관 서브쿼리를 조인으로 바꾸는 것이 항상 같은 결과는 아니다. EXISTS는 존재만 확인해 원래 행을 남기지만, JOIN은 일치 행 수만큼 복제한다.