Decompose and Conquer: Fast Query Processing via Decomposition

A core task of database systems is to provide efficient querying facilities. As big queries (e.g., queries automatically generated by analytical tools) are becoming more and more common, new challenges arise for query optimization and evaluation. It has been observed that traditional cost-based query optimization reaches its limits: a significant shortcoming of this approach is that it does not pay sufficient attention to structural properties of the query. Recently, considerable progress has been made in the area of (hyper-)graph based methods of decomposing queries. Here, the idea is to turn a query into an acyclic one by computing small joins involving only 2 or 3 relations. By a landmark result of Yannakakis, acyclic queries can be evaluated efficiently without the risk of any explosion of intermediate results. However, the big drawback of decomposition-based query answering is that it completely ignores relevant properties of the data such as statistics, dependencies, indexes, etc. The goal of this project is to bring these two, so far isolated, paradigms together. The main research questions are concerned with (1) integrating cost-based optimization into query decompositions and (2) integrating query decompositions into today's query optimizers. By combining the strengths of the two approaches, we will pave the way for a new generation of query engines – leading to data management tools capable of dealing with "Big Data" and ‘Big Queries".