16.1 Introduction

optimizer는 가장 적은 비용의 query evaluation plan을 찾기 위해서 주어진 표현식에 대해 같은 결과를 출력하는 다른 query evaluation plan을 만들어 낼 필요가 있다. 그런 후에 가장 적은 비용으로 수행되는 plan을 선택한다. query evaluation plan을 만들어 내는 것은 다음의 세 단계로 이루어진다.

1. 논리적으로 주어진 표현식과 동등한 식을 만들어 낸다.
2. 각 표현식에 여러 가지 방법의 주석(annotation)을 달아 서로 다른 query evaluation plan을 만든다.
3. 각 evaluation plan의 비용을 추정하고 비용이 가장 적은 것을 선택한다.

(1), (2), (3)은 질의 최적화기에서 서로 맞물려 있다(순서가 뒤죽박죽). 몇 개의 표현식이 만들어지고 만들어진 표현식에 주석을 단 후에 다른 표현식을 만들고 주석을 다는 과정을 반복한다. 평가 계획이 생성되는 동안, 릴레이션 크기, 인덱스 깊이 등 릴레이션에 관한 통계를 수집해 평가 계획의 비용 추정이 이루어진다.