UC Berkeley

Data has been growing at an unprecedented rate in the past two decades. As a result, systems that store, process, and analyze data have become mission-critical. Crucial to the performance of data systems is the query optimizer, which translates high-level declarative queries (e.g., SQL) into efficient execution plans. However, query optimization is highly complex, leading to two key challenges. First, optimizers use a myriad of hand-designed heuristics to tame the complexity, but heuristics leave performance on the table. Second, optimizers are highly costly to develop, where human experts may spend months writing a first version and years refining it.

This dissertation applies and enhances machine learning advances to tame the complexity in query optimization. First, we remove for the first time decades-old and accuracy-impacting heuristics in cardinality estimation—the Achilles’ heel of optimizers where heuristics particularly abound—thereby significantly improving estimation accuracy. We present Naru and NeuroCard, two cardinality estimators based on self-supervised learning advances that learn the joint data distribution of tables without any heuristic assumptions. Our estimators improve the accuracy of cardinality estimation by orders of magnitude compared to the prior state of the art. Second, we show that automatically learning to optimize SQL queries, without learning from an expert-designed optimizer, is both possible and efficient, thereby potentially alleviating the high development cost. We introduce Balsa, a deep reinforcement learning agent that automatically learns to optimize SQL queries by trial-and-error. Balsa can learn to outperform the optimizers of PostgreSQL—one of the most popular database systems—and a commercial database engine with a few hours of learning.

Overall, by enhancing machine learning advances with new, carefully designed systems and ML techniques, this line of work improves existing query optimizers, while opening the possibility of alleviating the complex optimization in future environments and engines.