UC Merced

Query optimization remains a crucial element of relational database systems. With rapidly expanding data volumes and an increasing trend of machine-generated queries, the significance of query optimization is only increasing and requires continuous advancements. The objective of the query optimizer is to identify an optimal query execution plan from a vast number of semantically equivalent query plans. The success of this search process depends on the optimal operation of the internal inter-connected components of the query optimizer.

In this dissertation, we introduce COMPASS, a novel query optimization paradigm for in-memory databases based on a single type of statistics - Fast-AGMS sketches. While maintaining high accuracy, the highly parallelizable nature of Fast-AGMS empowers the query optimizer to accommodate more complex queries. Subsequently, we redefine the objective of the query optimizer to find a spanning tree with a low cost. Capitalizing on the polynomial time complexity of spanning tree algorithms, we present ESTE, an ensemble spanning tree-based enumeration strategy. ESTE systematically enumerates different parts of the search space, thereby enhancing the robustness of the query optimizer. We believe this perspective enables the application of well-studied spanning-tree algorithms to the field of query optimization. Finally, we address the impact of cardinality estimation errors on query optimizers. Given their inevitability, these errors can cause a domino effect, leading to additional mistakes in the subsequent components of the optimizer. We propose L1-error, a new indicator designed to identify sub-optimal plans. L1-error accounts for the fact that certain estimation errors may have more impact on selecting an optimal plan than others.