@@ -31,7 +31,7 @@ import org.apache.spark.sql.types._
3131
3232/**
3333 * Rewrites supported uncorrelated IN-subquery inequality self-joins into
34- * `GROUP BY + HAVING COUNT(DISTINCT) > 1 `, avoiding the self-join cross-product.
34+ * `GROUP BY + HAVING MIN(neq) <> MAX(neq) `, avoiding the self-join cross-product.
3535 *
3636 * Supports a direct self-join (Pattern A') and a self-join nested under an outer inner join
3737 * (Pattern A2, where only the self-join child becomes an Aggregate). Unsupported and correlated
@@ -46,7 +46,8 @@ import org.apache.spark.sql.types._
4646 */
4747object RewriteSelfJoinInequalityToAggregate extends Rule [LogicalPlan ] with PredicateHelper {
4848
49- private val CountDistinctAliasName = " _rewrite_selfjoin_inequality_cnt_distinct"
49+ private val MinNeqAliasName = " _rewrite_selfjoin_inequality_min"
50+ private val MaxNeqAliasName = " _rewrite_selfjoin_inequality_max"
5051
5152 override def apply (plan : LogicalPlan ): LogicalPlan = {
5253 if (! conf.getConf(SQLConf .REWRITE_SELF_JOIN_INEQUALITY_TO_AGGREGATE_ENABLED )) {
@@ -69,26 +70,31 @@ object RewriteSelfJoinInequalityToAggregate extends Rule[LogicalPlan] with Predi
6970 // ============================================================================
7071
7172 /**
72- * Build `Filter(cnt > 1, Aggregate(equiKeys, child))` with a `COUNT(DISTINCT neqCol)`.
73+ * Build `Filter(min <> max, Aggregate(equiKeys, child))`, taking MIN and MAX over the neq column.
74+ * `MIN(neqCol) <> MAX(neqCol)` is true exactly when the group holds two or more distinct non-null
75+ * values -- the same test as `COUNT(DISTINCT neqCol) > 1`, but avoids the distinct-dedup
76+ * aggregation stages and supports partial aggregation.
7377 *
7478 * The `IsNotNull(equiKeys)` filter preserves the equi-join's NULL semantics: `=` never matches a
7579 * NULL key, but GROUP BY would fold all NULL keys into one group that can leak NULL into a
76- * `NOT IN`. The neq column needs no filter -- `COUNT(DISTINCT)` already ignores NULL.
80+ * `NOT IN`. The neq column needs no filter -- MIN/MAX ignore NULL, and a group with fewer than
81+ * two non-null values has `min = max` (or both NULL, which makes `<>` NULL), so `<>` is never
82+ * true for it and the group is dropped.
7783 */
78- private def buildAggregateHavingDistinctGt1 (
84+ private def buildAggregateHavingMultipleDistinct (
7985 equiKeys : Seq [Attribute ],
8086 neqCol : Attribute ,
8187 child : LogicalPlan ): LogicalPlan = {
82- val countExpr = Count ( Seq (neqCol)) .toAggregateExpression(isDistinct = true )
83- val countAlias = Alias (countExpr, CountDistinctAliasName )()
84- val aggExprs : Seq [NamedExpression ] = equiKeys :+ countAlias
88+ val minAlias = Alias ( Min (neqCol).toAggregateExpression(), MinNeqAliasName )( )
89+ val maxAlias = Alias (Max (neqCol).toAggregateExpression(), MaxNeqAliasName )()
90+ val aggExprs : Seq [NamedExpression ] = equiKeys :+ minAlias :+ maxAlias
8591 val nonNullChild = equiKeys
8692 .map(a => IsNotNull (a): Expression )
8793 .reduceOption(And )
8894 .map(Filter (_, child))
8995 .getOrElse(child)
9096 val agg = Aggregate (equiKeys, aggExprs, nonNullChild)
91- Filter (GreaterThan (countAlias .toAttribute, Literal ( 1L , LongType )), agg)
97+ Filter (Not ( EqualTo (minAlias .toAttribute, maxAlias.toAttribute )), agg)
9298 }
9399
94100 /**
@@ -198,7 +204,8 @@ object RewriteSelfJoinInequalityToAggregate extends Rule[LogicalPlan] with Predi
198204
199205 val innerLeftEquiAttrs : Seq [Attribute ] = equiPairs.map(_._1)
200206 val innerLeftNeqAttr : Attribute = neqPairs.head._1
201- val filtered = buildAggregateHavingDistinctGt1(innerLeftEquiAttrs, innerLeftNeqAttr, innerLeft)
207+ val filtered =
208+ buildAggregateHavingMultipleDistinct(innerLeftEquiAttrs, innerLeftNeqAttr, innerLeft)
202209
203210 // Fail closed on a bare-Join subquery: with no wrapper Project, replacing the self-join output
204211 // with `Project(equiKeys, filtered)` shrinks arity and RewritePredicateSubquery's positional
@@ -271,7 +278,7 @@ object RewriteSelfJoinInequalityToAggregate extends Rule[LogicalPlan] with Predi
271278 }
272279 if (! projectOk) return None
273280
274- val filtered = buildAggregateHavingDistinctGt1 (sjLeftEquiAttrs, sjLeftNeqAttr, sjLeft)
281+ val filtered = buildAggregateHavingMultipleDistinct (sjLeftEquiAttrs, sjLeftNeqAttr, sjLeft)
275282
276283 val (newSelfJoinSide, outputRemap): (LogicalPlan , Map [ExprId , Attribute ]) =
277284 selfJoinProjectOpt match {
@@ -387,58 +394,45 @@ object RewriteSelfJoinInequalityToAggregate extends Rule[LogicalPlan] with Predi
387394 if (totalMatched != predicates.size) return None
388395 if (equiPairs.isEmpty || neqPairs.isEmpty) return None
389396
390- // Only rewrite the single-inequality case. Multiple inequality conjuncts cannot be represented
391- // by COUNT(DISTINCT) over a single column.
397+ // A single inequality only: MIN/MAX over one column cannot represent multiple neqs.
392398 if (neqPairs.size != 1 ) return None
393399
394- // The rewrite swaps SQL comparison equality for grouping/DISTINCT equality: `<>` becomes
395- // COUNT(DISTINCT neqCol) and `=` becomes GROUP BY equiKey. It is only sound on types where
396- // those two notions of equality coincide, so gate every equi-key and the neq column on a
397- // positive `isSafeComparisonGroupingType` allowlist rather than `RowOrdering.isOrderable`:
398- // orderable only proves an order/hash exists, not that comparison and grouping agree. Fail
399- // closed on anything not proven safe (float -0.0/NaN, complex types, non-binary collations,
400- // and future/unknown types).
401- //
402- // Check BOTH ends of every pair, not just the sjLeft attribute. `isSameBaseRelation` proves
403- // the two sides are canonically equal, but `AttributeReference.canonicalized` rewrites the
404- // reference to drop metadata, so canonical equality does NOT prove the sjRight attribute
405- // carries the same CHAR/VARCHAR metadata that `isSafeComparisonGroupingAttribute` reads. Gate
406- // each side independently rather than assume they match.
407- val keyAttrs =
408- (equiPairs ++ neqPairs).flatMap { case (left, right) => Seq (left, right) }
400+ // The rewrite swaps comparison equality (`=`/`<>`) for grouping and MIN/MAX ordering equality,
401+ // so gate every equi-key and the neq column -- both ends of each pair, since canonicalization
402+ // drops the metadata that `isSafeComparisonGroupingAttribute` reads and the two ends may differ
403+ // -- on a positive type allowlist. Fail closed on anything not proven safe.
404+ val keyAttrs = (equiPairs ++ neqPairs).flatMap { case (l, r) => Seq (l, r) }
409405 if (! keyAttrs.forall(isSafeComparisonGroupingAttribute)) return None
410406
411- // Canonicalization intentionally erases cosmetic Alias names, so name equality cannot prove
412- // that the two predicate ends refer to the same underlying column. Resolve each end by its own
413- // ExprId against its child output and require matching output ordinals instead.
414- val equiValid = equiPairs.forall {
415- case (l, r) => sameOutputPosition(leftPlan, rightPlan, l, r)
416- }
417- val neqValid = neqPairs.forall {
418- case (l, r) => sameOutputPosition(leftPlan, rightPlan, l, r)
419- }
407+ // The rewrite expresses "two or more distinct values" as MIN(neq) <> MAX(neq), so the neq
408+ // column must be orderable. The allowlist above already implies this, but assert Spark's own
409+ // MIN/MAX input contract (RowOrdering.isOrderable, the same check Min/Max run) explicitly, so
410+ // the requirement is visible at the rewrite site.
411+ if (! RowOrdering .isOrderable(neqPairs.head._1.dataType)) return None
412+
413+ // Resolve each predicate end by ExprId and require matching output ordinals, not name equality
414+ // (canonicalization erases cosmetic Alias names).
415+ val equiValid =
416+ equiPairs.forall { case (l, r) => sameOutputPosition(leftPlan, rightPlan, l, r) }
417+ val neqValid = neqPairs.forall { case (l, r) => sameOutputPosition(leftPlan, rightPlan, l, r) }
420418 if (! equiValid || ! neqValid) return None
421419
422- // Equi-key output positions must be distinct across pairs. Keep the same positional identity
423- // here so swapped or duplicate aliases cannot make two different underlying columns look equal.
420+ // Equi-key output positions must be distinct, so swapped/duplicate aliases cannot collide.
424421 val leftEquiOrdinals = equiPairs.map { case (l, _) => outputOrdinal(leftPlan, l) }
425422 if (leftEquiOrdinals.exists(_ < 0 )) return None
426423 if (leftEquiOrdinals.distinct.size != leftEquiOrdinals.size) return None
427424
428- // Defensive: reject when the neq column overlaps an equi-key column
429- // (e.g. `t1.k = t2.k AND t1.k <> t2.k`).
425+ // Reject when the neq column overlaps an equi-key column (e.g. `t1.k = t2.k AND t1.k <> t2.k`).
430426 val neqLeftOrdinal = outputOrdinal(leftPlan, neqPairs.head._1)
431427 if (neqLeftOrdinal < 0 || leftEquiOrdinals.contains(neqLeftOrdinal)) return None
432428 Some ((equiPairs, neqPairs))
433429 }
434430
435431 /**
436- * Attribute-aware gate applied to the equi keys and the neq column. A CHAR/VARCHAR column reaches
437- * the optimizer as StringType with its declared type recorded in the attribute metadata
438- * (CharVarcharUtils stamps it when the relation output is built), so checking `attr.dataType`
439- * alone would let it through the StringType branch of [[isSafeComparisonGroupingType ]]. Recover
440- * the declared raw type from the metadata (falling back to `dataType` when there is no marker)
441- * and run it through the datatype allowlist, so CHAR/VARCHAR fail closed there in every config.
432+ * Type gate applied to each equi-key and the neq column. CHAR/VARCHAR reach the optimizer as
433+ * StringType with the declared type recorded in the attribute metadata, so recover the raw type
434+ * from metadata (falling back to `dataType`) before running the datatype allowlist -- otherwise
435+ * they would slip through the StringType branch.
442436 */
443437 private def isSafeComparisonGroupingAttribute (attr : Attribute ): Boolean = {
444438 val rawType = CharVarcharUtils .getRawType(attr.metadata).getOrElse(attr.dataType)
@@ -447,7 +441,7 @@ object RewriteSelfJoinInequalityToAggregate extends Rule[LogicalPlan] with Predi
447441
448442 /**
449443 * Positive allowlist of types where comparison equality (`=`/`<>`) provably coincides with
450- * grouping/distinct equality, so a key can move into GROUP BY / COUNT(DISTINCT) . Float/Double
444+ * grouping and MIN/MAX ordering equality, so a key can move into GROUP BY / MIN-MAX . Float/Double
451445 * (NaN, signed zero), CHAR/VARCHAR (declared-type/padding), non-binary collated strings, complex
452446 * types, UDTs / Variant and unknown types fail closed.
453447 */
0 commit comments