Profiling and Quality Assessment of Query Optimizer

Query optimizers have long been considered as among the most complex components of a database engine, while the assessment of an optimizer's quality remains a challenging task. Indeed, existing performance benchmarks for database engines (like TPC benchmarks [3]) produce a performance assessment of the query runtime system rather than its query optimizer. Thus, they fall short of insights on the quality of the optimization process independent of the underlying execution engine. However, such an insight is particularly useful to query optimizer developers who strive to understand the pros and cons of the optimizer of a given DBMS with the goal of improving the quality of the optimization process. To address this challenge, in this thesis we are proposing a profiling and quality assessment approach for query optimizers. Our approach produces metrics that provide insight on the quality of the optimizer. The metrics and evaluation techniques are also incorporated into an optimizer profiling toolkit, referred to as OptMark, that is runnable over any DBMS regardless of the hardware and OS platforms over which it runs.;Our profiling and quality assessment approach for query optimizers is designed to offer a number of desirable properties. First, it decouples the quality of an optimizer from the quality of its underlying execution engine. Second, it evaluates independently both the effectiveness of an optimizer (i.e., quality of the optimizer-chosen plans) and its efficiency (i.e., optimization time spent in optimization). Finally, it is incorporated into OptMark, a profiling toolkit that is minimum invasive to the DBMS that wishes to use it. Any DBMS can provide a system-specific implementation of a simple API that allows OptMark to run and generate assessment metrics for the specific system.;The profiling and assessment metrics can not only reflect the end-to-end quality of an optimizer, it can also be used to examine the quality of the cost model and the enumeration strategy of the optimizer. With the help of OptMark, developers can get a sense of why the optimizer doesn't come up with a better plan. For example, an inaccurate cost model could lead to a suboptimal plan if it inaccurately estimates the cost of a better plan. On the other hand, if a better plan is not enumerated by the optimizer, then we need to reexamine the heuristics used in enumerating plans.;In the five years of this doctoral work, we designed and developed the metrics for evaluating an optimizer's effectiveness and efficiency, the framework of OptMark and a simple API that needs to be implemented by a specific DBMS that wishes to use OptMark. We have implemented OptMark on the open-source MySQL engine [2] as well as two commercial database systems. Using these implementations we are able to assess the quality of the optimizers on these three systems based on the TPC-DS [4] benchmark queries. Based on the results, we believe OptMark is both effective and easy to use in profiling and assessing the quality of a query optimizer.