--- title: 'Statistics and Cardinality' source: 'https://academia.sh/en/courses/advanced-sql/statistics-and-cardinality' course: 'Advanced SQL' language: en updated: '2026-08-23T07:00:38+00:00' license: 'CC BY-SA 4.0' --- # Statistics and Cardinality The planner's row count estimate, the default values used before statistics are collected, the estimate's correction after ANALYZE, the estimate's measured effect on the plan, the consequences of stale statistics, and the average's failure to describe a skewed distribution. 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 ```sh 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`). ```sh 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. ```sh 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. ```sh 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. ```sh 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.