Query Optimization 이란

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

Query Optimization

쿼리 최적화(QO) 란 다음과 같이 볼 수 있습니다.

SQL 쿼리가 주어질 때 최단시간내에 출력될 수 있는 최적의 query plan 을 선택하는 작업입니다.
그러나 이 작업은 여러가지 제약들로 인해 굉장히 어렵습니다.

TPC-H(벤치마크) 에서 8 개의 쿼리를 수행할 때,
8개의 쿼리로 생성할 수 있는 query plan 은 2천만개 정도 됩니다.
2천만개의 쿼리 플랜의 코스트를 계산하기 위해서는 몇일이 소요될 수 있지만,
실제 데이터베이스 시스템에서는 몇초 안에 플랜을 추정하여 쿼리를 수행해야합니다.
그래서 우선 시간의 제약 이 있습니다.

데이터베이스 시스템은 다음과 같은 프로세스로 SQL 쿼리를 수행합니다.

사용자가 입력한 SQL 쿼리는 parser 를 통해서 Logical operatior tree 로 변환이 되고,
이 트리는 Query Optimizer 를 통해 Physical operator tree 로 변환이 됩니다.
이 트리의 순서에 따라 query 가 수행됩니다.

Logical operator 는 union, selction 등으로 구성하여, 어떤 순서로 쿼리를 수행할지를 나타내고,
Physical operator 는 기존 logical 에서 index, hash join 과 같이 어떻게 쿼리를 수행할지를 나타냅니다. 다음그림 과 같이 볼 수 있습니다.

사용자가 ‘SELECT Average(Rating) FROM Reviews WHERE MID=932’ 라는 쿼리를 입력하면
parser 는 위 그림과 같이 논리적 순서로 tree 를 만듭니다.
(1)Reviews 테이블에서 (2)MID가 932 인 것을 선택하여, (3)Rating 을 평균을 내도록 합니다.

이런 logical operator tree 는 Query Optimizer 를 거쳐서 Physical operator tree 가 됩니다.
위 그림과 같이, 하나의 logical tree 로 2개의 query plan 을 만들 수 있습니다.

• 첫번째 플랜은 Review 테이블의 페이지 만큼의 디스크 IO 를 수행하고, sequential 하게 읽습니다.
  읽으면서 MID = 932 인 행을 찾고, 그 조건에 만족하는 행들만으로 평균을 계산합니다.
• 두번째 플랜은 index 를 사용한 플랜입니다.
  MID 어트리뷰트에 대해 index 가 설정되어 있는 상황에서, 인덱스를 사용해 932를 찾고,
  그 조건에 만족하는 행들로 평균을 계산합니다.

위 두 플랜 중 어떤 것이 optimal 한지 생각해 봅시다.
index 를 사용한 두번째 플랜이 더 좋을 것이라 생각할 수 있지만,
이는 상황에 따라 달라집니다.

index를 사용하면 단일 데이터를 읽어오는 것은 빠를 수 있습니다.
그러나 index 가 정렬되어 있지 않을 때, 데이터를 sequencial 하게 읽어와야하는 경우에는
Random IO 를 수행해야되서 속도가 더 느려질 수 있습니다.

위와 같이 단순한 두개의 플랜에서도,
상황에 따라 여러 고려 사항이 발생합니다.
예를들어, IO 시간, 스캔하는 데이터의 크기, index 의 유무, index가 정렬되었는지 여부 등
쿼리의 cost 에 미치는 다양한 요소들이 있습니다.

QO 는 모든 plan 의 cost를 다 계산하기도 어렵고,
cost에 영향을 주는 요소들을 전부 고려하여 계산하기도 어렵습니다.

위 상황은 physical operator tree 의 plan 만 고려한 것이고,
이전에 logical operator tree 에서도 최적화를 고려해야합니다.
또한 이 parser(logical) 단계에서 생기는 오차는 이후 QO 단계에서 propagate 되어
더 큰 오차가 될 수 있습니다.

이와 같은 이유들로 QO 를 잘하는 것은 굉장히 어려운 작업입니다.

이후 포스팅에서는 logical, physical 단계에서 만들 수 있는 여러 equivalent plan 에 대해 확인하고,
쿼리 플랜들의 cost 를 추정하는 방법에 대해 살펴보겠습니다.

​