SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning

Summary: Reinforcement learning drives on-the-fly join ordering without statistics or cost models, achieving regret-bounded execution. Execution splits into time slices testing orders, merging results, and switching plans with a custom engine; experiments show gains vs MonetDB/Postgres with negligible overhead. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5620
Venue: SIGMOD
Year: 2019
Pagerank: 9.2598438e-05
Overall Rank: 2,222 | 84.56%
DOI: 10.1145/3299869.3300088

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 39 of 39 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
905	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00015423174
1,404	DB-BERT: A Database Tuning Tool that "Reads the Manual"	2022	SIGMOD	0.00012179714
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
2,090	Balsa: Learning a Query Optimizer Without Expert Demonstrations	2022	SIGMOD	9.5668285e-05
2,781	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1282042e-05
3,105	GPTuner: A Manual-Reading Database Tuning System via GPT-Guided Bayesian Optimization	2024	VLDB	7.5567226e-05
3,241	A Learned Query Rewrite System using Monte Carlo Tree Search	2022	VLDB	7.32744e-05
3,345	Lero: A Learning-to-Rank Query Optimizer	2023	VLDB	7.1908499e-05
3,466	AI Meets Database: AI4DB and DB4AI	2021	SIGMOD	7.0645718e-05
3,729	Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection	2022	VLDB	6.8078013e-05
4,151	openGauss: An Autonomous Database System	2021	VLDB	6.4020605e-05
4,730	UDO: Universal Database Optimization using Reinforcement Learning	2021	VLDB	5.9604983e-05
5,129	The Art of Balance: A RateupDBTM Experience of Building a CPU/GPU Hybrid Database Product	2021	VLDB	5.6724875e-05
5,463	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	5.4920768e-05
5,506	Can Large Language Models Predict Data Correlations from Column Names?	2023	VLDB	5.4711611e-05
5,540	Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling	2021	VLDB	5.450319e-05
5,673	Budget-aware Index Tuning with Reinforcement Learning	2022	SIGMOD	5.3789277e-05
5,787	Machine Learning for Databases	2021	VLDB	5.3256401e-05
5,886	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	5.2847297e-05
6,862	Join Order Selection with Deep Reinforcement Learning: Fundamentals, Techniques, and Challenges	2023	VLDB	4.9004921e-05
6,883	PilotScope: Steering Databases with Machine Learning Drivers	2024	VLDB	4.8918682e-05
7,220	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	4.7926382e-05
7,854	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	4.6306186e-05
8,027	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	4.5986382e-05
8,162	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	4.5686903e-05
8,440	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	4.505741e-05
8,612	The Case for NLP-Enhanced Database Tuning: Towards Tuning Tools that "Read the Manual"	2021	VLDB	4.4807455e-05
8,772	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	4.451034e-05
8,975	A Learned Query Rewrite System	2023	VLDB	4.4146872e-05
9,191	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	4.3738237e-05
9,206	Themis: A GPU-accelerated Relational Query Execution Engine	2025	VLDB	4.3695556e-05
9,692	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	4.2986161e-05
10,156	Divo: Learning a Stable and Effective Query Optimizer with a Diverse Workload	2026	SIGMOD	4.1905499e-05
10,219	Practical Parameterized Query Optimization via Efficient Plan Reuse and List-wise Ranking	2026	SIGMOD	4.1905499e-05
10,501	Intra-Query Runtime Elasticity for Cloud-Native Data Analysis	2025	SIGMOD	4.1905499e-05
10,714	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.1905499e-05
10,757	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	4.1905499e-05
11,300	Demonstrating ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Joins via Reinforcement Learning	2023	VLDB	4.1905499e-05
11,310	SIFTER: Space-Efficient Value Iteration for Finite-Horizon MDPs	2023	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
116	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00046191288
144	Optimization of Nonrecursive Queries	1986	VLDB	0.00041430126
181	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00036970794
369	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025502381
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
680	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018193263
716	Performance Prediction for Concurrent Database Workloads	2011	SIGMOD	0.00017623897
786	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00016624743
1,017	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00014627121
1,233	Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources	2003	VLDB	0.0001312635
1,268	Proactive Re-Optimization	2005	SIGMOD	0.00012914584
1,756	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010659753
2,632	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	8.4153283e-05
2,671	A Black-Box Approach to Query Cardinality Estimation	2007	CIDR	8.3385014e-05
4,342	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	6.2680535e-05
5,012	Dynamically Optimizing Queries over Large Scale Data Platforms	2014	SIGMOD	5.7543101e-05
5,019	Automated Statistics Collection in DB2 UDB	2004	VLDB	5.7492033e-05
5,699	PREDIcT: Towards Predicting the Runtime of Large Scale Iterative Analytics	2013	VLDB	5.3655096e-05
5,824	StatAdvisor: Recommending Statistical Views	2009	VLDB	5.311975e-05
6,616	QUEST: An Exploratory Approach to Robust Query Processing	2014	VLDB	4.9881716e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
7,011	Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis	2023	VLDB	4.8583284e-05
5,289	LearnedSQLGen: Constraint-aware SQL Generation using Reinforcement Learning	2022	SIGMOD	5.5790771e-05
10,945	Sub-optimal Join Order Identification with L1-error	2024	SIGMOD	4.1905499e-05
5,682	LSched: A Workload-Aware Learned Query Scheduler for Analytical Database Systems	2022	SIGMOD	5.3752251e-05
8,772	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	4.451034e-05
6,862	Join Order Selection with Deep Reinforcement Learning: Fundamentals, Techniques, and Challenges	2023	VLDB	4.9004921e-05
8,027	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	4.5986382e-05
11,300	Demonstrating ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Joins via Reinforcement Learning	2023	VLDB	4.1905499e-05
2,154	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.4176683e-05