Cardinality Estimation

Understanding cardinality estimation

Cardinality estimation addresses a fundamental challenge in database systems: determining how many unique values exist in a dataset without exhaustively counting them. This is particularly important in time-series databases where datasets can be massive and continuous.

For example, in a financial trading system monitoring stock transactions, you might need to estimate:

• Number of unique traders per day
• Distinct symbols traded in a time window
• Unique price levels observed

Exact counting would require storing every value in memory, which becomes impractical at scale. Cardinality estimation algorithms provide efficient approximations with controlled error rates.

How cardinality estimation works

Most modern cardinality estimation techniques use probabilistic data structures that maintain a compact representation of the observed values. Popular algorithms include:

1. HyperLogLog: Uses bit pattern observations to estimate cardinality
2. Linear Counting: Employs a bitmap and probability theory
3. LogLog Counting: Provides estimates using logarithmic space complexity

These algorithms trade perfect accuracy for dramatic improvements in memory efficiency.

Applications in time-series databases

Cardinality estimation serves several critical functions in time-series databases:

Query optimization

• Helps the query planner choose efficient execution strategies
• Estimates result set sizes for join operations
• Optimizes memory allocation for aggregations

Resource management

• Prevents unexpected memory spikes from high-cardinality operations
• Guides partitioning decisions for better data distribution
• Supports capacity planning and scaling decisions

Performance monitoring

SELECT 
    symbol,
    count(DISTINCT price) AS unique_prices,
    count(*) AS total_trades
FROM trades
WHERE timestamp > dateadd('h', -1, now())
GROUP BY symbol;

Considerations and tradeoffs

When implementing cardinality estimation, several factors need consideration:

Accuracy vs. memory usage

• Higher accuracy requires more memory
• Error bounds typically follow statistical distributions
• Most algorithms offer configurable precision/memory tradeoffs

Update performance

• Some algorithms support incremental updates
• Others require periodic rebuilding
• Write-heavy workloads may need specialized approaches

Scale requirements

• Small datasets might not benefit from estimation
• Very large datasets require careful algorithm selection
• Distributed systems need consistent estimation across nodes

Best practices

1. Choose appropriate error bounds for your use case
2. Monitor estimation accuracy over time
3. Consider using different algorithms for different cardinality ranges
4. Test with realistic data volumes and patterns
5. Account for estimation errors in dependent systems

Remember that cardinality estimation is about finding the right balance between accuracy and resource usage for your specific requirements.