Deklarative Performanz für Datalog

• Antragsteller: Professor Dr. Sebastian Erdweg; Professor Dr. Felix Schuhknecht
• Fachliche Zuordnung: Softwaretechnik und Programmiersprachen ; Datenmanagement, datenintensive Systeme, Informatik-Methoden in der Wirtschaftsinformatik
• Förderung: Förderung seit 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 508316729

In letzter Zeit gewinnt Datalog in den verschiedensten Bereichen, wie beispielsweise in der Programmanalyse oder dem verteilten Rechnen, stetig mehr an Bedeutung als leistungsfähige und flexible Anfragesprache. Da es sich bei Datalog um eine deklarative Sprache handelt, muss ein Benutzer lediglich formulieren, welches Ergebnis eine Berechnung liefern soll, nicht aber, wie die Berechnung ausgeführt werden soll. Damit fällt die Erzeugung des eigentlichen Ausführungsplans vollständig in die Verantwortung der Datalog-Engine. Leider führen aktuelle Systeme im Zuge der Plangenerierung wenige bis keine automatischen Optimierungen durch. Bestenfalls verlassen sich die Systeme auf manuell annotierte Hinweise, die jedoch ein tiefes Verständnis der Verarbeitungs-Pipeline durch den Benutzer erfordern. Ein solches Expertenwissen ist nicht nur für die meisten Benutzer unerreichbar, sondern widerspricht auch der deklarativen Natur von Datalog. In der Praxis führt ein solcher Mangel an automatischer Anfrageoptimierung zu schwerwiegenden Performance-Problemen.In diesem Projekt verfolgen wir daher das Ziel, tatsächliche deklarative Performance in Datalog-Engines zu integrieren. Die Datalog-Engine soll in der Lage sein, ohne manuelle Eingriffe des Benutzers das deklarative Programm in einen hochoptimierten Ausführungsplan zu übersetzen. Dazu schlagen wir vor, eine Kombination aus (1) analytischen Optimierungen und (2) empirischen Optimierungen anzuwenden. Auf der analytischen Seite werden wir Datenflussanalysen für das gesamte Programm durchführen, die es uns ermöglichen, nicht-lokale Optimierungen, wie z.B. Constraint-Elimination oder Subquery-Spezialisierung, umzusetzen. Auf der empirischen Seite werden wir Strategien entwickeln, um den Ausführungsplan gegen repräsentative Eingabedaten in einer Feedback-Schleife zu evaluieren und physikalisch zu (re-)optimieren. Dadurch kann die Engine inkrementell die geeigneten Operatoren, physischen Layouts und Datenstrukturen identifizieren. Darüber hinaus werden wir das äußerst performance-kritische Join-Order-Problem betrachten, sowie die Identifizierung von Materialisierungsstrategien durch Kombination der Informationen aus den analytischen und empirischen Ansätzen bearbeiten. Im Zuge des Projektes werden wir die gesammelten Forschungsergebnisse in die weit verbreitete State-of-the-Art Datalog-Engine Soufflé integrieren, um unsere Ergebnisse unmittelbar für die Community nutzbar zu machen.

• DFG-Verfahren: Sachbeihilfen