Statistics and Cardinality

In the previous lessons, the planner’s decisions always turned out to be the right ones: it drove the correct table, it chose the correct index, it avoided unnecessary sorting. What it based those decisions on has not been asked.

The planner decides before the query runs. It has no data in hand; if it did, it would already have run the query itself. Instead, it estimates how many rows each step will return and compares options based on these estimates. The source of the estimate is statistics collected beforehand about tables and indexes. This lesson makes that estimate visible, measures it, and shows what happens when it goes wrong.

Data Set

rm -f library.db
cat > setup.sql <<'SQL'
CREATE TABLE branch (
  branch_id INTEGER PRIMARY KEY,
  name      TEXT NOT NULL,
  city      TEXT NOT NULL
);
CREATE TABLE member (
  member_id         INTEGER PRIMARY KEY,
  name              TEXT NOT NULL,
  city              TEXT NOT NULL,
  registration_date TEXT NOT NULL
);
CREATE TABLE book (
  book_id   INTEGER PRIMARY KEY,
  title     TEXT NOT NULL,
  author    TEXT NOT NULL,
  year      INTEGER NOT NULL,
  branch_id INTEGER NOT NULL
);
CREATE TABLE loan (
  loan_id     INTEGER PRIMARY KEY,
  book_id     INTEGER NOT NULL,
  member_id   INTEGER NOT NULL,
  pickup_date TEXT NOT NULL,
  return_date TEXT
);

INSERT INTO branch (branch_id, name, city) VALUES
  (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul'),
  (4,'Beyoglu','Istanbul'),(5,'Konak','Izmir'),(6,'Nilufer','Bursa'),
  (7,'Selcuklu','Konya'),(8,'Cankaya','Ankara');

INSERT INTO member (member_id, name, city, registration_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000)
SELECT n, 'Member ' || n,
       CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir'
                  WHEN 3 THEN 'Bursa' ELSE 'Konya' END,
       date('2015-01-01', '+' || (n % 3200) || ' days')
FROM counter;

INSERT INTO book (book_id, title, author, year, branch_id)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 200000)
SELECT n, 'Book ' || n, 'Author ' || (n % 4000), 1950 + (n % 75), 1 + (n % 8)
FROM counter;

INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000)
SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000),
       date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'),
       CASE WHEN n % 9 = 0 THEN NULL
            ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END
FROM counter;
SQL
sqlite3 library.db < setup.sql

The Estimate Can Be Made Visible

The .scanstats est command adds four numbers next to plan nodes: how many times the node ran (loops), how many rows it produced in total (rows), rows per run (rpl), and what the planner estimated this would be (est).

sqlite3 library.db <<'SQL'
CREATE INDEX loan_member ON loan(member_id);
CREATE INDEX book_author ON book(author);
.scanstats est
SELECT count(*) FROM loan WHERE member_id = 4242;
SELECT count(*) FROM book WHERE author = 'Author 7';
SQL

17
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_member (member_id=?)     (loops=1 rows=17 rpl=17.0 est=10.0)
50
QUERY PLAN
`--SEARCH book USING COVERING INDEX book_author (author=?)     (loops=1 rows=50 rpl=50.0 est=10.0)

The estimate is the same in both nodes: ten. The two indexes have different densities, the tables are different sizes, and the actual counts are seventeen and fifty. The estimate being ten in both cases shows that this is not a computation but a default value: for an index with no collected statistics, the planner assumes an equality condition will return a fixed number of rows.

This assumption is harmless when the options are close to each other. If one option is a hundred times more expensive than another, and the difference comes from exactly this number, the wrong plan gets chosen.

Collecting Statistics

ANALYZE scans the tables and indexes and writes summary information into a system table.

sqlite3 library.db <<'SQL'
ANALYZE;
SELECT tbl, idx, stat FROM sqlite_stat1 ORDER BY tbl, idx;
.scanstats est
SELECT count(*) FROM loan WHERE member_id = 4242;
SELECT count(*) FROM book WHERE author = 'Author 7';
SQL

book|book_author|200000 50
branch||8
loan|loan_member|2000000 17
member||120000
17
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_member (member_id=?)     (loops=1 rows=17 rpl=17.0 est=16.0)
50
QUERY PLAN
`--SEARCH book USING COVERING INDEX book_author (author=?)     (loops=1 rows=50 rpl=50.0 est=48.0)

Every row in the statistics table carries two numbers: the table’s row count and the average number of rows per index key. loan_member reading 2000000 17 says that there are two million loan records and that a member has an average of seventeen records. This number is called a cardinality estimate.

The estimates rose to sixteen and forty-eight instead of ten; the actual values are seventeen and fifty. The planner can now tell the two indexes apart.

The Estimate’s Effect on the Plan

Correcting the estimate is not just a matter of one number improving; the plan changes too.

rm -f plan.db
sqlite3 plan.db < setup.sql
sqlite3 plan.db <<'SQL'
CREATE INDEX book_branch ON book(branch_id);
EXPLAIN QUERY PLAN
SELECT count(*) FROM loan l JOIN book b ON b.book_id = l.book_id WHERE b.branch_id = 3;
.timer on
.stats vmstep
SELECT count(*) FROM loan l JOIN book b ON b.book_id = l.book_id WHERE b.branch_id = 3;
.timer off
.stats off
ANALYZE;
EXPLAIN QUERY PLAN
SELECT count(*) FROM loan l JOIN book b ON b.book_id = l.book_id WHERE b.branch_id = 3;
.timer on
.stats vmstep
SELECT count(*) FROM loan l JOIN book b ON b.book_id = l.book_id WHERE b.branch_id = 3;
SQL

QUERY PLAN
|--SCAN l
`--SEARCH b USING COVERING INDEX book_branch (branch_id=? AND rowid=?)
250000
VM-steps: 10250011
Run Time: real 0.357 user 0.347190 sys 0.010091
QUERY PLAN
|--SCAN l
|--BLOOM FILTER ON b (branch_id=? AND rowid=?)
`--SEARCH b USING INDEX book_branch (branch_id=? AND rowid=?)
250000
VM-steps: 13425016
Run Time: real 0.105 user 0.094947 sys 0.009198

The query, the indexes, and the data are the same; the only thing that changed is the presence of statistics. A new node was added to the plan: the fact that most of the two million loan records do not belong to the searched branch is now weeded out with a cheap filter beforehand, and the tree descent is done only for what remains. Time dropped by about three and a half times in this environment.

Step count, however, rose: from 10,250,011 to 13,425,016. This is where the two measures diverge. The filter itself also runs instructions; what it saves is not instructions but tree descents and page reads. This is the limit of treating step count as the only measure — step count counts the work the plan does, not the unit cost of that work.

When Statistics Go Stale

Statistics describe the data as it was at the moment they were collected. As the data changes, what they describe drifts away from reality.

rm -f stale.db
sqlite3 stale.db < setup.sql
sqlite3 stale.db <<'SQL'
CREATE INDEX loan_member ON loan(member_id);
ANALYZE;
INSERT INTO loan (book_id, member_id, pickup_date, return_date)
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 500000)
SELECT 1 + ((n * 7) % 200000), 4242,
       date('2025-01-01', '+' || (n % 200) || ' days'), NULL
FROM s;
SELECT tbl, idx, stat FROM sqlite_stat1 WHERE idx = 'loan_member';
.scanstats est
SELECT count(*) FROM loan WHERE member_id = 4242;
.scanstats off
ANALYZE;
SELECT tbl, idx, stat FROM sqlite_stat1 WHERE idx = 'loan_member';
.scanstats est
SELECT count(*) FROM loan WHERE member_id = 4242;
SELECT count(*) FROM loan WHERE member_id = 5000;
SQL

loan|loan_member|2000000 17
500017
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_member (member_id=?)     (loops=1 rows=500017 rpl=500017.0 est=16.0)
loan|loan_member|2500000 21
500017
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_member (member_id=?)     (loops=1 rows=500017 rpl=500017.0 est=20.0)
16
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_member (member_id=?)     (loops=1 rows=16 rpl=16.0 est=20.0)

A contrived situation has been set up: five hundred thousand records were added for a single member. Because the statistics were collected before the insert, they still say 2000000 17 and the estimate stays at sixteen; the actual number is 500,017. The estimate is off by more than thirty thousand times.

When ANALYZE runs again, the statistics become 2500000 21. The estimate rises from sixteen to twenty — still not even close to 500,017. This is not a bug, it is the definition of the measure: the stored number is an average, and when two and a half million records are divided across one hundred and twenty thousand members, the average really does come out to twenty-one.

What the Average Cannot Describe

The last line of the last output completes the distinction: for member number 5000, the actual value is sixteen, the estimate is twenty. The average works perfectly well for ordinary members; it is only completely wrong for the outlier member. In a skewed distribution, a single average cannot serve two groups at once.

The answer to this is to keep statistics per value: a list of the most frequent values and the distribution of value ranges — in other words, a histogram. Some engines collect this information and produce separate estimates for member_id = 4242 and member_id = 5000. In engines that do not, the only remedy is to manage the skew through query writing or partial indexes.

The second limit is dependency between columns. The planner mostly treats conditions like city = 'Bursa' and registration_date >= '2020-01-01' as independent and multiplies their selectivities. If the conditions are actually dependent, the result inflates or shrinks significantly.

The lesson to draw on the practical side is short: statistics collection should be repeated after data volume changes substantially — after bulk loads, archiving, and schema changes. When a query slows down for no apparent reason, one of the first places to look is the gap between the estimate and the actual value.

Summary

• The planner bases its decisions on estimates of how many rows each step will return; these estimates can be seen side by side with actual counts in plan output.
• Before statistics are collected, the estimate is a fixed default value; it came out as ten for two separate indexes in this data set.
• ANALYZE writes table row count and average rows per key into a system table; estimates moved closer to actual values afterward.
• The presence of statistics changed the plan and cut time by about three and a half times in this environment; because step count rose on the same query, the two measures did not point in the same direction.
• The stored number is an average; in skewed distributions, the estimate can be off by thousands of times for outlier values, which is why some engines keep a histogram per value.

Next Step

Every query in this topic so far has been a fixed piece of text. Applications, however, often build queries at run time: conditions get added depending on the fields filled in a search screen, the sort column comes from the user. Building the query text by string concatenation has consequences on the correctness side, the security side, and the performance side. The final lesson takes up these three consequences and the answer a bound parameter gives to all of them at once.