Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

preprint · arXiv (Cornell University) · 2023

Adaptive Recursive Query Optimization

Anna Herlihy, Guillaume Martres, Anastasia Ailamaki, Martin Odersky

Cited by 0Open access

Abstract

Performance-critical industrial applications, including large-scale program, network, and distributed system analyses, are increasingly reliant on recursive queries for data analysis. Yet traditional relational algebra-based query optimization techniques do not scale well to recursive query processing due to the iterative nature of query evaluation, where relation cardinalities can change unpredictably during the course of a single query execution. To avoid error-prone cardinality estimation, adaptive query processing techniques use runtime information to inform query optimization, but these systems are not optimized for the specific needs of recursive query processing. In this paper, we introduce Adaptive Metaprogramming, an innovative technique that shifts recursive query optimization and code generation from compile-time to runtime using principled metaprogramming, enabling dynamic optimization and re-optimization before and after query execution has begun. We present a custom join-ordering optimization applicable at multiple stages during query compilation and execution. Through Carac, a custom Datalog engine, we evaluate the optimization potential of Adaptive Metaprogramming and show unoptimized recursive query execution time can be improved by three orders of magnitude and hand-optimized queries by 6x.

Cite this paper

APA 7

Herlihy, A., Martres, G., Ailamaki, A., & Odersky, M. (2023). Adaptive Recursive Query Optimization. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2312.04282

MLA 9

Herlihy, Anna, et al. “Adaptive Recursive Query Optimization.” arXiv (Cornell University), 2023, https://doi.org/10.48550/arxiv.2312.04282.

Chicago

Herlihy, Anna, Guillaume Martres, Anastasia Ailamaki, and Martin Odersky. 2023. “Adaptive Recursive Query Optimization.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2312.04282.

Harvard

Herlihy, A. et al. (2023) ‘Adaptive Recursive Query Optimization’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.2312.04282.

BibTeX
@misc{herlihy2023adaptive,
  title = {{Adaptive Recursive Query Optimization}},
  author = {Herlihy, Anna and Martres, Guillaume and Ailamaki, Anastasia and Odersky, Martin},
  journal = {arXiv (Cornell University)},
  year = {2023},
  doi = {10.48550/arxiv.2312.04282}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.

Related papers