조인 알고리즘 - DB는 세 가지 방법 중 하나를 고른다

개발할 때는 빨랐다. 데이터가 쌓이자 같은 쿼리가 30초씩 걸린다. 인덱스도 그대로고 쿼리도 안 고쳤다.

JOIN을 쓰면 DB가 알아서 두 테이블을 붙여준다. 그런데 “어떻게” 붙일지는 우리가 안 정한다. DB가 고른다. 그리고 잘못 고르면 위 같은 일이 생긴다.

방법은 대체로 셋이다. 셋 다 결과는 같고, 걸리는 시간만 수천 배 다르다.

중첩 반복 (Nested Loop)

가장 단순하다. 한쪽을 한 줄씩 읽으면서, 그때마다 다른 쪽에서 짝을 찾는다.

바깥이 3건이면 안쪽을 3번 뒤진다. 바깥이 100만 건이면 100만 번 뒤진다. 비용이 바깥 건수에 그대로 비례한다.

그래서 이 방식의 운명은 두 가지에 달려 있다. 바깥이 작은가, 그리고 안쪽 탐색이 싼가.

안쪽 조인 키에 인덱스가 있으면 한 번 탐색이 디스크 세 번이다. 바깥이 3건이면 총 9번. 눈 깜짝할 사이다.

인덱스가 없으면? 한 번 탐색이 풀스캔이다. 비교 횟수로 치면 바깥 100만 × 안쪽 100만 = 1조 번. 이게 “개발할 땐 빨랐는데” 사고의 전형이다. 데이터가 적을 땐 100 × 100 = 1만 번이라 티가 안 났을 뿐이다.

해시 (Hash Join)

발상이 다르다. 매번 뒤지지 말고, 아예 찾기 좋은 자료구조를 한 번 만들어두자.

두 단계다. 작은 쪽으로 해시 테이블을 만들고(Build), 큰 쪽을 훑으면서 조회한다(Probe).

핵심은 양쪽을 딱 한 번씩만 읽는다는 것이다. 중첩 반복처럼 같은 테이블을 100만 번 뒤지지 않는다. 그래서 둘 다 크고 인덱스도 없을 때 압도적으로 유리하다.

대신 두 가지 제약이 있다.

등호 조인만 된다. 해시는 “같은 값”을 찾는 도구다. a.id = b.id는 되지만 a.price > b.price는 못 한다. 해시값이 같다는 게 크기 관계를 말해주진 않으니까.

메모리가 필요하다. 해시 테이블이 메모리에 안 들어가면 디스크로 넘친다. 그 순간 성능이 확 꺾인다. 그래서 DB는 작은 쪽을 Build로 고른다. 어느 쪽이 작은지는 통계를 보고 판단한다.

정렬 병합 (Sort-Merge)

세 번째는 양쪽을 줄 세워놓고 나란히 훑는다.

양쪽에 손가락을 하나씩 얹고, 작은 쪽 손가락을 앞으로 민다. 값이 같으면 짝을 만들고 둘 다 민다. 각자 한 번씩만 지나가면 끝난다.

문제는 정렬 비용이다. 100만 건을 정렬하는 건 싸지 않다. 그래서 정렬을 새로 해야 하는 상황이면 대개 밀린다.

그런데 이미 정렬돼 있다면 얘기가 완전히 달라진다. 인덱스는 정렬된 자료구조다. 조인 키가 인덱스 순서와 같으면 정렬을 건너뛰고 바로 병합만 하면 된다. 그때는 셋 중 가장 빠를 수도 있다. 결과를 어차피 그 순서로 내보내야 하는 경우에도 정렬을 한 번에 해결하는 셈이라 유리하다.

그리고 해시가 못 하는 걸 한다. 범위 조인이 된다. 정렬돼 있으니 “이 값보다 큰 것들”을 손가락 위치로 알 수 있다.

셋을 나란히 놓으면

셋 중에 “제일 좋은 것”은 없다. 상황이 정한다. 그리고 그 상황을 판단하는 건 옵티마이저다.

어느 쪽을 바깥에 둘 것인가

세 방식을 설명하면서 계속 “바깥”과 “안쪽”, “작은 쪽으로 해시 테이블”이라고 했다. 그런데 어느 테이블이 바깥이 되는지는 우리가 안 정한다. 이것도 옵티마이저가 고른다.

그리고 이 선택이 성능을 가른다. 중첩 반복에서 바깥은 한 번만 읽지만, 안쪽은 바깥 건수만큼 되풀이해서 뒤진다.

바깥 3건 · 안쪽 100만건   →  안쪽 탐색 3번
바깥 100만건 · 안쪽 3건   →  안쪽 탐색 100만번

같은 두 테이블인데 순서만 뒤집혀도 일의 양이 이만큼 달라진다. 그래서 규칙은 단순하다. 작은 쪽이 바깥, 큰 쪽이 안쪽이다. 그리고 안쪽에는 인덱스가 있어야 한다. 되풀이해서 뒤질 곳이니까.

해시도 같은 문제를 다르게 푼다. 해시 테이블을 어느 쪽으로 만드느냐인데, 작은 쪽으로 만들어야 메모리에 들어간다. 큰 쪽으로 만들면 메모리를 넘쳐 디스크로 밀린다.

그럼 옵티마이저는 어느 쪽이 작은지를 어떻게 아나. 미리 세어둔 통계로 짐작한다. WHERE 조건까지 걸린 뒤의 건수를 짐작해야 하니, 실제로 세보는 게 아니라 추정이다.

여기가 이 글의 급소다. 추정이 틀리면 순서가 뒤집힌다. “이 조건이면 3건쯤”이라고 보고 바깥에 뒀는데 실제로 30만 건이면, 안쪽을 30만 번 뒤지는 계획이 그대로 실행된다. 알고리즘을 잘못 고른 게 아니라 크기를 잘못 짐작한 것이다.

그래서 왜 갑자기 느려지나

여기까지 오면 맨 앞의 사고가 설명된다.

옵티마이저는 통계를 보고 알고리즘을 고른다. “바깥이 몇 건일까”를 통계로 추정하고, 3건이라고 판단하면 중첩 반복을 고른다. 합리적인 선택이다.

그런데 실제로 30만 건이면? 판단은 그대로인데 결과는 재앙이 된다. 30만 번을 뒤지고 있는 것이다.

통계가 낡으면 이런 일이 생긴다. 데이터는 계속 쌓이는데 통계가 옛날 그대로면, 옵티마이저는 옛날 세상을 기준으로 판단한다.

세 가지로 안 끝난다

여기까지 “붙이는 방법 셋”을 봤다. 그런데 실행 계획을 열어보면 셋 말고 다른 이름이 나온다. 붙이는 방식이 아니라 붙이는 목적이 다른 것들이다.

가장 자주 만나는 게 있는지만 확인하는 조인이다.

-- 주문이 있는 사용자를 찾는다
SELECT * FROM users u
 WHERE EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id);

이건 사용자와 주문을 붙여서 내보내려는 게 아니다. “주문이 하나라도 있나”만 알면 된다. 그래서 DB는 첫 번째를 찾는 순간 그 사용자에 대한 탐색을 멈춘다. 100건이 있든 1건이 있든 하는 일이 같다. 계획에는 세미 조인(semi join) 같은 이름으로 나온다.

반대도 있다. 없는 것을 찾는 조인이다.

-- 주문이 한 번도 없는 사용자를 찾는다
SELECT * FROM users u
 WHERE NOT EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id);

이쪽은 하나라도 찾으면 탈락시킨다. 안티 조인(anti join)이라고 부른다.

그리고 한쪽을 다 남기는 조인이 있다. LEFT JOIN이 그것인데, 짝이 없어도 왼쪽 행은 남기고 오른쪽을 NULL로 채운다. 짝을 못 찾았다고 버릴 수 없으니, DB는 그 사실을 기억하면서 붙여야 한다.

여기서 중요한 건 이름을 외우는 게 아니다. 앞에서 본 셋(중첩 반복·해시·정렬 병합)은 어떻게 붙일지이고, 방금 본 것들은 무엇을 남길지다. 축이 다르다. 그래서 실행 계획에는 둘이 겹쳐서 나온다 - “해시 세미 조인”처럼.

실무에서 기억할 것

• 중첩 반복 + 안쪽 인덱스 없음 = 시한폭탄이다. 데이터가 적을 땐 안 터진다.
• 해시 조인이 보이면 메모리를 본다. 디스크로 넘치고 있으면 그때부터 느려진다.
• 정렬 병합이 보이는데 정렬을 새로 하고 있으면 인덱스로 그 정렬을 없앨 수 있는지 본다.
• 알고리즘을 강제로 지정하는 힌트가 대부분의 DBMS에 있지만 마지막 수단이다. 셋 중 뭐가 맞는지는 상황이 정하는데, 힌트는 그 상황이 바뀌어도 안 바뀐다.