조인 알고리즘
드라이빙 테이블, 드리븐 테이블
드라이빙 테이블(Driving Table)과 드리븐 테이블(Driven Table)을 간단하게 설명하면 드라이빙 테이블은 조인하기 위해 먼저 접근한 테이블이고 드리븐 테이블은 조인을 위해 드라이빙 테이블 이후 접근한 테이블을 의미한다.
이때 드라이빙 테이블의 데이터 수가 드리븐 테이블의 데이터 수보다 많다면 성능이 떨어지기 때문에 드라이빙 테이블을 무엇으로 선택할지 판단하는 것은 중요하다.
중첩 루프 조인
중첩 루프 조인(Nested Loop Join)은 드라이빙 테이블 1건 당 드리븐 테이블을 반복해서 조회하여 공통된 데이터를 출력한다.
예를 들어서 인덱스가 없다고 가정한다면 최악의 경우 드라이빙 테이블에서 전체 조회해야하고, 드리븐 테이블에서도 전체 조회 후 공통 데이터를 가져오게 된다.
만약 인덱스가 있다면 앞서 랜덤 엑세스가 일어났던 것과는 달리 순차 정렬을 이용해서 조회하기 때문에 조회 성능이 훨씬 좋아진다.
블록 중첩 루프 조인
앞서 중첩 루프 조인은 인덱스가 없다면 랜덤 엑세스를 통해 무척 비효율적으로 조회한다. 블록 중첩 루프 조인(Block Nested Loop Join)은 드라이빙 테이블에 조인 버퍼 개념을 도입해서 조인 성능을 높인다.
예를 들어 드라이빙 테이블에서 먼저 해당되는 데이터를 찾은 후 조인 버퍼에 쌓아둔다. 그리고 드리븐 테이블과 조인 버퍼를 한번의 테이블 풀 스캔으로 조인해서 조인 성능을 높이는 방식이다.
배치 키 엑세스 조인
배치 키 엑세스 조인(Batched Key Access Join)은 앞서 블록 중첩 조인의 조인 버퍼 개념을 그대로 사용한다. 그리고 드리븐 테이블에 필요한 데이터를 미리 예측해서 버퍼에 쌓아두는 랜덤 버퍼를 사용한다. 이런 기능을 다중 범위 읽기라고 한다.
예를 들어 드라이빙 테이블에서 먼저 데이터를 찾아서 조인 버퍼에 쌓아둔다. 그리고 드리븐 테이블의 인덱스를 기반으로 필요한 데이터를 예측해서 랜덤 버퍼에 쌓아둔다. 이후 조인 조건절로 두 버퍼를 비교한다. 만약 동일한 데이터가 있다면 최종적으로 드리븐 테이블의 데이터에 접근해서 조인 후 결과를 조회하게 된다.
해시 조인
해시 조인은 MySQL 8.0.18버전부터 지원하는 조인 방식이다. 해시 조인은 앞서 선후관계(드라이빙 테이블, 드리븐 테이블)를 사용했던 중첩 루프 조인 방식과는 달리 조인에 참여하는 테이블의 해시 값을 내부에 저장해서 해시값을 비교하는 과정을 통해 조인이 이뤄진다.
예를 들어 조인에 참여하는 각 테이블은 데이터마다 해시값을 가지게 된다. 이후 데이터마다 해시값을 비교해서 동일한 해시값일 때 조인 버퍼에 저장하게 된다.
해시 조인은 해시의 특성상 동등 비교 연산만 가능하고 인덱스를 이용한 순차 비교 연산은 활용하기 어렵다.
