Skip to content

Commit 5600063

Browse files
hhr293guowangyzhulipeng
committed
[SPARK-41416][SQL] Use MIN(v) <> MAX(v) instead of COUNT(DISTINCT v) > 1
The self-join inequality rewrite emitted GROUP BY k HAVING COUNT(DISTINCT v) > 1. Switch it to MIN(v) <> MAX(v), which is semantically equivalent -- both mean the group has at least two distinct non-null values -- but avoids the distinct-dedup aggregation stages and supports partial aggregation. This reduces the aggregation overhead observed with the COUNT(DISTINCT) form at low multiplicity. MIN/MAX require an orderable input, so assert Spark's own RowOrdering.isOrderable contract at the rewrite site (the type allowlist already implies it) and reword the config doc and the gate comments in terms of MIN/MAX ordering equality. The structural tests can no longer compare the rewritten plan against a hand-written aggregate SQL: the rule builds its HAVING MIN(v) <> MAX(v) filter in a later optimizer batch, so InferFiltersFromConstraints adds isnotnull(min)/isnotnull(max) to the hand-written HAVING but not to the rule's own filter, and the two diverge. Assert the Aggregate + Filter(Not(EqualTo(min, max))) shape directly, and require both signature aliases so a rewrite that emitted one but dropped the other is still caught. Co-authored-by: Guo Wangyang <[email protected]> Co-authored-by: Lipeng Zhu <[email protected]> Signed-off-by: hengrui hu <[email protected]>
1 parent ffef266 commit 5600063

3 files changed

Lines changed: 100 additions & 101 deletions

File tree

‎sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala‎

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -673,9 +673,14 @@ object SQLConf {
673673
buildConf("spark.sql.optimizer.rewriteSelfJoinInequalityToAggregate.enabled")
674674
.internal()
675675
.doc("When true, rewrites a supported existence-only inequality self-join inside an " +
676-
"uncorrelated IN subquery into a GROUP BY with HAVING COUNT(DISTINCT) > 1 over a single " +
676+
"uncorrelated IN subquery into a GROUP BY with HAVING MIN(v) <> MAX(v) over a single " +
677677
"copy of the relation, removing the self-join cross-product. The rewrite fails closed " +
678-
"unless the self-join sides are proven to be the same repeatable relation.")
678+
"unless the self-join sides are proven to read the same repeatable source -- currently " +
679+
"stock Parquet scans, Range, and local relations -- so it never changes results for " +
680+
"non-repeatable inputs. This is experimental and off by default: there is no cost " +
681+
"model, and the benefit depends on per-key multiplicity because the eliminated " +
682+
"self-join can generate quadratically many candidate pairs. Enable it only for " +
683+
"workloads known to contain such high-multiplicity self-joins.")
679684
.version("4.4.0")
680685
.withBindingPolicy(ConfigBindingPolicy.NOT_APPLICABLE)
681686
.booleanConf

‎sql/core/src/main/scala/org/apache/spark/sql/execution/RewriteSelfJoinInequalityToAggregate.scala‎

Lines changed: 42 additions & 48 deletions
Original file line numberDiff line numberDiff line change
@@ -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
*/
4747
object 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

Comments
 (0)