# SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning

arXiv: https://arxiv.org/abs/1901.05152 · HTML: https://mlsanity.com/paper/1901.05152/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2019.

## Built on by (most cited first, 17 of 17)

- [Lero: A Learning-to-Rank Query Optimizer](https://mlsanity.com/paper/2302.06873/) (2023)
- [DB-BERT: a Database Tuning Tool that "Reads the Manual"](https://mlsanity.com/paper/2112.10925/) (2021)
- [Balsa: Learning a Query Optimizer Without Expert Demonstrations](https://mlsanity.com/paper/2201.01441/) (2022)
- [A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration](https://mlsanity.com/paper/2101.01507/) (2021)
- [A Survey on Deep Reinforcement Learning for Data Processing and Analytics](https://mlsanity.com/paper/2108.04526/) (2021)
- [CodexDB: Generating Code for Processing SQL Queries using GPT-3 Codex](https://mlsanity.com/paper/2204.08941/) (2022)
- [No DBA? No regret! Multi-armed bandits for index tuning of analytical and HTAP workloads with provable guarantees](https://mlsanity.com/paper/2108.10130/) (2021)
- [Larch: Learned Query Optimization for Semantic Predicates](https://mlsanity.com/paper/2606.07923/) (2026)
- [A Reinforcement Learning Based R-Tree for Spatial Data Indexing in Dynamic Environments](https://mlsanity.com/paper/2103.04541/) (2021)
- [Can Deep Neural Networks Predict Data Correlations from Column Names?](https://mlsanity.com/paper/2107.04553/) (2021)
- [ML-Powered Index Tuning: An Overview of Recent Progress and Open Challenges](https://mlsanity.com/paper/2308.13641/) (2023)
- [JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning](https://mlsanity.com/paper/2307.11704/) (2023)
- [Implementing Semantic Join Operators Efficiently](https://mlsanity.com/paper/2510.08489/) (2025)
- [Multi-agent Databases via Independent Learning](https://mlsanity.com/paper/2205.14323/) (2022)
- [Learning-Based Data Storage [Vision] (Technical Report)](https://mlsanity.com/paper/2206.05778/) (2022)
- [Selective Use of Yannakakis' Algorithm to Improve Query Performance: Machine Learning to the Rescue](https://mlsanity.com/paper/2502.20233/) (2025)
- [Piece of CAKE: Adaptive Execution Engines via Microsecond-Scale Learning](https://mlsanity.com/paper/2602.04181/) (2026)

## Abstract (arXiv)

SkinnerDB is designed from the ground up for reliable join ordering. It maintains no data statistics and uses no cost or cardinality models. Instead, it uses reinforcement learning to learn optimal join orders on the fly, during the execution of the current query. To that purpose, we divide the execution of a query into many small time slices. Different join orders are tried in different time slices. We merge result tuples generated according to different join orders until a complete result is obtained. By measuring execution progress per time slice, we identify promising join orders as execution proceeds. Along with SkinnerDB, we introduce a new quality criterion for query execution strategies. We compare expected execution cost against execution cost for an optimal join order. SkinnerDB features multiple execution strategies that are optimized for that criterion. Some of them can be executed on top of existing database systems. For maximal performance, we introduce a customized execution engine, facilitating fast join order switching via specialized multi-way join algorithms and tuple representations. We experimentally compare SkinnerDB's performance against various baselines, including MonetDB, Postgres, and adaptive processing methods. We consider various benchmarks, including the join order benchmark and TPC-H variants with user-defined functions. Overall, the overheads of reliable join ordering are negligible compared to the performance impact of the occasional, catastrophic join order choice.