조인(join)

조인(join)

Created
Mar 25, 2024
Created by
Tags
Mysql
Property
 

NL(Nested Loop) join

 
중첩 for-loop 와 같은 구조로 테이블을 조인한다.
예를 들어 아래와 같이 세일즈 부서의 직원들이 관리하는 고객 정보를 가져온다고 하면
SELECT customer.*
FROM customer JOIN employee ON customer.manager_id = employee.id
WHERE employee.employeed_at > '2024-01-01';
 
대략 아래의 중첩 for-loop 을 수행하는 것과 비슷하다.
result = []
for emp in employee:
  if emp.employeed_at > '2024-01-01':
      for cus in customer:
        if cus.manager_id == emp.id:
           result.append(cus)
 
일반적으로 조인 기준 컬럼 (customer.manager_id, employee.id) 에 모두 인덱스가 있어야 옵티마이저가 NL 조인을 채택한다.
단, 테이블에 데이터 레코드 갯수가 적으면 인덱스가 없어도 NL 조인을 채택할 수 있다.
 
notion image
 
NL 조인의 특징
  • 드라이빙 테이블 내에 조건을 만족하는 레코드 갯수만큼 드리븐 테이블의 인덱스를 스캔한다.
      • 위 예시에서 employee 테이블에 employeed_at > ‘2024-01-01’ 를 만족하는 데이터 레코드가 1000건이라면, idx_manager_id 인덱스도 1000번 스캔한다.
  • 조인할 데이터가 많을수록 random I/O 또한 많아진다.
      • 위 예시에서 employee 테이블에 employeed_at > ‘2024-01-01’ 를 만족하는 데이터 레코드가 1000건이라면, employee 테이블 대상으로 1000번의 random I/O 가 발생하고 customer 테이블에서도 조인 조건을 만족하는 레코드 갯수만큼 random I/O 가 발생한다.
→ 대량의 데이터 레코드를 조인할 때 불리하다.
 
💡
Block NL 조인
드리븐 테이블 대상으로 인덱스 풀 스캔 또는 테이블 풀 스캔하는 게 불가피하면 옵티마이저는 Block NL 조인을 수행한다.
Block NL 조인 특징
  • 조인 버퍼를 사용한다. (드라이빙 테이블에서 읽은 레코드를 메모리에 캐시하고, 드리븐 테이블과 캐싱된 레코드를 조인한다.)
  • Block NL 조인을 수행하면 실행 계획표의 Extra 항목에 Using Join buffer 라고 표시한다.
  • Mysql 8.0.20 버전 이후로는 해시 조인으로 대체되었다.
 
 
 

hash join

적절한 인덱스가 없어서 NL 조인의 비용이 크면 옵티마이저는 해시조인을 선택한다. (Mysql 8.0.20 버전 이후)
해시 조인은 빌드 단계(build-phase)와 프로브 단계(probe-phase) 로 나누어 처리한다.
 
빌드 단계(build-phase)
조인의 대상이 되는 테이블들 중에 레코드 갯수가 적은 테이블을 가지고 조인 버퍼에 해시 테이블을 생성한다.
해시 테이블로 만드는 테이블을 빌드 테이블이라고 한다.
 
프로브 단계(probe-phase)
나머지 테이블의 레코드를 읽어서 조인 버퍼에 생성한 해시 테이블과 조인한다.
해시 테이블과 조인하는 테이블을 프로브 테이블이라고 한다.
 
아래 그림에서는 employee 가 빌드 테이블이 되고, customer 가 프로브 테이블이 되었다.
 
notion image
 
빌드 테이블과 프로브 테이블을 구분해서 보려면 EXPLAIN FORMAT=TREE 을 사용하면 된다.
 

해시 테이블이 조인 버퍼보다 클 때 처리 과정

해시 테이블의 레코드 갯수가 많아서 조인 버퍼 공간이 부족할 수 있다.
이 때는 빌드 테이블과 프로브 테이블을 join_buffer_size 보다 작은 청크 단위로 나눠서 처리한다.
 
  1. chunking
조인 컬럼 내 모든 필드들을 해시 함수에 넣고, 반환된 값에 따라 디스크 내 temporary 테이블에 나눠서 저장한다.
이 때 빌드 테이블과 프로브 테이블 내에서 같은 해시값을 갖는 데이터 레코드들은 아래처럼 서로 짝이 되는 청크에 저장된다.
notion image
 
  1. hash join
빌드 테이블의 청크를 하나 가져와서 해시테이블을 만들고, 해당 청크의 짝이 되는 프로브 테이블 청크를 가져와서 조인을 수행한다.
notion image
 
  1. 모든 chunk pair 들을 대상으로 해시 조인을 수행한다.
 
 
 

semi join

 
Mysql 에서는 아래 3가지 쿼리를 세미 조인으로 처리한다.
 
  • IN 절 + 서브쿼리
SELECT *
FROM employee as e
WHERE e.emp_no IN (SELECT emp_no FROM salary WHERE amount > 6000);
 
  • = 연산 + 서브쿼리
SELECT *
FROM employee as e
WHERE e.emp_no = (SELECT emp_no FROM salary WHERE contract_id = 421);
 
  • EXISTS 절 + 서브쿼리
SELECT customer.name
FROM customer
WHERE EXISTS (
  SELECT 1
  FROM employee
  WHERE customer.manager_id = employee.emp_no
);
 

anti-semi join

 
Mysql 에서는 아래 3가지 쿼리를 세미 조인으로 처리한다.
 
  • NOT IN 절 + 서브쿼리
SELECT *
FROM employee as e
WHERE e.emp_no NOT IN (SELECT emp_no FROM salary WHERE amount > 6000);
 
  • <> 연산 + 서브쿼리
SELECT *
FROM employee as e
WHERE e.emp_no != (SELECT emp_no FROM salary WHERE contract_id = 421);
 
  • NOT EXISTS 절 + 서브 쿼리
SELECT customer.name
FROM customer
WHERE NOT EXISTS (
  SELECT 1
  FROM employee
  WHERE customer.manager_id = employee.emp_no
);