How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches

Relational database systems internally construct a physical query execution plan (QEP) that specifies exactly how to compute a desired result. However, choosing a QEP involves determining a specific join order, deciding how to access base relations, specifying concrete physical implementations to compute the algebraic operations defined by the given SQL query, and much more. In general, choosing the optimal QEP w.r.t. a predefined cost model is a hard optimization task, referred to as query optimization problem (QOP), that requires super-exponential time in the worst-case.

Even though query optimization is a fundamental problem that has been studied for decades now, related work often focuses only on a specific subtask like join ordering. Furthermore, by inspecting open-source database systems, fundamentally different query optimization strategies can be observed. These strategies exhibit vastly different optimization times while having a major impact on the resulting QEP qualities. In this work, we revisit two conceptually different approaches to solve query optimization, namely split and holistic. We discuss their advantages and disadvantages and present a detailed experimental evaluation in our research database system mu t able. Additionally, we propose a hybrid strategy called top-k that is able to rediscover the holistically optimal QEPs while being significantly closer to the optimization time of split.