The Case for Cardinality Lower Bounds

This paper introduces xBound, the first theoretical framework for computing provable join size lower bounds, which addresses the critical issue of cardinality underestimation in production databases by correcting 23.6% of errors and delivering up to 20.1x query speedups on Microsoft's Fabric Data Warehouse.

The Gist

Imagine you are the Traffic Controller for a massive, bustling airport (the Database). Every day, thousands of planes (queries) arrive, and you have to decide how many ground crew members, fuel trucks, and baggage handlers (CPU and memory resources) to assign to each flight.

For decades, you've been guessing how many passengers are on each plane. Sometimes you guess too high, and you send a huge crew for a tiny private jet (wasteful, but safe). But often, you guess too low. You send a small team to handle a jumbo jet full of 500 people. The result? Chaos. The crew gets overwhelmed, the plane sits on the tarmac for hours, and the airport grinds to a halt.

This paper, "The Case for Cardinality Lower Bounds," introduces a new tool called xBound to fix this specific problem: underestimating the size of data.

Here is the story of how they did it, explained simply.

1. The Problem: The "Optimist" Optimizer

In the world of databases, the "Optimizer" is the brain that plans how to execute a query. It has a bad habit: it is an eternal optimist. It consistently thinks, "Oh, this join between two tables will only return 100 rows."

In reality, it might return 100,000 rows.

Because the Optimist thinks the job is small, it assigns a tiny team of workers. When the data actually arrives, the team is crushed. The system runs out of memory, spills data to slow hard drives, and the query takes 20 times longer than it should.

The authors looked at Microsoft's massive "Fabric Data Warehouse" and found a scary truth: Just 0.05% of these bad guesses were causing 95% of the slowdowns. It's like 1 in 2,000 flights being assigned a bicycle instead of a jet engine, causing a massive traffic jam.

2. The Previous Solution: The "Ceiling"

Researchers had already invented a tool called LpBound to fix the other problem: overestimation.

• The Analogy: Imagine LpBound is a Ceiling. If the Optimist guesses 1,000,000 rows, LpBound says, "No, it can't possibly be more than 500,000." It puts a cap on the guess to prevent wasting resources.
• The Flaw: LpBound is great at stopping you from guessing too high, but it does nothing to stop you from guessing too low. It's like having a ceiling but no floor. You can still fall into a pit.

3. The New Solution: xBound (The "Floor")

The authors introduce xBound, the first tool to build a mathematical Floor.

Instead of guessing the exact number, xBound asks: "What is the absolute minimum number of rows this could possibly be, based on the data we have?"

It doesn't need to know the exact answer. It just needs to prove that the answer is at least X. If the Optimist guesses 100, but xBound proves the floor is 10,000, the system immediately says, "Whoa, upgrade the crew!"

4. How Does xBound Work? (The Magic Tricks)

To build this floor without doing all the heavy lifting (which would be too slow), xBound uses some clever math tricks and "lightweight" statistics.

Trick A: The "Heavy Hitters" List

Imagine you are counting people entering a stadium. You know that 99% of the time, the crowd is small. But you also know that Team A has 50,000 die-hard fans who always show up.

• xBound's move: It keeps a short, special list of these "Heavy Hitters" (the most popular keys). It tracks them exactly. If the query involves these popular keys, xBound knows the floor is high immediately.

Trick B: The "Light Partitions" (Zooming In)

If the keys aren't "heavy," xBound doesn't look at the whole stadium. It divides the stadium into 16 smaller sections (bins).

• The Analogy: Instead of guessing how many people are in the whole city, it looks at specific neighborhoods. It asks, "In the 'North Side' neighborhood, what is the minimum number of people we know are there?" By looking at smaller chunks, it can make a much tighter, safer guess.

Trick C: The "Reverse Math" (The Secret Sauce)

This is the theoretical heart of the paper. Usually, math helps you find the maximum possible size. xBound uses a special type of math called Reverse Inequalities (specifically involving something called Pólya–Szegő and Reverse Hölder inequalities).

• The Analogy: Imagine you have two bags of marbles. You don't know how many are in each, but you know the average weight and the heaviest marble in each bag.
• Standard math tries to guess the total weight.
• xBound's math says: "Even if we arrange these marbles in the worst possible way to minimize the total, they still weigh at least X."
• It uses a few simple numbers (like the "heaviest" key and the "lightest" key) to prove that the result cannot be smaller than a certain number.

5. The Results: Saving the Day

The authors tested xBound on a massive dataset (StackOverflow questions and answers).

• The Fix: xBound caught 23.6% of the dangerous underestimates that the database was making.
• The Speedup: For the queries that were previously crashing or slowing down, xBound fixed the resource allocation. Some queries ran 20 times faster (20x speedup) because the system finally assigned enough workers to handle the real workload.

Summary: Why This Matters

For years, the database world has been obsessed with preventing people from guessing too high (wasting money). This paper argues that guessing too low is actually more dangerous (it breaks the system).

xBound is like installing a safety net under a tightrope walker. It doesn't tell you exactly where the walker will step, but it guarantees they won't fall below a certain point. By ensuring the database never underestimates the workload, it prevents the "catastrophic slowdowns" that plague massive cloud systems today.

It's a shift from "Hope for the best" to "Plan for the worst-case minimum," ensuring that the airport (database) always has enough crew to handle the flight, no matter how big it turns out to be.

Technical Summary

Here is a detailed technical summary of the paper "The Case for Cardinality Lower Bounds" by Stoian et al.

1. Problem Statement

Despite decades of research, cardinality estimation remains a critical weakness in database query optimizers. While recent theoretical work (e.g., LpBound) has focused on providing provable upper bounds to correct overestimation, the more dangerous problem of underestimation remains largely unaddressed.

• The Production Reality: In industrial systems like Microsoft Fabric Data Warehouse (DW), underestimation is far more prevalent and harmful than overestimation.
• The Consequence: Underestimation tricks the optimizer into selecting fragile execution plans (e.g., nested-loops instead of hash joins) and leads to severe resource starvation (out-of-memory errors, excessive disk spilling).
• The Scale of the Issue: In Fabric DW, a mere 0.05% of extreme underestimates account for 95% of all CPU under-allocation, causing thousands of daily queries to suffer preventable slowdowns.
• The Gap: Existing provable bounds only cap estimates from above. There is no theoretical framework for computing provable lower bounds on join sizes using lightweight statistics.

2. Methodology: The xBound Framework

The authors introduce xBound, the first theoretical framework for computing provable join size lower bounds using only a handful of lightweight base table statistics.

Core Mathematical Insight

The size of a join is the inner product of the degree vectors (frequency distributions of join keys) of the participating relations.

• Reverse Inequalities: While standard inequalities (like Hölder's) provide upper bounds, xBound utilizes reverse inequalities (e.g., Pólya–Szegő, Generalized Reverse Hölder) to provide lower bounds.
• The Challenge: Reverse inequalities require strictly positive input vectors. However, real-world degree vectors contain zeros for keys that do not exist in a specific relation.
• The Solution: xBound first computes a hard lower bound on the number of distinct joining keys ($m$). It then restricts the application of reverse inequalities to the prefix of length $m$ of the degree sequences, effectively ignoring the zero-padding and ensuring the vectors are positive.

Key Components of xBound

1. Hard $\ell_0$ Lower Bounds (Distinct Joining Keys):

   • Uses Zone Maps (min/max values of columns) to bound the intersection of key domains.
   • Formula: $|K_A \cap K_B| \ge \max(0, |K_A| + |K_B| - (\max(K_A, K_B) - \min(K_A, K_B)))$.
   • Generalized for multi-way joins using the union bound.

2. Probabilistic $\ell_0$ Lower Bounds:

   • For large datasets where exact $\ell_0$ is expensive, xBound uses ThetaSketches (from Apache DataSketches) to estimate the intersection size of $n$ sets with 99% confidence.

3. Reverse Inner-Product Inequalities:

   • Once the prefix length $m$ is established, xBound applies reverse inequalities to the degree sequence prefixes.
   • Min-Degree Bound: A simple bound using $\ell_1$ and $\ell_{-\infty}$ (minimum frequency).
   • Generalized Reverse Hölder's Inequality: A tighter bound using $\ell_2$, $\ell_\infty$, and $\ell_{-\infty}$ norms.

4. Optimization Techniques:

   • Heavy Partition: Maintains a set of "heavy hitters" (frequent keys) using a CountMinSketch. These are tracked separately to avoid the "long tail" of sparse keys, significantly improving bound tightness.
   • Light Partitions: Splits value ranges into equi-width bins to refine $\ell_0$ estimates for specific data ranges.
   • Norm Stitching: A technique to derive accurate norm values for non-power-of-two prefix lengths by "stitching" together values from power-of-two prefixes and padding with $\ell_\infty$ values.
   • Predicate Support: Extends the framework to handle equality, range, conjunction, and disjunction predicates by adapting the statistics (e.g., using MCVs for equality, hierarchical histograms for ranges).

3. Key Contributions

1. First Provable Lower Bound Framework: Introduced xBound, the first system to compute provable lower bounds for join sizes, addressing the critical blind spot in current optimizer theory.
2. Theoretical Extension: Extended the framework to support filtered table scans (equality/range predicates) and multi-way joins over a single key.
3. Practical Implementation: Demonstrated the integration of xBound into Microsoft Fabric DW, a production-grade cloud data warehouse.
4. Statistical Efficiency: Showed that provable lower bounds can be computed using only lightweight statistics ($\ell_0, \ell_1, \ell_2, \ell_\infty$, min/max) without storing full degree sequences.

4. Experimental Results

The authors evaluated xBound on the StackOverflow-CEB benchmark (220 GB dataset) running on Microsoft Fabric DW.

• Correction Rate: xBound corrected 23.6% of Fabric DW's underestimates on the benchmark.
• Q-Error Reduction:
  • Reduced the 90th-percentile Q-error of underestimates by 35.8x.
  • Reduced the median Q-error of underestimates by 3.2x.
• Performance Gains:
  • Correcting underestimates allowed the optimizer to allocate sufficient CPU resources.
  • End-to-end query speedups of up to 20.1x were observed for severely underestimated queries (e.g., Query Q90).
  • Queries that were previously suffering from resource starvation (disk spilling) saw massive improvements.
• Overhead: The statistical overhead is lightweight. For the benchmark, the partitioned $\ell_0$ statistics and heavy partition stats required roughly 196 MB of storage and took ~6 minutes to build on a single node. Estimation time per query is projected to be under 1ms in optimized implementations.

5. Significance and Future Work

• Production Impact: This work shifts the focus from "average-case" accuracy to "worst-case" safety. By providing a mathematical safety net against catastrophic underestimation, xBound prevents the most severe performance regressions in production systems.
• Paradigm Shift: It challenges the community to move beyond upper bounds and treat underestimation as a first-class problem requiring provable guarantees.
• Future Directions:
  • Extending support to cyclic queries and multi-key joins.
  • Handling outer joins and group-by operations.
  • Investigating tighter bounds using more granular statistics beyond min/max.
  • Refining the confidence guarantees when combining probabilistic sketches for heavy keys.

In conclusion, xBound demonstrates that even a "first step" toward provable lower bounds can deliver massive, tangible gains in real-world database performance, validating the urgent need for the database community to prioritize this direction.