Database ‐ Join Optimization - thought-corner/backend-roadmap GitHub Wiki

조인의 동작 원리 - NLJ

for each row in 바깥쪽_테이블 { -- 외부 루프
    for each row in 안쪽_테이블 { -- 내부 루프
        if (조인 조건 일치) {
            결과 추가
        }
    }
}

• MySQL은 인덱스를 사용할 수 있는 조인을 기본적으로 이 중첩 루프 방식으로 실행한다. 테이블이 N개가 될 때마다 루프가 중첩되는 깊이가 달라질뿐 기본 구조는 같다.

드라이빙 테이블과 드리븐 테이블

• 드라이빙 테이블(Driving Table) : 외부 루프를 담당하는 테이블이다. 조인의 시작점이 된다.
• 드리븐 테이블(Driven Table) : 내부 루프를 담당하는 테이블이다. 드라이빙 테이블의 각 행마다 반복적으로 접근되는 테이블이다.
• 성능 최적화를 위해서라면 트라이빙 테이블의 행 수를 줄이는 것이 매우 중요하다.

NLJ와 인덱스 - Driven Table

• 드리븐 테이블 탐색은 시작할 때마다 비용이 든다. 왜냐하면 인덱스 탐색 한 번은 루트에서 리프까지 내려가는 작업이기 때문이다.
• 결국 같은 양을 읽어도 루프 횟수가 큰 쪽이 더 느리다. 드리븐에서 가져오는 행이 늘어나는 것은 상대적으로 싸다. 그래서 조인 튜닝의 1순위는 항상 드라이빙 테이블 결과를 줄이는 것이다.
• 조인 쿼리가 느릴 때 가장 먼저 확인할 것은 드라이빙 테이블의 EXPLAIN 실행 계획이다. 드리븐 테이블의 인덱스를 아무리 정비해도 드라이빙 결과를 줄이지 못하면 루프 횟수 자체는 줄지 않는다. 드라이빙 테이블의 숫자를 줄이는 것이 튜닝의 출발점이 된다.
• 일반적으로 사용하는 NLJ의 성능 공식은 드라이빙 결과 건수(루프 횟수) x 드리븐 테이블 1회 탐색 비용이다.
  • 드라이빙 테이블의 WHERE 조건과 인덱스 루프 횟수를 줄인다.
  • 드리븐 테이블의 조인 조건 인덱스가 1회 탐색 비용을 줄인다.

해시 조인 - 인덱스가 없을 때

• 해시 탐색은 키를 해시 함수에 넣으면 위치가 한 번에 계산된다. 따라서 행 수가 아무리 많아도 탐색 비용은 거의 일정하다.
• 해시 테이블은 키-값 쌍을 저장하는 자료구조다. 키를 해시 함수에 넣으면 숫자가 하나 계산되는데, 그 숫자가 곧 데이터가 저장될 위치다. 저장할 때도 찾을 때도 같은 계산을 하므로 데이터가 5건이든 500만 건이든 키만 있다면 위치를 O(1) 시간 복잡도로 한 번에 찾아간다.
• 대신 해시 테이블은 데이터가 정렬되어 보관되지 않는다. 따라서 데이터가 계산된 위치에 흩어져 저장되므로, 키가 정확히 일치하는 등호 탐색만 가능하다. 범위 검색과 정렬까지 처리해야 하는 인덱스가 해시가 아니라 B+Tree를 사용하는 이유다.

해시 조인의 조건과 한계

• 인덱스가 있으면 NLJ가 우선이다. 드리븐 테이블에 인덱스가 있으면 NLJ는 필요한 소수 행만 정확히 탐색한다. 옵티마이저는 사용할 인덱스가 있으면 NLJ를, 없으면 해시 조인을 자동으로 선택한다.
• 해시 테이블은 메모리에 만든다. 사용할 수 있는 메모리 최대 크기가 join_buffer_size다. 기본값 262,144바이트(256KB)다. 빌드 입력이 이 크기를 초과하면 MySQL은 디스크의 임시 파일로 나눠서 처리하고, 성능이 상당히 저하된다. 빌드 입력이 작을수록 해시 조인이 유리한 이유이기도 하다.

비교 항목	중첩 루프 조인 (NLJ)	해시 조인 (Hash Join)
기본 동작	드라이빙 행마다 드리븐 탐색	빌드(해시 테이블) + 프로브(1회 스캔)
드리븐 인덱스	필수 (생명줄)	불필요
인덱스 있을 때	매우 효율적 (소수 행만)	한쪽 전체를 읽으므로 불리
인덱스 없을 때	매 루프 풀 스캔 (재앙)	효율적
메모리	거의 안 씀	join_buffer_size 의존, 초과 시 디스크
옵티마이저 선택	인덱스 있으면 우선	인덱스 없는 조인에서 자동

• 드라이빙 테이블은 SQL에 쓴 순서대로 정해지는 것이 아니다. 옵티마이저가 비용을 계산해서 직접 고르는 것이다.

• WHERE 조건으로 결과가 가장 적게 나오는 테이블이 드라이빙 테이블이 되어야 한다. 옵티마이저는 이 통계를 기반으로 판단을 자동으로 해주고 있었던 것이다.

옵티마이저를 맹목적으로 신뢰하라는 말이 아니다.

• 대부분 조인 순서를 옵티마이저에게 맡기면 되지만 옵티마이저의 판단 근거는 통계 정보다. 통계는 추정치고, 데이터가 대량으로 변경된 직후나 분포가 심하게 편중된 상황에서는 추정이 빗나갈 수 있다.
• 추정이 빗나가면 옵티마이저가 드라이빙 테이블을 잘못 선택할 수 있기에 만약 옵티마이저가 이상한 순서를 골랐다고 의심이 될 경우 대응 순서를 다음과 같이 정리할 수 있다.
  • ANALYZE TABLE로 통계를 갱신한다. 가장 흔한 원인이 낡은 통계다.
  • 히스토그램을 검토한다. 편중된 컬럼이 원인이라면 히스토그램이 해결책이다.
  • 드라이빙 후보 테이블의 WHERE 조건에 인덱스를 보강한다. 옵티마이저가 좋은 순서를 고를 수 있는 재료를 준다.
  • 힌트는 최후의 수단이다. JOIN_FIXED_ORDER()과 같은 순서 강제 힌트는 그때그때의 데이터 분포에 대한 판단을 코드에 고정시켜 버린다. 지금은 옳은 순서가 될 수 있지만 1년 뒤에는 틀린 순서가 될 수 있다.