Informatiker will effiziente Datenbanken «züchten»

Das Team von Jens Dittrich nutzt sogenannte evolutionäre Algorithmen, um die bestmöglichen Ergebnisse zu «züchten». Das Papier, in dem sie das Konzept vorstellen, veröffentlichten sie auf einer der weltgrössten Fachkonferenzen zu Datenbanken. Die Ausarbeitung der Methode wird nun von der Deutschen Forschungsgemeinschaft gefördert.

Das Team um Jens Dittrich, Professor für «Big Data Analytics» der Universität des Saarlandes, denkt althergebrachte Weisheiten der Datenwissenschaft völlig neu. Dabei geht es um zwei der wichtigsten Ressourcen unserer Zeit: Daten und Datenbanken. Ob bei einfachen Suchanfragen im Internet, der Erforschung weltbewegender Ereignisse wie dem Klimawandel oder beim Einsatz und der Entwicklung von Zukunftstechnologien wie KI-Chatbots: Daten sind der Treibstoff der modernen digitalen Technologie und Datenbanken sind die Werkzeuge, die dabei helfen, diese Daten zu organisieren, zu speichern und zu analysieren. Täglich kommt jeder damit in Kontakt, mal mehr, mal weniger bewusst.

Der Teil der Datenverarbeitung, mit dem sich die Saarbrücker Informatiker befassen, sind sogenannte Indexstrukturen. Also die Art und Weise, wie auf eine Datenbank zugegriffen wird. «Indexstrukturen sind für die Arbeit mit Datenbanken unerlässlich, denn damit lassen sich gespeicherte Daten schnell und effizient auffinden. Indexe beschleunigen die Suche enorm, da nicht mehr die gesamte Datenbank durchsucht werden muss», erläutert der Professor, der am Saarland Informatics Campus forscht. Jeder wisse, wie etwa Bibliothekskataloge sortiert seien. «In der Informatik sind die Daten jedoch oft sehr komplex und in gigantischen Mengen vorhanden, sodass man ausgeklügeltere Methoden für das Indexieren benötigt», so Professor Dittrich weiter.

Indexstrukturen sind in der Informatik deshalb gut erforscht. Über Jahrzehnte hinweg wurden «von Hand» Organisationsmethoden entwickelt, die zwar bei einer breiten Palette von Anwendungsfällen vergleichsweise gut funktionieren, aber für keinen wirklich optimiert sind. Dittrich stellt mit seinem Team nun einen Ansatz vor, mit dem sich für jede Datenbank und jeden Anwendungsfall passgenaue Indexstrukturen automatisch erzeugen lassen sollen.

Die Methode nennen sie «Genetische Generische Generierung von Indexstrukturen (GENE)». Sie basiert auf sogenannten «evolutionären Algorithmen», einer speziellen Art der Optimierungsalgorithmen. Mit diesen wird der natürliche Prozess der Evolution emuliert. «Startpunkt ist ein ‹normaler›, nicht optimierter Index. Von diesem werden, ähnlich wie in der Evolution, zufällige Mutationen erzeugt. Diese werden gemäss ihrer Leistungsfähigkeit sortiert und nur die besten werden in der nächsten Generation weitergeführt. Diese Schritte werden so lange wiederholt, bis sich keine nennenswerten Verbesserungen mehr zwischen den Generationen einstellen», erklärt Dittrich.

Bisher wurden Indexstrukturen wie abgeschlossene Systeme behandelt. «Man sagte zum Beispiel, dass für manche Probleme am besten Baumstrukturen als Organisationsmethode passten, während man bei anderen besser Hashtabellen verwenden sollte. Wir aber betrachten alle bisherigen Indexstrukturen so, als hätten sie einen gemeinsamen ‹Vorfahren›», sagt Dittrich. Das erlaubt den Forschern, diese «Meta-Indexstruktur» zu mutieren und die besten Eigenschaften heute geläufiger Indexstrukturen miteinander zu kombinieren, und zwar für jede Datenbank und jeden Anwendungsfall individuell optimiert. «So wollen wir für jede Datenbank eine perfekt passende und effiziente Indexstruktur ‹züchten›, die die bisherige in der Performanz übertrifft», erläutert der Professor. In Vorarbeiten konnte das Team das grosse Potenzial dieses Ansatzes bereits zeigen: Gängige Indexstrukturen, die zuvor über Jahrzehnte hinweg von Hand entwickelt wurden, können damit «wiederentdeckt», also automatisch erzeugt oder repliziert werden.

Angewendet wird die Entwicklung des Teams um Jens Dittrich noch nicht, da es sich dabei um Grundlagenforschung handelt. Aber wie es die Natur von Grundlagenforschung ist, könnte sich das in Zukunft radikal ändern, denn die Menge der produzierten Daten steigt rasant. Zukünftig könnten also höchst optimierte Methoden, wie die von Jens Dittrich, die diese explodierenden Datenmengen schnell durchsuchen und damit verarbeiten können, immer wichtiger werden.

Die Arbeit unter dem Titel «The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures» wurde in den Proceedings der «International Conference on Very Large Data Bases (VLDB)» veröffentlicht.

Publikation:
Jens Dittrich, Joris Nix, Christian Schön: «The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures», Proceedings of the VLDB Endowment, Vol. 15(3): 527-540 (2021)
https://www.vldb.org/pvldb/vol15/p527-dittrich.pdf