🤖 machine learning

A Practical Theory of Generalization in Selectivity Learning

This paper bridges the gap between theory and practice in query-driven selectivity learning by establishing learnability under signed measures and deriving out-of-distribution generalization bounds, which leads to two strategies that significantly improve model accuracy and latency on OOD queries while preserving in-distribution performance.

Original authors: Peizhi Wu, Haoshu Xu, Ryan Marcus, Zachary G. Ives

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Peizhi Wu, Haoshu Xu, Ryan Marcus, Zachary G. Ives

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to predict how many people will show up to a dinner party based on the invitations you've sent out. In the world of databases, this is called selectivity estimation: guessing how many rows of data will match a specific search query.

For decades, database systems used simple rules (like "assume everyone is evenly distributed") to make these guesses. But these rules often fail when the data is messy or the questions are tricky. Recently, scientists started using Machine Learning (AI) to learn these patterns. These AI models are great at guessing for questions they've seen before, but they often crash and burn when asked a question that's slightly different from what they were trained on. This is called the Out-of-Distribution (OOD) problem.

This paper, "A Practical Theory of Generalization in Selectivity Learning," tries to fix the gap between the math that says AI should work and the reality that it often doesn't work well on new, weird questions.

Here is the breakdown in simple terms:

1. The Problem: The "Probability" Trap

The best math theories we had before (called PAC learning) relied on a strict rule: the AI's predictions had to act like a perfect probability map.

The Metaphor: Imagine a map where the ink represents the chance of finding data. The old theory said, "The ink must always be positive, and the total amount of ink on the whole map must equal exactly 1."
The Reality: The most powerful AI models (like Deep Learning) don't follow these strict rules. They might predict "negative ink" or "more than 100% ink" in certain spots because they are just trying to minimize errors. Because they broke the "perfect map" rule, the old math said, "We can't prove these models will work on new data."
The Result: We had powerful tools, but no mathematical guarantee that they wouldn't fail when the data changed.

2. The Breakthrough: The "Signed Map" Theory

The authors realized we don't need a "perfect probability map." We just need a "Signed Map."

The Metaphor: Imagine a map where the ink can be positive (blue) or negative (red). As long as the math balances out, the map still works.
The Discovery: They proved that even if an AI model uses these "signed" (positive and negative) predictions, it is still learnable.
The Big Win: They proved that if an AI learns well on the training data, it will also do a decent job on new, unseen data (OOD), provided the new data isn't completely alien (e.g., it's still within the general area the model knows). This is a huge leap because it covers the powerful Deep Learning models that the old theories couldn't explain.

3. The Solution: Two New Strategies

Using this new "Signed Map" theory, the authors built two practical tools to help existing AI models get better at guessing on new data.

Strategy A: NeuroCDF (The "CDF" Approach)

Instead of asking the AI to guess the answer directly (e.g., "How many rows?"), they asked the AI to guess the Cumulative Distribution Function (CDF).

The Metaphor: Instead of asking, "How many people are in the room right now?" (which is hard if the room changes), they asked the AI, "How many people are in the room up to this specific point?"
How it works: The AI learns the shape of the data distribution (the CDF). To get the answer for a specific query, the system simply adds and subtracts these CDF points (like calculating the area of a rectangle by knowing the corners).
The Benefit: Because this method mathematically forces the AI to act like a "Signed Map," it is guaranteed to be robust on new data.
The Catch: It's a bit tricky to train because sometimes it might give a negative number, which doesn't make sense for a count of rows.

Strategy B: SeConCDF (The "Self-Consistency" Trainer)

This is the more practical, "plug-and-play" solution. It takes any existing AI model and gives it a special training routine.

The Metaphor: Imagine a student taking a test. Usually, they just memorize the answers. With SeConCDF, the teacher also asks the student to explain why the answer is what it is, based on the underlying rules (the CDFs).
How it works: The AI is trained to do two things at once:
1. Predict the answer directly (the usual way).
2. Predict the underlying CDFs and check if those CDFs are consistent with the answer.
The Benefit: This "self-check" forces the AI to learn the underlying structure of the data, not just memorize answers. It makes the model much more robust to new questions without changing the model's architecture or slowing it down.

4. The Results: Does it Work?

The authors tested these ideas on real database datasets (like movie databases and census data).

Accuracy: When they asked the models questions that were slightly different from the training data (e.g., asking about a different year or a different range of values), the models trained with SeConCDF made far fewer mistakes than the standard models.
Speed: Because the guesses were more accurate, the database system didn't waste time trying to process the wrong amount of data. The queries ran faster.
Comparison: The new methods beat the old "perfect probability" models (which were theoretically safe but practically weak) and significantly improved the powerful Deep Learning models (which were practically strong but theoretically risky).

Summary

The paper says: "We found a new mathematical rule that proves powerful AI models can be trusted on new data, even if they don't follow the old strict rules. We then built a training method (SeConCDF) that uses this rule to make database AI models much smarter and more reliable when facing unexpected questions."

Technical Summary: A Practical Theory of Generalization in Selectivity Learning

1. Problem Statement

The paper addresses the theoretical gap between practical query-driven selectivity learning models and state-of-the-art (SOTA) learning theory. While query-driven models (e.g., deep learning regressors like MSCN) have demonstrated superior empirical performance over traditional histograms, existing theoretical frameworks—specifically the Probably Approximately Correct (PAC) learning framework—fail to explain their efficacy.

Two primary limitations of prior theory are identified:

Restrictive Hypothesis Assumptions: SOTA theory [26] assumes that selectivity predictors are induced by probability measures (satisfying positivity and sum-to-unity constraints). However, high-performing practical models, such as regression-based deep learning and LEO, often violate these constraints (e.g., producing negative values or non-monotonic outputs) and are not induced by probability measures. Consequently, existing learnability results do not apply to these practical models.
In-Distribution Limitation: The PAC framework characterizes generalization only when training and test workloads are drawn from the same distribution. It cannot quantify Out-of-Distribution (OOD) generalization error, which is critical in real-world database scenarios where query workloads frequently shift (e.g., changes in query centers or granularity).

The paper aims to bridge these gaps by: (1) relaxing the theoretical reliance on probability measures to include signed measures, and (2) establishing OOD generalization error bounds under mild assumptions.

2. Methodology and Theoretical Framework

2.1 Theoretical Foundations

The authors introduce a new theoretical framework based on signed measures.

Signed Measures: Unlike probability measures, signed measures satisfy countable additivity but relax the constraints of positivity (C2) and sum-to-unity (C3). This allows the theory to encompass regression-based models that may output negative values or values summing to non-unity.
In-Distribution Learnability (Theorem 4.1): The authors prove that the class of selectivity predictors induced by signed measures (specifically those absolutely continuous with respect to the Lebesgue measure) is PAC learnable. They establish that the fat-shattering dimension of this class is finite, bounded by $\tilde{O}(C \cdot (1/\gamma)^{\lambda+1})$ , where $C$ is a bound on the measure's total variation and $\lambda$ is the VC dimension of the range space. This implies that with sufficient training data, the training error and true error remain close.

2.2 Out-of-Distribution (OOD) Generalization

Moving beyond the PAC framework, the paper establishes Theorem 4.2, which provides an OOD generalization error bound.

Assumptions: The theorem relies on three mild assumptions:
1. Boundedness: The learned selectivity function is bounded.
2. Support Containment: The testing distribution's support is contained within the training distribution's support (i.e., the test workload does not query regions unseen during training).
3. Diversity: The training ranges cover a diverse set of regions, ensuring the error is not minimized only on specific "easy" ranges.
Result: Under these assumptions, if a predictor $\hat{S}$ has an in-distribution error bounded by $\epsilon$ , its OOD error on a different distribution $P$ is bounded by $O(\sqrt{\epsilon})$ . This result holds for any predictor induced by a signed measure.

2.3 Proposed Strategies

Leveraging these theoretical insights, the authors propose two strategies to improve existing models:

Strategy 1: NeuroCDF (Modeling CDFs)

Concept: Instead of directly modeling the selectivity of a query, NeuroCDF uses a neural network to model the underlying Cumulative Distribution Function (CDF). The selectivity of a range query is then computed as a linear combination of CDF values at the query's vertices (via the inclusion-exclusion principle).
Theoretical Guarantee: Because NeuroCDF explicitly models CDFs, its predictions are provably induced by signed measures. Thus, it inherits the OOD generalization guarantees of Theorem 4.2.
Limitation: NeuroCDF struggles with relative error metrics like Qerror because the linear combination of CDFs can yield negative estimates, which are invalid for Qerror.

Strategy 2: SeConCDF (CDF Self-Consistency Regularization)

Concept: To combine the flexibility of direct selectivity modeling (which supports Qerror) with the OOD robustness of CDF modeling, the authors propose SeConCDF.
Mechanism: SeConCDF trains a standard query-driven model (e.g., MSCN or LW-NN) using a composite loss function:
1. Original Prediction Loss: Standard loss (e.g., Qerror or RMSE) on direct selectivity predictions.
2. CDF Prediction Loss: An auxiliary loss forcing the model to predict CDF values consistent with the observed data.
3. Consistency Loss: A regularization term enforcing consistency between the direct selectivity prediction and the selectivity derived from the model's learned CDFs.
Goal: This "soft constraint" encourages the model to behave as if it were induced by a signed measure, thereby improving OOD generalization without sacrificing the ability to optimize for Qerror or changing the model architecture.

3. Experimental Results

The authors evaluate SeConCDF by integrating it into two state-of-the-art deep learning models: LW-NN and MSCN. Experiments are conducted on single-table (Census) and multi-table datasets (IMDb-small, DSB, CEB) with synthetic OOD workloads involving Query Center Moves and Query Granularity Shifts.

OOD Generalization Accuracy:
- Standard deep models (MSCN, LW-NN) exhibit significant performance degradation on OOD queries (e.g., median Qerror jumping from single digits to four digits).
- SeConCDF significantly mitigates this drop. For instance, on the IMDb-small dataset with a granularity shift, SeConCDF reduces the median Qerror of MSCN from ~103 to ~2.1, while maintaining strong in-distribution performance.
- NeuroCDF also shows improved OOD robustness but is limited by its incompatibility with Qerror.
Query Latency:
- Improved selectivity estimation accuracy translates directly to better query execution plans.
- In OOD scenarios, models trained with SeConCDF achieve query latencies comparable to PostgreSQL and significantly better than standard MSCN, which often suffers from poor cardinality estimates leading to suboptimal plans.
Comparison with SOTA Theory Models: Models based on the previous SOTA theory (induced by probability measures, e.g., PtsHist, QuadHist) show better OOD stability than raw deep learning models but generally underperform deep models in in-distribution accuracy and overall OOD performance compared to SeConCDF-enhanced deep models.

4. Key Contributions

Theoretical Extension: The paper proves that selectivity predictors induced by signed measures are learnable, extending the scope of PAC learning beyond probability measures to include practical regression-based models.
OOD Generalization Bounds: It establishes the first non-trivial OOD generalization error bounds for selectivity learning under mild assumptions, showing that error scales with the square root of the in-distribution error ( $O(\sqrt{\epsilon})$ ).
Practical Frameworks:
- NeuroCDF: A new paradigm modeling CDFs to guarantee signed measure induction.
- SeConCDF: A general training methodology that enhances OOD generalization for existing models via CDF self-consistency regularization, compatible with standard loss functions like Qerror.
Empirical Validation: Demonstrates that these theoretical insights lead to tangible improvements in both prediction accuracy and query latency for OOD workloads in real-world database scenarios.

5. Significance and Claims

The paper claims that its primary contribution is bridging the gap between theory and practice in selectivity learning. By relaxing the restrictive assumption of probability measures, the authors provide a theoretical foundation that explains why and when practical deep learning models generalize.

The significance lies in the ability to formally guarantee and practically improve the robustness of learned cardinality estimators against workload shifts. The authors emphasize that their goal is not merely to outperform existing SOTA models in a specific benchmark, but to validate that their theoretical framework can be operationalized to make existing models more reliable in dynamic, real-world environments where query distributions inevitably shift. They conclude that their approach offers a principled path to enhancing the reliability of learned database components.