{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T11:06:20Z","timestamp":1790075180377,"version":"4.0.1"},"reference-count":88,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T00:00:00Z","timestamp":1780876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"NSF","award":["2216964"],"award-info":[{"award-number":["2216964"]}]},{"name":"NSF","award":["2143061"],"award-info":[{"award-number":["2143061"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,6,8]]},"abstract":"<jats:p>Trees can accelerate queries that search or aggregate values over large collections. They achieve this by storing metadata that enables quick pruning (or inclusion) of subtrees when predicates on that metadata can prove that none (or all) of the data in a subtree affect the query result. Existing systems implement this pruning logic manually for each query predicate and data structure. We generalize and mechanize this class of optimization. Our method derives conditions for when subtrees can be pruned (or included wholesale), expressed in terms of the metadata available at each node. We efficiently generate these conditions using symbolic interval analysis, extended with new rules to handle geometric predicates (e.g., intersection, containment). Additionally, our compiler fuses compound queries (e.g., reductions on filters) into a single tree traversal. These techniques enable the automatic derivation of generalized single-index and dual-index tree joins that support a wide class of join predicates beyond standard equality and range predicates. The generated traversals match the behavior of expert-written code that implements query-specific traversals, and can asymptotically outperform the linear scans and nested-loop joins that existing systems fall back to when hand-written cases do not apply.<\/jats:p>","DOI":"10.1145\/3808256","type":"journal-article","created":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T18:04:09Z","timestamp":1780941849000},"page":"226-252","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Bonsai: Compiling Queries to Pruned Tree Traversals"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6221-1389","authenticated-orcid":false,"given":"Alexander J","family":"Root","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8493-1133","authenticated-orcid":false,"given":"Christophe","family":"Gyurgyik","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2618-092X","authenticated-orcid":false,"given":"Purvi","family":"Goel","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8754-0429","authenticated-orcid":false,"given":"Kayvon","family":"Fatahalian","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6243-9543","authenticated-orcid":false,"given":"Jonathan","family":"Ragan-Kelley","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6766-670X","authenticated-orcid":false,"given":"Andrew","family":"Adams","sequence":"additional","affiliation":[{"name":"Adobe Research, San Francisco, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2267-903X","authenticated-orcid":false,"given":"Fredrik","family":"Kjolstad","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,8]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"113","volume-title":"Proceedings of the Conference on High Performance Graphics (Saarbrucken, Germany) (HPG \u201910)","author":"Aila Timo","year":"2010","unstructured":"Timo Aila and Tero Karras. 2010. Architecture considerations for tracing incoherent rays. In Proceedings of the Conference on High Performance Graphics (Saarbrucken, Germany) (HPG \u201910). Eurographics Association, Goslar, DEU, 113\u2013122."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1572769.1572792"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.2312\/cgvc.20141206"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1038\/324446a0"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3675377"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3231578.3231581"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_3_2_9_2","volume-title":"Designing Languages for Parallel Portability of Physical Simulations, Using Relational Algebraic Abstractions","author":"Bernstein Gilbert Louis","year":"2019","unstructured":"Gilbert Louis Bernstein. 2019. Designing Languages for Parallel Portability of Physical Simulations, Using Relational Algebraic Abstractions. Ph.D. Dissertation. Stanford University."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507751"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3563338"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276493"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1291151.1291199"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509511"},{"key":"e_1_3_2_18_2","first-page":"803","volume-title":"Proceedings of the Fourth International Symposium on Spatial Data Handling","author":"Egenhofer Max J.","year":"1990","unstructured":"Max J. Egenhofer and John Herring. 1990. AMathematical Framework for the Definition of Topological Relationships. In Proceedings of the Fourth International Symposium on Spatial Data Handling. International Geographical Union, Zurich, Switzerland, 803\u2013813. https:\/\/web.archive.org\/web\/20100614161335\/http:\/\/www.spatial.maine.edu\/~max\/MJEJRHSDH1990.pdf Accessed: 2025-05-01."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/SSDBM.2007.10"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.70230"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/1121584"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3680528.3687619"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277725"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-015-0830-y"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03730-6_10"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2492045.2492054"},{"key":"e_1_3_2_28_2","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob et al. 2010. Eigen v3. http:\/\/eigen.tuxfamily.org."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3808253"},{"key":"e_1_3_2_31_2","first-page":"101","volume-title":"Generalized search trees for database systems","author":"Hellerstein Joseph M.","year":"1998","unstructured":"Joseph M. Hellerstein, Jeffrey F. Naughton, and Avi Pfeffer. 1998. Generalized search trees for database systems. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 101\u2013112."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485505"},{"key":"e_1_3_2_33_2","unstructured":"Richard D. Hipp and The SQLite Development Team. 2025. SQLite. Available at https:\/\/www.sqlite.org\/. Accessed: October 19 2025."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.commatsci.2019.04.004"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356506"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/2383795.2383801"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/15886.15916"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392429"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831362"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3473596"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01377.x"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3689721"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-018-0329-2"},{"key":"e_1_3_2_45_2","unstructured":"Morgan McGuire. 2017. Computer Graphics Archive. https:\/\/casual-effects.com\/data https:\/\/casual-effects.com\/data."},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2669983"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.142662"},{"key":"e_1_3_2_48_2","unstructured":"Don P. Mitchell. 1991. Three Applications of Interval Analysis in Computer Graphics. In Frontiers of Rendering Course Notes. ACM SIGGRAPH. Course No. 14 SIGGRAPH \u201991."},{"issue":"2","key":"e_1_3_2_49_2","first-page":"40","article-title":"Spatio-temporal Access Methods","volume":"26","author":"Mokbel Mohamed F.","year":"2003","unstructured":"Mohamed F. Mokbel, Thanaa M. Ghanem, and Walid G. Aref. 2003. Spatio-temporal Access Methods. IEEE Data Engineering Bulletin 26, 2 (2003), 40\u201349.","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485496"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428234"},{"issue":"2","key":"e_1_3_2_53_2","first-page":"46","article-title":"Spatio-Temporal Access Methods: Part 2 (2003 - 2010)","volume":"33","author":"Nguyen-Dinh Long-Van","year":"2010","unstructured":"Long-Van Nguyen-Dinh, Walid G. Aref, and Mohamed F. Mokbel. 2010. Spatio-Temporal Access Methods: Part 2 (2003 - 2010). IEEE Data Eng. Bull. 33, 2 (2010), 46\u201355. http:\/\/sites.computer.org\/debull\/A10june\/Aref.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","unstructured":"Jia Pan Sachin Chitta and Dinesh Manocha. 2012. FCL: A general purpose library for collision and proximity queries. In 2012 IEEE International Conference on Robotics and Automation. 3859\u20133866. doi:10.1109\/ICRA.2012.6225337","DOI":"10.1109\/ICRA.2012.6225337"},{"key":"e_1_3_2_55_2","first-page":"87","volume-title":"Proceedings of the Conference on High Performance Graphics (Saarbrucken, Germany) (HPG \u201910)","author":"Pantaleoni J.","year":"2010","unstructured":"J. Pantaleoni and D. Luebke. 2010. HLBVH: hierarchical LBVH construction for real-time ray tracing of dynamic geometry. In Proceedings of the Conference on High Performance Graphics (Saarbrucken, Germany) (HPG \u201910). Eurographics Association, Goslar, DEU, 87\u201395."},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322955"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3136040.3136044"},{"key":"e_1_3_2_58_2","volume-title":"Physically Based Rendering: From Theory to Implementation","author":"Pharr Matt","year":"2023","unstructured":"Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2023. Physically Based Rendering: From Theory to Implementation (4 ed.). MIT Press. https:\/\/mitpress.mit.edu\/9780262048026\/physically-based-rendering\/","edition":"4"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185528"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462176"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3365663"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-51074-9_9"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3623278.3624768"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","unstructured":"Alexander J Root Gyurgyik Christophe Goel Purvi Kayvon Fatahalian Jonathan Ragan-Kelley Adams Andrew and Fredrik Berg Kjolstad. 2026. Artifact for PLDI 2026 Paper: Bonsai: Compiling Queries into Work-Efficient Tree Traversals. doi:10.5281\/zenodo.19091467","DOI":"10.5281\/zenodo.19091467"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/3689752"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314626"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.5555\/1076819"},{"key":"e_1_3_2_69_2","unstructured":"Rohan Sawhney. 2021. FCPW: Fastest Closest Points in the West."},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392374"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/3365655"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/3652605"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/142920.134024"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598601"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610515"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1145\/3649820"},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196893"},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.1145\/3675380"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","DOI":"10.1145\/1618452.1618488"},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00508"},{"key":"e_1_3_2_82_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"e_1_3_2_83_2","first-page":"41","volume-title":"Proceedings of High Performance Graphics (Lyon, France) (HPG \u201914)","author":"Woop Sven","year":"2014","unstructured":"Sven Woop, Carsten Benthin, Ingo Wald, Gregory S. Johnson, and Eric Tabellion. 2014. Exploiting local orientation similarity for efficient ray traversal of hair and fur. In Proceedings of High Performance Graphics (Lyon, France) (HPG \u201914). Eurographics Association, Goslar, DEU, 41\u201349."},{"key":"e_1_3_2_84_2","unstructured":"Yichen Yang Phitchaya Phothilimthana Yisu Wang Max Willsey Sudip Roy and Jacques Pienaar. 2021. Equality Saturation for Tensor Graph Superoptimization. In Proceedings of Machine Learning and Systems A. Smola A. Dimakis and I. Stoica (Eds.) Vol. 3. 255\u2013268. https:\/\/proceedings.mlsys.org\/paper_files\/paper\/2021\/file\/cc427d934a7f6c0663e5923f49eba531-Paper.pdf"},{"key":"e_1_3_2_85_2","doi-asserted-by":"publisher","DOI":"10.1145\/3550454.3555430"},{"key":"e_1_3_2_86_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2025.34"},{"key":"e_1_3_2_87_2","doi-asserted-by":"publisher","DOI":"10.1145\/3498696"},{"key":"e_1_3_2_88_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276491"},{"key":"e_1_3_2_89_2","doi-asserted-by":"publisher","DOI":"10.1145\/3722212.3724447"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3808256","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3808256","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T10:43:16Z","timestamp":1790073796000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3808256"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,8]]},"references-count":88,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2026,6,8]]}},"alternative-id":["10.1145\/3808256"],"URL":"https:\/\/doi.org\/10.1145\/3808256","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,8]]},"assertion":[{"value":"2025-11-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}