Bonsai: Compiling Queries to Pruned Tree Traversals
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_ | 1866914498595520512 |
|---|---|
| author | Root, Alexander J Gyurgyik, Christophe Goel, Purvi Fatahalian, Kayvon Ragan-Kelley, Jonathan Adams, Andrew Kjolstad, Fredrik |
| author_facet | Root, Alexander J Gyurgyik, Christophe Goel, Purvi Fatahalian, Kayvon Ragan-Kelley, Jonathan Adams, Andrew Kjolstad, Fredrik |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_15000 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bonsai: Compiling Queries to Pruned Tree Traversals Root, Alexander J Gyurgyik, Christophe Goel, Purvi Fatahalian, Kayvon Ragan-Kelley, Jonathan Adams, Andrew Kjolstad, Fredrik Programming Languages Databases D.3 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. |
| title | Bonsai: Compiling Queries to Pruned Tree Traversals |
| topic | Programming Languages Databases D.3 |
| url | https://arxiv.org/abs/2511.15000 |