[MYSQL] JOIN 알고리즘 용어

다수의 테이블에서 JOIN을 수행할 때 동시에 여러 개의 테이블에 접근할 수 없는 만큼 접근하는 우선순위를 정하게 됨

 

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

학생 정보가 저장된 학생 테이블, 학생가족 정보가 저장된 비상연락망 테이블이 있다고 가정

 

학생의 학번이 1과 100에 해당할 때만 학생정보와 비상연락망 정보를 조회하는 SQL문

SELECT 학생.학번, 학생.이름, 비상연락망.관계, 비강연락망.연락처
 	FROM 학생
 	JOIN 비상연락망
  	ON 학생.학번 = 비상연락망.학번
  WHERE 학생.학번 IN (1, 100)

1. 학생 테이블의 데이터 찾기 - 학생.학번 IN (1, 100)

2. 비상연락망 테이블에서 학번 1과 100 검색

 

드라이빙 테이블(outer table) : 학생 테이블 (먼저 접근)

드리븐 테이블(inner table) : 비상연락망 테이블 (학생 테이블의 검색 결과를 통해 뒤늦게 검색하는 테이블)

 

※ 드라이빙 테이블에서 많은 건수가 반환되면 해당 결과를 가지고 드리븐 테이블에 접근하게 되는 만큼 드라이빙 테이블으로 선정할지는 매우 중요한 문제
가능하면 적은 결과가 반환될 것으로 예상되는 드라이빙 테이블을 선정하고, JOIN 조건절의 열이 인덱스로 설정되도록 구성

---

중첩 루프 조인

중첩 루프 조인(nested loop join, NL JOIN)은 드라이빙 테이블의 데이터 1건당 드리븐 테이블을 반복해 검색하며 최종적으로 양쪽 테이블에 공통된 데이터를 출력

 

1. 극단적인 중첩루프 조인 - 기본 키와 인덱스가 없는 두 테이블이 존재

SELECT 학생.학번, 학생.이름, 비상연락망.관계, 비상연락방.연락처
	FROM 학생
    JOIN 비상연락망
    ON 학생.학번 = 비상연락망.학번
WHERE 학생.학번 IN (1, 100)

 

1. 학번 1을 학생 테이블에서 검색하려고 학생 테이블의 데이터 100건에 모두 접근

2. 학번 1과 동일한 데이터를 가졌는지 비교하기 위해 비상연락망 테이블의 데이터 1,000건에 모두 접근

3. 학번 100을 학생 테이블에서 검색하려고 학생 테이블의 데이터 100건에 모두 접근

4. 학번 100과 동일한 데이터를 가졌는지 비교하기 위해 비상연락망 테이블의 데이터 1,000건에 모두 접근

 

학번 1 데이터(100+1,000) + 학번 100 데이터(100+1,000) = 2,200건의 데이터 접근

* 실제로는 테이블 데이터가 뒤엉켜 있을 가능성이 높음

 

2. 인덱스가 있을 때의 중첩루프 조인 - 학생 테이블에 학번 열로 인덱스가 생성, 비상망 테이블에도 학번 열로 인덱스가 생성

 

학번 1 데이터(1+2) + 학번 100 데이터(1+1) = 6건의 데이터 접근

단, 인덱스의 다음 값을 확인하고 접근 대상이 되는지 여부를 판단하는 것도 실제로는 접근 횟수에 포함되어야 하지만 단순히 학번 1과 100에 해당하는 데이터만 계산

인덱스는 인덱스로 정의된 열 기준으로 순차 정렬되지만, 인덱스를 이용해 테이블의 데이터를 찾아가는 과정에서 임의 접근 방식인 랜덤 액세스(random access)가 발생

따라서, 랜덤 액세스를 줄일 수 있도록 데이터의 액세스 범위를 좁히는 방향으로 인덱스를 설계하고 조건절을 작성해야 함

랜덤 액세스를 유발하는 인덱스는 기본 키가 아닌 비고유 인덱스일 경우 해당

기본 키는 클러스터형 인덱스이므로 키본 키 순서대로 테이블의 데이터가 적재되어 있어 조회 효율이 매우 높음

---

블록 중첩 루프 조인

블록 중첩 루프 조인(block nested loop join, BNL JOIN) - 중첩 루프 조인의 효울성을 높이고자 탄생

 

학생 테이블 - 드라이빙 테이블, 비상연락망 테이블 - 인덱스 없이 생성되어 있다고 가정

 

중첩 루프 조인 수행

1. 학생 인덱스로 학번 1 데이터를 찾은 뒤, 인덱스가 없는 비상연락망 테이블의 전체 데이터에 모두 접근

2. 학생 테이블에서 학번 100 데이터를 찾고, 또다시 비상연락망 테이블은 전체 데이터 1,000건에 접근

 

즉, 인덱스가 없는 드리븐 테이블에 대해 매번 전체 데이터를 비효율적으로 검색해야만 함

드라이빙 테이블에 대해 조인 버퍼(join buffer)라는 개념을 도입하여 JOIN 성능을 향상시킬 수 있음

 

블록 중첩 조인 메커니즘 (BNL JOIN 수행 절차)

1. 드라이빙 테이블인 학생 테이블에서 학번 1과 100에 해당하는 데이터 검색

2. 검색된 데이터를  조인 버퍼에 가득 채워질때까지 적재

3. ⓪ 조인 버퍼와 비상연락망 테이블 데이터 비교

 - ⓪ 조인 버퍼와 ② 데이터를 조인하고, 다시 ⓪ 조인 버퍼와 ③ 데이터를 조인하는 식으로 반복하여 비상연락망 데이터에 모두 접근

- 조인 버퍼의 데이터들과 비상연락망 테이블의 한 번의 테이블 풀스캔(table full scan)으로 원하는 데이터를 모두 찾을 수 있음

- 비상연락망 테이블의 테이블 풀 스캔을 줄이는 게 목적으로 성능 저하를 개선하는 조인 알고리즘 방식

 

---

배치 키 액세스 조인

중첩 루프 조인 방식은 필연적으로 데이터 접근 시 인덱스에 의한 랜덤 액세스가 발생(비효율적인 조인 방식)

랜덤 액세스의 단점을 해결하고자 접근할 데이터를 미리 예상하고 가져오는데 착안한 조인 알고리즘을 배치 키 액세스 조인(batched key access join, BKA JOIN)

BKA 조인은 블록 중첩 루프 조인에서 활용한 드라이빙 테이블의 조인 버퍼 개념을 그대로 사용

드리븐 테이블에 필요한 데이터를 미리 예측하고 정렬된 상태로 담는 랜덤 버퍼의 개념을 도입

드리븐 테이블의 데이터를 예측하고 정렬된 상태로 버퍼에 적재하는 기능을 다중 범위 읽기(multi range read, MRR)

즉, 미리 예측된 데이터를 가져와 정렬된 상태에서 랜덤 버퍼에 담기 때문에 드리븐 테이블에 대해 랜덤 액세스가 아닌 시퀀셜 액세스를 수행하는 방식

 

1. 드라이빙 테이블에서 필요한 데이터를 추출하여 조인버퍼에 적재 (학번 1과 100인 데이터 저장)

2. 드리븐 테이블의 인덱스 기반으로 필요한 데이터를 예측하여 랜덤 버퍼에 적재하고 학번 1과 100 데이터를 랜덤 버퍼인 메모리상에 상주시킴

3. 학생.학번 = 비상연락방.학번에 대한 조인 조건절로 비교

4. 동일한 데이터가 있다고 판단되면 드리븐 테이블의 데이터에 접근하고 결과를 조인하여 반환

---

해시 조인

해시 조인(hash join)은 MYSQL 8.0.18 버전부터 지원되는 조인 방식

선후 관계를 두고 조인을 수행하는 중첩 루프 조인 방식과 달리, 조인에 참여하는 각 테이블의 데이터를 내부적으로 해시값으로 만들어 내부 조인을 수행

 

학생 테이블과 비상연락망 테이블이 해시 조인으로 처리된다고 가정

 

학생 테이블의 학번 1 데이터는 내부적으로 생성된 해시값과 비상연락망 테이블의 학번 1의 해시값을 비교한 뒤 서로 동일한 경우에만 조인 버퍼에 저장

해시 조인은 보통 대용량 데이터의 동등 비교 연산에서 확인할 수 있지만, 아직은 MYSQL에서 핵심적인 조인 알고리즘으로 처리되지 못함

 

* 참고

- 업무에 바로쓰는 SQL 튜닝(도서) - 2장 SQL 튜닝 용어를 직관적으로 이해하기