# A Practical Theory of Generalization in Selectivity Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 68 references that are in the map.
- First posted on arXiv 11 Sep 2024.

## Builds on (most cited first, 18 of 18)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [Certified Monotonic Neural Networks](https://mlsanity.com/paper/2011.10219/) (2020)
- [An End-to-End Learning-based Cost Estimator](https://mlsanity.com/paper/1906.02560/) (2019)
- [Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation](https://mlsanity.com/paper/2109.05877/) (2021)
- [Learning from Label Proportions by Learning with Label Noise](https://mlsanity.com/paper/2203.02496/) (2022)
- [Flow-Loss: Learning Cardinality Estimates That Matter](https://mlsanity.com/paper/2101.04964/) (2021)
- [NeuroCard: One Cardinality Estimator for All Tables](https://mlsanity.com/paper/2006.08109/) (2020)
- [A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation](https://mlsanity.com/paper/2107.12295/) (2021)
- [DeepDB: Learn from Data, not from Queries!](https://mlsanity.com/paper/1909.00607/) (2019)
- [FactorJoin: A New Cardinality Estimation Framework for Join Queries](https://mlsanity.com/paper/2212.05526/) (2022)
- [ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads (Extended)](https://mlsanity.com/paper/2310.05349/) (2023)
- [QuickSel: Quick Selectivity Learning with Mixture Models](https://mlsanity.com/paper/1812.10568/) (2018)
- [Duet: efficient and scalable hybriD neUral rElation undersTanding](https://mlsanity.com/paper/2307.13494/) (2023)
- [Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries](https://mlsanity.com/paper/2402.15953/) (2024)
- [SafeBound: A Practical System for Generating Cardinality Bounds](https://mlsanity.com/paper/2211.09864/) (2022)
- [PARQO: Penalty-Aware Robust Plan Selection in Query Optimization](https://mlsanity.com/paper/2406.01526/) (2024)

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

- [Data-Agnostic Cardinality Learning from Imperfect Workloads](https://mlsanity.com/paper/2506.16007/) (2025)
- [ZeroCard: Cardinality Estimation with Zero Dependence on Target Databases -- No Data, No Query, No Retraining](https://mlsanity.com/paper/2510.07983/) (2025)
- [Selectivity Estimation for Linear Queries via Online Learning](https://mlsanity.com/paper/2607.02895/) (2026)

## Abstract (arXiv)

Query-driven machine learning models have emerged as a promising estimation technique for query selectivities. Yet, surprisingly little is known about the efficacy of these techniques from a theoretical perspective, as there exist substantial gaps between practical solutions and state-of-the-art (SOTA) theory based on the Probably Approximately Correct (PAC) learning framework. In this paper, we aim to bridge the gaps between theory and practice. First, we demonstrate that selectivity predictors induced by signed measures are learnable, which relaxes the reliance on probability measures in SOTA theory. More importantly, beyond the PAC learning framework (which only allows us to characterize how the model behaves when both training and test workloads are drawn from the same distribution), we establish, under mild assumptions, that selectivity predictors from this class exhibit favorable out-of-distribution (OOD) generalization error bounds. These theoretical advances provide us with a better understanding of both the in-distribution and OOD generalization capabilities of query-driven selectivity learning, and facilitate the design of two general strategies to improve OOD generalization for existing query-driven selectivity models. We empirically verify that our techniques help query-driven selectivity models generalize significantly better to OOD queries both in terms of prediction accuracy and query latency performance, while maintaining their superior in-distribution generalization performance.