데이터베이스 조인 알고리즘(Nested Loop · Sort-Merge · Hash Join)

1. 개요

가. 정의

조인 알고리즘(Join Algorithm) 은 관계형 데이터베이스에서 두 개 이상의 릴레이션(테이블)을 조인 조건에 따라 물리적으로 결합해 결과 집합을 만들어 내는 처리 방식을 말한다. 사용자가 SQL에 FROM A, B WHERE A.k = B.k와 같이 '무엇을 결합할지'만 선언하면, 어떤 물리적 절차로 두 집합의 짝을 찾을지는 옵티마이저가 조인 알고리즘을 선택해 결정한다.

조인 알고리즘을 이해하는 핵심은 '같은 조인 결과를 만드는 방법이 여러 가지이고, 데이터 규모·분포·정렬 상태·인덱스 유무에 따라 어느 방법이 수십~수천 배 빠를 수 있다'는 데 있다. 관계형 모델에서 조인은 가장 비싸면서도 가장 빈번한 연산이다. 두 테이블을 결합한다는 것은 본질적으로 한쪽 집합의 각 행에 대해 다른 쪽 집합에서 짝이 되는 행을 찾는 탐색(matching) 문제이며, 이 탐색을 어떻게 조직하느냐가 곧 알고리즘의 차이다. 아무 전략 없이 모든 행 쌍을 비교하면 두 테이블의 곱(카티전 곱)에 비례하는 비용이 들지만, 정렬을 쓰거나 해시 테이블을 쓰면 그 비용을 선형에 가깝게 낮출 수 있다.

조인이 왜 본질적으로 비싼 연산인지는 집합론적으로도 분명하다. 두 릴레이션의 조인은 개념적으로 카티전 곱(모든 행의 조합)을 만든 뒤 조인 조건을 만족하는 행만 남기는 것과 같다. A가 100만 건, B가 100만 건이면 카티전 곱은 1조(10^12) 조합이 되어, 조건을 아무리 효율적으로 걸러도 '곱을 실제로 만들어 거르는' 순진한 방식은 현실적으로 불가능하다. 세 조인 알고리즘은 모두 '곱을 실제로 만들지 않고도 조건을 만족하는 짝만 직접 찾아내는' 방법이며, 그 수단이 각각 인덱스 탐색·정렬 순서·해시 주소화인 것이다. 조인 알고리즘을 공부한다는 것은 결국 '지수적 탐색 공간을 선형에 가깝게 줄이는 세 가지 공학적 트릭'을 이해하는 일이다.

관계형 DBMS가 조인 알고리즘을 자동으로 고르는 이유는 SQL이 선언형 언어이기 때문이다. 사용자는 결합의 '의미'만 적을 뿐 결합의 '절차'를 지정하지 않으므로, 데이터 양과 분포가 바뀔 때마다 최적 절차도 바뀐다. 상용·오픈소스 DBMS가 공통으로 구현하는 조인 알고리즘은 크게 세 가지 — 중첩 루프 조인(Nested Loop Join), 정렬 병합 조인(Sort-Merge Join), 해시 조인(Hash Join) — 이며, 비용 기반 옵티마이저(CBO)는 통계정보를 근거로 이 중 가장 저렴한 방식을 질의마다 선택한다.

나. 필요성과 위치

조인 알고리즘의 선택은 질의 성능을 좌우하는 결정적 변수다. 예를 들어 주문 테이블(1,000만 건)과 고객 테이블(100만 건)을 결합하는 질의에서, 조건이 극소수만 걸러내는 경우에는 인덱스를 경유한 Nested Loop가 밀리초 단위로 끝나지만, 두 테이블의 대부분을 결합해야 하는 배치성 질의에서 같은 Nested Loop를 쓰면 수억 번의 랜덤 I/O가 발생해 수십 분이 걸린다. 반대로 이 배치 질의에 Hash Join을 쓰면 각 테이블을 한 번씩만 스캔해 수 초에 끝난다. 즉 알고리즘 선택 하나가 서비스 응답성과 자원 소비를 비선형적으로 바꾼다.

조인 알고리즘은 SQL 처리 파이프라인(파싱 → 최적화 → 실행) 중 옵티마이저가 세우는 실행계획(execution plan) 의 핵심 구성요소다. 옵티마이저는 ① 접근 경로(인덱스 vs 전체 스캔), ② 조인 순서(어느 테이블을 먼저 읽을지), ③ 조인 방식(알고리즘) 의 세 축을 조합해 후보 계획을 만들고 비용을 비교한다. 따라서 각 알고리즘의 동작 원리·비용 구조·전제 조건을 이해하는 것은 DB 튜닝, 힌트 설계, 실행계획 해석, 용량 산정의 근간이 되는 핵심 역량이다.

2. 조인 알고리즘 전체 구조

세 알고리즘은 '어떻게 짝을 찾는가'라는 공통 목표를 서로 다른 전략으로 푼다. 아래 전체 구조도는 조인 요청이 옵티마이저를 거쳐 세 갈래의 물리적 알고리즘으로 분기하는 모습을 보여준다.

flowchart TB
  SQL["조인 질의(FROM A JOIN B ON ...)"] --> OPT["옵티마이저(CBO)"]
  STAT["통계정보(카디널리티·분포·인덱스)"] --> OPT
  OPT --> NL["Nested Loop Join(중첩 루프)"]
  OPT --> SM["Sort-Merge Join(정렬 병합)"]
  OPT --> HJ["Hash Join(해시)"]
  NL --> NLU["소량 집합·인덱스 존재 시 유리"]
  SM --> SMU["이미 정렬됨·부등호 조인 시 유리"]
  HJ --> HJU["대량 동등 조인·비정렬 시 유리"]
  style OPT fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
  style STAT fill:#fef3e8,stroke:#ed8f2f,stroke-width:2px

여기서 반드시 구분할 것은 조인 순서(join order) 와 조인 방식(join method) 이다. 조인 순서는 '어느 테이블을 먼저 읽어 결과를 줄일지(driving table)'의 문제이고, 조인 방식은 '선택된 두 집합을 어떤 알고리즘으로 결합할지'의 문제다. 테이블이 셋 이상이면 옵티마이저는 조인을 두 개씩 단계적으로(left-deep 또는 bushy 트리) 수행하는데, 각 단계마다 순서와 방식을 함께 결정한다. 중간 결과 집합의 크기가 다음 단계 비용을 좌우하므로, '먼저 작게 거르는 순서'를 찾는 것이 방식 선택만큼 중요하다. 조인 테이블 수가 늘수록 가능한 순서의 조합이 계승적으로 폭발하기에, 옵티마이저는 동적 계획법·휴리스틱으로 탐색 공간을 제한한다.

세 알고리즘의 본질적 차이는 '짝 찾기 비용을 어디서 줄이는가'에 있다. Nested Loop 는 한 행씩 다른 테이블을 탐색하되 인덱스로 탐색을 가속한다 — 즉 '탐색의 국소성'에 기댄다. Sort-Merge 는 양쪽을 미리 정렬해 한 번의 동시 순회(병합)로 짝을 찾는다 — 즉 '정렬이 만드는 순서'에 기댄다. Hash Join 은 한쪽으로 해시 테이블을 만들어 상수 시간 조회로 짝을 찾는다 — 즉 '해싱이 만드는 직접 주소화'에 기댄다. 이 세 전략은 각각 전제 조건(인덱스·정렬·메모리)이 다르므로, 데이터 상황에 따라 우열이 뒤집힌다. 옵티마이저가 하나를 고정하지 않고 질의마다 다시 고르는 이유가 여기에 있다.

3. Nested Loop Join(중첩 루프 조인)

Nested Loop Join은 가장 직관적인 방식으로, 바깥 테이블(outer, driving)의 각 행마다 안쪽 테이블(inner)을 반복 탐색해 조인 조건을 만족하는 짝을 찾는다. 이름 그대로 이중 반복문 구조이며, 바깥 루프가 선행 집합을 한 행씩 꺼내고 안쪽 루프가 그 행의 조인 키로 후행 집합을 뒤진다.

이 구조에서 바깥 테이블을 '선행(driving) 테이블'이라 부르며, 선행 집합의 크기가 전체 반복 횟수를 결정하므로 '작은 집합을 바깥에 두는' 조인 순서가 성능의 절반을 좌우한다. 옵티마이저는 통계를 보고 결과를 더 적게 만드는 쪽을 선행으로 고르지만, 통계가 왜곡되면 큰 집합을 선행으로 잘못 선택해 반복이 폭증하는 사고가 난다.

핵심은 '안쪽 테이블에 조인 키 인덱스가 있는가'이다. 인덱스가 있으면 안쪽 탐색이 전체 스캔이 아니라 인덱스 탐색(랜덤 액세스)으로 바뀌어, 바깥 행 하나당 몇 번의 블록 읽기만으로 짝을 찾는다. 이 경우 전체 비용은 대략 '바깥 건수 × (인덱스 탐색 + 테이블 랜덤 액세스)'에 비례한다. 따라서 바깥 집합이 소량이고 안쪽에 적절한 인덱스가 있을 때 압도적으로 유리하다. 예컨대 '오늘 가입한 고객 50명'(바깥)에 대해 각자의 주문 내역(안쪽, 고객ID 인덱스 보유)을 붙이는 질의는 50번의 인덱스 탐색만으로 끝난다.

반대로 바깥 집합이 크면 치명적이다. 바깥이 100만 건이면 안쪽 인덱스 탐색을 100만 번 반복하는데, 이 랜덤 I/O는 디스크 헤드 이동(또는 SSD의 랜덤 접근)을 수반해 순차 I/O보다 훨씬 느리다. 또한 안쪽에 인덱스가 없으면 바깥 행마다 안쪽을 전체 스캔하므로 비용이 두 테이블 건수의 곱(카티전 곱)에 비례해 폭발한다. 이를 완화하기 위해 현대 DBMS는 블록 Nested Loop(여러 바깥 행을 묶어 버퍼 단위로 처리), 안쪽 블록 캐싱, 바깥 키 정렬 후 접근(prefetch) 등의 변형을 사용한다.

Nested Loop는 부분 범위 처리(partial range) 에 유리하다는 실무적 장점도 있다. 결과를 처음부터 한 행씩 만들어 내므로, ROWNUM <= 10이나 LIMIT 10처럼 상위 소수만 필요한 OLTP 질의에서 전체를 처리하지 않고 필요한 만큼만 뽑고 멈출 수 있다. 그래서 OLTP 트랜잭션·화면 페이징·소량 결과 조회에 기본으로 쓰인다.

Nested Loop의 성능을 결정하는 또 다른 변수는 클러스터링 팩터(clustering factor), 즉 인덱스 순서와 실제 테이블 저장 순서의 정합도다. 안쪽 인덱스로 찾은 행들이 테이블 블록에 흩어져 있으면(클러스터링 팩터가 나쁨) 바깥 행마다 서로 다른 블록을 랜덤 액세스해야 해, 인덱스가 있어도 체감 성능이 떨어진다. 반대로 조인 키 순서와 저장 순서가 일치하면 같은 블록을 재방문할 확률이 높아져 버퍼 캐시 적중률이 오르고 랜덤 I/O가 준다. 그래서 Nested Loop 튜닝은 '인덱스를 만들었는가'를 넘어 '인덱스가 가리키는 행들이 물리적으로 모여 있는가'까지 봐야 한다. 이 점에서 조인 알고리즘 선택은 테이블 설계·적재 순서와도 맞닿아 있다.

flowchart LR
  O["Outer 테이블(소량·선행)"] --> R1["행 1 → 조인키로 Inner 탐색"]
  O --> R2["행 2 → 조인키로 Inner 탐색"]
  O --> R3["행 N → 조인키로 Inner 탐색"]
  R1 --> IDX["Inner 조인키 인덱스"]
  R2 --> IDX
  R3 --> IDX
  IDX --> RES["짝(matched row) 반환"]
  style IDX fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px

4. Sort-Merge Join(정렬 병합 조인)

Sort-Merge Join은 두 테이블을 각각 조인 키로 정렬한 뒤, 정렬된 두 스트림을 동시에 훑으며(merge) 짝을 맞추는 방식이다. 전화번호부 두 권을 나란히 놓고 같은 이름을 찾아 내려가는 모습을 떠올리면 된다. 두 집합이 같은 순서로 정렬되어 있으면, 각 집합을 단 한 번씩만 순차적으로 읽으면서 포인터를 전진시켜 짝을 찾을 수 있다.

Sort-Merge가 성립하는 근거는 '정렬된 두 수열에서 공통 원소를 찾는 데는 양쪽을 한 번씩만 훑으면 충분하다'는 성질이다. 양쪽이 같은 키 순서로 정렬되어 있으므로, 한쪽 키가 다른 쪽보다 작으면 작은 쪽만 전진시키면 되고 되돌아갈 필요가 없다. 다만 조인 키가 중복되는(일대다·다대다) 경우에는 매칭 구간에서 한쪽 포인터를 되감아(rewind) 모든 조합을 출력해야 하므로, 중복도가 높으면 병합 단계도 가벼운 역행이 발생한다.

이 알고리즘은 크게 정렬 단계(Sort) 와 병합 단계(Merge) 로 나뉜다. 정렬 단계에서 두 집합을 조인 키 순으로 정렬하며, 이 비용이 대략 N log N으로 전체 비용을 지배한다. 병합 단계는 양쪽 포인터를 비교해 작은 쪽을 전진시키고, 키가 같으면 결과로 출력하는 선형 순회(O(N + M))다. 따라서 정렬 비용을 얼마나 줄이느냐가 관건이며, 이미 정렬된 상태(인덱스 풀스캔으로 정렬 순서가 보장되거나, 이전 연산의 출력이 정렬되어 있는 경우) 라면 정렬 단계를 건너뛰어 매우 효율적이 된다.

Sort-Merge Join의 결정적 강점은 부등호(비동등) 조인을 처리할 수 있다는 점이다. Hash Join은 해시 값의 일치만 판별하므로 =(동등) 조건에서만 동작하지만, Sort-Merge는 정렬된 순서를 이용하므로 >=, BETWEEN, 범위 겹침 같은 조건에도 적용할 수 있다. 예를 들어 '상품 가격이 특정 구간에 속하는 할인 정책을 매핑'하는 범위 조인은 Sort-Merge의 전형적 영역이다. 또한 정렬 결과를 그대로 ORDER BY나 GROUP BY에 재활용할 수 있어, 후속 연산이 정렬을 요구할 때 추가 이득을 준다.

한계는 정렬 비용이다. 두 집합이 모두 크고 정렬되어 있지 않다면, 두 번의 대규모 정렬(필요 시 디스크를 쓰는 외부 정렬)이 선행되어 Hash Join보다 느려질 수 있다. 과거에는 Hash Join이 표준화되기 전까지 대량 조인의 기본이었으나, 오늘날 동등 조인 대량 처리의 자리는 대체로 Hash Join이 가져갔고, Sort-Merge는 '이미 정렬됨' 또는 '부등호 조인'이라는 조건에서 선택된다.

정렬 단계에서 메모리가 부족하면 외부 정렬(external sort) 로 전환되어, 중간 결과를 임시 디스크에 여러 런(run)으로 나눠 쓰고 다시 병합한다. 이 디스크 쓰기·읽기가 추가되면 정렬 비용이 더욱 커지므로, Sort-Merge를 쓸 때도 정렬 작업 영역(예: Oracle의 SORT_AREA/PGA)의 크기가 성능을 좌우한다. 반대로 조인 키에 이미 B+Tree 인덱스가 있어 인덱스 풀스캔만으로 정렬 순서가 보장되면, 정렬 단계를 통째로 생략해 병합 순회만으로 끝낼 수 있다. 이처럼 '정렬을 공짜로 얻을 수 있는가'가 Sort-Merge 채택의 실질적 판단 기준이 된다.

구분	Nested Loop	Sort-Merge	Hash Join
기본 전략	바깥 행마다 안쪽 탐색	양쪽 정렬 후 병합 순회	빌드 해시 테이블 + 프로브
유리한 상황	소량 집합·인덱스 존재	이미 정렬됨·부등호 조인	대량 동등 조인·비정렬
조인 조건	동등·부등호 모두	동등·부등호 모두	동등(=) 전용
인덱스 의존	높음(안쪽 인덱스 필수급)	낮음(정렬이 대신함)	없음(해시가 대신함)
메모리 민감도	낮음	중간(정렬 영역)	높음(해시 영역)
부분 범위 처리	우수(조기 반환)	불리(정렬 완료 필요)	불리(빌드 완료 필요)
대표 비용	바깥건수 × 안쪽탐색	N log N + M log M	N + M(메모리 충분 시)

5. Hash Join(해시 조인)

Hash Join은 작은 쪽 테이블(build input)으로 조인 키의 해시 테이블을 메모리에 만든 뒤, 큰 쪽 테이블(probe input)을 한 행씩 읽으며 같은 해시 버킷을 조회해 짝을 찾는 방식이다. 핵심은 해시 테이블 조회가 평균 상수 시간(O(1))이라는 점으로, 이 덕분에 큰 테이블을 단 한 번만 순차 스캔하면서 각 행의 짝을 즉시 찾을 수 있다. 전체 비용은 메모리가 충분하면 대략 두 테이블을 한 번씩 읽는 O(N + M)에 수렴한다.

실제 산업 사례로, 대형 전자상거래의 일일 매출 집계 배치를 들 수 있다. 하루 수천만 건의 주문 로그(fact)를 상품·회원·지역 차원 테이블(dimension)과 결합해 집계하는 전형적 스타 스키마 질의에서, 차원 테이블은 작고 fact는 거대하므로 각 차원으로 해시 테이블을 만들고 fact를 한 번 훑는 Hash Join이 수십 초 내에 처리를 끝낸다. 같은 작업을 Nested Loop로 하면 수천만 건에 대해 차원 인덱스 탐색을 반복해 몇 시간이 걸릴 수 있다. 데이터 웨어하우스·BI 집계가 사실상 Hash Join 위에 서 있다고 해도 과언이 아닌 이유다.

동작은 빌드(Build) 와 프로브(Probe) 두 단계로 나뉜다. 빌드 단계에서 옵티마이저는 통계를 보고 더 작은 집합을 골라, 그 조인 키에 해시 함수를 적용해 버킷별로 적재한 해시 테이블을 만든다. 프로브 단계에서는 큰 집합의 각 행에 같은 해시 함수를 적용해 해당 버킷을 찾고, 버킷 안에서 실제 키 일치를 확인해 결과를 출력한다. 빌드 집합이 작을수록 해시 테이블이 메모리에 통째로 들어가 가장 빠르며, 그래서 '작은 테이블을 빌드로 삼는' 선택이 성능을 좌우한다.

Hash Join의 결정적 강점은 대량 데이터의 동등 조인에서 인덱스 없이도 빠르다는 점이다. Nested Loop가 바깥 건수만큼 랜덤 I/O를 반복하는 것과 달리, Hash Join은 양쪽을 순차 스캔(sequential I/O)만 하므로 대용량 배치·DW 집계·ETL에서 압도적으로 유리하다. 예컨대 매출 1억 건과 상품 10만 건을 상품코드로 결합하는 분석 질의는, 상품 10만 건으로 해시 테이블을 만들고 매출 1억 건을 한 번 훑어 끝낸다 — 인덱스가 전혀 없어도 된다.

약점은 메모리와 동등 조인 전용이라는 제약이다. 빌드 집합이 가용 메모리(해시 영역)보다 크면 해시 테이블이 메모리에 다 들어가지 않아, 데이터를 여러 파티션으로 나눠 디스크에 내렸다가 다시 읽는 Grace Hash Join / 하이브리드 해시 로 전환된다. 이때 디스크 I/O가 늘어 성능이 떨어지므로, 해시 영역(예: Oracle PGA, PostgreSQL work_mem) 크기 설정이 중요하다. 또한 해시는 값의 일치만 판별하므로 = 조건에서만 쓸 수 있고, >·BETWEEN 같은 부등호 조인에는 적용할 수 없어 그 경우 Sort-Merge나 Nested Loop로 넘어간다. 데이터 편향(skew)이 심해 특정 버킷에 값이 몰리면 해시 충돌이 늘어 성능이 저하되는 점도 유의해야 한다.

Grace Hash Join의 동작을 조금 더 풀면, 빌드·프로브 양쪽을 같은 해시 함수로 N개 파티션으로 분할해 디스크에 저장한 뒤, 같은 번호의 파티션 쌍끼리만 다시 읽어 조인한다. 짝이 될 수 있는 행은 반드시 같은 해시 파티션에 들어가므로, 메모리에 한 번에 다 올리지 못하는 대용량도 '파티션 단위로 쪼개 메모리 내 조인'을 반복해 처리할 수 있다. 하이브리드 해시는 여기에 더해 첫 파티션은 디스크에 내리지 않고 메모리에 유지해, 가능한 범위에서 디스크 왕복을 줄이는 절충이다. 이런 장치 덕분에 Hash Join은 '메모리가 충분하면 매우 빠르고, 부족해도 완만하게 느려지는' 안정적 확장성을 갖는다 — 이것이 대용량 DW가 조인의 기본 무기로 Hash Join을 채택하는 이유다.

6. 비교와 선택 기준: 차이가 생기는 이유

세 알고리즘의 우열이 상황에 따라 뒤집히는 근본 원인은 '짝 찾기의 지배적 비용이 무엇인가'가 데이터 규모·정렬·인덱스·메모리에 따라 달라지기 때문이다. 소량 결과를 뽑는 OLTP 질의에서는 '얼마나 적게 건드리느냐'가 중요하므로, 바깥 소량 집합만 처리하고 조기 반환하는 Nested Loop가 이긴다. 반대로 대량을 전부 결합하는 OLAP·배치 질의에서는 '전체를 몇 번 읽느냐'가 중요하므로, 두 테이블을 한 번씩만 순차 스캔하는 Hash Join이 이긴다. Sort-Merge는 그 사이에서 '이미 정렬되어 정렬 비용이 없거나, 부등호라 해시를 못 쓰는' 틈새를 메운다.

이 관점에서 보면 '어떤 알고리즘이 더 좋은가'라는 질문 자체가 성립하지 않는다. 세 알고리즘은 우열 관계가 아니라 적용 영역이 다른 상보 관계이며, 각자의 전제 조건(인덱스·정렬·메모리)이 충족되는 구간에서만 최선이 된다. 옵티마이저가 하나를 영구 채택하지 않고 질의마다·통계 변화마다 다시 고르는 것, 그리고 적응형 실행이 런타임에 전환까지 하는 것은 바로 이 상보성 때문이다. 엔지니어의 역할은 '최고의 알고리즘을 고르는 것'이 아니라 '각 질의가 올바른 알고리즘 구간에 놓이도록 데이터와 통계를 정돈하는 것'이다.

실무적 함의는 분명하다. 첫째, 인덱스 전략과 조인 알고리즘은 한 몸이다. Nested Loop를 의도한다면 안쪽 조인 키 인덱스가 필수이고, Hash Join을 의도한다면 오히려 인덱스보다 순차 스캔 효율(파티셔닝·압축)이 중요하다. 둘째, 통계 신선도가 알고리즘 선택을 바꾼다. 통계가 오래되어 대량 집합을 소량으로 오판하면 옵티마이저가 Hash Join 대신 Nested Loop를 골라 수 초 질의가 수십 분이 되는 전형적 장애가 발생한다 — 그래서 실행계획이 갑자기 느려지면 가장 먼저 통계와 조인 방식을 확인한다. 셋째, 옵티마이저 힌트(USE_NL, USE_HASH, USE_MERGE 등) 로 알고리즘을 강제할 수 있으나, 이는 통계가 왜곡된 상황의 임시 처방일 뿐 근본 해법은 통계·인덱스·질의 구조 교정이라는 점을 잊지 말아야 한다.

구체적 수치 감각을 더하면, 1,000만 건 ⨝ 100만 건 동등 조인에서 결과가 전체 대부분을 차지할 때 Hash Join은 두 번의 순차 스캔(수 초)으로 끝나지만, 같은 질의를 Nested Loop로 강제하면 1,000만 번의 인덱스 탐색 랜덤 I/O로 수십 분이 걸린다. 반대로 '방금 가입한 고객 10명의 주문'을 찾는 질의에서는 Nested Loop가 10번의 인덱스 탐색(밀리초)으로 끝나지만, Hash Join으로 강제하면 1,000만 건 주문 전체를 스캔해 해시 테이블을 만드느라 수 초가 낭비된다. 같은 두 테이블이라도 '결과의 선택도(selectivity)'가 알고리즘의 우열을 완전히 뒤집는 것이다.

선택의 지침을 한 문장으로 요약하면 이렇다. "선택도가 낮아(결과 소량) 선행 집합을 작게 만들 수 있고 후행에 인덱스가 있으면 Nested Loop, 선택도가 높아(결과 대량) 양쪽을 다 읽어야 하는 동등 조인이면 Hash Join, 한쪽이 이미 정렬되어 있거나 조인 조건이 부등호이면 Sort-Merge." 실무 튜닝에서는 이 지침을 역으로 이용한다 — 즉 '원하는 알고리즘이 나오도록 인덱스·통계·질의 구조를 설계'하는 것이다. 예를 들어 소량 결과 OLTP 질의가 엉뚱하게 Hash Join으로 풀린다면, 선행 집합을 좁히는 조건과 후행 조인 키 인덱스를 보강해 옵티마이저가 Nested Loop를 선택하도록 유도한다. 거꾸로 대량 배치가 Nested Loop로 풀려 느리다면, 통계를 갱신하거나 USE_HASH 힌트로 Hash Join을 유도한다. 이처럼 알고리즘의 원리를 알면 '왜 느린지'를 진단하고 '어떻게 유도할지'를 설계할 수 있게 된다.

7. 심화: 현대 DBMS의 조인 처리 진화와 실무 적용

조인 알고리즘의 기본 세 가지는 수십 년간 변하지 않았지만, 그 위에 쌓인 최적화 기법은 꾸준히 발전해 왔다. 실무에서 마주치는 최신 동향을 세 가지로 정리한다.

이 세 흐름은 모두 '조인 비용을 더 줄이려는' 공통 목표 아래 서로 다른 지점을 공략한다. 적응형 조인은 선택의 정확성을, 병렬·분산 조인은 처리의 확장성을, 조인 제거·사전 집계는 작업량 자체의 절감을 겨냥한다. 기술사 시험과 실무 모두에서 이 세 축을 함께 엮어 '왜 느린가 → 어떤 수준(선택·확장·제거)에서 손댈 것인가'를 설계할 수 있어야 한다.

첫째, 적응형 조인(Adaptive Join) 이다. Oracle 12c의 Adaptive Plan, SQL Server의 Adaptive Join처럼, 옵티마이저가 실행 전에 하나의 방식으로 확정하지 않고 실행 중 실제 처리 행 수를 보고 Nested Loop와 Hash Join 사이를 동적으로 전환한다. 이는 통계 오차로 인한 '추정 카디널리티와 실제의 괴리' 문제를 런타임에 보정하려는 시도로, 통계가 다소 부정확해도 심각한 오판을 막는 안전장치 역할을 한다. 같은 맥락에서 PostgreSQL은 실행 중 수집한 통계로 다음 실행을 개선하는 방향을 넓혀 왔다.

둘째, 병렬 조인과 분산 조인 이다. 대용량 분석 환경(MPP DW, Spark, Presto/Trino 등)에서는 해시 조인을 여러 노드로 쪼개 병렬 수행한다. 이때 조인 키로 양쪽을 재분배하는 셔플 조인(shuffle/repartition join) 과, 작은 테이블을 모든 노드에 복제해 셔플을 없애는 브로드캐스트 조인(broadcast join) 의 선택이 분산 성능을 좌우한다. 한쪽이 충분히 작으면 브로드캐스트가 네트워크 셔플 비용을 없애 압도적으로 빠른데, 이는 단일 노드 Hash Join의 '작은 쪽을 빌드로' 원리가 분산 환경으로 확장된 형태다. 데이터 편향(skew)이 심한 조인 키에서는 특정 노드에 작업이 몰리는 'skew join' 문제가 생겨, 핫키를 별도 처리하는 skew 최적화가 적용된다.

아울러 조인 연산의 종류(semi/anti/outer join)에 따른 전용 처리도 중요하다. EXISTS·IN은 짝이 하나만 있으면 되는 세미 조인(semi join) 으로, 첫 매칭에서 탐색을 멈춰 비용을 줄인다. NOT EXISTS는 안티 조인(anti join) 으로 역의 논리를 쓰고, OUTER JOIN은 짝이 없는 행도 NULL로 채워 보존해야 하므로 알고리즘 구현이 조금씩 달라진다. 옵티마이저는 이들을 서브쿼리 평탄화(unnesting)로 일반 조인처럼 바꿔 세 알고리즘을 재사용하되, 세미/안티의 '조기 종료' 특성을 살려 추가 최적화한다. 같은 Hash Join이라도 세미 조인이면 빌드 측 매칭 여부만 표시하고 멈추는 식이다.

셋째, 조인 제거와 사전 집계 다. 옵티마이저는 외래키-기본키 무결성이 보장되면 결과에 영향이 없는 조인을 아예 제거(join elimination)하고, 자주 쓰는 조인 결과를 구체화 뷰(Materialized View) 로 미리 계산해 두는 전략이 DW에서 표준이다. 또한 컬럼 기반 저장·벡터화 실행 엔진과 결합해, 해시 조인을 SIMD 단위로 처리해 CPU 효율을 높이는 하드웨어 친화적 구현도 보편화되었다. 실무에서는 실행계획(EXPLAIN, EXPLAIN ANALYZE, Oracle DBMS_XPLAN)에서 어떤 조인 방식이 선택됐는지와 추정 대비 실제 행 수의 차이를 반드시 확인하는 것이 튜닝의 출발점이다.

8. 고려사항 및 시사점

조인 알고리즘은 단순한 이론이 아니라 성능·자원·운영 안정성을 가르는 실무 핵심이므로, 기술사 관점에서 다음을 종합적으로 고려해야 한다. 특히 조인은 '설계 시점에 결정되는 인덱스·파티션·통계'와 '실행 시점에 선택되는 알고리즘'이 서로를 제약하는 관계임을 염두에 두고, 물리 설계 단계부터 예상 질의 패턴에 맞는 조인 전략을 선반영하는 것이 바람직하다.

• 적용 전략 — 질의 성격에 맞춘 알고리즘 유도: OLTP(소량·고동시성)는 Nested Loop와 인덱스 설계에, OLAP·배치(대량·집계)는 Hash Join과 순차 스캔 효율(파티셔닝·압축·병렬도)에 각각 최적화한다. 하나의 DBMS를 OLTP/OLAP가 혼재된 워크로드로 쓸 때는 각 질의군의 특성을 분리해 인덱스·통계·메모리 전략을 차등 적용해야 한다.

• 트레이드오프 — 메모리 vs I/O, 응답성 vs 처리량: Hash Join은 메모리를 써서 I/O를 줄이는 교환이며, 해시 영역이 부족하면 디스크 기반으로 전락해 이득이 사라진다. Nested Loop는 메모리에 둔감하지만 대량에서 랜덤 I/O가 폭증한다. 또 Nested Loop는 첫 결과를 빨리 주는(응답성) 반면 Hash/Sort-Merge는 전체를 다 처리해야(처리량) 하므로, SLA가 '첫 응답 시간'인지 '전체 완료 시간'인지에 따라 선택이 달라진다.

• 운영 안정성 — 통계 관리와 계획 안정화: 조인 방식 오판의 90%는 '오래되거나 부정확한 통계'에서 비롯되므로, 정기·자동 통계 수집과 히스토그램(편향 분포 표현)이 선행되어야 한다. 중요 질의에는 SQL Plan Baseline·Plan 고정, 힌트, 결과 캐시 등으로 계획이 갑자기 바뀌어 장애가 나는 것을 막는 '계획 안정화(plan stability)' 장치를 둔다.

• 진단 역량 — 실행계획 독해: 장애 대응의 출발점은 EXPLAIN/EXPLAIN ANALYZE로 '옵티마이저가 어떤 조인 방식을 택했고, 추정 행 수(estimated rows)와 실제 행 수(actual rows)가 얼마나 벌어졌는가'를 읽는 것이다. 둘의 괴리가 크면 통계·카디널리티 추정 오류를 의심하고, 느린 단계가 Nested Loop의 과다 반복인지 Hash Join의 디스크 스필(spill)인지 Sort-Merge의 외부 정렬인지를 식별해 원인별로 처방해야 한다.

• 전망과 연계 기술: 적응형 실행과 벡터화·GPU 가속, 분산 질의 엔진의 보급으로 조인 처리는 '정적 선택'에서 '런타임 적응'으로 이동하고 있다. 조인 알고리즘 지식은 [[db-optimizer]](옵티마이저 RBO·CBO), [[btree-bplus-index]](인덱스 구조), [[db-tuning]](DB 튜닝), [[materialized-view]](구체화 뷰), [[columnar-storage]](컬럼 기반 저장)와 긴밀히 연계되며, 이들을 하나의 성능 체계로 통합해 이해·설계하는 것이 기술사에게 요구되는 역량이다.

참고자료

• Oracle Database SQL Tuning Guide — Joins, https://docs.oracle.com/en/database/oracle/oracle-database/19/tgsql/joins.html
• PostgreSQL Documentation — Planner/Optimizer, https://www.postgresql.org/docs/current/planner-optimizer.html
• Microsoft SQL Server — Adaptive Query Processing, https://learn.microsoft.com/en-us/sql/relational-databases/performance/intelligent-query-processing

---

한 줄 요약: 조인 알고리즘은 두 테이블의 짝을 찾는 물리적 전략으로, 소량·인덱스엔 Nested Loop, 이미 정렬됨·부등호엔 Sort-Merge, 대량 동등 조인엔 Hash Join이 유리하며, 그 선택의 품질은 결국 정확한 통계와 적절한 인덱스·메모리 설계에 달려 있다.