9.3.2 조인 최적화 알고리즘

조인 최적화 알고리즘

MYSQL에는 조인쿼리의 실행 계획 최적화를 위한 알고리즘이 2개 있다.

결합 쿼리에 대해 MySQL 최적화에 의해 조사 될 계획의 수는 쿼리에서 참조되는 테이블 수와 함께 기하 급수적으로 증가합니다.  몇몇 테이블 (일반적으로 7 ~ 10 미만)의 경우 이것은 문제가되지 않습니다. 그러나 큰 쿼리가 전송 된 경우 쿼리 최적화에 소요되는 시간이 서버 성능의 주요 병목 현상하는 경향이 있습니다. 

Exhaustive 알고리즘(완전 탐색)

SELECT * FROM A, B, C WHERE ... 

MYSQL5.0과 그 이전 버전에서 사용되던 조인 알고리즘으로, FROM절에 명시된 모든 테이블의 조합에 대해 실행 계획의 비용을 계산해서
최적의 조합 1개를 찾는 방법이다.
테이블이 20개라면 이 방법으로 처리했을때 가능한 조인 조합은 20!(3628800)개가 된다.
Exhaustive Search 알고리즘에서는 테이블이 10개만 넘어가도 실행 계획을 수립하는데 몇 분이 걸린다.

Greedy 검색 알고리즘

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

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

요약 : Divide and Qonquer(분할 정복) 방식이며 각각 부분 결과들을 조합한 결과를 사용한다.
각 부분에서 최적을 찾는다고 그 조합이 무조건 전체의 최적이라고는 할 수 없다.

optimizer_seqrch_depth

Greedy 검색 알고리즘은 optimizer_seqrch_depth 시스템 변수에 설정된 값에 따라 조인 최적화의 비용이 상당히 줄어든다.
기본값은 62이다.

• 이 시스템 변수는 Greedy 검색 알고리즘과 Exhausitive 검색 알고리즘 중에서 어떤 알고리즘을 사용할지 결정하는 시스템 변수이다.
• 0으로 설정할 경우는 Greedy를 쓰지않겠다 라는 의미는 아니고, 옵티마이저가 개수를 정하도록 위임한다는 의미
• 63으로 설정할 경우가 Greedy를 사용하지 않겠다 는 의미인데 이 경우엔 Exhaustive 방식을 사용하게 된다.
• 기본값은 62인데 사실 62개가 넘는 조인쿼리는 쓸일이 거의 없으므로 기본은 Exhaustive라고 봐도 무방하다. Greedy Search를 사용하기 위해서는 해당 값을 확 줄여야한다. (4~5 정도가 좋다고 함)

MYSQL5.6

MYSQL8.0 Document

optimizer_search_depth 값이 작을수록 쿼리 컴파일 시간이 크게 줄어들 수 있습니다. 예를 들어, optimizer_search_depth가 쿼리의 테이블 수에 가까울 경우 12개, 13개 또는 그 이상의 테이블을 가진 쿼리는 컴파일하는 데 몇 시간 및 심지어 며칠이 걸릴 수 있습니다. 동시에 3 또는 4와 동일한 optimizer_search_depth로 컴파일할 경우, optimizer는 동일한 쿼리에 대해 1분 이내에 컴파일할 수 있습니다.  optimizer_search_depth에 대한 합리적인 값이 무엇인지 확신할 수 없는 경우, 이 변수를 0으로 설정하여 자동으로 값을 결정하도록 optimizer에게 알려줄 수 있습니다.