Advanced Cardinality Estimation

Executive Summary

Target Industries: Data warehousing, Business intelligence, Analytics platforms

Problem Being Solved

The Query Plan Disaster

Poor cardinality estimation causes severe query performance issues:

• Hash join vs nested loop decision completely wrong
• Memory allocation failures from underestimated results

Current Pain Points

• Outdated Statistics: Manual ANALYZE runs become stale
• Correlation Blindness: Independent column assumptions fail
• Skew Handling: Uniform distribution assumptions wrong
• Join Estimation: Compound errors across multiple joins
• Complex Predicates: AND/OR combinations poorly estimated
• Subquery Opacity: Nested query cardinality unknown
• Dynamic Data: Statistics lag behind data changes

Why This Problem Exists

Traditional estimators use simplistic assumptions:

• Independence assumption ignores correlations
• Histograms are single-column only
• No learning from execution feedback
• Manual statistics collection
• No probabilistic data structures

Technical Implementation

Cardinality Estimation Architecture

Query Parser                    Cardinality Engine                    Statistics Store
+-------------------+          +--------------------+            +-------------------+
|                   |          |                    |            |                   |
| SELECT ... WHERE  |--Parse--> | Predicate Analyzer |            | Single-Column     |
| col1 = X AND      |          | - Extract filters  |            | Multi-Column      |
| col2 BETWEEN Y,Z  |          | - Identify joins   |            | HyperLogLog       |
|                   |          | - Subquery detect  |            | ML Models         |
+-------------------+          +--------------------+            +-------------------+
                                        |                                 ^
                                        v                                 |
                               +--------------------+                     |
                               | Estimator Ensemble |                     |
                               | - Histogram lookup |<----Feedback--------|
                               | - HLL cardinality  |
                               | - ML prediction    |
                               +--------------------+
                                        |
                                        v
                               +--------------------+
                               | Confidence Scorer  |
                               | - Estimate range   |
                               | - Uncertainty      |
                               | - Alternative plans|
                               +--------------------+

Cardinality Configuration

-- Configure advanced cardinality estimation
SELECT helios_cardinality_configure(
    config => '{
        "estimators": {
            "single_column_histogram": {"buckets": 200, "mcv_count": 100},
            "multi_column_histogram": {"enabled": true, "max_columns": 5},
            "hyperloglog": {"precision": 14},
            "ml_model": {"enabled": true, "model_type": "gradient_boosting"}
        },
        "auto_statistics": {
            "enabled": true,
            "sample_rate": 0.01,
            "refresh_threshold_pct": 10
        },
        "feedback_learning": {
            "enabled": true,
            "min_samples": 100,
            "learning_rate": 0.1
        }
    }'::jsonb
);

-- System tables for statistics
CREATE TABLE _helios_column_stats (
    table_name TEXT,
    column_name TEXT,
    distinct_count BIGINT,
    null_count BIGINT,
    histogram BYTEA,
    mcv_values JSONB,
    mcv_frequencies FLOAT[],
    hll_sketch BYTEA,
    last_updated TIMESTAMP,
    PRIMARY KEY (table_name, column_name)
);

CREATE TABLE _helios_correlation_stats (
    table_name TEXT,
    column_set TEXT[],
    correlation_coefficient FLOAT,
    multi_histogram BYTEA,
    last_updated TIMESTAMP,
    PRIMARY KEY (table_name, column_set)
);

Concrete Business Examples

Example 1: Complex Filter Cardinality

Scenario: E-commerce query with multiple correlated filters.

-- Query with correlated filters
EXPLAIN ANALYZE
SELECT *
FROM orders
WHERE customer_region = 'Northeast'
  AND product_category = 'Electronics'
  AND order_date BETWEEN '2024-01-01' AND '2024-03-31';

-- Traditional estimation (independence assumption):
/*

Actual: 45,000 rows (Northeast customers buy more electronics)

Plan impact: Chose nested loop instead of hash join
*/

-- HeliosDB multi-column histogram estimation:
SELECT * FROM helios_cardinality_explain(
    query => '
        SELECT * FROM orders
        WHERE customer_region = ''Northeast''
          AND product_category = ''Electronics''
          AND order_date BETWEEN ''2024-01-01'' AND ''2024-03-31''
    '
);

/*
{
    "query_id": "Q-001",
    "estimation_methods": {
        "traditional_independence": {
            "estimate": 7500,
            "confidence": "LOW"
        },
        "multi_column_histogram": {
            "column_set": ["customer_region", "product_category"],
            "correlation_detected": 0.72,
            "adjusted_estimate": 42000,
            "confidence": "HIGH"
        },
        "hll_distinct": {
            "distinct_combinations": 1234,
            "estimate": 44500,
            "confidence": "HIGH"
        },
        "ml_model": {
            "features_used": ["region", "category", "date_range", "historical_pattern"],
            "estimate": 45200,
            "confidence": "VERY_HIGH",
        }
    },
    "ensemble_estimate": {
        "final_estimate": 44800,
        "confidence_interval": [42000, 48000],
        "confidence_level": 0.95,
        "estimation_error_pct": 0.4
    },
    "actual_rows": 45000,
}
*/

-- Actual execution with correct estimate:
/*
->  Hash Join (correct plan chosen)
    Estimated rows: 44,800
    Actual rows: 45,000

*/

Example 2: Join Cardinality with Compound Errors

Scenario: Multi-table join where estimation errors compound.

-- Complex join query
EXPLAIN ANALYZE
SELECT
    c.customer_name,
    o.order_date,
    p.product_name,
    oi.quantity * oi.unit_price as line_total
FROM customers c
JOIN orders o ON c.customer_id = o.customer_id
JOIN order_items oi ON o.order_id = oi.order_id
JOIN products p ON oi.product_id = p.product_id
WHERE c.customer_segment = 'Enterprise'
  AND p.category = 'Premium'
  AND o.order_date >= '2024-01-01';

-- Traditional estimation with error compounding:
/*
customers (Enterprise): 5,000 (actual: 5,200)
orders join: 5,000 * 10 = 50,000 (actual: 85,000)  -- Enterprise orders more
order_items join: 50,000 * 3 = 150,000 (actual: 425,000)  -- More items per order
products filter: 150,000 * 0.1 = 15,000 (actual: 127,500)  -- Premium preference

Plan chosen: Nested loop (wrong!)
*/

-- HeliosDB join cardinality estimation
SELECT * FROM helios_join_cardinality_analyze(
    query => '...'  -- query above
);

/*
{
    "join_graph": [
        {
            "tables": ["customers", "orders"],
            "join_type": "INNER",
            "traditional_estimate": 50000,
            "adjusted_estimate": 82000,
            "adjustment_factors": [
                {"factor": "join_key_correlation", "multiplier": 1.4},
                {"factor": "predicate_interaction", "multiplier": 1.17}
            ]
        },
        {
            "tables": ["orders", "order_items"],
            "join_type": "INNER",
            "traditional_estimate": 150000,
            "adjusted_estimate": 410000,
            "adjustment_factors": [
                {"factor": "segment_ordering_pattern", "multiplier": 2.5},
                {"factor": "historical_feedback", "multiplier": 1.1}
            ]
        },
        {
            "tables": ["order_items", "products"],
            "join_type": "INNER",
            "traditional_estimate": 15000,
            "adjusted_estimate": 123000,
            "adjustment_factors": [
                {"factor": "premium_preference_correlation", "multiplier": 3.0},
                {"factor": "category_segment_affinity", "multiplier": 2.7}
            ]
        }
    ],
    "final_estimate": {
        "traditional": 15000,
        "ml_enhanced": 125000,
        "actual": 127500,
    },
    "plan_impact": {
    }
}
*/

Example 3: Real-Time Statistics Collection

Scenario: Fast-changing data requiring up-to-date statistics.

-- Enable real-time statistics for high-velocity table
SELECT helios_stats_configure_realtime(
    table_name => 'events',
    config => '{
        "collection_mode": "streaming",
        "sample_rate": 0.001,
        "update_frequency_ms": 1000,
        "hll_precision": 14,
        "sketch_merge_interval_sec": 60
    }'::jsonb
);

-- Statistics stay current with data changes
SELECT * FROM helios_stats_freshness('events');

/*
{
    "table": "events",
    "row_count": 847293847,
    "last_stats_update": "2024-03-15T14:23:44.789Z",
    "stats_age_seconds": 1.2,
    "data_changes_since_stats": 1234,
    "stats_freshness": "CURRENT",
    "collection_metrics": {
        "samples_collected": 847293,
        "hll_updates": 60,
        "histogram_refreshes": 60,
        "cpu_overhead_pct": 0.3
    },
    "accuracy_metrics": {
        "recent_queries": 12847,
    }
}
*/

-- Compare with stale statistics scenario
SELECT * FROM helios_stats_accuracy_comparison(
    table_name => 'events',
    compare_modes => ARRAY['realtime', 'hourly', 'daily']
);

/*
{
    "table": "events",
    "modes": {
        "realtime": {
            "p95_error_pct": 8,
            "queries_within_2x": 99.2
        },
        "hourly": {
            "p95_error_pct": 45,
            "queries_within_2x": 87.5
        },
        "daily": {
            "p95_error_pct": 150,
            "queries_within_2x": 72.3
        }
    },
    "recommendation": "Use realtime mode for time-sensitive analytics"
}
*/

Example 4: ML-Enhanced Estimation with Feedback

Scenario: Learning from query execution to improve estimates.

-- Enable ML feedback learning
SELECT helios_cardinality_ml_enable(
    config => '{
        "model_type": "gradient_boosting",
        "features": [
            "table_size",
            "predicate_type",
            "column_correlation",
            "historical_selectivity",
            "time_of_day",
            "data_recency"
        ],
        "feedback_learning": {
            "enabled": true,
            "sample_queries": true,
            "min_samples_for_update": 100,
            "learning_rate": 0.05
        },
        "online_learning": true
    }'::jsonb
);

-- After query execution, system learns
-- Query: SELECT * FROM orders WHERE status = 'pending' AND amount > 1000

-- ML feedback captured:
/*
{
    "query_id": "Q-12345",
    "predicate_signature": "status=X AND amount>Y",
    "estimation": {
        "traditional": 5000,
        "ml_predicted": 12300,
        "actual": 12847
    },
    "feedback": {
        "ml_error_pct": 4.3,
        "traditional_error_pct": 61.1,
        "model_updated": true
    }
}
*/

-- View ML model performance over time
SELECT * FROM helios_cardinality_ml_performance(
    period => interval '7 days'
);

/*
{
    "period": "7 days",
    "model_metrics": {
        "queries_analyzed": 1234567,
        "queries_used_for_training": 847293,
        "current_model_version": 47,
        "model_updates": 12
    },
    "accuracy_trend": {
    },
    "improvement": {
    },
    "learned_patterns": [
        {"pattern": "date range selectivity varies by day of week", "correction_applied": true},
        {"pattern": "amount filters have skewed distribution", "correction_applied": true}
    ]
}
*/

Example 5: Subquery and Complex Expression Estimation

Scenario: Nested queries with complex predicates.

-- Complex query with subquery and expressions
EXPLAIN ANALYZE
SELECT *
FROM orders o
WHERE o.customer_id IN (
    SELECT customer_id
    FROM customers
    WHERE signup_date >= '2023-01-01'
      AND total_purchases > 10000
)
AND o.order_total * (1 - o.discount_pct) > 500
AND o.status IN ('shipped', 'delivered');

-- Traditional estimation completely fails:
/*
Expression (order_total * (1 - discount_pct)): Estimated poorly
IN list: Simple selectivity calculation

*/

-- HeliosDB advanced estimation
SELECT * FROM helios_cardinality_complex_analyze(
    query => '...'  -- query above
);

/*
{
    "query_components": {
        "subquery": {
            "type": "IN_SUBQUERY",
            "subquery_estimation": {
                "traditional": 1000,
                "materialized_estimate": 8234,
                "actual": 8456,
            },
            "technique": "subquery_materialization_cardinality"
        },
        "expression_predicate": {
            "expression": "order_total * (1 - discount_pct) > 500",
            "computed_estimate": {
                "technique": "expression_histogram_projection",
                "selectivity": 0.67,
                "confidence": 0.92
            }
        },
        "in_list_predicate": {
            "expression": "status IN ('shipped', 'delivered')",
            "mcv_based_estimate": 0.72,
            "actual_selectivity": 0.71,
        }
    },
    "final_estimation": {
        "traditional": 5000,
        "advanced": 42300,
        "actual": 43567,
    }
}
*/

Conclusion

Key Value Propositions:

• ML-enhanced - Learns from query execution
• Multi-column aware - Handles correlations
• Real-time statistics - Always current
• Complex query support - Subqueries, expressions

Call to Action: Enable advanced cardinality with SELECT helios_cardinality_configure();