Skip to content
Tutorials Center
My learning

Topics

Lesson 61 of 79 ยท Query Processing and Optimization

Statistics, Cost Estimation and Plan Search

How a cost-based optimizer estimates row counts with statistics and histograms, searches join orders with dynamic programming, and how ANALYZE changes SQLite plans.

A query can be executed in thousands of ways: different join orders, different join algorithms, an index scan or a table scan for each table. A cost-based optimizer chooses among them by estimating what each candidate plan would cost and picking the cheapest. The estimates come from statistics the database keeps about its own data. If the statistics are good, the plans are usually good. If they are stale or the data is skewed, an optimizer can pick a plan that is a hundred times slower than the best one.

This lesson covers the three parts of that machinery: estimating how many rows each step produces (cardinality estimation), turning row counts into cost, and searching the space of plans, especially join orders, with dynamic programming. You will also see the live effect of ANALYZE on the plans of SQLite. It follows the query processing pipeline and chooses among the join algorithms you just met.

What an optimizer needs

Statistics Row counts, distinct values, histograms.
Selectivity The fraction of rows a predicate keeps.
Cost model I/O and CPU for each operator.
Plan search Join order and algorithm choices.

Estimate, then compare, then pick the cheapest.

1 / 2

Statistics a catalog keeps

For every table the catalog stores at least the number of rows (and pages). For every column it typically stores:

  • the number of distinct values (often written V(A));
  • the minimum and maximum values;
  • the fraction of NULLs;
  • the most common values with their frequencies;
  • a histogram of the rest.

Statistics are refreshed by a command (ANALYZE in SQLite and PostgreSQL, UPDATE STATISTICS in SQL Server) or by background jobs, so they can lag behind the data. They are also stored as ordinary rows you can read, as you will see in SQLite's sqlite_stat1 table.

Selectivity and cardinality

The selectivity of a predicate is the fraction of rows it keeps, a number between 0 and 1. The estimated output size, the cardinality, is rows ร— selectivity. The standard formulas assume values are spread uniformly and that predicates are independent:

  • A = constant: selectivity 1 / V(A).
  • A > constant: roughly (max - constant) / (max - min).
  • p1 AND p2: multiply the selectivities. p1 OR p2: s1 + s2 - s1 ร— s2. NOT p: 1 - s.
  • Equi-join R.a = S.b: |R| ร— |S| / max(V(R.a), V(S.b)). Read this as: every R row matches about |S| / V(S.b) rows of S, assuming the key values of the smaller domain are all present in the larger.

These assumptions are wrong for real data. A column status with the values shipped (94% of rows), returned and cancelled has V = 3, so the uniform rule predicts a third of the table for every value. Optimizers fix this with a most-common-values (MCV) list and histograms. An equi-width histogram splits the value range into buckets of the same width; an equi-depth (equi-height) histogram splits it so each bucket holds the same number of rows, which is more accurate where the data is dense. Within a bucket the estimate interpolates linearly.

Python Uniform guess vs most-common values vs histogram

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The table shows the point of MCV lists: the uniform rule predicts 333 rows for every status, which is off by a factor of 22 for cancelled, while the MCV estimate matches the truth. The histogram part builds five buckets that each hold 200 prices, so the dense low-price region gets narrow buckets and the long tail gets one wide bucket. Estimates are very close in the dense region and loosest in the sparse tail, because the straight-line interpolation inside the last wide bucket is only a guess.

Costing a plan

Once cardinalities are known, each operator gets a cost from formulas like the ones in the join algorithms lesson: page reads weighted by random or sequential access, plus a small charge per row processed. The plan's cost is the sum of its operators. Production optimizers calibrate these constants (for example how much slower a random page read is than a sequential one) because the winner can change with them.

Searching for the best join order

The number of join orders explodes. For n tables there are n! left-to-right orders, and counting all tree shapes (bushy trees) is far larger: for 10 tables there are over 17 billion bushy trees. The optimizer cannot try them all.

The classic answer (System R, 1979) is dynamic programming over subsets and the restriction to left-deep trees, where the right input of every join is a single base table. The key observation is that the best plan for a set of tables S is the best plan for some subset S minus one table, extended by that table. So the optimizer computes, for subsets of size 1, 2, 3, and so on, the cheapest plan for each subset and keeps only that one (plus plans with interesting sort orders). The work falls from n! to about 2^n subsets. Plans that would need a cross product are postponed or skipped when a join predicate links the tables.

flowchart LR
  A["items โ‹ˆ products<br/>800 rows"] --> B["โ‹ˆ orders<br/>800 rows"]
  B --> C["โ‹ˆ customers<br/>800 rows"]

A left-deep plan: each join takes the previous result as its left input and one base table as its right input.

The program below defines four tables and join selectivities, runs the dynamic program, and checks it against brute force over all orders. A filter on products (5 of 500 products survive) makes starting from items and products much cheaper than starting from the biggest join. The cost used here is the sum of the intermediate result sizes, a classic simplified cost function.

Python Join order by dynamic programming

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The best orders cost 2,400 intermediate rows; the worst connected order costs 160,800, about 67 times more. Two orders tie for first place because swapping the first two tables of a join does not change the intermediate sizes in this simple model. With only four tables the savings of dynamic programming are small (10 stored subsets against 8 complete orders), but at 15 or 20 tables brute force is impossible while 2^n subsets is still feasible. For very large queries, real optimizers switch to heuristics or genetic search after a threshold (PostgreSQL does so beyond 12 FROM items by default).

Statistics in SQLite, live

SQLite's optimizer is simpler than a server's, but it follows the same idea. Without statistics it makes default guesses; after ANALYZE it reads sqlite_stat1, which stores for each index the table's row count followed by the average number of rows per distinct key prefix. The next example builds an orders table where 99% of the rows are shipped and only 20 are cancelled, and indexes the status column.

SQL ANALYZE changes the plan (and shows the uniformity trap)

Press Run (or Ctrl + Enter) to see the result here.

Before ANALYZE the plan is SEARCH orders USING INDEX idx_orders_status. After it, sqlite_stat1 says 2000 1000 for the status index: 2,000 rows and on average 1,000 rows per status value. With that statistic a scan looks cheaper than 1,000 random index lookups, so the plan becomes SCAN orders, even though only 20 rows are cancelled. This is the uniformity assumption failing in a real engine: stat1 keeps one average per index and has no histogram, so it cannot tell the common value from the rare one (SQLite can be compiled with an optional sqlite_stat4 table of samples for this; the plans above show it makes no difference in this build). The customer_id index has 2000 10, meaning 10 rows per customer on average, so it keeps SEARCH ... USING INDEX idx_orders_customer. Server databases avoid the status trap with MCV lists and histograms, and with parameter-aware plans.

The second experiment compares join orders. SQLite normally chooses the order itself, but writing CROSS JOIN pins the left-to-right order, which lets you compare the optimizer's choice with a forced one.

SQL The optimizer's join order versus a forced one

Press Run (or Ctrl + Enter) to see the result here.

The chosen plan first searches customers by the country index (the few Norwegian customers) and then looks up each one's orders through idx_orders_customer: the filtered table drives the join. The forced plan scans the whole orders index first and probes customers for every order, which touches far more rows, so SQLite also adds a Bloom filter to skip hopeless probes. Same answer, different work.

Practical consequences

  • Run ANALYZE (or your engine's equivalent) after bulk loads and large changes; stale statistics are the most common cause of sudden slow queries.
  • Skewed or correlated columns (city and postcode, for instance) defeat independence assumptions; extended or multi-column statistics exist in several engines for this.
  • Functions on columns (WHERE lower(name) = ...) hide the column from its statistics, so estimates fall back to defaults.
  • When a plan looks wrong, compare the estimated rows with the actual rows in the plan output; the first step where they diverge is the culprit.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A column has 50 distinct values and a table has 10,000 rows. Under the uniform assumption, how many rows does WHERE col = 'x' return?

    Selectivity is 1/V = 1/50, so the estimate is 10,000 / 50 = 200 rows.
  2. 2. Why do optimizers keep a most-common-values list next to histograms?

    Skewed values are exactly where the uniform formula fails, so the heavy hitters are recorded with their true counts and the histogram covers the rest.
  3. 3. How does dynamic programming reduce the cost of searching join orders?

    The best plan for a set of tables is built from the best plan for a smaller set, so the work grows with the number of subsets (about 2^n), not with n!.
  4. 4. In SQLite, after ANALYZE a query on a rare status value stops using the status index. What is the most likely reason?

    The statistics contain a single average per index. With two status values that average is half of the table, so a scan looks cheaper than an index lookup for every value.

Summary

  • A cost-based optimizer estimates cardinalities from catalog statistics (row counts, distinct values, min/max, MCVs, histograms), costs each operator, and picks the cheapest plan.
  • Uniformity and independence are the default assumptions; skew and correlation break them, which is why MCV lists, histograms and extended statistics exist.
  • Join ordering is searched with dynamic programming over subsets, usually restricted to left-deep trees; very large queries fall back to heuristics.
  • ANALYZE fills sqlite_stat1 and can change plans, for better or worse; compare estimated and actual rows when a plan surprises you.

Next: Algebraic Equivalence and Heuristic Optimization.