SQL 106 🛢️ Cost-Based Optimizer (CBO) Statistics and Histograms

The cost-based optimizer is the component of a database that decides how to execute a query. It does not guess. It reads statistics about the tables, columns, and indexes involved, estimates how many rows each step of the plan will produce, and assigns a cost to every candidate plan. The plan with the lowest cost wins. The entire decision rests on the quality of the statistics. When the statistics are accurate, the optimizer picks the right plan. When they are stale, missing, or mischaracterized, the optimizer picks a plan that can be orders of magnitude slower than the alternative .

The statistics come in two flavors. The basic statistics are the row count of the table, the number of distinct values in a column, the fraction of nulls, and the average row length. The histogram is the second flavor: it captures the distribution of values within a column, which is what allows the optimizer to estimate selectivity for a predicate that matches some values much more often than others . A column with a uniform distribution needs no histogram. A column with skew—where 90% of the rows share one value—needs one, because without it the optimizer assumes uniformity and produces an estimate that is wrong by orders of magnitude.

Key point: The optimizer estimates cardinality by combining the table’s row count with the selectivity of each predicate. Selectivity comes from the column’s statistics and histogram. Without a histogram, the optimizer assumes a uniform distribution, which is wrong for skewed data. The histogram is what tells the optimizer that status = 'COMPLETED' matches 90% of the table while status = 'FAILED' matches 5% .

---

Why statistics and histograms determine the plan

The cardinality estimation problem. Every plan decision is a bet on how many rows the next step will produce. A nested loop join is fast when the outer table is small and slow when it is large. A hash join is the reverse. The optimizer chooses between them based on the estimated cardinality of the outer input. If the estimate is wrong by a factor of a thousand, the optimizer picks the wrong join method and the query runs for minutes instead of milliseconds . The statistics are the input to that estimate, and the histogram is the part of the statistics that handles skew.

The uniform-distribution assumption. Without a histogram, the optimizer assumes that every distinct value in a column appears the same number of times. The selectivity of an equality predicate is 1 / num_distinct. This assumption is correct for a primary key or a unique column. It is catastrophically wrong for a status column where one value dominates. The histogram removes the assumption for the columns where it matters .

The MCV problem. PostgreSQL splits the distribution information into two structures: the most-common-values (MCV) list and the histogram. The MCV list holds the values that appear significantly more often than the average, and their exact frequencies. The histogram covers the remaining values, which are assumed to be roughly uniform. When a query asks for a value in the MCV list, the selectivity is the exact frequency from the list. When the value is not in the list, the selectivity is computed from the remaining fraction of the column divided by the remaining number of distinct values . This split is what makes the estimation precise for the skewed values without wasting histogram buckets on them.

The staleness problem. Statistics are a snapshot. When rows are inserted, updated, or deleted, the distribution changes, and the snapshot becomes a lie. The optimizer’s estimate drifts from reality, and the plan it chooses drifts from optimal. The automatic statistics update mechanisms exist to keep the snapshot current, but they are thresholds, not continuous synchronization. SQL Server’s AUTO_UPDATE_STATISTICS counts row modifications and triggers an update when the count exceeds a threshold derived from the table’s cardinality . The threshold is the compromise between the cost of gathering statistics and the cost of a bad plan.

---

a. The basic statistics and the selectivity calculation

The basic statistics are the inputs to the selectivity formula. The table’s cardinality is the number of rows. The column’s n_distinct is the number of distinct values. The null_frac is the fraction of rows that are null.

For an equality predicate on a column with no histogram, the selectivity is (1 - null_frac) / n_distinct. The estimated rows is cardinality * selectivity. For a range predicate, the histogram is used to interpolate how many values fall below the boundary.

-- The statistics for a column, as PostgreSQL stores them
-- null_frac: fraction of nulls
-- n_distinct: number of distinct values
-- most_common_vals: the MCV list
-- most_common_freqs: the frequency of each MCV
-- histogram_bounds: the bucket boundaries
SELECT null_frac, n_distinct, most_common_vals, most_common_freqs, histogram_bounds
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'status';

The histogram_bounds is an array of values that divide the column into equal-frequency buckets. When a query asks for status < 'shipped', the optimizer locates the bucket that contains 'shipped', counts the whole buckets before it, and interpolates within the bucket. The result is a selectivity estimate that reflects the actual distribution rather than a uniform assumption .

The histogram is not useful for equality predicates on skewed columns. That is what the MCV list is for. PostgreSQL’s scalar1tsel function first applies the equality condition to each MCV and sums the frequencies of the matching ones. If the value is not in the MCV list, it falls back to the histogram formula . This two-part estimation is why the MCV list and the histogram are not redundant: they cover different parts of the distribution.

---

b. The histogram types and when they are chosen

Different databases offer different histogram types, and the type is chosen based on the number of distinct values and the skew.

Oracle uses four histogram types. A frequency histogram is used when the number of distinct values is less than or equal to 254. It stores one bucket per distinct value with the exact frequency, which is the most precise form. A top-frequency histogram is used when the number of distinct values exceeds 254 but a small number of values cover a large fraction of the rows. It stores only the most frequent values and their frequencies. A hybrid histogram, introduced in Oracle 12c, is used when neither of the first two applies; it combines the most frequent values with height-balanced buckets for the rest. A height-balanced histogram is the legacy type and is no longer recommended .

-- Oracle: gather statistics with a frequency histogram on the status column
-- SIZE 254 means up to 254 buckets, which covers all distinct values if they are fewer
BEGIN
  DBMS_STATS.GATHER_TABLE_STATS(
    ownname   => 'HR',
    tabname   => 'ORDERS',
    method_opt => 'FOR COLUMNS SIZE 254 STATUS'
  );
END;

MySQL’s histogram support is more limited. ANALYZE TABLE ... UPDATE HISTOGRAM ON column WITH N BUCKETS creates a histogram, and the bucket count ranges from 1 to 1024. If the bucket count is omitted, the default is 100 . The histogram is stored in the data dictionary and is used by the optimizer when the column is not covered by an index prefix. MySQL does not support histograms on encrypted tables, temporary tables, JSON columns, or geometry columns .

SQL Server’s statistics objects contain a histogram by default. The histogram is a set of up to 200 steps, each representing a range of values and the estimated number of rows in that range. The AUTO_CREATE_STATISTICS option creates single-column statistics on predicate columns that do not already have a histogram in an existing statistics object, and the names of these auto-created statistics start with _WA .

---

c. The maintenance and the staleness problem

The statistics are only useful if they are current. The maintenance mechanisms differ by database, but the trade-off is the same: gathering statistics costs I/O and CPU, and stale statistics cost bad plans.

SQL Server’s automatic update threshold is the most documented. For a table with more than 500 rows, the pre-2016 threshold was 500 + 0.20 * n, where n is the row count at the last statistics update. For a 20,000-row table, that is 4,500 modifications before an update. Starting with SQL Server 2016 and compatibility level 130, the threshold is MIN(500 + 0.20 * n, SQRT(1000 * n)). For a 2-million-row table, that is MIN(400,500, 44,721), which means the statistics update every 44,721 modifications instead of every 400,500 . The dynamic threshold is what keeps large tables’ statistics from drifting too far before an update.

Oracle’s automatic statistics gathering runs as a scheduled job. The DBMS_STATS package gathers the statistics, and the METHOD_OPT parameter controls whether histograms are created. SIZE AUTO lets Oracle decide which columns need a histogram based on the workload, and SIZE SKEWONLY creates one only when the data is skewed . The warning is that histograms on columns used with bind variables can cause plan instability, because the optimizer peeks at the bind value and chooses a plan for that value, but the next execution with a different value may get a different plan .

The other maintenance consideration is the dynamic sampling option. When the statistics are missing or the optimizer cannot estimate selectivity from them, dynamic sampling scans a sample of the table at query compile time to estimate the selectivity directly. It is the fallback when the stored statistics are insufficient, and it is expensive because it adds I/O to the compilation step .

---

Complete Example Session

The following session traces the estimation of a query against a skewed column, showing the MCV and histogram behavior.

-- ============================================
-- PART 1: THE TABLE AND ITS STATISTICS
-- ============================================
-- The orders table has 10,000 rows
-- The status column has 676 distinct values
-- The MCV list contains the 10 most frequent values
-- The most common value appears 3.3% of the time
-- The histogram covers the remaining values

-- ============================================
-- PART 2: EQUALITY ON AN MCV
-- ============================================
-- The value 'CRAAAA' is in the MCV list
-- Its frequency is 0.003
-- The estimated rows is 10000 * 0.003 = 30
EXPLAIN SELECT * FROM orders WHERE status = 'CRAAAA';

-- ============================================
-- PART 3: EQUALITY ON A NON-MCV
-- ============================================
-- The value 'xxx' is not in the MCV list
-- The selectivity is (1 - sum(mcv_freqs)) / (n_distinct - num_mcv)
-- = (1 - 0.03) / (676 - 10) = 0.001456
-- The estimated rows is 10000 * 0.001456 = 15
EXPLAIN SELECT * FROM orders WHERE status = 'xxx';

-- ============================================
-- PART 4: RANGE ON A HISTOGRAM COLUMN
-- ============================================
-- The histogram divides the column into 10 equal-frequency buckets
-- The value 1000 falls in the second bucket
-- The selectivity is calculated by counting the first bucket and
-- interpolating within the second
-- The estimated rows is 10000 * 0.1007 = 1007
EXPLAIN SELECT * FROM orders WHERE unique1 < 1000;

-- ============================================
-- PART 5: THE STALENESS PROBLEM
-- ============================================
-- Insert 5,000 rows with status = 'CRAAAA'
-- The statistics are now stale
-- The optimizer still estimates 30 rows for the MCV
-- The actual number is 5,030
-- The plan may be wrong because the estimate is wrong

The five parts cover the statistics structure, the MCV estimation, the non-MCV estimation, the histogram estimation, and the staleness problem. What the session demonstrates is that the estimate for a skewed value is precise when the value is in the MCV list, approximate when it is not, and wrong when the statistics are stale.

---

Quick Reference

Statistics Components

Component	Purpose
Cardinality	Table row count
n_distinct	Number of distinct values
null_frac	Fraction of nulls
MCV list	Most common values and frequencies
Histogram	Bucket boundaries for the rest

Histogram Types (Oracle)

Type	When Used
Frequency	NDV <= 254
Top-frequency	NDV > 254, few values dominate
Hybrid	NDV > 254, 12c+
Height-balanced	Legacy

Maintenance (SQL Server)

Cardinality	Threshold (pre-2016)	Threshold (2016+)
n <= 500	500	500
n > 500	500 + 0.20*n	MIN(500 + 0.20*n, SQRT(1000*n))

Selectivity Formula

Predicate	Selectivity
Equality on MCV	mcv_freq
Equality not on MCV	(1 - sum(mcv_freqs)) / (n_distinct - num_mcv)
Range	Histogram interpolation

---

Best Practices

✅ Do This:

-- Create histograms on skewed predicate columns
DBMS_STATS.GATHER_TABLE_STATS(..., method_opt => 'FOR COLUMNS SIZE 254 STATUS');

-- Use parameters, not local variables, in queries
-- The optimizer cannot estimate a local variable's value
CREATE PROCEDURE GetOrders @status VARCHAR(20) AS
  SELECT * FROM orders WHERE status = @status;

❌ Don’t Do This:

-- Assume uniform distribution on a skewed column
-- Without a histogram, the estimate is wrong

-- Let statistics go stale on a heavily modified table
-- The estimate drifts, the plan degrades

---

Common Pitfalls

Pitfall	Why It Happens	Fix
Wrong plan for skewed data	No histogram	Create one
Plan changes between executions	Bind variable peeking + histogram	Avoid histograms on bind-variable columns
Statistics not updating	AUTO_UPDATE_STATISTICS off	Turn it on
Estimate wrong after bulk load	Statistics stale	Update after load
Histogram not created	Column type unsupported (MySQL)	Check the type

---

Real-World Examples

1. Frequency histogram

DBMS_STATS.GATHER_TABLE_STATS(..., method_opt => 'FOR COLUMNS SIZE 254 STATUS');

2. MCV selectivity

-- status = 'CRAAAA' is in the MCV list
-- selectivity = 0.003

3. Non-MCV selectivity

-- status = 'xxx' is not in the MCV list
-- selectivity = (1 - sum(mcv)) / (n_distinct - num_mcv)

4. Histogram interpolation

-- unique1 < 1000
-- selectivity = 0.1007

5. SQL Server threshold

-- 2M rows: MIN(400500, 44721) = 44721 modifications

6. MySQL histogram

ANALYZE TABLE t UPDATE HISTOGRAM ON c1 WITH 10 BUCKETS;

7. Oracle hybrid histogram

-- NDV > 254, not top-frequency
-- hybrid histogram chosen

8. Dynamic sampling

-- When statistics are missing, the optimizer samples the table

9. Auto-created statistics

-- SQL Server: names start with _WA

10. Stale statistics

-- After 5000 inserts, the MCV estimate is wrong by 167x

---

Visual

Cardinality Estimation

┌──────────────────────────────────────────────┐
│  Query: WHERE status = 'CRAAAA'              │
│         │                                    │
│         ▼                                    │
│  Is 'CRAAAA' in the MCV list?                │
│    ├─ YES → selectivity = mcv_freq           │
│    └─ NO  → selectivity = remaining fraction │
│         │                                    │
│         ▼                                    │
│  rows = cardinality * selectivity            │
└──────────────────────────────────────────────┘

MCV and Histogram Split

┌──────────────────────────────────────────────┐
│  Column distribution                         │
│  ┌────────────────────────────────────────┐  │
│  │ MCV list: most frequent values         │  │
│  │ exact frequencies, up to 254 values    │  │
│  ├────────────────────────────────────────┤  │
│  │ Histogram: the remaining values        │  │
│  │ equal-frequency buckets, interpolation │  │
│  └────────────────────────────────────────┘  │
└──────────────────────────────────────────────────────────────┘

Staleness Drift

┌──────────────────────────────────────────────┐
│  Statistics gathered: 10,000 rows            │
│  MCV 'CRAAAA' freq = 0.003 → estimate 30     │
│         │                                    │
│         ▼                                    │
│  Bulk insert 5,000 'CRAAAA'                  │
│         │                                    │
│         ▼                                    │
│  Actual rows = 5,030                         │
│  Estimate = 30                               │
│  Error factor = 167x                         │
└──────────────────────────────────────────────┘

---

Summary

Item	Value
Optimizer type	Cost-based
Statistics input	Cardinality, distinct values, nulls
Histogram purpose	Capture skew
MCV list	Most frequent values
Histogram	Remaining values
Oracle histogram types	Frequency, top-frequency, hybrid
MySQL bucket range	1–1024
SQL Server auto-update	Threshold-based
Staleness cost	Wrong cardinality, wrong plan

Key takeaways:

• The optimizer’s plan is only as good as its statistics. Cardinality estimates drive every join and access method decision, and the statistics are the input to those estimates .
• The histogram captures skew. Without it, the optimizer assumes uniform distribution, which is wrong for columns like status codes where one value dominates .
• The MCV list and the histogram are complementary. The MCV list holds the most frequent values with exact frequencies; the histogram covers the rest with bucket interpolation .
• Statistics go stale. The automatic update thresholds are the compromise between the cost of gathering and the cost of a bad plan. SQL Server’s dynamic threshold is MIN(500 + 0.20*n, SQRT(1000*n)) for large tables .
• Histograms on bind-variable columns can cause plan instability. The optimizer peeks at the bind value, and a plan built for one value may not suit the next .
• Dynamic sampling is the fallback. When statistics are missing or insufficient, the optimizer samples the table at compile time, at the cost of extra I/O .

Remember: The cost-based optimizer is a machine that makes decisions from data. The data is the statistics, and the histogram is the part of the statistics that describes the shape of the data rather than just its size. When the shape is skewed and the histogram is missing, the estimate is wrong and the plan is wrong. When the data changes and the statistics are stale, the estimate drifts and the plan drifts. The maintenance of statistics is not a background chore; it is the input to every query plan the database will ever choose.

---

---

Stop using slow, ad-bloated tool sites! 🤮

🔎 Search “KandZ Tools” on Google to use many professional utilities for free.

KandZ.me is the ultimate minimalist hub for:
✅ Finance (Mortgage, Interest, Inflation)
✅ Tech (Base64, JSON, Dev Suite, IP)
✅ Health (BMI, BMR, TDEE)
✅ Productivity (Timer, Workspace, QR)

⚡️ Fast & Private
🔒 No data leaves your device
💎 100% Free

🔗 Use it now: https://tools.kandz.me
🔖 Bookmark it—you’ll need it later!