logically equivalent plan 과 physical query plan

1 minute read

이 포스팅은 SQL Query Optimization: Why Is It So Hard To Get Right?(David J.DeWitt) 강의를 참조하여 작성하였습니다.

Logically Equivalent plan

이전 포스팅과 동일하게,
SQL query 를 아래서부터 위로 올라가는 tree 로 생각해 봅시다.

사용자가 입력하는 SQL 은 논리적 순서나, 실제 동작방식에 대해 명시하지 않습니다.
그래서 동일한 SQL 쿼리라도 여러가지 방식으로 나타낼 수 있고,
즉, 여러 tree 로 구성을 할 수 있습니다.

SQL 의 각 연산자들은 특정 특성을 갖고 있어서,
논리적으로는 동일하지만, 다른 형태로 나타낼 수 있습니다.
이러한 특성, 규칙을 euqivalence rule 이라고 하고,
다음과 같이 4가지 규칙이 존재합니다.

select 끼리는 그 순서를 바꿔도 논리적으로 equivalence 하고,
join 을 수행하는 table 의 순서는 바뀌어도 equivalence 합니다.

A 와 B 를 join 한 결과를 C 와 join 하는 것은, B 와 C 를 먼저 join 을 하고 그 결과를 A 와 join 해도 equivalence 합니다.

join 을 수행하는 테이블 중 하나에 대해 select 가 있다면,
select 를 먼저 수행하고, join 을 수행해도 equivalence 합니다.

그림과 같이 CID,Name 의 project 후에 Name 의 project 을 하는 것은 Name 의 project 만 사용하여도 equivalence 합니다.

이 euquivalence rule 들 가지고 하나의 쿼리에 대해 다양한 euqivalent plan 을 만들 수 있습니다.

위와 같이 단순한 logical operator tree 도
euqivalent rule 을 사용하여 9 개의 equialent plan 을 만들 수 있습니다.

9개 정도의 cost 는 계산하기 쉽지만,
이 다음단계에서 physical plan 들은 각 9 개의 logical plan 에 대해서 만들어야 하므로,
고려해야할 plan 이 크게 늘어나게 됩니다.

join 을 실제로 수행할 때는 다음과 같은 방식 중 하나를 선택해서 수행합니다.
Nested Loops(LP), Sort-merge Join(SMJ), Hash Join(HJ)

select 또한 2개의 방식이 있습니다.
Sequential Scan(SS), Index Scan(IS)

위에서 하나의 logical tree 에는 2개의 join 과 2개의 select 가 존재하므로

36(3x3x2x2) 개의 다른 physical tree 를 사용할 수 있습니다.

그래서 총 9x36 = 324 개의 가능한 plan 이 생기게 됩니다.
이런 방식으로 하나의 쿼리에 수많은 plan 이 생기므로,
실제 QO 수행할 때는 purning 과 같은 작업으로 plan 을 제거합니다.

다음 포스팅에서는 쿼리를 어떻게 최적화 하는지 살펴보겠습니다.