{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T17:42:54Z","timestamp":1757612574622,"version":"3.44.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:p>\n            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\n            <jats:italic toggle=\"yes\">uni-directional<\/jats:italic>\n            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.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we make a step towards enabling\n            <jats:italic toggle=\"yes\">single-pass bidirectional<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.14778\/3748191.3748196","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:50:16Z","timestamp":1756993816000},"page":"3299-3311","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Parachute: Single-Pass Bi-Directional Information Passing"],"prefix":"10.14778","volume":"18","author":[{"given":"Mihail","family":"Stoian","sequence":"first","affiliation":[{"name":"University of Technology Nuremberg, Nuremberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Zimmerer","sequence":"additional","affiliation":[{"name":"University of Technology Nuremberg, Nuremberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Skander","family":"Krid","sequence":"additional","affiliation":[{"name":"University of Technology Nuremberg, Nuremberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amadou Latyr","family":"Ngom","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jialin","family":"Ding","sequence":"additional","affiliation":[{"name":"Amazon Web Services, Boston, Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Kraska","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Kipf","sequence":"additional","affiliation":[{"name":"University of Technology Nuremberg, Nuremberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Liese Bekkers Frank Neven Stijn Vansummeren and Yisu Remy Wang. 2024. Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores. arXiv:2411.04042 [cs.DB] https:\/\/arxiv.org\/abs\/2411.04042"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681995"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3662010.3663442"},{"key":"e_1_2_1_4_1","volume-title":"The Dimension-Join: A New Index for Data Warehouses. In XVI Simp\u00f3sio Brasileiro de Banco de Dados, 1\u20133 Outubro","author":"Bizarro Pedro","year":"2001","unstructured":"Pedro Bizarro and Henrique Madeira. 2001. The Dimension-Join: A New Index for Data Warehouses. In XVI Simp\u00f3sio Brasileiro de Banco de Dados, 1\u20133 Outubro 2001, Rio de Janeiro, Brasil, Anais\/Proceedings, Marta Mattoso and Geraldo Xex\u00e9o (Eds.). COPPE\/UFRJ, 259\u2013273."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_2_1_6_1","volume-title":"19th International Conference on Very Large Data Bases, August 24\u201327, 1993, Dublin, Ireland, Proceedings, Rakesh Agrawal, Se\u00e1n Baker, and David A. Bell (Eds.). Morgan Kaufmann, 505\u2013516","author":"Chen Ming-Syan","year":"1993","unstructured":"Ming-Syan Chen, Hui-I Hsiao, and Philip S. Yu. 1993. Applying Hash Filters to Improving the Execution of Bushy Trees. In 19th International Conference on Very Large Data Bases, August 24\u201327, 1993, Dublin, Ireland, Proceedings, Rakesh Agrawal, Se\u00e1n Baker, and David A. Bell (Eds.). Morgan Kaufmann, 505\u2013516. http:\/\/www.vldb.org\/conf\/1993\/P505.PDF"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3653379"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554842"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research.","author":"Gross Paul","year":"2025","unstructured":"Paul Gross, Dani\u00ebl ten Wolde, and Peter Boncz. 2025. Adaptive Factorization Using Linear-Chained Hash Tables. In Proceedings of the Conference on Innovative Data Systems Research."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497486"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_13_1","volume-title":"A fast alternative to the modulo reduction. https:\/\/lemire.me\/blog\/2016\/06\/27\/a-fast-alternative-to-the-modulo-reduction\/ Retrieved","author":"Lemire Daniel","year":"2025","unstructured":"Daniel Lemire. 2016. A fast alternative to the modulo reduction. https:\/\/lemire.me\/blog\/2016\/06\/27\/a-fast-alternative-to-the-modulo-reduction\/ Retrieved: March 1, 2025."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16863"},{"key":"e_1_2_1_15_1","volume-title":"VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24\u201327","author":"Moerkotte Guido","year":"1998","unstructured":"Guido Moerkotte. 1998. Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing. In VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24\u201327, 1998, New York City, New York, USA, Ashish Gupta, Oded Shmueli, and Jennifer Widom (Eds.). Morgan Kaufmann, 476\u2013487. http:\/\/www.vldb.org\/conf\/1998\/p476.pdf"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.52778"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476259"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_2_1_19_1","volume-title":"Freitag","author":"Neumann Thomas","year":"2020","unstructured":"Thomas Neumann and Michael J. Freitag. 2020. Umbra: A Disk-Based System with In-Memory Performance. In 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12\u201315, 2020, Online Proceedings. www.cidrdb.org. http:\/\/cidrdb.org\/cidr2020\/papers\/p29-neumann-cidr20.pdf"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/211990.212001"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2407.11418"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209950.3209955"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3653395"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3682031"},{"key":"e_1_2_1_26_1","volume-title":"Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries. In 14th Conference on Innovative Data Systems Research, CIDR 2024","author":"Yang Yifei","year":"2024","unstructured":"Yifei Yang, Hangdong Zhao, Xiangyao Yu, and Paraschos Koutris. 2024. Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries. In 14th Conference on Innovative Data Systems Research, CIDR 2024, Chaminade, HI, USA, January 14\u201317, 2024. www.cidrdb.org. https:\/\/www.cidrdb.org\/cidr2024\/papers\/p22-yang.pdf"},{"key":"e_1_2_1_27_1","volume-title":"7th International Conference, September 9\u201311","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In Very Large Data Bases, 7th International Conference, September 9\u201311, 1981, Cannes, France, Proceedings. IEEE Computer Society, 82\u201394."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611501"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Junyi Zhao Kai Su Yifei Yang Xiangyao Yu Paraschos Koutris and Huanchen Zhang. 2025. Debunking the Myth of Join Ordering: Toward Robust SQL Analytics. arXiv:2502.15181 [cs.DB] https:\/\/arxiv.org\/abs\/2502.15181","DOI":"10.1145\/3725283"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3090163.3090167"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.148"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3748191.3748196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:52:39Z","timestamp":1756993959000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3748191.3748196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":31,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10.14778\/3748191.3748196"],"URL":"https:\/\/doi.org\/10.14778\/3748191.3748196","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}