Parachute: Single-Pass Bi-Directional Information Passing

|—––|—––| | Paper | Parachute: Single-Pass Bi-Directional Information Passing (PDF) | | Konferenz | VLDB 2025 |

Zusammenfassung

Sideways Information Passing ist eine bekannte Technik, um die Auswirkungen großer Build-Seiten in einem Datenbank-Anfrageplan abzumildern. In Produktionssystemen ermöglicht Sideways Information Passing derzeit nur einen unidirektionalen Informationsfluss, im Gegensatz zu instanzoptimalen Algorithmen wie dem von Yannakakis. Letztere benötigen jedoch einen zusätzlichen Durchlauf über die Eingabe, was die Übernahme in Produktionssystemen erschwert.

In diesem Beitrag machen wir einen Schritt hin zu einpassigem bidirektionalem Information Passing während der Anfrageausführung. Wir erreichen das, indem wir statisch analysieren, zwischen welchen Tabellen der Informationsfluss blockiert ist, und indem wir vorberechnete join-induzierte Fingerprint-Spalten auf FK-Tabellen nutzen. Auf dem JOB-Benchmark verbessert Parachute die End-to-End-Ausführungszeit von DuckDB v1.2 ohne bzw. mit Semi-Join-Filterung um das 1,54- bzw. 1,24-Fache, wenn 15 % zusätzlicher Speicher erlaubt sind.