조인 알고리즘: 중첩 루프, 해시, 병합

INNER JOIN을 문법으로 이미 알고 계실 것입니다. 시니어 수준의 면접에서는 면접관이 데이터베이스가 조인을 물리적으로 실행하는 방식을 질문합니다. 조인에는 세 가지 알고리즘이 있습니다:

• 중첩 루프 조인
• 해시 조인
• 병합 조인(정렬-병합)

논리적 조인 유형(INNER, LEFT)은 알고리즘과 별개입니다. 플래너는 테이블 크기, 인덱스, 정렬 순서를 기준으로 알고리즘을 선택합니다. 각 알고리즘이 언제 유리한지 아는 것이 이 강의의 핵심입니다.

중첩 루프는 가장 단순한 방식입니다. 외부 테이블의 각 행마다 내부 테이블을 스캔하여 일치하는 항목을 찾습니다. 의사 코드로 표현하면 한 루프 안에 다른 루프가 있는 형태입니다.

순진하게 실행하면 O(외부 * 내부)이므로 대규모 테이블에서는 매우 비효율적입니다. 하지만 내부 쪽에 조인 키 인덱스가 있으면 매우 효율적입니다. 각 외부 행마다 내부 테이블 전체를 스캔하는 대신 비용이 적은 인덱스 조회를 실행하기 때문입니다.

따라서 외부 테이블이 작고 내부 조인 열에 인덱스가 있을 때 플래너가 선호하는 방식입니다.

중첩 루프의 특징은 내부 노드에 loops가 표시된다는 점입니다. 예시에 loops=3이 표시된 이유는 외부 쪽에서 3개의 행을 생성하여 내부 인덱스 스캔이 3번 실행되었기 때문입니다.

문제는 외부 쪽이 클 때 발생합니다. 외부에서 200만 개의 행을 생성하면 내부 쪽이 200만 번 실행됩니다. 빠른 0.01ms 조회라도 20초가 걸립니다.

면접에서는 좋은 인덱스가 없는 내부 테이블에 대해 loops가 큰 중첩 루프가 보이면 경고 신호로 지적하십시오. 이것이 느린 쿼리입니다.

해시 조인은 정렬되지 않은 대규모 테이블을 처리하는 데 적합합니다. 두 단계로 실행됩니다:

• 빌드: 더 작은 테이블을 읽어 조인 열을 키로 사용하는 메모리 내 해시 테이블에 적재합니다.
• 탐색: 더 큰 테이블을 스캔하면서 각 행의 조인 키를 해시하고 해시 테이블에서 조회합니다.

각 테이블을 한 번만 읽으므로 대략 O(외부 + 내부)의 시간이 걸립니다. 인덱스나 정렬된 입력이 필요하지 않기 때문에 동등 조건을 사용하는 대규모 분석 조인에서는 해시 조인이 우세합니다.

해시 조인에 관해 반드시 언급해야 할 두 가지가 있습니다:

• 동등 조건을 사용하는 조인에서만 작동합니다(a.id = b.id). a.x < b.y와 같은 범위 조건에는 해시 조인을 사용할 수 없습니다.
• 빌드 쪽은 work_mem에 들어갈 수 있어야 합니다. 들어가지 않으면 포스트그레스가 배치를 디스크에 넘겨 저장합니다(Batches: > 1과 디스크 사용량이 표시됨). 이 경우 조인이 크게 느려집니다.

따라서 빌드 쪽이 매우 큰데 work_mem이 너무 작은 해시 조인은 실제 환경에서 지적해야 할 성능 버그입니다.

병합 조인(정렬-병합)은 두 입력이 모두 조인 키를 기준으로 정렬되어 있어야 합니다. 그런 다음 정렬된 두 목록을 병합하듯 두 입력을 나란히 훑으며 뒤처진 포인터를 전진시킵니다.

입력이 이미 정렬되어 있을 때 효율적입니다. 예를 들어 키 순서의 인덱스에서 바로 나온 입력이라면 정렬 단계가 필요하지 않습니다. 또한 해시 조인과 달리 범위 조인과 부등식 조인도 지원합니다.

입력이 미리 정렬되어 있지 않으면 플래너가 명시적인 Sort 노드를 추가합니다. 이 정렬 비용 때문에 대신 해시 조인이 더 저렴해질 수 있습니다.

각 알고리즘이 언제 유리한지 외워 두십시오:

• 중첩 루프: 외부 테이블이 작고 내부 조인 키에 인덱스가 있을 때 적합합니다. 정렬된 입력이 없는 비동등 조인에서는 유일한 선택지이기도 합니다.
• 해시 조인: 정렬되지 않은 대규모 테이블을 동등 조건으로 조인할 때 적합합니다. 인덱스가 필요하지 않습니다.
• 병합 조인: 두 입력이 키를 기준으로 이미 정렬되어 있을 때(대개 인덱스를 통해) 또는 범위 조인에 적합합니다. 미리 정렬된 매우 큰 집합에서 특히 유리합니다.

플래너는 행 추정치를 바탕으로 각 비용을 추정하고 가장 저렴한 알고리즘을 선택합니다.

리소스 사용량은 크게 다르며 면접관은 이 부분을 파고듭니다:

• 중첩 루프: 메모리를 거의 사용하지 않지만 반복되는 내부 조회가 비용의 대부분을 차지합니다.
• 해시 조인: 해시 테이블에 사용할 메모리가 필요하며 너무 크면 디스크로 넘칩니다.
• 병합 조인: 병합 자체는 저렴하지만 먼저 정렬해야 하면 비용이 큽니다. 정렬에도 work_mem이 사용되며 디스크로 넘칠 수 있습니다.

따라서 work_mem을 늘리면 디스크로 넘쳐 느려진 해시 조인이나 정렬을 메모리 내 작업으로 전환할 수 있습니다. 이는 구체적인 최적화 답변이 됩니다.

전형적인 상황은 개발 환경에서는 빠르던 쿼리가 운영 환경에서 느려지는 경우입니다. 실행 계획에 loops=3000000인 중첩 루프가 표시됩니다.

플래너가 외부 행 수를 과소 추정했습니다. 오래된 통계에는 3개 행이라고 표시되었지만 실제로는 300만 개였기 때문에 중첩 루프를 선택한 것입니다. 정확한 통계가 있었다면 해시 조인을 선택했을 것입니다.

면접에서는 다음과 같이 답하면 됩니다: 추정치가 정확해지도록 ANALYZE를 실행하면 플래너가 해시 조인으로 전환하고 쿼리 속도가 크게 향상됩니다.

일반적으로 알고리즘을 강제로 지정해서는 안 되지만, 비교를 위해 테스트할 때는 지정할 수 있습니다. 포스트그레스는 방식별 토글을 제공합니다:

SET enable_nestloop = off;와 같이 enable_hashjoin 및 enable_mergejoin에도 사용할 수 있습니다. 하나를 끄고 EXPLAIN ANALYZE를 다시 실행하여 대안이 실제로 더 빠른지 확인하십시오.

근본적인 해결책은 최신 통계, 적절한 인덱스, 충분한 work_mem, 선택도가 높은 조건식입니다. 강제 지정은 진단 목적으로만 사용해야 합니다.

식별자를 기준으로 대규모 팩트 테이블과 차원 테이블을 조인하는 분석 작업에 적용해 보겠습니다:

• 차원 테이블이 메모리에 들어가면 대개 가장 좋은 선택인 해시 조인을 예상할 수 있습니다.
• 두 테이블이 인덱스에서 정렬된 상태로 도착하면 병합 조인으로 해시 테이블 빌드 단계를 피할 수 있습니다.
• 이 상황에서 중첩 루프가 선택되었다면 위험 신호입니다. 보통 잘못된 추정이 원인입니다.

플래너가 어떤 알고리즘을 선택했는지 읽고 그 선택이 적절했는지 판단하는 능력이 바로 이런 질문에서 평가하는 시니어 수준의 판단력입니다.

정렬되지 않은 대규모 테이블 두 개를 동등 조건 a.id = b.id으로 조인하고, 어느 테이블에도 유용한 인덱스가 없으며 통계가 정확하다고 하겠습니다. 플래너는 어떤 조인 알고리즘을 선택할 가능성이 가장 높을까요?

세 가지 조인 알고리즘:

• 중첩 루프: 외부 행마다 내부를 조회합니다. 외부 테이블이 작고 내부 키에 인덱스가 있으면 뛰어나지만 loops가 매우 크면 위험합니다.
• 해시 조인: 빌드 후 탐색합니다. 정렬되지 않은 대규모 동등 조인에 가장 적합하지만 동등 조건에서만 사용할 수 있고 work_mem의 제약을 받습니다.
• 병합 조인: 정렬된 입력을 나란히 훑습니다. 데이터가 이미 정렬되어 있거나 범위 조인일 때 이상적입니다.

플래너는 비용과 통계를 기준으로 선택합니다. 루프 수가 매우 큰 예상 밖의 중첩 루프는 거의 항상 잘못된 행 추정이 원인입니다. 통계를 수정하십시오.