The Database Never Reads a Row

Before anything can be said about indexes, there has to be a baseline, and the

baseline is reading the whole table. It is worth doing carefully, because

almost every surprise later in the course is a case where the baseline was

cheaper than people assumed.

A database does not read rows. It reads pages: fixed-size blocks, eight

kilobytes in most systems, which is the smallest thing storage will hand over.

A row lives inside a page along with as many of its neighbours as fit, and

reading one row means reading the whole page it sits on.

This single fact decides the cost of nearly everything.

The practical consequence is that row width is a performance decision. Two

hundred bytes a row gives forty rows per page; a thousand bytes a row gives

eight. The same query over the same ten million rows reads five times as many

pages in the second case, and nothing about the query changed.

Now the time. A scan reads every page of the table in storage order, which

means one long sequential request rather than a quarter of a million small

ones. On the sort of storage a database runs on today, that runs at something

like one to two gigabytes a second.

Two gigabytes at 1.6 gigabytes a second is about 1.3 seconds of reading. Add

the processor work of walking the rows in each page and applying the filter,

and a scan of ten million typical rows takes a couple of seconds.

The important property of this number is what it does not depend on. It does

not depend on how many rows match. One matching row or ten million, the same

pages were read and the same bytes were decoded. A scan has a cost and not a

range.

An index reads differently. It finds the identifiers of the matching rows and

then fetches each one, and those rows are wherever they happen to be, which

means one small request per page rather than one long one.

Each of those requests carries its own latency. On a spinning disk the physical

arm movement made a scattered page roughly a hundred times the cost of a

sequential one, and every rule of thumb in the subject was built on that

ratio. On solid-state storage there is no arm, and the gap has narrowed to

something like four or five to one.

That change matters more than it sounds. Rules of thumb inherited from the

1990s assume random access is catastrophic; on modern hardware it is merely

expensive. Databases encode the current ratio as a pair of planner constants

you can read and, if your storage really is unusual, adjust.

Thirty per cent is the number to carry around, with the understanding that it

is a region rather than a threshold: it falls as rows get wider and rises as

storage gets faster. The reasoning behind it is what matters. If a filter

matches a third of a table whose rows are scattered uniformly, then nearly

every page of the table holds at least one matching row, so the index path ends

up reading nearly every page anyway, one at a time, after having read the index

first.

This explains a result that otherwise looks like a bug: an index on a column

with three possible values is almost never used, because any filter on it

matches a third of the table. It is not that the database failed to notice the

index. It considered it, costed it, and correctly concluded that scanning was

faster.

The next lesson takes the other road. If scanning is what it costs because

nothing about the layout helps, what is the cheapest change to the layout that

does help? The answer is to sort the file, and the trouble that creates is the

rest of the course.