SQL:Trek Automated Index Design at Airbnb

Download PDF

Abstract

Automating index design has been an active area of research for decades due to the significant impact that indexes have on query performance and database efficiency. Existing approaches range from brute-force search to cost-based optimizations and, more recently, machine learning techniques. However, many suffer from high computational costs, reliance on inaccurate cost models, or the need for deep integration with database internals. We introduce SQL:Trek, a time-efficient tool for automated index design that operates entirely as an external utility. SQL:Trek leverages query compiler cost models to identify effective indexes while mitigating false positives through execution on a lightweight simulation database. This approach enables fast, iterative index selection without modifying database internals, making it broadly applicable across relational databases, including most MySQL â and PostgreSQL â derivative databases. Our evaluation demonstrates that SQL:Trek delivers significant query performance improvements while keeping index selection computationally efficient, with most workloads analyzed in under five minutes. Unlike many cost-based what-if analysis methods, SQL:Trek significantly improved performance of many production workloads while avoiding the majority of detrimental index recommendations caused by optimizer misestimates. These results highlight SQL:Trek as a practical, scalable solution for automated index tuning in modern database environments. This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 18, No. 12 ISSN 2150-8097. doi:10.14778/3750601.3750638