UC Merced

Query optimization is crucial for maintaining the efficiency of relational database systems, especially as data volumes increase and machine-generated queries become more common. The primary goal of a query optimizer is to choose the most efficient execution plan from many semantically equivalent options. This selection depends heavily on the performance of the optimizer's components, particularly the cardinality estimator, which uses various statistics to generate estimates. Inaccurate statistics result in poor cardinality estimates, leading to suboptimal plans that cause longer execution times, inefficient resource use, and a degraded user experience.

Traditionally, query optimizers have relied heavily on cardinality estimates to guide plan selection. Databases like PostgreSQL, Oracle, and Db2 use various synopsis structures, such as histograms, samples, and sketches, to generate these estimates. In contrast, modern main-memory databases like DuckDB and HEAVY.AI often operate with limited or even no cardinality estimation, yet manage to achieve competitive performance. This observation raises questions about the role of cardinality estimation in contemporary query optimization.

To further investigate the role of statistics in query optimization, we benchmark a range of database systems --- PostgreSQL, a commercial system (DBMS A), COMPASS, MonetDB, and MapD --- using the IMDB dataset and the Join Order Benchmark (JOB). These systems differ in their reliance on statistics, from the extensive use of histograms and row counts to minimal or no statistical usage. Our evaluation highlights the strengths and weaknesses of various optimization strategies, demonstrating that while advanced statistics typically enhance plan quality and execution time, simpler approaches can also yield competitive performance under certain conditions. This finding suggests a need for a more nuanced understanding of the relationship between the complexity of statistics and their impact on optimization, challenging the notion that more advanced statistics always result in better query performance.

In order to gain a deeper understanding of query optimizer behavior in the absence of cardinality estimates, this dissertation introduces Simpli-Squared, a novel query optimization algorithm that does not depend on traditional statistical methods. Instead, Simpli-Squared leverages readily available information such as database schema, functional dependencies, and table sizes to generate query execution plans. Remarkably, Simpli-Squared demonstrates competitive performance, even while deviating from conventional optimization approaches that rely heavily on cardinality estimation.

To understand the effectiveness of methods that do not use statistics, such as Simpli-Squared, we conduct a comprehensive analytical study, comparing traditional optimizers that utilize cardinality estimates with those that do not, like Simpli-Squared. Our findings indicate that while cardinality estimates may have a limited impact in scenarios without indexes, inaccuracies can be detrimental when indexes are present. Additionally, in highly parallel main-memory databases, the influence of cardinality estimates appears to be minimal.

Finding optimal query execution plans, particularly when indexes are involved, relies heavily on accurate cardinality estimation. While estimates for single-table queries are generally reliable, both traditional and machine learning-based methods often struggle with more complex queries, resulting in suboptimal plans. Although existing methods like P-error and L1-error can identify such plans, they are limited to offline analysis. To address this, we introduce PLANSIEVE, a framework that dynamically identifies suboptimal plans during query execution using a robust machine learning model. PLANSIEVE improves its predictions incrementally, becoming more accurate with each query processed. Our experiments across various workloads demonstrate PLANSIEVE's real-time effectiveness, highlighting its potential to enhance query optimization in dynamic and complex data environments.