The Three Ways to Join
Last timeThe Plan Is Built on a Guess
There are only three ways to match rows in one table against rows in another, each wins in a different situation, and most slow joins are the wrong one of the three.
Joining is where queries go from slow to unusable, because the three available
methods differ not by a few percent but by factors of thousands. Every database
has all three, and the whole art is in which one gets used.
One row at a time
The simplest method takes the first row of one side, searches the other side for
rows matching it, emits the matches, and moves on. The side being walked is the
outer side; the side being searched is the inner.
Its cost is the number of outer rows multiplied by the cost of one search, and
that multiplication is the whole story. Twelve outer rows against an indexed
inner side costs almost nothing. Two million outer rows is two million index
descents, and if the inner side has no usable index, two million full scans,
which is the worst thing a database can be made to do.
- the total time for the join
- the number of rows on the outer side, the one being walked
- the cost of one descent into the inner side's index
- the number of matching rows found per outer row
- the cost of fetching one matching row, which is a scattered read
- the shape that matters, a cost strictly proportional to the outer side, with nothing in it that improves as the join gets bigger
Building a lookup structure
The second method reads one side completely and arranges it in memory so that
any value can be found immediately. Then it reads the other side once, looks each
row up, and emits what matches.
The accounting is completely different. Each side is read exactly once, and the
probing side's rows cost almost nothing each, so this is the default for joining
two large tables and usually what you want to see in a plan.
The condition is memory. What has to fit is not the table but the rows and
columns the query uses from it.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis 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