Histograms

Min/max values and uniform distribution assumptions work adequately when data is evenly spread across ranges. But real-world data is rarely so cooperative. Consider a salary column where:

• 60% of employees earn between $40,000-$60,000
• 30% earn between $60,000-$100,000
• 10% are executives earning $100,000-$500,000

A simple uniform-range calculation for salary > 100000 would estimate 80% selectivity (based on the range 0-500K). The true selectivity is just 10%. Such errors lead to catastrophically wrong query plans.

Histograms solve this problem by dividing the value range into buckets that capture the actual data distribution, enabling precise selectivity estimates for any range predicate.

In the context of database statistics, a histogram is a data structure that approximates the distribution of values in a column by dividing the value domain into buckets. Each bucket represents a range of values and stores summary statistics about that range.

Histogram Anatomy:

Column: salary (range $0 - $500,000)

Bucket | Range              | Row Count | Frequency
-------+--------------------+-----------+-----------
  1    | $0 - $40,000       |   50,000  |   5%
  2    | $40,000 - $60,000  |  600,000  |  60%
  3    | $60,000 - $100,000 |  300,000  |  30%
  4    | $100,000 - $500,000|   50,000  |   5%
                             ----------
                             1,000,000    100%

With this histogram, the optimizer can precisely estimate:

• salary > 100000: ~5% (bucket 4 only)
• salary BETWEEN 40000 AND 60000: ~60% (bucket 2)
• salary < 60000: ~65% (buckets 1 + 2)

The two fundamental histogram designs differ in how they partition the value domain into buckets.

Understanding how databases build histograms clarifies their limitations and helps interpret their contents.

Equi-Depth Histogram Construction:

Algorithm: BuildEquiDepthHistogram(column, num_buckets)

1. SAMPLE: Collect sample of rows (e.g., 30,000 rows)
   sample = RandomSample(column, sample_size)

2. SORT: Sort sampled values
   sorted_values = Sort(sample)

3. PARTITION: Divide into equal-count buckets
   rows_per_bucket = sample_size / num_buckets
   
   FOR i = 0 TO num_buckets - 1:
       start_idx = i * rows_per_bucket
       end_idx = (i + 1) * rows_per_bucket - 1
       
       bucket[i].low = sorted_values[start_idx]
       bucket[i].high = sorted_values[end_idx]
       bucket[i].frequency = rows_per_bucket / sample_size

4. EXTRAPOLATE: Scale frequencies to full table
   FOR each bucket:
       bucket.estimated_rows = bucket.frequency * table_row_count

5. STORE: Write histogram to system catalog

Handling Edge Cases:

Repeated Values at Bucket Boundaries:

Sorted sample: [10, 10, 10, 10, 20, 20, 30, 40, 50, 60]
With 2 buckets, boundary falls on repeated 10s

Solution 1: Include all identical values in same bucket
  Bucket 1: [10, 10, 10, 10, 20]  — 5 values
  Bucket 2: [20, 30, 40, 50, 60]   — 5 values (20 split)

Solution 2: Popular value extraction
  MCV: 10 (frequency 0.4)
  Histogram: [20, 30], [40, 50, 60]

Sparse Regions:

Sorted sample: [1, 2, 3, 1000000, 1000001]
With 2 buckets:
  Bucket 1: [1, 2, 3]        — dense region
  Bucket 2: [1000000, 1000001] — sparse, long range
  
  Query: value = 500000
  Bucket 2 contains it, but actual frequency is 0!

This is why equi-depth outperforms equi-width for skewed data—the sparse region gets a single wide bucket instead of many empty ones.

Histograms transform range predicate selectivity from crude estimation to precise calculation. Here's how the optimizer uses histograms:

Algorithm: Histogram Range Selectivity

Function: EstimateRangeSelectivity(histogram, low, high)

1. LOCATE BUCKETS: Find buckets overlapping [low, high]
   start_bucket = FindBucket(low)
   end_bucket = FindBucket(high)

2. FULL BUCKETS: Sum frequency of fully contained buckets
   full_selectivity = SUM(bucket.frequency) 
                      for buckets between start_bucket and end_bucket

3. PARTIAL BUCKETS: Interpolate for boundary buckets
   
   For start_bucket (if partially overlapped):
     overlap_fraction = (bucket.high - low) / bucket.width
     start_contrib = bucket.frequency * overlap_fraction
   
   For end_bucket (if partially overlapped):
     overlap_fraction = (high - bucket.low) / bucket.width
     end_contrib = bucket.frequency * overlap_fraction

4. COMBINE: Return total selectivity
   RETURN start_contrib + full_selectivity + end_contrib

Worked Example:

Histogram for 'price' column (equi-depth, 4 buckets, 100K rows each):

Bucket | Range        | Count  | Frequency
-------+--------------+--------+-----------
  1    | $0 - $25     | 100,000|   25%
  2    | $25 - $50    | 100,000|   25%
  3    | $50 - $100   | 100,000|   25%
  4    | $100 - $500  | 100,000|   25%

Query: WHERE price BETWEEN 30 AND 120

1. Locate buckets:
   - $30 falls in bucket 2 (range $25-$50)
   - $120 falls in bucket 4 (range $100-$500)

2. Full buckets: 
   - Bucket 3 ($50-$100) is fully contained: 25%

3. Partial buckets:
   - Bucket 2: overlap = ($50 - $30) / ($50 - $25) = 20/25 = 80%
     contribution = 25% × 0.80 = 20%
   - Bucket 4: overlap = ($120 - $100) / ($500 - $100) = 20/400 = 5%
     contribution = 25% × 0.05 = 1.25%

4. Total selectivity: 20% + 25% + 1.25% = 46.25%
   Estimated rows: 400,000 × 0.4625 = 185,000

The number of histogram buckets directly impacts estimation accuracy. More buckets capture finer distribution details but consume more storage and increase maintenance overhead.

Estimation Error Analysis:

For an equi-depth histogram with k buckets:

Maximum estimation error for any range query:
  error ≤ 2/k (two bucket-boundary approximations)

With 100 buckets: max error ≤ 2% per bucket boundary
With 200 buckets: max error ≤ 1% per bucket boundary

When to Increase Bucket Count:

1. Query performance is sensitive to accurate cardinality estimates for this column
2. Data is highly skewed with multiple density regions
3. Range queries dominate the workload on this column
4. Join cardinality depends on this column and is frequently misestimated

Histograms are powerful but not perfect. Understanding their limitations helps diagnose estimation problems.

The Correlation Problem in Detail:

Table: employees (100,000 rows)

Column: department (10 distinct values)
  - Engineering: 50,000 rows (50%)
  - Sales: 30,000 rows (30%)
  - Other 8 depts: 20,000 rows (20%)

Column: skill (100 distinct values)
  - 'python': 40,000 rows (40%) — but 95% are in Engineering!
  - 'sales_training': 25,000 rows (25%) — 100% are in Sales

Query: WHERE department = 'Engineering' AND skill = 'python'

Optimizer's estimate (independence assumption):
  sel = sel(Engineering) × sel(python)
  sel = 0.50 × 0.40 = 0.20
  estimated_rows = 100,000 × 0.20 = 20,000

Actual rows:
  38,000 (95% of python users are in Engineering!)

Error: 1.9x underestimate

This correlation blindness is why some databases support extended statistics (PostgreSQL) or multi-column statistics (SQL Server) that capture cross-column dependencies.

Modern database systems employ sophisticated techniques to overcome basic histogram limitations.

1. Extended Statistics for Correlations (PostgreSQL):

-- Create statistics tracking correlation between columns
CREATE STATISTICS ext_dept_skill (dependencies)
ON department, skill
FROM employees;

ANALYZE employees;

-- Now optimizer uses functional dependency:
-- P(skill | department) instead of assuming independence

2. Filtered Statistics (SQL Server):

-- Create histogram only for subset of data
CREATE STATISTICS stat_recent_orders
ON orders (amount)
WHERE order_date >= '2024-01-01'
WITH FULLSCAN;

-- Optimizer uses this for queries with matching filter

3. Expression Statistics:

-- PostgreSQL: Statistics on expressions
CREATE STATISTICS expr_stats 
ON (EXTRACT(YEAR FROM order_date))
FROM orders;

-- Now WHERE EXTRACT(YEAR FROM order_date) = 2024 can use histogram

4. Adaptive Statistics and Machine Learning:

Some advanced commercial databases use query feedback to improve estimates:

1. Execute query with estimated cardinalities
2. Observe actual cardinalities during execution
3. Update statistical model with observed data
4. Future queries benefit from learned corrections

-- SQL Server Adaptive Query Processing:
-- Memory grant feedback
-- Batch mode adaptive joins
-- Interleaved execution

-- Oracle Adaptive Plans:
-- Runtime plan switching based on actual cardinality

5. Incremental Histogram Updates:

Instead of rebuilding histograms from scratch:

-- Track insertions/deletions by bucket
-- Adjust bucket frequencies incrementally
-- Rebalance when buckets become too uneven

-- This reduces the cost of keeping histograms fresh
-- But accumulates error over time (periodic full refresh needed)