Repository navigation
Commit ac9173e
committed
perf: stop re-pairing marked rows in the scope-key null-aware join
A correlated NOT IN with an equality correlation gets a correlation scope
key. To decide which rows are UNKNOWN, the join looked up every probe row
in the scope map, and paired it with every row of its scope. A marked row
stays UNKNOWN, but it was still paired again, so the cost grew with the
square of the scope size:
SELECT count(*) FROM small_outer o
WHERE o.z > 900
OR o.id_n50 NOT IN (
SELECT i.id_n0 FROM small_inner i WHERE i.k = o.k AND i.z < o.z);
took about 538 ms with 100k rows in each table, against about 7 ms for a
NOT IN with only the `i.z < o.z` correlation (release `datafusion-cli`,
median of 10 runs). It now takes about 7 ms.
The lookup drops the matches whose build row is marked before it makes
pairs. That alone still walks each scope once per probe row, and a
RightAnti, which marks probe rows, still paired each probe row with its
whole scope. So the join counts the matches that the lookup per probe row
wastes. When they cost more than a sort, it estimates from a sample of
the rest of the probe rows whether groups of equal hashes save work:
- with marks on build rows, when a group holds more than one probe row,
which then share one walk of the hash chain;
- with marks on probe rows, when the pairs of a group fill more than a
chunk, so that the later chunks can skip the marked probe rows.
If they do, the join sorts the rest of the probe rows by hash, looks up
each hash once, and pairs each group like a cross product that drops the
rows as they are marked. A group of probe rows stops its walk of the hash
chain when all of them are marked. Otherwise the lookup per probe row
goes on, so scopes of a few rows never pay for a sort.
With marks on build rows, a check of the marks that drops nothing makes
the next checks less frequent, so a filter that marks nothing costs
little. Every pair now comes from a pairing that drops the marked rows,
so the marking closure no longer checks them again.
The unit tests pin the cost decisions and bound the matches walked, and
the test diff shows that the walk no longer grows with the product of
the rows.1 parent 5f55098 commit ac9173e
1 file changed
Lines changed: 648 additions & 55 deletions
0 commit comments