Parachute: Single-Pass Bi-Directional Information Passing
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908409092112384 |
|---|---|
| author | Stoian, Mihail Zimmerer, Andreas Krid, Skander Ngom, Amadou Latyr Ding, Jialin Kraska, Tim Kipf, Andreas |
| author_facet | Stoian, Mihail Zimmerer, Andreas Krid, Skander Ngom, Amadou Latyr Ding, Jialin Kraska, Tim Kipf, Andreas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_13670 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parachute: Single-Pass Bi-Directional Information Passing Stoian, Mihail Zimmerer, Andreas Krid, Skander Ngom, Amadou Latyr Ding, Jialin Kraska, Tim Kipf, Andreas Databases 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. |
| title | Parachute: Single-Pass Bi-Directional Information Passing |
| topic | Databases |
| url | https://arxiv.org/abs/2506.13670 |