Presto’s History-based Query Optimizer

Summary: Records execution histories to predict intermediate cardinalities and operator costs for complex query shapes, replacing brittle analytic estimators. Lightweight, adaptive HBO uses a Redis-backed statistics store to optimize similar future queries and is production-deployed at Meta and Uber. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h5b87d73db6f99446
Venue: VLDB
Year: 2024
Pagerank: 5.2078543e-05
Overall Rank: 9,141 | 38.73%
DOI: 10.14778/3685800.3685828
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Pranjal Shankhdhar (Meta)
2. Feilong Liu (Meta)
3. Jay Narale (Uber)
4. James Sun (Meta)
5. Rebecca Schlussel (Meta)
6. Lyublena Antova (Meta)

BibTeX Citation

@article{shankhdhar_vldb24,
        title = {{Presto’s History-based Query Optimizer}},
        author = {Shankhdhar, Pranjal and Liu, Feilong and Narale, Jay and Sun, James and Schlussel, Rebecca and Antova, Lyublena},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {12},
        pages = {4077--4089},
        doi = {10.14778/3685800.3685828},
        url = {https://doi.org/10.14778/3685800.3685828},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,903	ReSequel: Robust LLM-assisted Query Rewriting and Optimization using Templatization and Sampling	2026	VLDB	4.9605343e-05
11,005	OmniTable: A Unified Wide-Table System for Petabyte-Scale LLM Data Curation and Exploration	2026	VLDB	4.9605343e-05
11,011	Ultron: History-Based Query Optimization at Databricks	2026	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
31	Hive - A Warehousing Solution Over a Map-Reduce Framework	2009	VLDB	0.00049707539
142	Neo: A Learned Query Optimizer	2019	VLDB	0.00029114937
254	The History of Histograms (abridged)	2003	VLDB	0.00022999992
355	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00020146245
372	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019768921
689	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014725904
983	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00012677179
1,064	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012181459
1,281	Orca: A Modular Query Optimizer Architecture for Big Data	2014	SIGMOD	0.00011198917
1,511	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	0.00010408003
2,025	Query Optimization in Microsoft SQL Server PDW	2012	SIGMOD	9.1520946e-05
2,348	Learned Cardinality Estimation: An In-depth Study	2022	SIGMOD	8.5910072e-05
2,523	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB	8.3316032e-05
2,619	Zero-Shot Cost Models for Out-of-the-box Learned Cost Prediction	2022	VLDB	8.1985665e-05
2,852	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	7.9201312e-05
3,142	Statistics on Views	2003	VLDB	7.5858292e-05
3,847	Presto: A Decade of SQL Analytics at Meta	2023	SIGMOD	6.9668258e-05
4,683	AutoSteer: Learned Query Optimization for Any SQL Database	2023	VLDB	6.4545989e-05
4,724	Optimizer Plan Change Management: Improved Stability and Performance in Oracle 11g	2008	VLDB	6.433795e-05
4,798	Cost Models DO Matter: Providing Cost Information for Diverse Data Sources in a Federated System	1999	VLDB	6.3970893e-05
5,611	StatAdvisor: Recommending Statistical Views	2009	VLDB	6.0498181e-05
7,162	Sibyl: Forecasting Time-Evolving Query Workloads	2024	SIGMOD	5.5798063e-05
9,430	Intelligent Automated Workload Analysis for Database Replatforming	2022	SIGMOD	5.1658393e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,261	Sampling-Based Query Re-Optimization	2016	SIGMOD
2	5,101	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD
3	5,006	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD
4	4,088	Dynamically Optimizing Queries over Large Scale Data Platforms	2014	SIGMOD
5	10,979	Incremental Query Optimizer Statistics in Amazon Redshift	2026	VLDB
6	2,696	Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection	2022	VLDB
7	5,248	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD
8	2,025	Query Optimization in Microsoft SQL Server PDW	2012	SIGMOD
9	568	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
10	11,011	Ultron: History-Based Query Optimization at Databricks	2026	VLDB