„Zucht“ extrem schneller Datenbanken Forscher wollen den Turbo für Big Data einlegen

Anbieter zum Thema

Windhoff Group

Universität des Saarlandes

An der Universität des Saarlandes arbeitet ein Team um Informatik-Professor Dr. Jens Dittrich an einem disruptiven Ansatz zur Optimierung von Datenbanken. Evolutionäre Algorithmen sollen dabei die bestmöglichen Ergebnisse „züchten“.

Das Forscherteam denkt dazu althergebrachte Weisheiten der Datenwissenschaft völlig neu. Dabei geht es vor allem um zwei der wichtigsten Ressourcen unserer Zeit: Daten und Datenbanken. Im Fokus stehen dabei sogenannte Indexstrukturen. Sie bezeichnen die Art und Weise, wie auf eine Datenbank zugegriffen wird.

Gängige Methoden sind gut, aber nicht optimal

„Indexstrukturen sind für die Arbeit mit Datenbanken unerlässlich, denn damit lassen sich gespeicherte Daten schnell und effizient auffinden“, erklärt Prof. Dittrich. Indizes würden die Suche enorm beschleunigen, da nicht mehr die gesamte Datenbank durchsucht werden müsse. Jeder kenne etwa Bibliothekskataloge. „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 Dittrich.

Dementsprechend sind Indexstrukturen in der Informatik gut erforscht. Über Jahrzehnte hinweg wurden manuell Organisationsmethoden entwickelt, die zwar für unterschiedlichste Anwendungsfälle gut funktionieren, aber in keinem Fall wirklich optimiert sind. Gemeinsam mit seinem Team hat Dittrich nun einen Ansatz vorgestellt, der für jede Datenbank und jeden Anwendungsfall passgenaue Indexstrukturen automatisch erzeugen soll.

Evolutionäre Algorithmen im Einsatz

Die Forscher haben ihre Methode „Genetische Generische Generierung von Indexstrukturen“ (GENE) getauft. Sie basiert auf sogenannten evolutionären Algorithmen, einer speziellen Art von Optimierungsalgorithmen. Sie emulieren den natürlichen Prozess der Evolution. „Startpunkt ist ein ‚normaler‘, nicht optimierter Index. Von diesem werden, ähnlich wie in der Evolution, zufällige Mutationen erzeugt. Diese werden gemäß ihrer Leistungsfähigkeit sortiert und nur die besten werden in der nächsten Generation weitergeführt“, verdeutlicht Dittrich. Diese Schritte würden so lange wiederholt, bis sich keine nennenswerten Verbesserungen mehr zwischen den Generationen einstellen.

Bisher wurden Indexstrukturen wie abgeschlossene Systeme behandelt. So nutzte man beispielsweise für manche Probleme Baumstrukturen und für andere Hashtabellen. „Wir aber betrachten alle bisherigen Indexstrukturen so, als hätten sie einen gemeinsamen ‚Vorfahren‘“, sagt Dittrich. Auf diese Weise könne man diese „Meta-Indexstruktur“ mutieren und die besten Eigenschaften heute geläufiger Indexstrukturen miteinander kombinieren – und dies individuell auf jede Datenbank und jeden Anwendungsfall optimiert. „So wollen wir für jede Datenbank eine perfekt passende und effiziente Indexstruktur ‚züchten‘, die die bisherige in der Performanz übertrifft“, ist der Professor zuversichtlich.

Noch handelt es sich um Grundlagenforschung, doch erstes Potenzial wurde bereits in Vorarbeiten sichtbar: Gängige Indexstrukturen, die zuvor über Jahrzehnte hinweg händisch entwickelt wurden, konnten „wiederentdeckt“, also automatisch erzeugt oder repliziert werden.

Die vollständige 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.

(ID:49468458)