What a Query Is Actually Spending

A query's time is almost entirely the number of rows the database had to look at, multiplied by how expensive it was to reach each one. Everything else is detail.

Somebody reports that a page is slow. Somebody else finds the query behind it and

says it needs an index. Often that works, and it is still the wrong place to

start, because it skips the only question worth asking first: what is this query

actually spending its time on?

FIG 1What happens between asking and answering

Only one of these boxes is a choice, and all the others inherit their cost from it. That is why reasoning about a slow query starts at the second box rather than at the last one.

The gap between examined and returned

The number that sets the time is how many rows were looked at, not how many came

back. These are often wildly different, and the difference is where almost every

problem in this subject lives.

A query that returns a single row can take thirty seconds if it had to read

forty million rows and throw away all but one. A query that returns two hundred

thousand rows can come back in fifty milliseconds if those rows sat next to each

other and nothing had to be discarded. Nothing about the result tells you which

situation you are in.

FIG 2Time against table size, for two ways of finding one row

look at every rowuse a sorted copy to go straight there

The two lines cross early and then diverge without limit. At a thousand rows the difference is not worth anybody's attention, which is exactly why the problem is always discovered in production rather than in development.

That shape explains a familiar experience. A feature works perfectly for months

and then becomes unusable, with no change to the code. Nothing broke. The table

crossed the point where the straight line overtook the flat one.

Rows are not the unit of work

Databases do not fetch rows. They fetch pages, which are fixed-size blocks of

storage, usually four or eight kilobytes, each holding as many rows as fit.

Reading one row means reading the entire page it lives on.

This has a consequence that explains a great deal. A hundred rows that happen to

be stored next to each other cost one page read between them. The same hundred

rows scattered across a large table cost a hundred page reads, which is a hundred

times the work for exactly the same answer. The rows are identical. Their

arrangement is not.

FIG 3What a query costs, in the terms the database itself uses

: the total time for the query
: the number of pages that had to be fetched
: the time to fetch one page, which depends entirely on where it was
: the number of rows examined, which is usually far more than the number returned
: the work done on each row once it is in hand, which is small unless the condition is expensive or the result must be sorted
: the fetching term, which dominates almost every slow query you will meet

Both terms are real, but they are not comparable in practice. The first term is measured in page fetches that may cost half a millisecond each; the second in operations that cost a fraction of a microsecond. Attention belongs on the first unless you have evidence otherwise.

Where the page is, is everything

The cost of fetching one page is not a constant. It depends on where the page

happens to be at that moment, and the range is enormous.

FIG 4The cost of reaching one row, by where its page is sitting

	microseconds to reach on	rows reached in one mill	cost relative to memory	how often this holds, on
the row is already decod	0.1	10000.0	1.0	4.0
the page is in the datab	1.0	1000.0	10.0	4.0
the page is on a local s	100.0	10.0	1000.0	2.0
the page is on a network	500.0	2.0	5000.0	1.0

The marked row is the one a healthy database spends most of its time in. The gap between it and the two below is why the same query can be instant at ten in the morning and slow at midnight, when a nightly job has pushed the useful pages out of memory.

There is a second effect of the same kind. Pages fetched in the order they are

laid out can be read ahead of time in large runs, so the per-page cost collapses.

Pages fetched in an unpredictable order cannot. This is the single most

counter-intuitive fact in the subject: reading an entire table in order is often

faster than using an index, because the index produces a few thousand scattered

fetches and the scan produces one long sequential run.

FIG 5The same unchanged query, as the table grows

step	rows in the table	rows examined	pages fetched	milliseconds	what happened
1	5000	5000	70	3	Early on. Every page of the table fits in memory, so looking at everything costs almost nothing.
2	400000	400000	5600	48	Still comfortable. Nobody has noticed, and nobody has written down that this query examines every row.
3	9000000	9000000	126000	980	The table no longer fits in memory. The pages now come from disk and the cost per page has risen tenfold on top of the growth.
4	22000000	22000000	308000	4100	The same query, the same code, the same correct answer. It is now the slowest thing on the page.

4 steps

Two things grew at once, which is why the degradation feels sudden rather than gradual. The row count rose steadily, and then the working set stopped fitting in memory and the cost of each page rose on top of it.

What to hold on to

The time a query takes is the pages it fetched times what each fetch cost, plus a

small amount of work per row. Rows returned tell you nothing. Rows examined tell

you almost everything, and the arrangement of those rows on pages tells you the

rest. Before reaching for an index, find out how many rows the database is being

asked to look at, because every remaining lesson is a way of reducing that number

or of making each row cheaper to reach.

Recap

The cost of a query tracks the rows it examines, not the rows it returns, and the gap between those two numbers is where nearly every performance problem lives.
Databases do not read rows, they read fixed-size pages, so the real question is how many pages a query touches and whether those pages were already in memory.
Reaching a page already in memory and reaching one on a disk differ by a factor of hundreds, which is why the same query can be instant one minute and slow the next with nothing changed.

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

NextA Sorted Copy With a Pointer Back →