JOIN: 관계형 테이블을 조건으로 결합하는 연산과 세 가지 실행 알고리즘
JOIN은 둘 이상의 테이블에서 조건에 맞는 행을 이어 붙여 하나의 결과 집합(result set)을 만드는 관계형 연산이다. INNER, LEFT, FULL 같은 종류별 결과 차이와 PostgreSQL 옵티마이저가 선택하는 Nested Loop, Hash Join, Merge Join의 동작 원리를 다룬다. EXPLAIN으로 실행 계획을 읽는 방법과 실무
By 송민성
1. 개념
JOIN은 두 테이블의 행을 조인 조건(join condition) 에 따라 짝지어 하나의 결과 집합으로 만드는 연산이다. 이론적으로는 카테시안 곱(Cartesian product)에 선택(selection) 조건을 적용한 것과 같다. 즉 A JOIN B ON 조건은 "A×B의 모든 조합 중 조건을 만족하는 것만 남긴다"는 의미다.
주요 종류는 다음과 같다.
| 종류 | 결과 |
|---|---|
| INNER JOIN | 양쪽에서 조건이 일치하는 행만 |
| LEFT (OUTER) JOIN | 왼쪽 전체 + 일치하는 오른쪽 (없으면 NULL) |
| RIGHT (OUTER) JOIN | 오른쪽 전체 + 일치하는 왼쪽 (없으면 NULL) |
| FULL (OUTER) JOIN | 양쪽 전체, 일치하지 않는 쪽은 NULL |
| CROSS JOIN | 조건 없이 모든 조합 (카테시안 곱) |
| SELF JOIN | 같은 테이블끼리 결합 (별칭 필요) |
2. 왜 사용하는가
정규화(normalization)된 스키마는 중복을 없애기 위해 데이터를 여러 테이블로 나눈다. 주문 정보는 orders에, 고객 정보는 users에 한 번만 저장하고, 조회 시점에 외래 키(foreign key)로 다시 합친다. JOIN은 이 "분리 저장, 조회 시 결합" 모델을 가능하게 하는 연산이다.
- 데이터 중복과 갱신 이상(update anomaly)을 피하면서도 합쳐진 형태로 조회할 수 있다.
- 애플리케이션에서 쿼리를 여러 번 보내 코드로 합치는 것보다 DB 안에서 처리하는 편이 네트워크 왕복이 적고, 옵티마이저가 최적화할 여지가 크다.
3. 동작 원리
옵티마이저(optimizer)는 통계 정보와 인덱스를 바탕으로 비용이 가장 낮은 조인 알고리즘을 고른다. PostgreSQL은 세 가지를 지원한다.
Nested Loop Join 바깥 테이블(outer)의 각 행마다 안쪽 테이블(inner)을 탐색한다. 안쪽에 조인 키 인덱스가 있으면 행마다 인덱스 조회로 끝나므로, 바깥 결과가 작을 때 유리하다. 인덱스가 없으면 안쪽을 매번 전체 스캔하므로 O(N×M)이 된다.
Hash Join 작은 쪽 테이블로 조인 키 기반 해시 테이블(hash table)을 메모리에 만들고(build), 큰 쪽을 훑으면서 해시 조회(probe)로 짝을 찾는다. 등치(=) 조건에서만 쓸 수 있다. 해시 테이블이 work_mem을 넘으면 디스크로 나누어 처리(batch)하므로 느려진다.
Merge Join 양쪽을 조인 키로 정렬한 뒤 두 포인터를 앞으로 움직이며 병합한다. 이미 정렬되어 있거나 인덱스로 정렬 순서를 얻을 수 있으면 효율적이다. 등치 조건뿐 아니라 정렬 가능한 범위 비교에도 쓰인다.
4. 코드 예제
PostgreSQL에서 그대로 실행할 수 있는 예제다.
CREATE TABLE users (
id SERIAL PRIMARY KEY,
name TEXT NOT NULL
);
CREATE TABLE orders (
id SERIAL PRIMARY KEY,
user_id INT REFERENCES users(id),
amount INT NOT NULL
);
CREATE INDEX idx_orders_user_id ON orders(user_id);
INSERT INTO users (name) VALUES ('민수'), ('지영'), ('철수');
INSERT INTO orders (user_id, amount) VALUES
(1, 15000), (1, 8000), (2, 32000), (NULL, 5000);
-- INNER JOIN: 주문이 있는 사용자만
SELECT u.name, o.amount
FROM users u
INNER JOIN orders o ON o.user_id = u.id;
-- LEFT JOIN: 주문이 없는 '철수'도 포함 (amount는 NULL)
SELECT u.name, o.amount
FROM users u
LEFT JOIN orders o ON o.user_id = u.id;
-- 안티 조인 패턴: 주문이 한 건도 없는 사용자
SELECT u.name
FROM users u
LEFT JOIN orders o ON o.user_id = u.id
WHERE o.id IS NULL;
-- FULL JOIN: user_id가 NULL인 주문과 주문 없는 사용자 모두 포함
SELECT u.name, o.amount
FROM users u
FULL JOIN orders o ON o.user_id = u.id;
-- 사용자별 주문 합계 (집계와 함께)
SELECT u.name, COALESCE(SUM(o.amount), 0) AS total
FROM users u
LEFT JOIN orders o ON o.user_id = u.id
GROUP BY u.id, u.name
ORDER BY total DESC;
-- 실행 계획 확인
EXPLAIN ANALYZE
SELECT u.name, o.amount
FROM users u
JOIN orders o ON o.user_id = u.id;EXPLAIN 출력에서 Nested Loop, Hash Join, Merge Join 노드를 확인할 수 있다. 데이터가 몇 건뿐이면 옵티마이저가 인덱스가 있어도 순차 스캔(Seq Scan)을 고를 수 있다. 데이터 규모와 통계에 따라 계획이 달라지는 것은 정상이다.
5. 시간 복잡도 또는 성능 특성
N, M을 각각 두 테이블의 행 수라 할 때 이론적 복잡도는 다음과 같다.
| 알고리즘 | 시간 복잡도 | 비고 |
|---|---|---|
| Nested Loop (인덱스 없음) | O(N×M) | 한쪽이 매우 작을 때만 적합 |
| Nested Loop (안쪽 B-tree 인덱스) | O(N log M) | 바깥 결과가 작을 때 유리 |
| Hash Join | O(N+M) | 등치 조건만, 메모리 한도 영향 |
| Merge Join | O(N log N + M log M) | 이미 정렬되어 있으면 O(N+M) |
실제 성능은 이론 복잡도 외에 조인 키 인덱스 유무, 통계의 정확도, work_mem, 결과 행 수에 크게 좌우된다. 최종 판단은 EXPLAIN (ANALYZE, BUFFERS)로 실측해서 한다.
6. 실무 사용 사례
- 목록 화면: 주문 목록에 사용자 이름과 상품명을 함께 보여주기 위해
orders,users,products를 JOIN한다. - N+1 문제 해결: 목록 조회 후 행마다 연관 데이터를 쿼리하는 대신, ORM의 fetch join이나
JOIN/IN쿼리로 한 번에 가져온다. - 미존재 탐지: 주문이 없는 사용자, 결제가 누락된 주문처럼 "없는 것"을 찾을 때
LEFT JOIN ... WHERE 우측.id IS NULL또는NOT EXISTS를 쓴다. - 계층 구조 조회: 직원과 매니저처럼 같은 테이블 안의 부모-자식 관계는 SELF JOIN으로 푼다.
- 리포트 집계: 여러 테이블을 JOIN한 뒤
GROUP BY로 매출, 가입자 수 등을 집계한다.
7. 주의할 점
1) LEFT JOIN에서 ON과 WHERE는 다르다. 오른쪽 테이블 조건을 WHERE에 쓰면 NULL 행이 걸러져 사실상 INNER JOIN이 된다.
-- 의도: 모든 사용자 + 15000 초과 주문만 붙이기
SELECT u.name, o.amount
FROM users u
LEFT JOIN orders o ON o.user_id = u.id AND o.amount > 15000; -- 올바름
-- 아래는 amount가 NULL인 사용자가 WHERE에서 제거된다
SELECT u.name, o.amount
FROM users u
LEFT JOIN orders o ON o.user_id = u.id
WHERE o.amount > 15000;2) 1:N 조인은 행을 늘린다. 사용자 1명에 주문이 3건이면 결과도 3행이다. 이 상태에서 사용자 단위로 COUNT나 SUM을 하면 값이 부풀려진다. 집계 단위를 먼저 맞추거나 서브쿼리로 미리 집계한 뒤 조인한다.
3) NULL은 조인 조건에서 일치하지 않는다. NULL = NULL은 참이 아니라 NULL(unknown)이므로 user_id가 NULL인 행은 INNER JOIN에서 빠진다. NULL끼리 매칭하려면 IS NOT DISTINCT FROM을 사용한다.
4) 조인 키에 인덱스가 없는 경우. PostgreSQL은 외래 키 컬럼에 인덱스를 자동으로 만들지 않는다. 참조하는 쪽(orders.user_id)에 직접 인덱스를 만들어야 Nested Loop 성능이 나오고, 부모 행 삭제 시의 참조 검사도 빨라진다.
5) 조건 없는 조인. ON 조건을 빠뜨리거나 잘못 쓰면 카테시안 곱이 되어 행 수가 N×M으로 폭증한다.
6) 조인 키의 타입과 함수. 조인 키 양쪽의 타입이 다르거나 ON lower(a.email) = b.email처럼 컬럼에 함수를 씌우면 일반 인덱스를 쓰지 못할 수 있다. 필요하면 표현식 인덱스(expression index)를 만든다.
8. 핵심 정리
- JOIN은 조건에 맞는 행을 결합하는 연산이며, INNER·LEFT·RIGHT·FULL·CROSS 종류별로 일치하지 않는 행의 처리가 다르다.
- PostgreSQL은 Nested Loop, Hash Join, Merge Join 중 통계와 인덱스를 기준으로 비용이 낮은 방식을 고른다.
- Hash Join은 등치 조건에서 O(N+M), 인덱스를 쓰는 Nested Loop은 O(N log M)이 일반적이다. 실제 성능은
EXPLAIN ANALYZE로 확인한다. - LEFT JOIN의 ON과 WHERE 위치, 1:N으로 인한 행 증가, NULL 비교는 실무에서 가장 흔한 오류의 원인이다.
- 외래 키 컬럼에는 직접 인덱스를 만들어야 한다.