Reaching Back to Move Forward: Using Old Ideas to Achieve a New Level of Query Optimization

Abstract

Join queries involving many relations pose a severe challenge to today’s query optimisation techniques. To some extent, this is due to the fact that these techniques do not pay sufficient attention to structural properties of the query. In stark contrast, the Database Theory community has intensively studied structural properties of queries (such as acyclicity and various notions of width) and proposed efficient query evaluation techniques through variants of Yannakakis’ algorithm for many years. However, although most queries in practice actually are acyclic or have low width, structure-guided query evaluation techniques based on Yannakakis’ algorithm have not found their way into mainstream database technology yet. The goal of this work is to address this gap between theory and practice. We want to analyse the potential of considering the query structure for speeding up modern DBMSs in cases that have been traditionally challenging. To this end, we propose a rewriting of SQL queries into a sequence of SQL statements that force the DBMS to follow a Yannakakis-style query execution. Through first empirical results we show that structure-guided query evaluation can indeed make the evaluation of many difficult join queries significantly faster.