sunchao opened a new issue, #25581:
URL: https://github.com/apache/datafusion/issues/25581
Semi/anti sort-merge joins can repeatedly search an equality-key group to
evaluate a residual predicate, even though their output needs only a Boolean
existence decision. Large groups with no qualifying witness can require work
proportional to the product of the group sizes.
For example, this query retains every document row for which no newer
version exists:
```sql
SELECT current.*
FROM documents current
WHERE NOT EXISTS (
SELECT 1 FROM documents other
WHERE other.document_id = current.document_id
AND other.version > current.version
);
```
For each equality-key group, the maximum non-null inner version is
sufficient to answer the residual for every outer row. Similarly, `outer.x <>
inner.y` needs only one non-null representative until a second distinct value
is observed, after which a flag suffices. This also applies to string conflict
checks and dates/timestamps. OR clauses can combine independent summaries;
conjunctions requiring the same inner witness cannot generally do so.
Proposed scope:
- Opt-in execution of exact summaries for eligible ordinary semi/anti
sort-merge joins, retaining existing execution for unsupported predicates.
- `<>`, `<`, `<=`, `>`, `>=`, supported scalar types, side-local guards, and
bounded OR composition.
- Preserve SQL null behavior, duplicate outer rows, join orientation, key
ordering, upstream errors, and cancellation by dropping the stream.
- Account for owned representative storage and expose activation/fallback,
group, row, and state-size metrics.
- Differential correctness tests and benchmarks covering large unsuccessful
searches, small groups, and early witnesses.
This does not change join selection, add hash-join support, or optimize
null-aware/mark joins, payload-returning joins, or distinct aggregation.
Full-query impact depends on how much time is spent evaluating residuals rather
than scanning, sorting, or shuffling.
--
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]
