Cardinality Estimation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

=============================================================
SELECTIVITY CALCULATION WALKTHROUGH
=============================================================
 
Table: orders (1,000,000 rows)
Column: status (MCV list: {pending:0.35, processing:0.25, shipped:0.20, 
                           delivered:0.15, cancelled:0.05})
 
Case 1: status = 'pending' (MCV match)
  Selectivity = 0.35 (directly from MCV frequency)
  Estimated rows = 1,000,000 × 0.35 = 350,000
 
Case 2: status = 'archived' (not in MCV list)
  MCV covers: 0.35 + 0.25 + 0.20 + 0.15 + 0.05 = 1.00 (all values!)
  No non-MCV values exist
  Selectivity = 0.0 (or near-zero default)
  This correctly identifies 'archived' as non-existent
 
Case 3: status != 'cancelled'
  Selectivity = 1 - 0.05 = 0.95
  Estimated rows = 1,000,000 × 0.95 = 950,000
 
=============================================================
Histogram-based range estimation
=============================================================
 
Column: total_amount
Histogram: 100 equal-height buckets spanning [0, 10000]
Each bucket represents 1% of rows (after MCV exclusion)
MCV values removed: ~5% of rows in MCVs
 
Query: WHERE total_amount BETWEEN 500 AND 2000
 
Histogram bounds at 500: between bucket 5 and 6
Histogram bounds at 2000: between bucket 20 and 21
 
Full buckets covered: 6, 7, 8, ..., 20 = 15 buckets
Partial bucket at start: ~50% of bucket 5
Partial bucket at end: ~20% of bucket 21
 
Non-MCV selectivity: (14 + 0.5 + 0.2) × 0.01 = 0.147 (14.7%)
Apply to non-MCV fraction: 0.147 × 0.95 = 0.13965
Add any MCVs in range: assume 2% in this range
Final selectivity: 0.14 + 0.02 = 0.16
 
Estimated rows: 1,000,000 × 0.16 = 160,000

=============================================================
COMBINING SELECTIVITIES (Assuming Independence)
=============================================================
 
Given predicates P1, P2 with selectivities s1, s2:
 
AND (Conjunction):
  Selectivity(P1 AND P2) = s1 × s2
  
  Example: status = 'active' AND country = 'USA'
            s1 = 0.4, s2 = 0.3
            Combined = 0.4 × 0.3 = 0.12 (12%)
 
OR (Disjunction):
  Selectivity(P1 OR P2) = s1 + s2 - (s1 × s2)
  
  Example: status = 'pending' OR status = 'processing'
            s1 = 0.35, s2 = 0.25
            Combined = 0.35 + 0.25 - (0.35 × 0.25) = 0.5125
 
NOT (Negation):
  Selectivity(NOT P1) = 1 - s1
  
  Example: NOT (status = 'deleted')
            s1 = 0.05
            Combined = 1 - 0.05 = 0.95
 
=============================================================
MULTI-PREDICATE EXAMPLE
=============================================================
 
Query: WHERE status = 'active' 
         AND total > 100 
         AND created_date > '2024-01-01'
         
Individual selectivities (from statistics):
  status = 'active':        0.40
  total > 100:              0.70  
  created_date > '2024-01-01': 0.25
 
Combined (assuming independence):
  0.40 × 0.70 × 0.25 = 0.07 (7%)
 
For 1,000,000 rows:
  Estimated output = 70,000 rows

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

=============================================================
JOIN CARDINALITY ESTIMATION EXAMPLES
=============================================================
 
=== CASE 1: Primary Key to Foreign Key Join ===
orders: 1,000,000 rows, order_id is PK (n_distinct = 1,000,000)
order_items: 5,000,000 rows, order_id FK (n_distinct = 1,000,000)
 
|orders ⋈ order_items| = 1,000,000 × 5,000,000 / 1,000,000
                       = 5,000,000 rows
 
Interpretation: Each order has ~5 items on average, correct!
 
=== CASE 2: Many-to-Many Join ===
products: 50,000 rows, category_id (n_distinct = 100)
categories: 100 rows, id is PK (n_distinct = 100)
 
|products ⋈ categories| = 50,000 × 100 / MAX(100, 100)
                        = 50,000 rows
 
Each product matches exactly one category, correct!
 
=== CASE 3: Filtered Join ===
SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id
WHERE c.country = 'USA'
 
Step 1: Apply filter to customers
  customers: 100,000 rows × 0.30 (USA) = 30,000 rows
  
Step 2: Join filtered customers with orders
  orders: 1,000,000 rows, customer_id n_distinct = 80,000
  filtered customers: 30,000 rows, id n_distinct = 30,000
  
  |orders ⋈ filtered_customers| = 1,000,000 × 30,000 / MAX(80,000, 30,000)
                                = 1,000,000 × 30,000 / 80,000
                                = 375,000 rows
 
=== CASE 4: Problematic Data Skew ===
orders: 1,000,000 rows, customer_id (n_distinct = 80,000)
Statistics show uniform distribution, but:
  Top 100 customers account for 50% of orders!
  
Query: JOIN for top_customer with 50,000 orders
Estimated: 1,000,000 / 80,000 = 12.5 orders per customer
Actual: 50,000 orders for this customer
 
Error: 4000× underestimate for this specific join!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

-- PostgreSQL: Diagnosing cardinality estimation problems
-- ================================================================
 
-- STEP 1: Get estimated vs actual comparison
EXPLAIN (ANALYZE, VERBOSE, BUFFERS)
SELECT o.order_id, c.name, SUM(oi.quantity * oi.price)
FROM orders o
JOIN customers c ON o.customer_id = c.id
JOIN order_items oi ON o.order_id = oi.order_id
WHERE o.order_date >= '2024-01-01'
  AND c.country = 'Germany'
GROUP BY o.order_id, c.name;
 
-- STEP 2: Look for large discrepancies in output
 
/*
Hash Aggregate  (cost=45678... rows=5000...)  
               (actual time=567... rows=125000 loops=1)
               ^^^^^^^^      ^^^^^^^^
               Estimated     Actual     <- 25× UNDERESTIMATE
 
  ->  Hash Join  (cost=23456... rows=15000...)
                 (actual time=234... rows=450000 loops=1)
                                          <- 30× UNDERESTIMATE
      
      ... deeper nodes ...
      
      ->  Seq Scan on customers c  (cost=... rows=8000...)
                                   (actual time=... rows=7850 loops=1)
                                                           <- OK (1.02×)
*/
 
-- STEP 3: Identify the source of the error
 
-- Check statistics freshness
SELECT relname, n_live_tup, n_mod_since_analyze, last_analyze
FROM pg_stat_user_tables
WHERE relname IN ('orders', 'customers', 'order_items');
 
-- Check column statistics
SELECT attname, null_frac, n_distinct, 
       array_length(most_common_vals::text[], 1) as mcv_count
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'order_date';
 
-- Check for correlation issues
SELECT 
    s1.attname as col1,
    s2.attname as col2,
    'Potential correlation - consider extended stats'
FROM pg_stats s1
CROSS JOIN pg_stats s2
WHERE s1.tablename = 'customers' 
  AND s2.tablename = 'customers'
  AND s1.attname = 'country' 
  AND s2.attname = 'city';
 
-- STEP 4: Test if extended statistics help
CREATE STATISTICS customers_country_region (dependencies, ndistinct)
ON country, region, city FROM customers;
 
ANALYZE customers;
 
-- Re-run EXPLAIN ANALYZE and compare estimates

=============================================================
ADAPTIVE QUERY EXECUTION (Conceptual Flow)
=============================================================
 
Traditional (Static) Planning:
1. Parse query
2. Estimate cardinalities using statistics
3. Generate optimal plan based on estimates
4. Execute plan
5. (Estimates may have been 100× wrong - too late!)
 
Adaptive Execution (e.g., Oracle, SQL Server, Databricks):
1. Parse query
2. Estimate cardinalities using statistics
3. Generate initial plan with "adaptation points"
4. Begin execution
5. At first adaptation point:
   - Compare actual cardinality to estimate
   - If within threshold: continue current plan
   - If different: reoptimize remaining operations
6. Continue with potentially adjusted plan
7. Log discrepancy for future statistics improvement
 
Example - Hash Join Adaptation:
 
Initial estimate: 10,000 rows from filter
Plan: Build hash table on 10K rows, probe with 1M rows
 
Execution begins:
- After scanning: 500,000 rows pass filter (50× more!)
- Adaptation triggered
- Replan: Switch build/probe sides, allocate more memory
- Continue with adjusted strategy
 
Result: Query completes in 10 seconds instead of failing
 
=============================================================
MACHINE LEARNING CARDINALITY ESTIMATION (Research Systems)
=============================================================
 
Training Phase:
- Execute thousands of queries with EXPLAIN ANALYZE
- Extract features: columns referenced, predicate types, table sizes
- Training labels: actual cardinalities from execution
- Train model (neural network, XGBoost, etc.)
 
Inference Phase:
- New query arrives
- Extract query features
- Feed to trained model
- Model outputs cardinality predictions
- Optimizer uses ML predictions instead of formula-based estimates
 
Advantages:
- Captures complex relationships histograms miss
- Learns from actual workload patterns
- Improves automatically as more queries execute
 
Challenges:
- Requires significant training data
- Model maintenance as data changes
- Explaining/debugging ML predictions is hard
- Cold start for new tables or query patterns

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

-- PostgreSQL: Practical cardinality fixes
-- ================================================================
 
-- 1. Force ANALYZE with increased statistics
ALTER TABLE orders ALTER COLUMN customer_id SET STATISTICS 1000;
ALTER TABLE orders ALTER COLUMN order_date SET STATISTICS 500;
ANALYZE orders;
 
-- 2. Create extended statistics for correlated columns
CREATE STATISTICS orders_customer_date (dependencies, ndistinct, mcv)
ON customer_id, order_date FROM orders;
ANALYZE orders;
 
-- 3. Create statistics on computed expression
CREATE STATISTICS orders_year_month (ndistinct)
ON (EXTRACT(YEAR FROM order_date)), (EXTRACT(MONTH FROM order_date))
FROM orders;
ANALYZE orders;
 
-- 4. Materialize problematic subquery to get accurate stats
-- Instead of:
SELECT * FROM (
    SELECT customer_id, COUNT(*) as order_count
    FROM orders
    WHERE order_date >= '2024-01-01'
    GROUP BY customer_id
) subq
WHERE order_count > 100;
 
-- Create materialized intermediate:
CREATE MATERIALIZED VIEW recent_customer_order_counts AS
SELECT customer_id, COUNT(*) as order_count
FROM orders
WHERE order_date >= '2024-01-01'
GROUP BY customer_id;
 
ANALYZE recent_customer_order_counts;
 
-- Now query the materialized view
SELECT * FROM recent_customer_order_counts WHERE order_count > 100;
 
-- 5. Use ROWS estimate hint for stubborn UDFs (PostgreSQL)
CREATE FUNCTION get_customer_tier(customer_id INT)
RETURNS TEXT AS $$
  -- Complex logic here
$$ LANGUAGE plpgsql STABLE ROWS 1;
 
-- Tells optimizer: this function returns approximately 1 row per input
 
-- 6. Consider pg_hint_plan extension for row count overrides
-- (Third-party extension)
/*
SET pg_hint_plan.enable_hint = on;
 
SELECT /*+ Rows(orders #100) */ *
FROM orders o
JOIN order_items oi ON o.id = oi.order_id;
*/