Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees

Zusammenfassung

Azyklische konjunktive Anfragen bilden das Rückgrat der meisten analytischen Workloads und wurden in der Literatur sowohl theoretisch als auch praktisch ausführlich untersucht. Zwischen Theorie und Praxis klafft jedoch noch eine große Lücke. Der 40 Jahre alte Yannakakis-Algorithmus bietet starke theoretische Laufzeitgarantien, wurde in realen Systemen aber wegen seines hohen versteckten Konstantenfaktors nicht übernommen. In diesem Beitrag wollen wir diese Lücke schließen und schlagen Yannakakis+ vor, eine verbesserte Version des Yannakakis-Algorithmus, die praxisnäher effizient ist und die theoretischen Garantien bewahrt. Unsere Experimente zeigen, dass Yannakakis+ den ursprünglichen Yannakakis-Algorithmus über eine breite Palette von Anfragen und Datensätzen hinweg durchgängig um das 2- bis 5-Fache übertrifft.

Eine weitere angenehme Eigenschaft unseres neuen Algorithmus: Er erzeugt einen klassischen DAG-Anfrageplan aus Standard-Operatoren der Relationenalgebra, sodass sich Yannakakis+ leicht in jede gängige SQL-Engine einfügen lässt. Unser Systemprototyp unterstützt derzeit vier SQL-Engines (DuckDB, PostgreSQL, SparkSQL und AnalyticDB von Alibaba Cloud). Die Experimente zeigen, dass Yannakakis+ bei 160 von 162 getesteten Anfragen bessere Leistung liefert als deren native Anfragepläne, mit einer durchschnittlichen Beschleunigung von 2,41× und einer maximalen Beschleunigung von 47.059×.