A database management system(DBMS) executes a query plan chosen by the query optimizer. There are two approaches for query optimization: heuristic query optimization and cost-based query optimization. When a DBMS deals with large databases, it is appropriate to use cost-based query optimization since we can perform more effective optimization saving the execution cost of the query than using heuristic optimization. On the other hand, cost-based query optimization requires maintaining the metadata for statistics. In this thesis, we design and implement an architecture and the cost model to implement cost-based query optimization for the Odysseus DBMS. We implement cost-based query optimization using the branch-and-bound technique to compare the estimated cost of every possible query plan efficiently. We also implement the mechanisms for updating the metadata for statistics. Here, we use the method of linear counting instead of sorting to obtain the number of unique values in linear time for large-scale database. In addition, we implement mechanisms to display the query plan that DBMS selects and to allow the user to select the query plan. In the experiment, we evaluate the performance of cost-based query optimization and updating the metadata with linear counting. We compare the results of cost-based query optimization with those of manual selection of selected users. The results show that cost-based query optimization significantly outperforms the manual selection, justifying the effectiveness of our query optimizer.
DBMS는 주어진 질의를 질의 최적화 과정을 통해 선택한 질의 계획으로 수행한다. 질의 최적화 과정은 heuristic query optimization과 cost-based query optimization이 있는데, 대용량의 데이터베이스를 다루는 경우 질의 계획을 선택하는 오버헤드보다 선택한 질의 계획을 수행하는 오버헤드의 비중이 더 크기 때문에 cost-based query optimization을 구현하는 것이 적절하다. 이 외에도 cost-based query optimization을 사용하기 위해 메타데이터로 유지하는 통계적 수치들을 갱신하는 오버헤드의 경우에는, 메타데이터를 갱신하는 기능을 구현하여 필요할 때 갱신하도록 하여 해소한다. 따라서 본 논문에서는 오디세우스 DBMS에 cost-based query optimization을 구현하기 위한 아키텍처와 비용 모델을 설계하고 구현한다. 효율적으로 질의 계획들의 추정 비용을 비교하는 branch-and-bound 기법을 사용하여 cost-based query optimization을 구현하고, linear counting 기법을 사용하여 정렬을 사용하지 않고 메타데이터를 갱신하는 기능을 질의로 구현한다. 이 외에도 사용자가 DBMS가 선택한 질의 계획을 확인하는 기능과 질의 계획을 선택/제한하는 기능을 질의로 구현한다. 마지막으로 실험을 수행하여 구현한 cost-based query optimization의 성능을 보인다. 실험 결과는 cost-based query optimization이 대용량의 데이터베이스를 다루는 질의들을 효율적으로 수행함을 보여준다.
