TIL

9.3(8) 조인 최적화 알고리즘

9.3.2 조인 최적화 알고리즘

• 조인을 할 때 테이블 개수가 많아지면 실행 계획 수립에 많은 시간이 걸릴 수도 있다.
• MySQL에는 최적화된 조인 실행 계획을 위한 2가지 알고리즘이 있다.

Exhaustive 검색 알고리즘

• MySQL 5.0과 그 이전에 사용되던 최적화 기법이다.
• FROM 절에 명시된 모든 테이블 조합에 대해 비용을 계산해서 최적의 실행 계획 1개를 찾는 방법이다.
• 테이블이 20개라면 조인 가능한 조합은 모두 20!개가 되고 테이블이 10개만 넘어도 실행 계획 수립에 몇 분이 걸릴 것이다.

Greedy 검색 알고리즘

• Exhaustive 알고리즘의 시간 소모 문제를 해결하기 위해 5.0 버전부터 도입된 조인 최적화
• t1, t2, t3, t4의 4개 테이블을 조인할 때 최적화 과정을 살펴보자.
  1. N개 테이블 중 optimizer_search_depth 변수에 정의된 개수의 테이블로 가능한 조인 조합을 생성
  2. 1번에서 생성된 조인 조합 중 최소 비용 계획 하나를 선정
  3. 2번에서 선정된 실행 계획의 첫 번째 테이블을 ‘부분 실행 계획’의 첫 번째 테이블로 선정
  4. 전체 N-1개 테이블 중(3번에서 선택된 테이블 제외) optimizer_search_depth 변수의 개수만큼 조인 가능한 테이블 조합 생성
  5. 4번에서 생성된 조인 조합들을 하나씩 3번에서 생성된 ‘부분 실행 계획’에 대입해 실행 비용 계산
  6. 5번의 비용 계산 겨로가, 최적 실행 계획에서 두 번째 테이블을 3번에서 생성된 ‘부분 실행 계획’의 두 번째 테이블로 선정
  7. 남은 테이블이 없어질 때까지 4~6번 과정을 반복하면서 ‘부분 실행 계획’에 조인 순서를 기록
  8. 최종적으로 ‘부분 실행 계획’이 테이블의 조인 순서로 결정됨

조인 최적화를 위한 시스템 변수

• optimizer_search_depth
  • optimizer_search_depth 변수의 기본값은 62이고 값에 따라 최적화 비용이 상당히 줄어들 수 있다.
  • 값이 0이 되면 Greedy 검색을 위한 조인 검색 테이블 개수를 옵티마이저가 자동으로 결정한다.
  • 조인에 사용된 테이블 개수가 이 시스템 변수 값보다 크면 변수 값만큼의 테이블은 Exhaustive 검색이 사용되고 나머지는 Greedy가 사용된다.
  • 조인에 사용된 테이블 개수가 이 시스템 변수 값보다 작으면 모두 Exhaustive 검색이 사용된다.
  • optimizer_prune_level 변수가 0인 경우 optimizer_search_depth 설정이 쿼리 성능에 심각한 영향을 줄 수 있으니 optimzier_search_depth는 4~5 정도로 설정하는 것이 좋다.
• optimizer_prune_level
  • 5.0 버전부터 추가된 Heuristic 검색 작동 방식을 제어한다.
  • Exhaustive이든 Greedy든 옵티마이저는 조인 순서 결정을 위해 많은 조인 경로를 비교하는데 Heuristic 검색의 가장 핵심적인 내용은 비용 계산 중 이미 계산했던 조인 순서 비용보다 큰 경우 언제든지 중간에 포기할 수 있다는 것이다.
  • optimizer_prune_level이 1로 설정되면 조인 순서 최적화에 경험 기반의 Heuristic 알고리즘을 사용한다. (0이면 적용되지 않음)
  • 조인 대상 테이블이 몇 개 안되더라도 성능 차이가 있기 때문에 가급적 1로 설정하자.

MySQL 8.0 버전의 조인 최적화는 많이 개선되어 optimizer_search_depth 변수에는 크게 영향 받지 않는 것으로 보인다. 하지만 optimizer_prune_level을 0으로 설정하면 optimizer_search_depth 값 변화에 따라 실행 계획 수립 시간이 급증하는 것을 확인할 수 있다. 조인 최적화 관련 휴리스틱을 비활성화할 필요가 없기 때문에 조인 관련 시스템 변수 조정은 더이상 필요치 않을 것으로 보인다.