GENE: Genetische Generische Generierung von Indexstrukturen

• Antragsteller: Professor Dr. Jens Dittrich
• Fachliche Zuordnung: Datenmanagement, datenintensive Systeme, Informatik-Methoden in der Wirtschaftsinformatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 513858547

In Datenbankmanagementsystemen (DBMS) sind effiziente Indexstrukturen einer der grundlegendsten Bausteine. Indexstrukturen sind notwendig, um beliebig große, heterogene und verteilte Datenbestände effizient durchsuchen zu können. Als Konsequenz ermöglichen Indexstrukturen einen hohen Transaktionsdurchsatz. Heutzutage werden Indexstrukturen manuell entwickelt, d.h. erfahrene Forscher*innen oder Software-Architekt*innen entwerfen und implementieren diese Indexstrukturen. In diesem Projekt wollen wir diese Art performance-kritische und wichtige Bausteine wie Indexstrukturen zu entwickeln vollständig über Bord werfen. Inspiriert vom großen Erfolg der automatischen relationalen Anfrageoptimierung wollen wir ein analoges Konzept erforschen: wir betrachten die Erzeugung von Indexstrukturen analog zur Erzeugung von Anfrageplänen aus SQLStatements als Optimierungsproblem. So wie ein Anfrageplan aus physischen Operatoren zusammengesetzt wird, setzen wir Indexstrukturen aus Komponenten zusammen. Dieser Ansatz erlaubt es uns, für einen gegebenen Datensatz und eine Menge von Anfragen (den Workload) automatisch die geeignetste Indexstruktur zu generieren. Im Gegensatz zur Optimierung von Anfrageplänen, bei denen potentiell für jedes SQL-Statement eine neue Optimierung angestoßen wird, müssen wir den Optmierungsprozess für Indexstrukturen nur sehr selten anstoßen. Wir haben in Vorarbeiten [DN20, DNS21] bereits das große Potenzial dieses Ansatzes zeigen können. Bereits jetzt kann unser Optimierungsverfahren gängige Indexstrukturen wiederentdecken. Das übergeordnete Ziel unseres Projektantrages GENE ist es, ein robustes und effizientes Framework für die automatische Indexstrukturerstellung zu entwickeln. Es soll die Performanz aktueller, manuell entworfener Indexstrukturen erreichen und übertreffen. Um dieses Ziel zu erreichen, müssen wir drei prinzipielle Probleme lösen: (1.) Wir müssen skalierbare Indexstrukturgenerierungsalgorithmen entwerfen, die mit der Komplexität des Suchraums umgehen können. (2.) Wir benötigen eine klare Abstraktion für die Komponenten einer Indexstruktur vergleichbar mit der Abstraktion eines Anfrageplans in Operatoren. Diese Abstraktion muss für Optimierungsalgorithmen geeignet sein. (3.) Wir müssen einen effizienten Compiler entwickeln, der Indexstrukturen in effizienten Code umsetzt. Dies ist notwendig, um den Preis der Abstraktion und Generizität zu kompensieren und damit letztendlich konkurrenzfähig zu manuell entworfenen Indexstrukturen zu sein. Dieses Projekt wird versuchen, all diese wesentlichen Probleme zu lösen. Wir sind uns bewusst, dass diese Forschung ehrgeizig und riskant ist. Gleichzeitig glauben wir, dass unser Ansatz, wenn er sich als erfolgreich erweist, die Art und Weise, wie wir in den vergangenen Jahrzehnten über die Konzeption von Indexstrukturen nachgedacht haben, komplett umkrempeln kann.

• DFG-Verfahren: Sachbeihilfen