viirya commented on PR #25679: URL: https://github.com/apache/datafusion/pull/25679#issuecomment-6404031644
Thanks for picking this back up! I re-ran the repros on the current head (440b2855f). The build-side path is fixed: with 8192 × 8192 rows and a constant scope key (outer_t: a = NULL, b = 1; inner_t: x = 2, y = 1), the LeftMark ```sql SELECT count(r) FROM (SELECT a NOT IN (SELECT x FROM inner_t i WHERE i.y = o.b) AS r FROM outer_t o); ``` goes from ~210 ms to ~1 ms. **`RightAnti` still pairs every row of a scope bucket, and is now slower.** On the same data, the anti-join form ```sql SELECT count(*) FROM outer_t o WHERE a NOT IN (SELECT x FROM inner_t i WHERE i.y = o.b); ``` plans as a null-aware `RightAnti` (probe = `outer_t`) and goes from ~300 ms on main to ~410 ms with this PR. The comment in `scope_matches` says a probe row is looked up once, so grouping never pays off for marks on probe rows. But that single lookup returns the probe row's whole bucket (up to `batch_size` matches), and they are all pushed before the first chunk is sent. `lookup_unmarked` only drops matches of a probe row that a chunk already sent has marked, so it never skips a probe row's own matches. Each NULL-valued probe row is still paired with every build row in its scope, O(probe × bucket) as before, with the bit check and push added per match. With a medium bucket (64 scopes, 128 rows each) the difference is small (3 → 4 ms), so it is mostly the large-bucket shape. Would it work to group the probe rows by scope hash for `UnknownMarks::Probe` too, and pair each group with its chain's build rows the way `cross_product` already does for `Probe` marks (the group's probe rows as `decided_rows` in `pair_unmarked`, the build rows as the outer loop), stopping the chain walk once the whole group is marked? A constant-key bucket would then cost about one chunk per group instead of one bucket per probe row. The grouped phase's `lookup_unmarked` maps positions to group indices, so it can't be reused as is for `Probe` marks. This matters for #26214: after #26213, its multi-column repro `(a, b) NOT IN (SELECT x, y FROM inner_t)` with `b`/`y` NOT NULL also plans as `RightAnti` and goes through the same path. I'm happy to do the probe-side part as a follow-up if you'd rather keep this PR to the build side. Which would you prefer? **Fully marked buckets are walked again in every probe batch.** Nothing carries over between probe batches, so each batch walks the whole marked chain at least once per group. The LeftMark query above at N × N rows with a constant key takes ~260 ms at 1M, ~960 ms at 2M and ~3.7 s at 4M. The no-scope cross product grows the same way (`(a, b) NOT IN` without a scope key: 84 ms at 1M, 274 ms at 2M), so this isn't specific to this PR and is fine as a follow-up. I'm only flagging it in case you had considered keeping each scope's unmarked build rows across batches. **Coverage of the grouped path.** +1 to Copilot's point. Grouping starts only after more than 8 skipped matches per probe row, and only `unmarked_pairs_do_not_grow_with_probe_rows` reaches it, with a closure that marks every pair. The real `mark` closure (multi-column value tuples, join filter, LeftMark) is never run together with the grouping: a group split across two lookup chunks, the `MidChain` row paired again, the per-group refresh with rows left unmarked. The null-aware fuzz tables are too small to get there. Could you add an slt case that does, for example a LeftMark with a constant scope key, more than 8 NULL-valued build rows in that scope, a residual filter that leaves some of them unmarked, and `batch_size` 1 and 7? It would pass before and after, but it would protect the grouped path from later changes. For reference, comparing `NOT IN` with `NOT EXISTS (... (o.a = i.x) IS NOT FALSE)` over low-cardinality scope keys (NULL and `-0.0` scope values, dictionary scope keys , filters, 1–3 value keys, batch sizes 1/7/64/8192, 1 and 4 partitions) showed no differences. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
