Understanding SQL Indexes and Query Performance

Part 9 of 16 · ~3 min

How the Query Optimizer Chooses: Seek vs. Scan

The last chapter said the optimizer "costed both plans." This chapter is about what that actually means, because it is the machinery behind every decision in this reference.

Every relational database of any consequence relies on a cost-based optimizer to make this call. Your SQL only ever states what result you're after, never how to produce it, so the optimizer's actual job is enumerating candidate execution strategies, pricing each one, and running whichever comes out cheapest. An index's mere existence buys it nothing on its own — the optimizer reaches for one only when its own math says that particular plan wins.

Two access paths, worth naming precisely because the vocabulary differs by engine:

• An index seek drills down the B-tree to a specific value or range and touches only the rows that actually qualify — so its expense tracks the result size, not the table's. Depending on which engine's plan you're reading, the same operation shows up under a different label: a seek in SQL Server, an Index Scan in Postgres, or SEARCH in SQLite's output. One idea, three names.
• A full table scan, by contrast, walks every row in the order it happens to sit in on disk, so how few of those rows actually satisfy the query is irrelevant — what drives the cost is the table's total size. SQLite reports this as SCAN; Postgres labels it a Seq Scan.

The estimate is built from statistics — a stored summary of the data that the engine keeps and consults instead of looking at the actual rows, because looking at the actual rows to decide how to look at the actual rows would defeat the purpose. Typically that includes the table's row count, the number of distinct values per column, the fraction that is NULL, and — the important one — a histogram of how values are distributed.

The histogram is what makes the two-departments result possible. Without one, the optimizer's best guess for dept = ? is uniform: 2.4 million rows over 38 departments, so about 63,000 rows per department, the same answer for every value. That estimate is wrong for both of our cases, badly, in opposite directions. With a histogram the engine knows that 'Sales' specifically covers 431,000 rows and 'Facilities' specifically covers 6,200, so it can cost the two queries differently and pick differently. Skewed data is common, and histograms are the mechanism that keeps it from wrecking plans.

Which leads to the most valuable practical fact in this chapter: statistics are a snapshot, and snapshots go stale. Bulk-load a few hundred thousand rows, mass-delete a division after a reorg, or watch a table grow quietly for two quarters, and the stored summary stops describing the data. The optimizer keeps making confident decisions from it and starts getting them wrong — estimating a few hundred rows where there are now half a million, choosing a seek-plus-lookup plan that the real distribution makes terrible.

Every engine ships a way to refresh them:

ANALYZE;              -- SQLite, Postgres, MySQL
UPDATE STATISTICS Employees;   -- SQL Server

Postgres and SQL Server run this automatically in the background; SQLite does not, and MySQL's thresholds can be coarse. A query that was quick yesterday and isn't today, with no deploy and no schema change in sight, points first at stale statistics — check those well before you start adding indexes. Adding an index to fix a stale-statistics problem tends to produce a table with one more index and the same problem.