Bao: Making Learned Query Optimization Practical

Summary: Bao is a bandit-based learned optimizer atop optimizers, offering per-query hints via Thompson sampling and tree-CNNs. Adapts to workload, data, and schema changes, improving end-to-end and tail latency; cloud tests show cost reductions and stronger performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h840803224e5b1dd4
Venue: SIGMOD
Year: 2021
Pagerank: 0.00019989474
Overall Rank: 362 | 97.57%
DOI: 10.1145/3448016.3452838

Incoming Non-self Citations Over Time

Authors

1. Ryan Marcus (Intel; Massachusetts Institute of Technology)
2. Parimarjan Negi (Massachusetts Institute of Technology)
3. Hongzi Mao (Massachusetts Institute of Technology)
4. Nesime Tatbul (Intel; Massachusetts Institute of Technology)
5. Mohammad Alizadeh (Massachusetts Institute of Technology)
6. Tim Kraska (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{marcus_sigmod21,
        title = {{Bao: Making Learned Query Optimization Practical}},
        author = {Marcus, Ryan and Negi, Parimarjan and Mao, Hongzi and Tatbul, Nesime and Alizadeh, Mohammad and Kraska, Tim},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3452838},
        url = {https://dl.acm.org/doi/10.1145/3448016.3452838},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 130 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,217	Refactoring Index Tuning Process with Benefit Estimation	2024	VLDB	5.5834823e-05
7,236	RCRank: Multimodal Ranking of Root Causes of Slow Queries in Cloud Database Systems	2025	VLDB	5.5790509e-05
7,367	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	5.5411636e-05
7,385	Towards Foundation Database Models	2025	CIDR	5.5385053e-05
7,410	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.5342768e-05
7,460	T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees	2025	SIGMOD	5.5215755e-05
7,598	SageDB: An Instance-Optimized Data Analytics System	2022	VLDB	5.4871733e-05
7,864	Blueprinting the Cloud: Unifying and Automatically Optimizing Cloud Data Infrastructures with BRAD	2024	VLDB	5.4367919e-05
7,977	The Holon Approach for Simultaneously Tuning Multiple Components in a Self-Driving Database Management System with Machine Learning via Synthesized Proto-Actions	2024	VLDB	5.4142519e-05
8,039	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	5.4017809e-05
8,332	Learned Offline Query Planning via Bayesian Optimization	2025	SIGMOD	5.3528188e-05
8,385	NeurDB: On the Design and Implementation of an AI-powered Autonomous Database	2025	CIDR	5.3420959e-05
8,389	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.3413016e-05
8,403	The Case for Learned In-Memory Joins	2023	VLDB	5.3389852e-05
8,524	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.3231221e-05
8,770	One Size Does Not Fit All: A Bandit-Based Sampler Combination Framework with Theoretical Guarantees	2022	SIGMOD	5.2812395e-05
8,850	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	5.2645282e-05
8,872	Tiresias: Enabling Predictive Autonomous Storage and Indexing	2022	VLDB	5.2584643e-05
8,962	GEqO: ML-Accelerated Semantic Equivalence Detection	2023	SIGMOD	5.2493925e-05
9,020	Optimizing the cloud? Don't train models. Build oracles!	2024	CIDR	5.2355482e-05
9,113	Presto’s History-based Query Optimizer	2024	VLDB	5.2276066e-05
9,115	Check Out the Big Brain on BRAD: Simplifying Cloud Data Processing with Learned Automated Data Meshes	2023	VLDB	5.2271833e-05
9,133	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	5.2229655e-05
9,276	BASE: Bridging the Gap between Cost and Latency for Query Optimization	2023	VLDB	5.204289e-05
9,300	GenJoin: Conditional Generative Plan-to-Plan Query Optimizer that Learns from Subplan Hints	2026	SIGMOD	5.1987909e-05
9,350	Automatic SQL Error Mitigation in Oracle	2023	VLDB	5.1891342e-05
9,546	Athena: An Effective Learning-based Framework for Query Optimizer Performance Improvement	2025	SIGMOD	5.1604755e-05
9,610	LIMAO: A Framework for Lifelong Modular Learned Query Optimization	2025	VLDB	5.1526493e-05
9,646	Are Joins over LSM-trees Ready? Take RocksDB as an Example	2025	VLDB	5.1453267e-05
9,670	Low Rank Learning for Offline Query Optimization	2025	SIGMOD	5.1452097e-05
9,706	Database Gyms	2023	CIDR	5.1376763e-05
9,720	APQO: An Adaptive Framework for Parametric Query Optimization	2026	SIGMOD	5.1349531e-05
9,730	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.1349531e-05
9,797	NeuSO: Neural Optimizer for Subgraph Queries	2026	SIGMOD	5.1257999e-05
9,954	Conformal Prediction for Verifiable Learned Query Optimization	2025	VLDB	5.1038322e-05
9,956	Graph Transformers for Query Plan Representation: Potentials and Challenges	2025	VLDB	5.1038322e-05
10,030	QO-Insight: Inspecting Steered Query Optimizers	2023	VLDB	5.0925155e-05
10,043	The Image Calculator: 10x Faster Image-AI Inference by Replacing JPEG with Self-designing Storage Format	2024	SIGMOD	5.0921006e-05
10,103	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	5.0789354e-05
10,143	Does A Fish Need a Bicycle? The Case for On-Chip NPUs in DBMS	2026	CIDR	5.0715586e-05
10,148	Improving DBMS Scheduling Decisions with Accurate Performance Prediction on Concurrent Queries	2025	VLDB	5.0715586e-05
10,168	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	5.0682654e-05
10,205	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.0603873e-05
10,285	Towards Full Stack Adaptivity in Permissioned Blockchains	2024	VLDB	5.0448662e-05
10,287	AdaChain: A Learned Adaptive Blockchain	2023	VLDB	5.0448662e-05
10,290	This is Going to Sound Crazy, But What If We Used Large Language Models to Boost Automatic Database Tuning Algorithms By Leveraging Prior History? We Will Find Better Configurations More Quickly Than Retraining From Scratch!	2026	SIGMOD	5.0431863e-05
10,309	Intra-Query Runtime Elasticity for Cloud-Native Data Analysis	2025	SIGMOD	5.0386264e-05
10,310	veDB-HTAP: a Highly Integrated, Efficient and Adaptive HTAP System	2025	VLDB	5.0386264e-05
10,322	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.0346745e-05
10,336	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	5.0200193e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046284649
85	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035864347
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034106982
145	Neo: A Learned Query Optimizer	2019	VLDB	0.0002908188
224	Self-Driving Database Management Systems	2017	CIDR	0.00024013745
406	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019045544
461	An End-to-End Learning-based Cost Estimator	2020	VLDB	0.00017829982
512	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00017050173
555	SageDB: A Learned Database System	2019	CIDR	0.00016506678
560	Plan-Structured Deep Neural Network Models for Query Performance Prediction	2019	VLDB	0.00016403151
682	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.0001481781
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011777105
1,279	AI Meets AI: Leveraging Query Executions to Improve Index Recommendations	2019	SIGMOD	0.00011226878
1,800	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.6093317e-05
1,842	On Predictive Modeling for Optimizing Transaction Execution in Parallel OLTP Systems	2012	VLDB	9.526552e-05
2,550	SQLShare: Results from a Multi-Year SQL-as-a-Service Experiment	2016	SIGMOD	8.3121033e-05
4,059	Database-Agnostic Workload Management	2019	CIDR	6.8251711e-05
5,087	Releasing Cloud Databases from the Chains of Performance Prediction Models	2017	CIDR	6.2809904e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,177	Approximating Opaque Top-k Queries	2025	SIGMOD
2	4,968	Budget-aware Index Tuning with Reinforcement Learning	2022	SIGMOD
3	9,276	BASE: Bridging the Gap between Cost and Latency for Query Optimization	2023	VLDB
4	10,802	BaCon: Efficient Batch Processing of Counting Queries	2026	VLDB
5	3,060	Towards a Hands-Free Query Optimizer through Deep Learning	2019	CIDR
6	9,670	Low Rank Learning for Offline Query Optimization	2025	SIGMOD
7	5,110	Steering Query Optimizers: A Practical Take on Big Data Workloads	2021	SIGMOD
8	8,332	Learned Offline Query Planning via Bayesian Optimization	2025	SIGMOD
9	1,199	Balsa: Learning a Query Optimizer Without Expert Demonstrations	2022	SIGMOD
10	4,683	AutoSteer: Learned Query Optimization for Any SQL Database	2023	VLDB