TIL

9.3(4) 세미 조인 최적화

세미 조인

• 세미조인이란 실제 조인을 수행하지 않고 다른 테이블에서 조건이 일치하는 레코드가 있는지만 체크하는 형태의 쿼리를 말한다.

SELECT *
FROM employees e
WHERE e.emp_no IN
	(SELECT de.emp_no FROM dept_emp de WHERE de.from_date='1995-01-01');

• MySQL에서 세미 조인 최적화가 없었을 땐 employees 테이블을 풀 스캔하면서 한 건씩 서브 쿼리와 일치하는지 비교했다.
• MySQL 8.0부터 세미 조인 최적화가 도입되었고 비교적 최근에 도입된 최적화들은 다음과 같다.
  • Table Pull-out
  • Duplicate Weed-out
  • First Match
  • Loose Scan
  • Materialization

테이블 풀-아웃(Table Pull-out)

• Table pullout 최적화는 세미 조인의 서브 쿼리에 사용된 테이블을 아우터 쿼리로 뺀 후 조인 쿼리로 재작성하는 형태의 최적화다.
  • 최적화 도입 이전에 수동으로 튜닝하던 대표적인 방법이었다.
• Table pullout 최적화의 몇 가지 제한 사항과 특성
  • 세미 조인 서브 쿼리에서만 사용 가능하다.
  • 서브 쿼리 부분이 UNIQUE 인덱스나 프라이머리 키 룩업으로 결과가 1건인 경우에만 사용 가능하다.
  • Table pullout이 적용된다고 하더라도 기존 쿼리에서 가능했던 최적화가 불가능한 것은 아니므로 MySQL에서는 가능하다면 Table pullout 최적화를 최대한 적용한다.
  • 만약 서브 쿼리의 모든 테이블이 아우터 테이블로 빠질 수 있다면 서브 쿼리 자체는 없어진다.
  • MySQL에서는 ‘최대한 서브 쿼리를 조인으로 풀어 사용해라’라는 튜닝 가이드가 있다. Table pullout 최적화 덕에 서브 쿼리를 조인으로 풀 필요가 없다.
• 실행 계획의 테이블 id 칼럼이 모두 같으면서 Extra 칼럼에 아무것도 출력되지 않는 경우에 최적화가 수행됐다고 볼 수 있다.
  • Table pullout 최적화는 별도로 Extra 칼럼에 표시되는 문구가 없다

퍼스트 매치(firstmatch)

• First Match 최적화는 IN(subquery) 형태의 세미 조인을 EXISTS(subquery) 형태로 튜닝한 것과 비슷하게 실행된다.

EXPLAIN SELECT *
FROM employees e WHERE e.first_name='Matt'
	AND e.emp_no IN (
		SELECT t.emp_no FROM titles t
		WHERE t.from_date BETWEEN '1995-01-01' AND '1995-01-30'
	);

id	table	type	key	rows	Extra
1	e	ref	ix_firstname	233	NULL
1	t	ref	PRIAMRY	1	Using where; Using index; FirstMatch(e)

• 실행 계획의 id 칼럼 값이 모두 ‘1’로 표시된 것을 봐서 서브 쿼리가 아닌 조인으로 처리됐다는 것을 알 수 있다.
• FirstMatch(e) 문구는 employees 테이블 레코드에 대해 titles 테이블에 일치하는 레코드 1건만 찾으면 더 이상 titles 테이블 검색을 하지 않는다는 의미이다.
  • 의미적으로 EXISTS(subquery)와 동일
  • 하지만 조인으로 풀어서 실행하면서 일치하는 첫 레코드만 검색하는 최적화를 실행한 것
• FirstMatch 최적화 제한 사항과 특성
  • 서브 쿼리에서 하나의 레코드만 검색하면 더 이상 검색을 멈추는 단축 실행 경로(Short-cut path)이기에 서브 쿼리가 참조하는 아우터 테이블이 먼저 조회된 이후에 실행된다.
  • 최적화가 수행되면 Extra에 FirstMatch(table-N) 문구가 표시된다.
  • 상관 서브 쿼리(Correlated subquery)에서도 사용될 수 있다.
  • GROUP BY나 집합 함수가 사용된 서브 쿼리에서는 사용할 수 없다.
• FirstMatch 최적화는 optimizer_switch 시스템 변수에서 semijoin 옵션과 firstmatch 옵션이 모두 on으로 활성화된 경우에만 사용할 수 있다.

루스 스캔(loosescan)

• 세미 조인 서브 쿼리 최적화의 LooseScan은 GROUP BY에서 동작하는 루스 인덱스 스캔과 비슷하게 동작한다.
  • 9.2.4 GROUP BY 처리 참고
• LooseScan 최적화는 루스 인덱스 스캔으로 서브 쿼리 테이블을 읽고, 아우터 테이블을 드리븐 테이블로 사용해 조인을 수행한다.
  • 서브 쿼리 부분이 루스 인덱스 스캔을 사용할 수 있어야 최적화가 가능하다.

루스 스캔 예제

• dept_emp 테이블에 (dept_no, emp_no) 프라이머리 키 인덱스가 존재한다고 했을 때 다음 쿼리를 보자.
  • department 테이블 레코드 수는 9건
  • dept_emp 테이블 레코드 수는 33만건

EXPLAIN 
SELECT * FROM departments d WHERE d.dept_no 
IN (SELECT de.dept_no FROM dept_emp de);

• dept_emp 레코드가 총 33만개니 전부 읽어야할 것 같지만 (dept_no, emp_no) 인덱스가 존재하고 dept_no로 그루핑하면 9건밖에 없다는 것을 알 수 있다.
• 즉 dept_emp 테이블의 프라이머리 키를 루스 인덱스 스캔으로 유니크한 dept_no만 읽으면 효율적으로 서브 쿼리를 처리할 수 있다.
  • dept_emp의 프라이머리 키 인덱스를 읽기 시작하는데 dept_no=’d001’인 레코드가 하나라도 등장한다면 그 뒤에 dept_no=’d001’인 (dept_no, emp_no) 인덱스는 읽지 않아도 된다.
  • 33만건이 아닌 9번만으로 결과를 반환할 수 있게 된다.

구체화(Materialization)

• Materialization 최적화는 세미 조인에 사용된 서브 쿼리 통째로 내부 임시 테이블로 생성해서 최적화한다는 것을 의미한다.

EXPLAIN SELECT *
FROM employees e
WHERE e.emp_no IN
	(SELECT de.emp_no FROM dept_emp de
		WHERE de.from_date='1995-01-01');

• 위 쿼리는 드라이빙 테이블에 대한 조건이 서브 쿼리 외에는 없기에 드라이빙 테이블을 풀 스캔해야 해서 FirstMatch 최적화가 별로 도움이 안된다.
• 다음 실행 계획을 보면 서브 쿼리가 임시 테이블을 생성했다는 것을 알 수 있다.
  • dept_emp 테이블을 읽는 서브 쿼리가 먼저 실행되어 그 결과로 임시 테이블이 만들어졌다.
  • 임세 테이블과 employee 테이블을 조인해서 결과를 반환한다.

id	select_type	table	type	key	ref
1	SIMPLE		ALL	NULL	NULL
1	SIMPLE	e	eq_ref	PRIMARY	.emp_no
2	MATERIALIZED	de	ref	ix_fromdate	const

• 다른 서브 쿼리 최적화와 달리 GROUP BY 절이 있어도 최적화가 가능하다.
• Materialization 최적화 제한 사항과 특성
  • IN(subquery)에서 서브 쿼리는 상관 서브 쿼리가 아니어야 한다.
  • 서브 쿼리는 GROUP BY나 집합 함수를 사용해도 된다.
  • 구체화가 사용된 경우 내부 임시 테이블이 사용된다.
• optimizer_switch 시스템 변수에서 semijoin 옵션 materialization 옵션 모두 ON으로 되어있어야 한다.

중복 제거(Duplicated Weed-out)

• Duplicate Weedout은 세미 조인 서브 쿼리를 일반적인 INNER JOUN으로 바꿔 마지막에 중복을 제거하는 방법으로 처리된다.
  • NNER JOIN + GROUP BY 처리와 동일하게 동작

EXPLAIN SELECT * FROM employees e
WHERE e.emp_no IN 
	(SELECT s.emp_no FROM salaries s WHERE s.salary>150000);

• 최적화 과정
  1. salaries 테이블의 ix_salary 인덱스를 스캔해서 급여가 150000원보다 큰 사원을 검색해 employees 테이블과 조인
  2. 조인 결과를 임시 테이블에 저장
  3. 임시 테이블에서 emp_no 기준으로 중복 제거
  4. 중복을 제거하고 남은 레코드 최종적으로 반환

id	select_type	table	type	key	Extra
1	SIMPLE	s	range	ix_salary	Using where; Using index; Start temporary
1	SIMPLE	e	eq_ref	PRIMARY	End temporary

• Extra 칼럼에 Start temporary와 End temporary 문구가 표시되면 Duplicated Weed-out 최적화가 실행된 것이다.

참고로 위 에제는 Materialization, FirstMatch, LooseScan 최적화를 사용하지 못하게 한 상태에서 테스트했다.

• Duplicate Weedout 최적화 장점과 제약 사항
  • 서브 쿼리가 상관 서브 쿼리라도 사용 가능
  • GROUP BY나 집합 함수가 사용되면 사용 불가
  • 이 최적화는 서브 쿼리 테이블을 조인으로 처리하기에 최적화할 수 있는 방법이 많다.