Towards a Converged Relational-Graph Optimization Framework

Zusammenfassung

Der jüngste Standard ISO SQL:2023 übernimmt SQL/PGQ (Property Graph Queries) und erleichtert graphartige Abfragen in relationalen Datenbanken. Dieser Fortschritt macht jedoch eine deutliche Lücke sichtbar: Wie lassen sich SQL/PGQ-Anfragen in relationalen Datenbanksystemen wirksam optimieren? Um diese Lücke zu schließen, erweitern wir die grundlegenden SPJ-Anfragen (Select-Project-Join) zu SPJM-Anfragen, die einen zusätzlichen Matching-Operator für Graph-Pattern-Matching in SQL/PGQ enthalten. SPJM-Anfragen lassen sich zwar in SPJ-Anfragen umwandeln und mit bestehenden relationalen Query-Optimierern optimieren, unsere Analyse zeigt jedoch, dass ein solches graph-agnostisches Verfahren nicht von graphspezifischen Optimierungstechniken aus der Literatur profitiert. Deshalb entwickeln wir RelGo, ein konvergiertes relational-graphisches Optimierungsframework für SPJM-Anfragen, das relationale und Graph-Query-Optimierung gemeinsam nutzt. Mit DuckDB als zugrundeliegender relationaler Ausführungsengine zeigen unsere Experimente, dass RelGo effiziente Ausführungspläne für SPJM-Anfragen erzeugen kann. Auf etablierten Benchmarks sind diese Pläne im Schnitt 21,90-mal schneller als die eines graph-agnostischen Optimierers.