GENE: Genetic, Generic Generation of Index Structures

• Applicant: Professor Dr. Jens Dittrich
• Subject Area: Data Management, Data-Intensive Systems, Computer Science Methods in Business Informatics
• Term: since 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 513858547

In database management systems (DBMS), efficient index structures are one of the most fundamental building blocks. Index structures are necessary to efficiently search arbitrarily large, heterogeneous, and distributed datasets. As a consequence, index structures enable high transaction throughput. Today, index structures are designed and conceived manually, i.e. experienced researchers and architects actively design, develop, and implement these index structures. In this project we want to discard the idea of handcrafting such a performance-critical and important component like an index structure. Inspired by the success of automatic relational query optimization, we want to explore an analogous concept to create index structures: we consider creating an index structure as an optimization problem much like creating query plans is an optimization problem. Like that, we can automatically generate the most suitable index structure for a given dataset and workload. In contrast to query plans which are potentially created for each and every incoming SQL statement, we rarely have to run the actual optimization process for index structures. We build upon very promising initial experimental results [DN20, DNS21] in which we show that our genetic optimization algorithm can rediscover state-of-the-art index structures automatically. The overall goal of our project proposal GENE is to develop a robust and efficient framework for automatic index creation that can match and outperform existing hand-optimized index structures. To reach that goal, we must solve three principal problems: (1) Develop scalable index structure generation algorithms that can cope with the complexity of the search space, (2) Devise a clear “relational algebra”-style abstraction of the different components of an index structure that is suitable for optimization. (3) Develop an efficient index structure compiler that overcomes the price of genericity and thus is able to compete with hand-tuned index structures. This project will try to answer all of these principal problems. We are aware that this research is ambitious and risky. At the same time, we believe that if our approach turns out to be successful, it can completely overturn how we have been thinking about index structure design in the past decades.

• DFG Programme: Research Grants