# QuickSel: Quick Selectivity Learning with Mixture Models

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Dec 2018.

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

- [A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation](https://mlsanity.com/paper/2107.12295/) (2021)
- [A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration](https://mlsanity.com/paper/2101.01507/) (2021)
- [Efficient Deep Learning Pipelines for Accurate Cost Estimations Over Large Scale Query Workload](https://mlsanity.com/paper/2103.12465/) (2021)
- [A Practical Theory of Generalization in Selectivity Learning](https://mlsanity.com/paper/2409.07014/) (2024)
- [Can Deep Neural Networks Predict Data Correlations from Column Names?](https://mlsanity.com/paper/2107.04553/) (2021)
- [Learned-Database Systems Security](https://mlsanity.com/paper/2212.10318/) (2022)
- [Data-Agnostic Cardinality Learning from Imperfect Workloads](https://mlsanity.com/paper/2506.16007/) (2025)
- [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)
- [A Lightweight Learned Cardinality Estimation Model](https://mlsanity.com/paper/2508.09602/) (2025)
- [CoLSE: A Lightweight and Robust Hybrid Learned Model for Single-Table Cardinality Estimation using Joint CDF](https://mlsanity.com/paper/2512.12624/) (2025)
- [Selectivity Estimation for Linear Queries via Online Learning](https://mlsanity.com/paper/2607.02895/) (2026)

## Abstract (arXiv)

Estimating the selectivity of a query is a key step in almost any cost-based query optimizer. Most of today's databases rely on histograms or samples that are periodically refreshed by re-scanning the data as the underlying data changes. Since frequent scans are costly, these statistics are often stale and lead to poor selectivity estimates. As an alternative to scans, query-driven histograms have been proposed, which refine the histograms based on the actual selectivities of the observed queries. Unfortunately, these approaches are either too costly to use in practice---i.e., require an exponential number of buckets---or quickly lose their advantage as they observe more queries. In this paper, we propose a selectivity learning framework, called QuickSel, which falls into the query-driven paradigm but does not use histograms. Instead, it builds an internal model of the underlying data, which can be refined significantly faster (e.g., only 1.9 milliseconds for 300 queries). This fast refinement allows QuickSel to continuously learn from each query and yield increasingly more accurate selectivity estimates over time. Unlike query-driven histograms, QuickSel relies on a mixture model and a new optimization algorithm for training its model. Our extensive experiments on two real-world datasets confirm that, given the same target accuracy, QuickSel is 34.0x-179.4x faster than state-of-the-art query-driven histograms, including ISOMER and STHoles. Further, given the same space budget, QuickSel is 26.8%-91.8% more accurate than periodically-updated histograms and samples, respectively.