Skip to content

Commit ac9173e

Browse files
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

File tree

  • datafusion/physical-plan/src/joins/hash_join

0 commit comments

Comments
 (0)