해시 조인

Hash Join

• MySQL 8.0.18 버전부터 추가로 지원되었다.
  • MySQL 8.0.17 버전까지는 해시 조인 기능이 없었기 때문에, 조인 조건이 좋지 않은 경우 블록 네스티드 루프 조인(Block Nested Loop) 알고리즘을 사용했다.
• MySQL 8.0.18과 8.0.19 버전에서는 동등 조인(Equi-Join)을 위해서는 해시 조인을 사용하고, 안티 조인이나 세미 조인을 위해서는 블록 네스티드 루프 조인을 사용했다.
• MySQL 8.0.20 버전부터는 네스티드 루프 조인을 사용할 수 없는 경우에는 항상 해시 조인이 사용되도록 바뀌었다.
  • block_nested_loop 옵티마이저 스위치 옵션 또는 BNL, NO_BNL과 같은 힌트들도 해시 조인을 유도하는 목적으로 사용된다.

해시 조인의 오해와 진실

• 많은 사용자는 기존의 네스티드 루프 조인(Nested Loop Join)보다 해시 조인이 빠르다고 생각한다.
• 네스티드 루프 조인은 최고 응답 속도(Best Response-time) 전략에 적합하고, 해시 쿼리는 최고 스르풋(Best Througjpuut) 전략에 적합하다.
  • 일반적인 웹 서비스는 온라인 트랜잭션(OLTP) 서비스이기 때문에 응답 속도가 더 중요하고
  • 분석과 같은 서비스는 전체적으로 처리 소요 시간이 중요하기 때문에 전체 스루풋이 더 중요하다.
• MySQL 서버는 범용 RDBMS이며, 여기서 범용은 온라인 트랜잭션 처리를 위한 데이터베이스 서버를 지칭하는 것이다.
  • 응답 속도에 집중해서 최적화할 것이다.
• MySQL 서버는 주로 다음 경우에 대해서만 해시 조인 알고리즘을 사용하도록 설계되어 있다.
  • 조인 조건의 칼럼이 인덱스가 없거나
  • 조인 대상 테이블 중 일부의 레코드 건수가 매우 적은 경우 등
• MySQL 서버의 해시 조인 최적화는 네스티드 루프 조인이 사용되기에 적합하지 않은 경우를 위한 차선책(Fallback strategy) 같은 기능으로 생각하는 것이 좋다.
  • 해시 조인이 빠르다고 하니까 강제로 해시 조인으로 실행 계획을 유도하는 것은 좋지 않다.

해시 조인의 최적화 방식

• 실행 계획에서 Extra 칼럼에 “hash join” 키워드가 표시된다.
  • MySQL 옵티마이저가 해시 조인으로 쿼리를 처리했다는 의미이다.
• 일반적으로 해시 조인은 빌드 단계(Build-phase)와 프로브 단계(Probe-phase)로 나뉘어 처리된다.
  • EXPLAIN FORMAT=TREE 명령 또는 EXPLAIN ANALYZE 명령을 사용하면 어느 테이블이 빌드 테이블이고 프로브 테이블인지 조금 더 쉽게 구분할 수 있다.

빌드 단계

• 조인 대상 테이블 중에서 레코드 건수가 적어서 해시 테이블로 만들기에 용이한 테이블을 골라서 메모리에 해시 테이블을 생성(빌드)하는 작업을 수행
• 빌드 단계에서 해시 테이블을 만들 때 사용되는 원본 테이블을 빌드 테이블이라고도 한다.

프로브 단계

• 나머지 테이블의 레코드를 읽어서 해시 테이블의 일치 레코드를 찾는 과정을 의미
• 프로브 단계에서 읽는 나머지 테이블을 프로브 테이블이라고도 한다.

해시 조인의 과정

메모리에서 모두 처리 가능한 경우

1. MySQL 옵티마이저는 해시 조인을 위해 빌드 테이블의 레코드를 읽어서 메모리에 해시 테이블을 생성한다.
   • MySQL 서버는 해시 테이블을 메모리에 저장할 때 join_buffer_size 시스템 변수로 크기를 조절할 수 있는 조인 버퍼를 사용한다. (기본 크기: 256KB)
2. 프로브 테이블로 선택된 테이블을 스캔하면서 메모리에 생성된 해시 테이블에서 레코드를 찾아서 결과를 사용자에게 반환한다.

해시 테이블이 조인 버퍼 메모리보다 큰 경우

• 해시 테이블의 레코드 건수가 많아서 조인 버퍼의 공간이 부족한 경우 다음 과정을 거친다.
  • 빌드 테이블과 프로브 테이블을 적당한 크기(하나의 청크가 조인 버퍼보다 작도록)의 청크로 분리
  • 청크별로 기존 해시 조인과 동일한 방식으로 처리
• 만들어질 해시 테이블이 설정된 메모리 크기(join_buffer_size )보다 큰지 알 수 없다면 처리 과정이 조금 복잡해진다.
  • 빌드 테이블로 선택된 테이블을 읽으면서 메모리의 해시 테이블을 준비하다가, 지정된 메모리 크기를 넘어서면 테이블의 나머지 레코드를 디스크에 정크로 구분해서 저장한다.
  • MySQL 서버는 프로브 테이블의 값으로 메모리의 해시 테이블을 검색해서 1차 조인 결과를 생성한다.
  • 동시에 프로프 테이블에서 읽은 레코드를 디스크에 청크로 구분해서 저장한다.
    • 디스크에는 2개의 그룹(빌드 테이블 청크, 프로브 테이블 청크)으로 구분된 청크 목록이 표현된다.
  • 1차 조인이 완료되면 MySQL 서버는 디스크에 저장된 빌드 테이블 청크에서 첫 번째 청크를 읽어서 다시 메모리 해시 테이블을 구축한다.
  • MySQL 서버는 프로브 테이블 청크에서 첫 번째 청크를 읽으면서 새로 구축한 메모리 해시 테이블과 조인을 수행해 2차 결과를 가져온다.
  • 디스크에 저장된 청크 개수만큼 이 과정을 반복 처리해서 완성된 조인 결과를 만들어낸다.

해시 조인 알고리즘

• MySQL 서버는 청크 단위로 조인을 수행하기 위해 2차 해시 함수를 이용해 빌드 테이블과 프로브 테이블을 동일 개수의 청크로 쪼개어 디스크로 저장한다.
  • 여기서 2차 해시 함수란 특정 해시 알고리즘이 아니라, 해시 조인을 위한 해시 키 생성용 해시 함수와는 다른 해시 함수를 사용해서 청크를 분리한다는 의미다.
  • 실제 청크를 구분하기 위해 사용하는 해시 함수 자체는 크게 중요하지 않다.
• MySQL 옵티마이저는 빌드 테이블의 크기에 따라 다음 해시 조인 알고리즘을 사용한다.
  • 메모리에서 모두 처리 가능한 경우: 클래식 해시 조인(Classic hash join) 알고리즘
  • 해시 테이블이 조인 버퍼 메모리보다 큰 경우: 그레이스 해시 조인(Grace hash join) 알고리즘을 하이브리드(Hybrid)하게 활용
• MySQL 서버의 해시 조인에서 해시 키를 만들 때 xxHash64 해시 함수를 사용하는데, 이 함수는 매우 빠르고 해시된 값의 분포도도 훌륭한 해시 알고리즘이다.

Reference

참고 서적

📔 Real MySQL 8.0