Cardinality Estimation Beyond the Attribute Independence Assumption

48 concepts41 papers1 proposal

When a database system executes a SQL query, its query optimizer must choose the most efficient execution plan from billions of possibilities. Should it scan Table A or Table B first? Should it use a hash join or a nested loop? To make this decision, the optimizer relies on cardinality estimation: predicting how many rows will satisfy a given set of filters or join conditions.

For decades, relational database systems have relied on a mathematically convenient but fundamentally flawed simplification: the attribute independence assumption. This assumption states that the values in different columns of a table are completely uncorrelated. Under this view, if 10% of cars are red and 10% of cars are electric, then exactly 1% ($0.10 \times 0.10$) of cars are red electric cars.

In reality, real-world data is highly correlated and heavily skewed. As Faloutsos (Modeling Skewed Distribution Using Multifractals and the '80-20' Law) demonstrated, real-world data distributions follow non-uniform patterns like the "80-20" law or Zipfian distributions rather than uniform spreads. When an optimizer ignores these patterns and multiplies independent probabilities together, estimation errors compound exponentially. A small error in a single predicate multiplies across joins, causing query execution times to explode from seconds to hours.

The Anatomy of Estimation Failure

Why does the independence assumption fail so spectacularly? Consider a database containing geographic data. As Jagadish et al. (Multi-Dimensional Substring Selectivity Estimation) point out, there are strong hidden correlations between attributes like phone number area codes and surnames. If an optimizer treats these columns as independent, it will severely underestimate the number of rows returned by a query filtering on both, leading to an inefficient plan.

This issue extends beyond standard data columns:

  • Correlated Filters: Shivakumar et al. (Filtering with Approximate Predicates) showed that even approximate filters or predicates can fail on the same underlying data subsets, meaning their error rates are highly correlated.
  • Semantic Dependencies: Mirzaei et al. (Table Union Search with Preferences) highlight that treating columns as independent sets ignores crucial semantic dependencies (such as city and country), which degrades the alignment and search of tabular data.
  • Expensive User-Defined Functions (UDFs): Joglekar et al. (Exploiting Correlations for Expensive Predicate Evaluation) note that optimizing expensive query predicates relies heavily on exploiting correlations with other attributes; if independence is blindly assumed, optimization potential is lost.

When traditional optimizers use single-column histograms, they multiply individual selectivities together, completely blinding themselves to these multi-attribute correlations. To fix this, researchers have developed several distinct paradigms to model data dependencies accurately without incurring prohibitive computational overhead.

Paradigm 1: Probabilistic Graphical Models and Factor Graphs

One elegant way to capture multi-attribute correlations without storing massive, unmanageable multi-dimensional histograms is to use Probabilistic Graphical Models (PGMs). Instead of assuming total independence or total dependence, PGMs map out the specific conditional dependencies between attributes.

Deshpande et al. (Probabilistic Graphical Models and their Role in Databases) proposed using undirected graphical models to represent these relationships, preventing the selection of poor execution plans caused by flawed independence assumptions. To make this practical inside a live database engine, Deshpande et al. (Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions) implemented a lightweight junction-tree framework within PostgreSQL. This approach models both intra-table correlations and join predicate dependencies, keeping optimization overhead down to tens of milliseconds.

Traditional (Independence):  P(A, B, C) = P(A) × P(B) × P(C)
Graphical Model (Junction Tree): P(A, B, C) = P(A) × P(B | A) × P(C | B)

More recently, Wu et al. (FactorJoin: A New Cardinality Estimation Framework for Join Queries) extended this concept by framing join cardinality estimation as an inference problem on a factor graph. By factorizing the joint distribution across tables, their framework achieves the accuracy of deep learning models while maintaining a tiny memory footprint and low latency.

Paradigm 2: Deep Learning and Neural Density Estimation

With the rise of deep learning, researchers realized that neural networks are exceptional at learning complex, non-linear joint distributions across many dimensions.

A prominent approach is neural density estimation via autoregressive models. Yang et al. (Deep Unsupervised Cardinality Estimation) introduced Naru, which breaks down the joint distribution of a table into a chain of conditional probabilities using the chain rule of probability:

$$P(A, B, C) = P(A) \cdot P(B \mid A) \cdot P(C \mid A, B)$$

By using deep autoregressive networks to learn these conditional chains, Naru eliminates the independence assumption entirely, improving accuracy by up to two orders of magnitude over traditional histograms. Yang et al. (NeuroCard: One Cardinality Estimator for All Tables) scaled this concept to entire database schemas with NeuroCard, capturing correlations across multiple tables and joins simultaneously.

Other deep learning architectures have also proven effective:

Paradigm 3: Dynamic Sampling and Run-Time Re-Optimization

Instead of trying to pre-model every possible correlation statically, why not look at the data dynamically? Sampling and re-optimization bypass static assumptions by measuring actual data distributions on the fly.

Leis et al. (Cardinality Estimation Done Right: Index-Based Join Sampling) demonstrated that using existing database indexes to perform online join sampling provides unbiased cardinality estimates that naturally account for real-world correlations.

If an optimizer does make a mistake due to bad initial estimates, run-time re-optimization acts as a safety net. Wu et al. (Sampling-Based Query Re-Optimization) introduced a lightweight, iterative re-optimization step that validates the optimizer's plan against a small data sample before full execution, catching catastrophic plan failures early. Similarly, van Keulen et al. (Run-time Optimization for Pipelined Systems) developed a run-time optimizer designed to handle complex data correlations in pipelined systems without full table materialization.

As Perron (How I Learned to Stop Worrying and Love Re-optimization) argues, rather than chasing the "impossible dream" of perfect static estimation, detecting errors at runtime and replanning can recover the vast majority of performance lost to correlation and skew.

Paradigm 4: Advanced Statistical and Workload-Driven Models

Other approaches enhance traditional statistical structures or learn directly from query workloads to capture dependencies efficiently.

For example, Li et al. (TKHist: Cardinality Estimation for Join Queries via Histograms with Dominant Attribute Correlation Finding) modified standard histograms to explicitly track the top-$k$ dominant items within individual bins. By modeling the correlation between these dominant join paths and query filters, they prevent the over-estimation errors that occur when standard independence assumptions fail to account for filters that eliminate dominant data segments.

Standard Histogram Bin:  [ Average Frequency ] -> Assumes Uniformity
TKHist Bin:              [ Top-k Dominant Items + Explicit Filter Correlations ]

Alternatively, Havenstein et al. (Fast Entropy Maximization for Selectivity Estimation of Conjunctive Predicates on CPUs and GPUs) utilized a high-performance Newton-based algorithm to solve the Maximum Entropy problem, allowing the system to find the most mathematically sound distribution that fits known predicate combinations without assuming blanket independence.

Finally, Wu et al. (Data-Agnostic Cardinality Learning from Imperfect Workloads) introduced GRASP, a data-agnostic framework that learns to predict result sizes purely from historical query workloads. This demonstrates that correlation patterns can be inferred from how users query the data, even without direct access to the underlying raw tables.

Key Foundational Work

Optimizing Backtrack Search for all Solutions to Conjunctive Problems (1987) — contributed 2 concept elements to this direction.
Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins (1992) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_attribute_independence_assumption_data_s_523cf367,
  title = {attribute independence assumption (data skew sensitivity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/attribute-independence-assumption-data-skew-sensitivity/rdr_523cf367addf4adf8e716ea274e4add8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_attribute_independence_assumption_data_s_523cf367_v1,
  title = {attribute independence assumption (data skew sensitivity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/attribute-independence-assumption-data-skew-sensitivity/rdr_523cf367addf4adf8e716ea274e4add8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake