테이블의 개수가 많아지면 실행 계획을 찾는 것이 상당히 어려워지고, 하나의 쿼리에서 조인되는 테이블의 개수가 많아지면 실행 계획을 수립하는 데만 몇 분이 걸릴 수도 있다.

MySQL에는 최적화된 조인 실행 계획 수립을 위한 2가지 알고리즘이 있으며, 4개의 테이블을 조인하는 쿼리가 조인 옵티마이저 알고리즘에 어떻게 처리되는지 살펴볼것이다.

1
2
3

SELECT *
FROM t1, t2, t3, t4
WHERE ...

Exhaustive 검색 알고리즘 (완전 탐색)

Exhausitve 검색 알고리즘은 MySQL 5.0 이하 버전에서 사용되던 조인 최적화 기법으로, FROM절에 명시된 모든 테이블의 조합에 대해 실행 계획의 비용을 계산해서 최적의 조합 1개를 찾는 방법이다.

테이블이 20개라면 이 방법으로 처리했을 때 가능한 조인 조합은 모드 20!(3628800)개가 된다.

Greedy 검색 알고리즘

Greedy 검색 알고리즘은 Exhaustive 검색 알고리즘의 시간 소모적인 문제점을 해결하기 위해 MySQL 5.0 부터 도입된 조인 최적화 기법이다.

1. 전체 N개의 테이블 중에서 optimizer_search_depth 시스템 변수에 정의된 개수의 테입르로 가능한 조인 조합 생성
2. 1번에서 생성된 조인 조합 중 최소 비용의 실행 계획 하나를 선정
3. 2번에서 선정된 실행 계획의 첫 번째 테이블을 “부분 실행 계획"의 첫 번째 테이블로 선정
4. 전체 N-1개의 테이블 중 시스템 설정 변수에 정의된 개수의 테이블로 가능한 조인 조합을 생성
5. 4번에서 생성된 조인 조합들을 하나씩 3번에서 생성된 “부분 실행 계획"에 대입해 실행 비용 계산
6. 5번의 비용 계산 결과, 최적 실행 계획에서 두 번째 테이블을 3번에서 생성된 “부분 실행 계획"의 두 번째 테이블로 선정
7. 남은 테이블이 모두 없어질 때까지 4~6 반복하며 “부분 실행 계획"에 테이블의 조인 순서를 기록
8. 최종적으로 “부분 실행 계획"이 테이블의 조인 순서로 결정

Greedy 검색 알고리즘은 optimizer_search_depth 시스템 변수 값에 따라 최적화의 비용이 상당히 줄어들 수 있으며 기본값은 62이다.

시스템 변수

• optimizer_search_depth: 값에 따라 어떤 알고리즘을 선택할지 결정한다.
  • 0: Exhaustive 검색 알고리즘
  • 1+: Greedy
  • 기본값은 62이나 많은 테이블이 조인되는 경우 상당히 부담될 수 있고 0일 경우 쿼리 성능에 심각항 영향을 미칠 수 있다.(일반적으로 4~5 가 적당하다.)
• optimizer_prune_level: MySQL 5.0 부터 추가된 Heuristic 검색이 작동하는 방식을 제어한다.
  • 다양한 조인 순서 비용을 계산하는 도중 이미 계산했던 조인 순서보다 비용이 크다면 중간에 포기한다.
  • 1로 설정시 Heuristic 알고리즘을 사용한다.
  • 실제 Hueuristic 조인 최적화는 조인 대상 테이블이 몇개 되지 않터라도 상당한 성능 차이를 내므로 0으로 변경하지 않을 것을 권장한다.