2025/06/16 by Mihail Stoian, Stoian, Mihail, Andreas Zimmerer +12 · 1 voice · 2 citations
Computer Science · Decision Sciences · #Databases (cs.DB) #FOS: Computer and information sciences #Fingerprint (computing) #Information flow #Information system #Message passing #Personal Information Management and User Behavior #Production (economics) #Table (database) #cs.DB
paper · pdf · doi:10.48550/arxiv.2506.13670
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2025/06/16 · arxiv published 2025/06/16 · arxiv updated 2025/06/16 · openalex created_date 2025/10/13 · openalex updated_date 2026/08/05
Sideways information passing is a well-known technique for mitigating the impact of large build sides in a database query plan. As currently implemented in production systems, sideways information passing enables only a uni-directional information flow, as opposed to instance-optimal algorithms, such as Yannakakis'. On the other hand, the latter require an additional pass over the input, which hinders adoption in production systems. In this paper, we make a step towards enabling single-pass bi-directional information passing during query execution. We achieve this by statically analyzing between which tables the information flow is blocked and by leveraging precomputed join-induced fingerprint columns on FK-tables. On the JOB benchmark, Parachute improves DuckDB v1.2's end-to-end execution time without and with semi-join filtering by 1.54x and 1.24x, respectively, when allowed to use 15% extra space.