hhr293 opened a new pull request, #12756:
URL: https://github.com/apache/gluten/pull/12756
## What changes are proposed in this pull request?
Adds a Catalyst optimizer rule `RewriteSelfJoinInequalityToAggregate`
that rewrites a self-join with an inequality predicate into an
aggregate + HAVING, when the join output is consumed by an
existence-only operator (`InSubquery` / `Exists` / `LeftSemi` /
`LeftAnti`).
Structural rewrite:
```
SELECT ...
WHERE key IN (
SELECT t1.key FROM T t1 JOIN T t2
ON t1.key = t2.key AND t1.col <> t2.col
)
-- becomes
SELECT ...
WHERE key IN (
SELECT key FROM T
GROUP BY key HAVING COUNT(DISTINCT col) > 1
)
```
**Motivation.** Under existence semantics only the set of qualifying
keys matters, not row multiplicity. The self-join produces `O(N^2)`
intermediate rows per equi-key group before being funneled into a
`LeftSemi` join; the aggregate produces one row per group with the
same membership predicate.
On TPC-DS q95, the two `LeftSemi` build tables downstream of the
inequality self-join hold **2.35 B / 3.08 B rows / 80 / 91 GiB** each
(measured from spark-history). After the rewrite they shrink to
**18 M / 22 M rows / 591 / 663 MiB** — a ~150x reduction in build-side
data — and q95 wall drops from 59.86 s to 18.64 s.
**Patterns matched.**
- **Pattern A'** — `InSubquery` / `Exists` whose subquery top-level
join is the self-join (primary path, fires before
`RewritePredicateSubquery`).
- **Pattern A2** — the self-join is nested inside another `InnerJoin`
within the subquery. Only the self-join subtree is replaced; the
outer join is preserved.
- **Pattern A** — `LeftSemi` / `LeftAnti` whose right child is an
Inner self-join (post-`RewritePredicateSubquery` fallback).
**Conservative guards (fail-closed).**
- Only accept `EqualTo(a, b)` and `Not(EqualTo(a, b))`; reject
`EqualNullSafe` and `IS DISTINCT FROM`.
- Single inequality column only. A disjunction such as
`col1 <> col1 OR col2 <> col2` is not equivalent to
`COUNT(DISTINCT single_col) > 1`.
- Both self-join sides must expose the same attribute names.
- `IsNotNull` predicates are only accepted on the equi / inequality
columns (those are auto-inserted by `InferFiltersFromConstraints`);
`IsNotNull` on any other column causes the rule to bail out so no
user-visible filter is silently dropped.
- For Pattern A2, the subquery's top-level `Project` must reference
only equi-key attributes from the self-join side, otherwise the
rewrite would leave unresolved references.
**Config.** Gated by `spark.gluten.sql.rewrite.selfJoinInequality`,
**opt-in default `false`**. The rewrite has been validated on TPC-DS
q95 across three hardware platforms but non-q95 workloads have not
been broadly exercised; keeping it opt-in until wider evidence
accumulates prevents surprising behavior for existing users.
## How was this patch tested?
**Unit tests** (`RewriteSelfJoinInequalityToAggregateSuite`, 10
cases):
- Positive: Pattern A' (EXISTS / InSubquery), Pattern A2 (nested).
- Semantic parity: NULL / 3VL row results identical with rule on vs.
off on a fixture that exercises NULL, distinct-only, and duplicate
values.
- Negative (rule must not fire): plain `InnerJoin` at top level,
`IS DISTINCT FROM`, multi-column inequality, `IsNotNull` on a
non-join column, `LeftOuter` join, and config disabled.
**TPC-DS SF=300** (3 executors x 4 cores, Intel Xeon GNR-AP):
- q95 wall: 59.86 s -> 18.64 s (-69%).
- All other 107 queries stay within a `+/- 2 s` noise band for a
single run; no regression attributable to the rule.
--
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]
