One of Them Is Quadratic and Sometimes It Is the Right Answer
Last timeWhat You Did Not Say
There are three ways to combine two sets of rows. Their costs can be derived in a paragraph each, and the derivation tells you exactly when each one wins.
Combining two sets of rows on a shared column admits exactly three sensible
algorithms. Each has a cost you can derive from the sizes of the inputs, and
once you have the three costs the planner's behaviour stops being mysterious.
The loop
The obvious method. Take each row of one input, and for each one, find the
matching rows in the other.
If the inner side has an index on the join column, each of those lookups is a
seek: two or three reads, as the index course established. So the total cost is
the number of outer rows times the cost of a seek, and the size of the inner
table barely enters into it.
If the inner side has no index, each lookup is a full scan of it, and the cost
is the product of the two sizes. For a thousand rows against a million, that is
a billion row comparisons, which is the classic disaster plan.
- outer rows times the cost of one lookup, where the lookup is a seek if there is an index and a whole scan of the inner side if there is not
- building the hash table from the smaller side, read once, at a per-row cost higher than a simple read
- one pass over each input, plus the cost of sorting whichever of them did not already arrive in order
The hash
Read the smaller input once and build a lookup table in memory, keyed on the
join column. Then read the larger input once, and for each row, look it up.
Each side is touched exactly once. The cost is the sum of the two sizes plus the
expense of building the table, and the size of the larger side enters linearly
rather than as a multiplier.
Two requirements come with it. The method works by hashing, so it handles
equality conditions and nothing else: a join on one column being less than
another cannot be done this way, for the reason the index course gave for hash
indexes. And the table has to fit in memory, or it must be split into partitions
that are processed in turn, which costs an extra write and read of both inputs.
The lesson stops here
3 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