You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@spark.apache.org by do...@apache.org on 2026/09/18 14:02:59 UTC
(spark) branch branch-4.x updated: [SPARK-59289][SQL] Decide a co-partitioned child's GroupPartitionsExec once, where the join's merged keys are known
This is an automated email from the ASF dual-hosted git repository.
dongjoon-hyun pushed a commit to branch branch-4.x
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/branch-4.x by this push:
new 6f77a291ae45 [SPARK-59289][SQL] Decide a co-partitioned child's GroupPartitionsExec once, where the join's merged keys are known
6f77a291ae45 is described below
commit 6f77a291ae45ac94489966135cde7e9a61e254f6
Author: Peter Toth <pe...@gmail.com>
AuthorDate: Fri Sep 18 07:02:39 2026 -0700
[SPARK-59289][SQL] Decide a co-partitioned child's GroupPartitionsExec once, where the join's merged keys are known
### What changes were proposed in this pull request?
A co-partitioned child's `GroupPartitionsExec` is decided once, at the one place that knows what the join's two sides settled on, and the node carries that decision instead of re-deriving it.
**Where the node comes from.** `ensureDistributionAndOrdering` resolved every child on its own first, so it placed a `GroupPartitionsExec` over a co-partitioned child before knowing the parent was a join. `checkKeyGroupCompatible` then rewrote or replaced it, descending past a local sort, merging new parameters in and dropping any grouping stacked on top. The two sites also worked in different index spaces, the placeholder's positions against the raw partition keys and the spec's agai [...]
Now the two paths are separate. `resolveChild` handles a child that answers for itself, and `coPartitionChildren` owns a co-partitioned one end to end, so no node is built before the pairing is known.
**How the children are carried.** The co-partitioned set used to be a `Seq[Int]` of child indexes beside an `isCoPartitioned` flag, threaded alongside `Seq[Distribution]`. It is one value now: a `Seq[Option[ClusteredDistribution]]` aligned with `children`, holding what each child has to satisfy and nothing for a child that answers for itself. Readers `zip` it instead of indexing, and it carries the type the split point already knew, so three asserts, four `asInstanceOf[ClusteredDistri [...]
**Who decides what.** `coPartitionChildren` recognises only the three shapes that need nothing arranged between the children, each at the same altitude: every side a single small partition, a storage-partitioned join, or two compatible pass-through specs. The shuffle is `shuffleToCoPartition`, and the layout it drags everyone onto is `pickCoPartitionTarget`, returning a `CoPartitionTarget` that names the winning member and, per child, the member pairing with it. `ShuffleSpecCollection [...]
**What the node holds.** `grouping`, `plannedPartitioning` and `childPartitioning` are constructor fields now, derived once by `GroupPartitionsExec.apply`. They were per-instance lazy vals, so every `copy` and `withNewChildren` threw the memo away. The node reports `plannedPartitioning` only while its child still reports the `childPartitioning` it was decided over, and `UnknownPartitioning` otherwise, so an AQE rewrite that changes the child's layout cannot leave the node claiming one [...]
**What `satisfies` answers.** `KeyedPartitioning.satisfies` returned `true` for a partitioning that only satisfies after a projecting node, for the storage-partitioned join's benefit alone. It is strict now, and the loose question moved to `keysCanSatisfy`, which `keysMaySatisfy` and `mayGroupToSatisfy` compose with the strict one. This is a precondition of the restructure rather than a fix of its own: with one decision point, "satisfies" has to mean "nothing left to do", or the singl [...]
`EnsureRequirements.resolveKeyedPartitioning` picks the positions to project onto through a new `KeyedPartitioning.positionsCoveringClusterKeys`, which `keysSatisfy` also reads, so the predicate that decides whether a projection is needed and the one that picks the positions cannot drift apart. Whether a projection is permitted at all is one `mayProjectToClusterKeys`, where it used to be spelled twice in opposite polarity.
The strict question can read partition keys, which the loose one never did, so the answer is memoized on the partitioning that computes it, by position set. The base kept the same answer in a `mutable.Map` local to `resolveKeyedPartitioning`; that scope is too narrow now, since `ValidateRequirements` and every `AQEShuffleReadRule` application ask `satisfies` of the same partitioning.
**What a second run sees.** Peeling and re-planning would re-decide a pairing an earlier run already settled, on an input that by then holds the keyed shuffle that run inserted. So `checkKeyGroupCompatible` asks first whether the two children satisfy their distributions and line up with each other as they arrive, and hands them back untouched when they do. Three terms, not one: the question is asked only where something was actually peeled, so a plan this rule has not seen decides as [...]
EnsureRequirements
ensureDistributionAndOrdering the two paths, and the ordering step
resolveChild a child that answers for itself
coPartitionChildren children that only answer together
checkKeyGroupCompatible try the join, build both nodes once
alreadyCoPartitioned unless a previous run settled it
resolveEachChild else each on its own
shuffleToCoPartition and shuffle whoever is left over
pickCoPartitionTarget onto one layout, picked once
GroupPartitionsExec(child, grouping, plannedPartitioning, childPartitioning, <recipe>)
GroupPartitionsExec.apply the only way to build one
computeGrouping pure, takes the child's KeyedPartitioning
computeOutputPartitioning pure, takes the same
Retires `rewriteGroupPartitions`, `applyGroupPartitions` and `innermostGroupPartition`'s sort-rebuilding half, along with the `orElse` and the two index spaces they served.
**On SPARK-59272**, which an earlier revision of this description claimed: it is not here. It shipped on its own as apache#58814 and is in master, so this PR is SPARK-59289 alone, and that is the ticket for the release note. Thanks to ulysses-you for asking for the two to be kept apart.
**Scope note**, also ulysses-you's. The `matchesClusterKeys` consolidation that accounted for most of `partitioning.scala`'s diff is reverted and filed for its own ticket; only `isClusterKey` and `allClusterKeysAmong` remain, because the new code calls them. The "operation key" to "cluster key" rename stays: it is 28 lines across four files, it makes the prose agree with `ClusteredDistribution.clustering`, and this change is master-only so no cherry-pick pays for it.
### Why are the changes needed?
**A join could commit to a pairing its own children then refuse.** `GroupPartitionsExec` gives up its keyed claim when it turns out to regroup a layout that pins undeclared rows to `hash(key) % numPartitions`, and only the node knows the permutation it performs, so that answer arrived after `checkKeyGroupCompatible` had skipped both shuffles. SPARK-59272 closed that hole with a gate at the end of the pairing. This PR removes the shape it guards: the decision and the node are at one pl [...]
**The same derivation ran many times.** Measured on `KeyGroupedPartitioningSuite`'s "join with two partition keys and matching & sorted partitions": the base derives the grouping 16 times over 48 node instances, this derives it 8 times over 64. A lazy val belongs to one instance, and the columnar and codegen rules rebuild the tree after this rule, so the derivations followed the instances. As fields they follow the planner's decisions instead.
**The caller was compensating for the predicate.** `resolveKeyedPartitioning` asked in two steps whether a member needed a node at all, the cheap full-coverage test and then the projection that decides whether a narrowing merges anything. `keysSatisfy` owns both now and the caller is `admitted.find(_.satisfiesAsIs)`.
**The rule was not idempotent.** Applying it to its own output changed the plan, which matters because AQE re-plans every query stage and two AQE rules hand the tree back to it. Measured over `KeyGroupedPartitioningSuite` by re-running the rule on each of its own results, 2713 applications in all: the base differs on 2, and it differs by adding a shuffle. Without the check described above this differs on 16, all of them a grouping node added over a shuffle. With it, on none. The gener [...]
### Does this PR introduce _any_ user-facing change?
**Yes**, two plan changes. No public API changes. What does move is `GroupPartitionsExec`'s case class signature and the predicates on `KeyedPartitioning` and `ClusteredDistribution`, in `sql.execution` and `sql.catalyst`, and `MimaExcludes` treats both packages as internals in its `defaultExcludes` section.
**`satisfies` accepts a partitioning whose expression *is* a cluster key**, such as a `years(ts)` under a clustering naming `years(ts)`. The old reference-level test refused it unless `requireAllClusterKeys` was set, while the `requireAllClusterKeys` arm accepted the same shape, so this removes an inconsistency. It is a widening on the default configuration. It reaches one second-order place: `PartitioningCollection.createShuffleSpec` now keeps such a member, and since `ShuffleSpecCol [...]
**A re-planned stage keeps the plan it had.** The rule is idempotent now, where the base can add a shuffle on the second pass, so an AQE stage's plan no longer drifts from the one first planned.
### How was this patch tested?
Fifteen new tests, and one rewrite of the existing peel test. Each fails once the decision it pins is put back, except the AQE one, which is marked below and says so in its own comment.
| test | the decision put back |
|---|---|
| `DistributionSuite`: satisfies is strict about a projection that merges partitions | the loose `keysSatisfy` |
| `DistributionSuite`: satisfies accepts a partition expression that is itself a cluster key | the reference-only coverage test |
| `ShuffleSpecSuite`: createShuffleSpec keeps a member that only satisfies after a projection | the collection filter on strict `satisfies` |
| `ShuffleSpecSuite`: createShuffleSpec drops a keyed member that is not grouped | widening that filter past what the base admitted |
| `GroupPartitionsExecSuite`: the keyed claim goes when the child no longer reports what was planned | reporting `plannedPartitioning` unconditionally |
| `EnsureRequirementsSuite`: an aligned grouping is wrapped by withJoinKeyPositions, not rebuilt | the assert that shape used to hit |
| SPARK-58996 only a local sort is looked through | descending through a global sort |
| a local sort with no grouping under it is left alone | peeling a sort with nothing under it |
| a grouped side is paired on its own key order | `toGrouped` for a grouped source too |
| pushing join key positions into a node re-derives its grouping | `copy` instead of the rebuild |
| single-partition children still honour a required partition count | leaving both children alone |
| a partitioning is never projected onto no position | projecting onto the empty position set |
| a second pass leaves a pairing this rule already made alone | re-deciding a settled pairing |
| pushed positions compose with the ones a node already carries | replacing a node's positions instead of composing |
| `KeyGroupedPartitioningSuite`: a second pass leaves a storage-partitioned join this rule planned alone | `keepArrivedPairing`, on the sixth of its six queries |
| `KeyGroupedPartitioningSuite`: a grouping over a keyed shuffle stage survives an AQE round | **nothing; this one is coverage** |
The idempotency set is ulysses-you's ask, one query per way the rule can plan a storage-partitioned join, including a partially clustered one so the re-plan path runs, each asserting `apply(apply(p)) == apply(p)` and pinning the shape it exercises. Only the last of the six needs `keepArrivedPairing`: with that term disabled the other five still pass.
The AQE test is dongjoon-hyun's ask, and it is honest about what it does not do. It runs the shape under AQE with every shuffle read rule enabled, but it does not get a rewrite applied to the keyed shuffle stage, and that looks structural: `CoalesceShufflePartitions` coalesces only a group whose leaves are all query stages, and `OptimizeShuffleWithLocalRead` needs the stage to be a broadcast join's own probe side. A storage-partitioned join always keeps one side as a scan, which is ne [...]
Three `SPARK-58968` test names and one `SPARK-58996` name lost the word "operation" with the rest of the prose. `SPARK-59272`'s new "partition filtering leaves a marked pair's merged keys alone" reads the count off `expectedKeyCount` rather than `expectedPartitionKeys.map(_.size)`, since this change replaces that field with the count itself; the assertion is the same.
**Execution refuses a child it was not planned over.** `GroupPartitionsExec.doExecute` and `doExecuteColumnar` check `child.outputPartitioning` against `childPartitioning` and throw an internal error rather than coalescing the new child on the planning-time indices. Giving up the keyed claim only gets `ValidateRequirements` to reject such a plan, and `AdaptiveSparkPlanExec.optimizeQueryStage` validates an `AQEShuffleReadRule`'s result and nothing else, so a rewrite from any other rule [...]
**A differential sweep is the strongest evidence here.** 307200 generated storage-partitioned join plans, 40 partitioning shapes a side crossed with six join types over 32 configuration cells, run against master and against this change. Each plan is checked three ways: that re-applying the rule to its own output changes nothing, that `ValidateRequirements` passes, and that two sides whose shuffles were both skipped really declare the same key sequence. The cases are keyed and set-diff [...]
| | master | this change |
|---|---|---|
| plans that skip both shuffles yet disagree on the keys | 0 | 0 |
| plans where re-applying the rule changes the plan | 0 | 0 |
| plans `ValidateRequirements` rejects | 4700 | 5340 |
| plans the planner cannot build at all | 29952 | 29312 |
**The whole delta is one set of 640 cases, moving from the third row to the second.** Nothing else changes, in either direction. A shape master could not plan at all is now planned, and rejected. Both of those are bad answers; a plan that runs without AQE rewrites is the less bad one.
Those 640, and the 29312 that remain, need a marked layout that is not grouped. Nothing builds one. The marker is only ever put on a layout `KeyedShuffleSpec.createPartitioning` has just laid out one partition per key, and both paths that would regroup a marked layout refuse it. The sweep reaches the shape only because its generator marks an ungrouped layout by hand. ulysses-you re-derived this independently at the previous revision.
Green: `DistributionSuite`, `ShuffleSpecSuite`, `EnsureRequirementsSuite`, `ValidateRequirementsSuite`, `PlannerSuite`, `GroupPartitionsExecSuite`, `ProjectedOrderingAndPartitioningSuite`, `KeyGroupedPartitioningSuite`, `DataSourceV2CatalystRuntimeFilterSuite`, `AdaptiveQueryExecSuite`, `ExchangeSuite`, `JoinSuite`, `CoalesceShufflePartitionsSuite` and `DataSourceV2Suite`. `dev/lint-scala` is clean.
All seven plan-stability suites are green as well, 322 tests, so no golden TPCDS or TPCH plan changed. That is the net for a stray plan change out of the `EnsureRequirements` restructuring, since the rule runs on every query and those two workloads have no storage-partitioned join.
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: Claude Code (Opus 5)
Closes #58659 from peter-toth/SPARK-59289-decide-node-once.
Authored-by: Peter Toth <pe...@gmail.com>
Signed-off-by: Dongjoon Hyun <do...@apache.org>
(cherry picked from commit 18af1f3d16a483dc328992142e71d93ff6937bbf)
Signed-off-by: Dongjoon Hyun <do...@apache.org>
---
.../sql/catalyst/plans/physical/partitioning.scala | 299 ++++-
.../spark/sql/catalyst/DistributionSuite.scala | 63 +-
.../spark/sql/catalyst/ShuffleSpecSuite.scala | 48 +
.../datasources/v2/GroupPartitionsExec.scala | 602 +++++----
.../execution/exchange/EnsureRequirements.scala | 1339 ++++++++++----------
.../connector/KeyGroupedPartitioningSuite.scala | 192 ++-
.../datasources/v2/GroupPartitionsExecSuite.scala | 59 +-
.../exchange/EnsureRequirementsSuite.scala | 305 ++++-
8 files changed, 1874 insertions(+), 1033 deletions(-)
diff --git a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/physical/partitioning.scala b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/physical/partitioning.scala
index 9b178e5047b2..8adbbd900ed4 100644
--- a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/physical/partitioning.scala
+++ b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/physical/partitioning.scala
@@ -17,7 +17,10 @@
package org.apache.spark.sql.catalyst.plans.physical
+import java.util.concurrent.ConcurrentHashMap
+
import scala.annotation.tailrec
+import scala.collection.immutable.BitSet
import scala.collection.mutable
import org.apache.spark.{SparkException, SparkUnsupportedOperationException}
@@ -27,6 +30,7 @@ import org.apache.spark.sql.catalyst.util.InternalRowComparableWrapper
import org.apache.spark.sql.connector.catalog.functions.Reducer
import org.apache.spark.sql.internal.SQLConf
import org.apache.spark.sql.types.{DataType, IntegerType}
+import org.apache.spark.util.TransientBestEffortLazyVal
/**
* Specifies how tuples that share common expressions will be distributed when a query is executed
@@ -121,6 +125,13 @@ case class ClusteredDistribution(
case (l, r) => l.semanticEquals(r)
}
}
+
+ /** Whether `e` is one of the cluster keys. */
+ def isClusterKey(e: Expression): Boolean = clustering.exists(_.semanticEquals(e))
+
+ /** Whether every cluster key is named by one of `expressions`. */
+ def allClusterKeysAmong(expressions: Iterable[Expression]): Boolean =
+ clustering.forall(key => expressions.exists(_.semanticEquals(key)))
}
/**
@@ -565,24 +576,25 @@ case class KeyLayout(
* or a `GroupPartitionsExec` can coalesce the partitions that share a key.
*
* == Distribution Satisfaction and Grouping ==
- * Besides the default `satisfies()`, `KeyedPartitioning` answers four questions. They differ in
- * what they let happen to the data before the distribution counts as met. Only `keysMaySatisfy()`
- * is asked from outside the class. The other three build it and `satisfies()` up.
+ * Besides the default `satisfies()`, `KeyedPartitioning` answers a family of questions. They differ
+ * in what they let happen to the data before the distribution counts as met. Only
+ * `keysMaySatisfy()` is asked from outside the class. The rest build it and `satisfies()` up.
*
- * - `nonGroupedSatisfies()`: is the distribution met by the partitioning as it stands, with no node
- * inserted? It is the default `Partitioning` implementation, so for a `ClusteredDistribution` it
- * is always false.
- * - `keysSatisfy()`: do the partition keys match what the distribution asks for? Duplicate keys are
- * ignored, so this asks about the key expressions alone. `satisfies()` is this plus `isGrouped`,
- * and nothing more.
+ * - `keysSatisfy()`: do the keys as they stand co-locate every cluster key, with nothing left for
+ * a node to project away? This is the strict question, and `satisfies()` is it plus `isGrouped`.
+ * Strict for a `ClusteredDistribution`; its `OrderedDistribution` arm is a gate on what may claim
+ * a global ordering, and the order itself is still the caller's to check.
+ * - `keysCanSatisfy()`: `keysSatisfy()`, or the keys co-locate them after a node has projected
+ * away the expressions that carry none. Only
+ * `spark.sql.sources.v2.bucketing.allowJoinKeysSubsetOfPartitionKeys` admits the second half.
* - `mayGroupToSatisfy()`: may `EnsureRequirements` insert a `GroupPartitionsExec` to meet the
* distribution? It is asked of non-grouped partitionings only, where such a node coalesces the
- * duplicate keys. So the answer is `keysSatisfy()`, plus whether that coalescing is allowed.
+ * duplicate keys. So the answer is `keysCanSatisfy()`, plus whether that coalescing is allowed.
* "Key Collapse" below says when it is not.
* - `keysMaySatisfy()`: the same question for a partitioning that may already be grouped, which is
* what `EnsureRequirements` asks. It is `mayGroupToSatisfy()` for a non-grouped one, and
- * `keysSatisfy()` for a grouped one, which has no duplicate keys left for the node to coalesce,
- * and so nothing for the permission to govern.
+ * `keysCanSatisfy()` for a grouped one, which has no duplicate keys left for the node to
+ * coalesce, and so nothing for the permission to govern.
*
* For `OrderedDistribution`, `GroupPartitionsExec` must also sort the partition keys to meet the
* ordering requirement.
@@ -805,19 +817,41 @@ case class KeyedPartitioning(
def projectKeys(positions: Seq[Int]): (Seq[DataType], Seq[InternalRowComparableWrapper]) =
KeyedPartitioning.projectKeys(partitionKeys, keyDataTypes, positions)
+ /**
+ * The counts `numPartitionsProjectedOn` has already worked out, by position set.
+ *
+ * Kept on the partitioning rather than at a caller because there is no one caller: `satisfies`
+ * asks this question, and the planner, `ValidateRequirements` and every `AQEShuffleReadRule`
+ * application all ask `satisfies` of the same partitioning. The partitioning is immutable and the
+ * answer depends only on the keys and the position set, so the cache cannot go stale.
+ *
+ * Not a constructor field, so it stays out of the product and leaves equality, `hashCode` and
+ * canonicalization alone. The map is built on first use, and on the default configuration nothing
+ * asks a narrowing question at all, since `mayProjectToClusterKeys` requires
+ * `spark.sql.sources.v2.bucketing.allowJoinKeysSubsetOfPartitionKeys`.
+ *
+ * [[TransientBestEffortLazyVal]] because a Scala 2 `lazy val` locks the instance to initialize
+ * it, and this is read from whichever thread is planning or validating.
+ */
+ private val projectedPartitionCounts =
+ new TransientBestEffortLazyVal[ConcurrentHashMap[BitSet, java.lang.Integer]](
+ () => new ConcurrentHashMap[BitSet, java.lang.Integer]())
+
/**
* The number of partitions a `GroupPartitionsExec` projecting these keys to `positions` would
- * leave, which is the number of distinct projected keys. `positions` must be distinct and in
- * range, as it must be for `project` and `projectKeys`.
+ * leave, which is the number of distinct projected keys. Every position has to be in range, as
+ * it must be for `project` and `projectKeys`, and a [[BitSet]] keeps them distinct. The order it
+ * puts them in does not matter here, since only the count is asked for.
*
* A projection that keeps every position is the identity on the key values, so it needs no
- * projected rows at all. The rest allocate a row per partition and hash it with an uncached
- * `hashCode`, which makes this the expensive question to ask of a partitioning. A caller asking
- * it for several position sets should memoize on the set.
+ * projected rows at all, and that case is answered before the memo is touched. The rest allocate
+ * a row per partition and hash it with an uncached `hashCode`, which makes this the expensive
+ * question to ask of a partitioning, so the answer is kept (see `projectedPartitionCounts`).
*/
- def numPartitionsProjectedOn(positions: Seq[Int]): Int = {
- if (positions.length < expressions.length) {
- projectKeys(positions)._2.distinct.size
+ def numPartitionsProjectedOn(positions: BitSet): Int = {
+ if (positions.size < expressions.length) {
+ projectedPartitionCounts.apply().computeIfAbsent(positions,
+ _ => projectKeys(positions.toSeq)._2.distinct.size)
} else if (isGrouped) {
numPartitions
} else {
@@ -834,41 +868,101 @@ case class KeyedPartitioning(
KeyedPartitioning.reduceKeys(partitionKeys, keyDataTypes, reducers)
override def satisfies0(required: Distribution): Boolean = {
- nonGroupedSatisfies(required) || (isGrouped && keysSatisfy(required))
+ super.satisfies0(required) || (isGrouped && keysSatisfy(required))
}
- /** The first of the four questions the class doc lists. */
- private def nonGroupedSatisfies(required: Distribution): Boolean = super.satisfies0(required)
+ /**
+ * The positions of the partition expressions that cover a cluster key of `required`, and so
+ * have to survive a projection. An expression covers one in two ways:
+ *
+ * - one of its *references* is a cluster key, as a `bucket(4, a)` covers `a`;
+ * - the expression *itself* is a cluster key, as a `years(ts)` under a clustering that names
+ * `years(ts)` rather than `ts`.
+ *
+ * `EnsureRequirements.resolveKeyedPartitioning` and `keysSatisfy` both read this, so the
+ * predicate deciding whether a projection is needed and the one choosing the positions to
+ * project onto cannot drift apart.
+ *
+ * Not the same question as `KeyedShuffleSpec.keyPositions`, and the two must not be merged. That
+ * one answers, per expression, which cluster key the expression is a function *of*. That is
+ * what `KeyedShuffleSpec.createPartitioning` needs, since it rebuilds the expression over the
+ * other side's clustering with `te.copy(children = ... clustering(positionSet.head))`. Handing it
+ * the second form above would rebuild a `years(ts)` clustered on `years(ts)` as
+ * `years(years(ts))`.
+ * The two coincide exactly where every expression has a single reference and no expression is
+ * itself a cluster key. Where they diverge, `createShuffleSpec` refuses to project rather than
+ * projecting onto nothing.
+ */
+ def positionsCoveringClusterKeys(required: ClusteredDistribution): BitSet =
+ expressions.zipWithIndex.collect {
+ case (e, i) if required.isClusterKey(e) || e.references.exists(required.isClusterKey) => i
+ }.to(BitSet)
+
+ /**
+ * Whether every partition expression is a function of cluster keys alone, so that rows sharing
+ * a cluster key share a partition and nothing needs projecting.
+ *
+ * The sibling of `positionsCoveringClusterKeys`, and the two differ in one word: this quantifies
+ * over an expression's references with `forall`, that one with `exists`. Both are right for what
+ * they are asked. A `bucket(4, b, c)` over a clustering naming `b` alone *carries* a cluster
+ * key, so its position survives a projection, yet two rows sharing `b` land in different buckets
+ * when their `c` differs, so it is not a function of the cluster keys. Deliberately not
+ * `positionsCoveringClusterKeys(required).size == expressions.length`.
+ */
+ private def isFunctionOfClusterKeys(required: ClusteredDistribution): Boolean =
+ expressions.forall { e =>
+ required.isClusterKey(e) || e.references.forall(required.isClusterKey)
+ }
+
+ /**
+ * Whether a `GroupPartitionsExec` may project these keys down to the cluster keys at all. Only
+ * `spark.sql.sources.v2.bucketing.allowJoinKeysSubsetOfPartitionKeys` permits it, and a marked
+ * layout cannot survive it, since the projection coarsens the declared set the out-of-set routing
+ * speaks for (see the `@param`). Whole keys co-locate there and subsets do not, so a window or
+ * aggregate keyed on a strict subset of the partition columns must still shuffle. The
+ * single-reference requirement is what makes keeping a position sound at all. A kept expression
+ * is then a function of one cluster key, so coalescing on the projected keys cannot put rows that
+ * share a cluster key on different partitions.
+ *
+ * Read by `keysSatisfy` and `keysCanSatisfy`, which is the point. They ask different things once
+ * the projection is permitted, so the permission has to be one rule rather than two spellings.
+ */
+ private def mayProjectToClusterKeys(required: ClusteredDistribution): Boolean =
+ !required.requireAllClusterKeys && !mayContainUnknownPartitionKeys &&
+ SQLConf.get.v2BucketingAllowKeysSubsetOfPartitionKeys &&
+ expressions.forall(_.references.size == 1)
- /** The second of the four questions the class doc lists. */
+ /**
+ * The strict question of the family the class doc lists, for a [[ClusteredDistribution]]. `true`
+ * only when the keys as they stand co-locate every cluster key, with no projection left for a
+ * `GroupPartitionsExec` to perform. It says nothing about duplicate keys, which such a node also
+ * coalesces, so an admitted layout can still need one: `satisfies` adds `isGrouped` on top.
+ *
+ * Two ways to be true. Every partition expression is a function of cluster keys alone, so
+ * nothing needs projecting. Or one is not, in which case the projection that drops it may still
+ * merge no partition, and then rows sharing a cluster key already sit on one partition. The
+ * second is the only branch that reads a partition key, and only
+ * `spark.sql.sources.v2.bucketing.allowJoinKeysSubsetOfPartitionKeys` admits it, so the ordinary
+ * configuration answers structurally.
+ *
+ * The strictness claim stops at [[ClusteredDistribution]]. The [[OrderedDistribution]] arm is a
+ * local gate on what may claim a global ordering at all, and it does not read the key order, so a
+ * side whose keys run the wrong way still answers `true` here. `EnsureRequirements.resolveChild`
+ * is what compares the keys against the required ordering and builds the sorting node, and it has
+ * to stay: nothing below tells it the keys are already in order.
+ */
private def keysSatisfy(required: Distribution): Boolean = {
required match {
- case c @ ClusteredDistribution(requiredClustering, requireAllClusterKeys, _, _) =>
- if (requireAllClusterKeys) {
+ case c: ClusteredDistribution =>
+ if (c.requireAllClusterKeys) {
// Checks whether this partitioning is partitioned on exactly same clustering keys of
// `ClusteredDistribution`.
c.areAllClusterKeysMatched(expressions)
} else {
- // We'll need to find leaf attributes from the partition expressions first.
- val attributes = AttributeSet.fromAttributeSets(expressions.map(_.references))
-
- if (mayContainUnknownPartitionKeys) {
- // Whole keys co-locate, subsets do not (see the `@param`): a window or aggregate
- // keyed on a strict subset of the partition columns must still shuffle.
- attributes.forall(x => requiredClustering.exists(_.semanticEquals(x)))
- } else if (SQLConf.get.v2BucketingAllowKeysSubsetOfPartitionKeys) {
- // The operation keys may be a subset of the partition keys, so one partition expression
- // covering one of them is enough. Partitions can then still hold rows that share an
- // operation key. What makes the distribution true is the projection onto the covering
- // positions, plus the grouping that follows it. Given the single reference per
- // expression that `supportsExpressions` enforces, the test below is exactly
- // `KeyedShuffleSpec.keyPositions.exists(_.nonEmpty)`, where `createShuffleSpec` takes
- // its `joinKeyPositions` from. Consolidating the two is left to a follow-up.
- requiredClustering.exists(x => attributes.exists(_.semanticEquals(x))) &&
- expressions.forall(_.references.size == 1)
- } else {
- attributes.forall(x => requiredClustering.exists(_.semanticEquals(x)))
- }
+ isFunctionOfClusterKeys(c) || (mayProjectToClusterKeys(c) && {
+ val positions = positionsCoveringClusterKeys(c)
+ positions.nonEmpty && numPartitionsProjectedOn(positions) == numPartitions
+ })
}
case o @ OrderedDistribution(_) if SQLConf.get.v2BucketingAllowSorting =>
@@ -888,8 +982,30 @@ case class KeyedPartitioning(
}
/**
- * The third of the four questions the class doc lists. Ask it only of a partitioning that is not
- * grouped, since a grouped one has nothing to coalesce and `keysMaySatisfy` covers both.
+ * Either way of co-locating the cluster keys, with or without a projection.
+ *
+ * The first case is the projecting one, and it is asked first because it is structural, while
+ * `keysSatisfy` may read the partition keys to decide whether a projection would merge anything.
+ * `mayProjectToClusterKeys` holds the permission.
+ *
+ * Given the single reference per expression that `supportsExpressions` enforces, that case
+ * coincides with `KeyedShuffleSpec.keyPositions.exists(_.nonEmpty)`, where `createShuffleSpec`
+ * takes its `joinKeyPositions` from. They cannot be merged into one derivation, see
+ * `positionsCoveringClusterKeys`.
+ */
+ private def keysCanSatisfy(required: Distribution): Boolean = {
+ val satisfiesAfterProjection = required match {
+ case c: ClusteredDistribution if mayProjectToClusterKeys(c) =>
+ // Some position covers a cluster key, so there is something to project onto.
+ expressions.exists(_.references.exists(c.isClusterKey))
+ case _ => false
+ }
+ satisfiesAfterProjection || keysSatisfy(required)
+ }
+
+ /**
+ * Ask this only of a partitioning that is not grouped, since a grouped one has nothing to
+ * coalesce and `keysMaySatisfy` covers both. See the class doc.
*/
private[sql] def mayGroupToSatisfy(required: Distribution): Boolean = {
val mayCoalesce = required match {
@@ -898,12 +1014,12 @@ case class KeyedPartitioning(
case _ => true
}
// The permission is the cheap half, so it is asked first.
- mayCoalesce && keysSatisfy(required)
+ mayCoalesce && keysCanSatisfy(required)
}
- /** The fourth of the four questions the class doc lists. */
+ /** What `EnsureRequirements` asks. See the class doc. */
private[sql] def keysMaySatisfy(required: Distribution): Boolean = {
- if (isGrouped) keysSatisfy(required) else mayGroupToSatisfy(required)
+ if (isGrouped) keysCanSatisfy(required) else mayGroupToSatisfy(required)
}
override def createShuffleSpec(distribution: ClusteredDistribution): KeyedShuffleSpec = {
@@ -927,8 +1043,17 @@ case class KeyedPartitioning(
if (mayContainUnknownPartitionKeys) {
return result
}
- // If allowing operation keys to be a subset of partition keys, create a new
- // `KeyedPartitioning` grouped on the operation keys, and use that as
+ // No position covers a cluster key, so there is nothing to project onto. Projecting onto
+ // none would coalesce every partition into one, which is never the answer, and it is the
+ // same refusal `EnsureRequirements.resolveKeyedPartitioning` makes for its own caller.
+ // `keyPositions` maps an expression's single *reference* onto the clustering, so this is
+ // reachable for a clustering that names the partition expression itself, where `keysSatisfy`
+ // says yes and this finds nothing. Return the unprojected spec, as above.
+ if (joinKeyPositions.isEmpty && expressions.nonEmpty) {
+ return result
+ }
+ // If allowing cluster keys to be a subset of partition keys, create a new
+ // `KeyedPartitioning` grouped on the cluster keys, and use that as
// the returned shuffle spec.
// `toGrouped` sorts the keys the same way `GroupPartitionsExec` does (both sort with
// `KeyedPartitioning.groupedKeyRowOrdering`). Otherwise, when only the keyed side is
@@ -1019,7 +1144,7 @@ object KeyedPartitioning {
* and the other side of the join may be shuffled onto exactly those keys, while the
* `GroupPartitionsExec` inserted on the keyed side independently re-groups its partitions with
* the same key positions and sorts them with this same ordering
- * (`GroupPartitionsExec.groupAndSortByKeys`). If the two sorts diverged, inner joins would fail
+ * (`GroupPartitionsExec.computeGrouping`). If the two sorts diverged, inner joins would fail
* loudly at planning time -- `ShuffledJoin` wraps both sides' partitionings into a
* `PartitioningCollection`, whose invariant requires equal partition keys -- but join types that
* expose only one side's partitioning (e.g. LEFT OUTER) run nothing that compares the two
@@ -1261,7 +1386,22 @@ case class PartitioningCollection(partitionings: Seq[Partitioning])
partitionings.exists(_.satisfies(required))
override def createShuffleSpec(distribution: ClusteredDistribution): ShuffleSpec = {
- val filtered = partitionings.filter(_.satisfies(distribution))
+ // `maySatisfyAfterProjection`, not `satisfies`. A spec says what its partitioning could
+ // co-partition on, and a grouped `KeyedPartitioning` whose keys are coarser than the
+ // operation's still can, through the projection a `GroupPartitionsExec` performs. That is the
+ // admission set this filter had before `satisfies` became strict, up to one shape it now also
+ // keeps, a partition expression that *is* a cluster key, which `areKeysCompatible` turns away
+ // anyway. The set matters because `ValidateRequirements` builds a spec from a finished plan
+ // through here.
+ //
+ // Every admitted member stays, because `isCompatibleWith` answers for any of them and the
+ // collection cannot know which one the other side matched. The cost is that
+ // `ShuffleSpecCollection.canCreatePartitioning` is a `forall` over members whose keyed half is
+ // false without `v2BucketingShuffleEnabled`, so a groupable keyed member beside a usable
+ // non-keyed one would cost the collection its role as a shuffle template. No operator is known
+ // to report that mixture.
+ val filtered =
+ partitionings.filter(PartitioningCollection.maySatisfyAfterProjection(_, distribution))
ShuffleSpecCollection(filtered.map(_.createShuffleSpec(distribution)))
}
@@ -1294,6 +1434,29 @@ object PartitioningCollection {
private[sql] def numKeyedPartitions(partitioning: Partitioning): Option[Int] =
representativeOf(partitioning).map(_.numPartitions)
+ /**
+ * Whether `p` can serve `required` once a `GroupPartitionsExec` has projected a
+ * [[KeyedPartitioning]]'s keys down to the cluster keys. `satisfies` asks whether it serves as it
+ * stands, and only a keyed partitioning answers the two differently.
+ *
+ * A partitioning that is not grouped is not admitted, even though a node would also group it.
+ * This is the admission set `satisfies` gave the one caller before it became strict, and the
+ * caller feeds `ValidateRequirements` as well as the planner, so it does not widen what a
+ * finished plan is checked against. `EnsureRequirements.createKeyedShuffleSpecs` is where the
+ * planner asks the wider question, for a child it is about to group itself.
+ *
+ * The partition count clause is here for consistency with the strict question. A node changes the
+ * count, so the pre-grouping one is no prediction of it.
+ */
+ private[sql] def maySatisfyAfterProjection(
+ p: Partitioning,
+ required: ClusteredDistribution): Boolean = flatten(p).exists {
+ case k: KeyedPartitioning =>
+ k.isGrouped && required.requiredNumPartitions.forall(_ == k.numPartitions) &&
+ k.keysMaySatisfy(required)
+ case other => other.satisfies(required)
+ }
+
/**
* The uniform `mayContainUnknownPartitionKeys` marker of `p`'s keyed members, read from its
* first keyed member, the same one `checkKeyedPartitioningInvariant` compares against.
@@ -1791,12 +1954,20 @@ case class KeyedShuffleSpec(
joinKeyPositions: Option[Seq[Int]] = None) extends LeafShuffleSpec {
/**
- * A sequence where each element is a set of positions of the partition expression to the cluster
- * keys. For instance, if cluster keys are [a, b, b] and partition expressions are
- * [bucket(4, a), years(b)], the result will be [(0), (1, 2)].
+ * Per partition expression, the positions of the clustering keys it is a function *of*. For
+ * cluster keys [a, b, b] and partition expressions [bucket(4, a), years(b)], the result is
+ * [(0), (1, 2)]. The mapping is very similar to `HashShuffleSpec`'s.
+ *
+ * `createPartitioning` rebuilds the expression over another clustering from this, and
+ * `areKeysCompatible` reads an overlap as "these two expressions are functions of a common
+ * cluster key". Both readings need the cluster key the expression consumes, which is why
+ * this looks at the expression's reference and not at the expression itself. An expression that
+ * *is* a cluster key therefore maps to nothing here, while
+ * `KeyedPartitioning.positionsCoveringClusterKeys` counts it. See that method for why the two
+ * stay apart.
*
- * Note that we only allow each partition expression to contain a single partition key.
- * Therefore the mapping here is very similar to that from `HashShuffleSpec`.
+ * The assertion is what makes the reference reading sound. With one reference per expression,
+ * "some reference is a cluster key" and "every reference is" are the same statement.
*/
lazy val keyPositions: Seq[mutable.BitSet] = {
val distKeyToPos = mutable.Map.empty[Expression, mutable.BitSet]
@@ -2016,10 +2187,10 @@ case class KeyedShuffleSpec(
!SQLConf.get.v2BucketingPartiallyClusteredDistributionEnabled &&
// Shuffling another child onto these partition keys assigns each key a single partition, so
// an ungrouped partitioning cannot be reproduced: its duplicate keys live in more than one
- // partition. This is the local gate. Such a spec is not reachable today for a non-local
- // reason -- `EnsureRequirements` wraps a child whose `KeyedPartitioning` does not satisfy the
- // distribution in a `GroupPartitionsExec` before it builds any spec -- so do not read this
- // clause as redundant.
+ // partition. This is the local gate. Such a spec is not reachable in a planned tree for a
+ // non-local reason -- `EnsureRequirements` wraps a child whose `KeyedPartitioning` does not
+ // satisfy the distribution in a `GroupPartitionsExec` before it builds any spec -- so do not
+ // read this clause as redundant.
partitioning.isGrouped &&
// Every partition expression must map to a clustering key, otherwise `createPartitioning`
// cannot rewrite it. This also keeps the unprojected spec returned by `createShuffleSpec`
diff --git a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/DistributionSuite.scala b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/DistributionSuite.scala
index 15727ad4dc4b..5ca1ead5d22e 100644
--- a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/DistributionSuite.scala
+++ b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/DistributionSuite.scala
@@ -20,14 +20,23 @@ package org.apache.spark.sql.catalyst
import org.apache.spark.SparkFunSuite
/* Implicit conversions */
import org.apache.spark.sql.catalyst.dsl.expressions._
-import org.apache.spark.sql.catalyst.expressions.{Ascending, AttributeReference, CollationAwareMurmur3Hash, Expression, Literal, Pmod, SortOrder}
+import org.apache.spark.sql.catalyst.expressions.{Ascending, AttributeReference, CollationAwareMurmur3Hash, Expression, Literal, Pmod, SortOrder, TransformExpression}
import org.apache.spark.sql.catalyst.plans.SQLHelper
import org.apache.spark.sql.catalyst.plans.physical._
+import org.apache.spark.sql.connector.catalog.functions.ScalarFunction
import org.apache.spark.sql.internal.SQLConf
-import org.apache.spark.sql.types.IntegerType
+import org.apache.spark.sql.types.{DataType, IntegerType}
class DistributionSuite extends SparkFunSuite with SQLHelper {
+ /** A bound function with a stable canonical name, enough to build a `TransformExpression`. */
+ private object TestYearsFunction extends ScalarFunction[Int] {
+ override def inputTypes(): Array[DataType] = Array(IntegerType)
+ override def resultType(): DataType = IntegerType
+ override def name(): String = "years"
+ override def canonicalName(): String = "test.years"
+ }
+
protected def checkSatisfied(
inputPartitioning: Partitioning,
requiredDistribution: Distribution,
@@ -413,6 +422,56 @@ class DistributionSuite extends SparkFunSuite with SQLHelper {
checkSatisfied(groupedKP, ClusteredDistribution(Seq(x)), true)
}
+ test("SPARK-59289: satisfies is strict about a projection that merges partitions") {
+ val a = AttributeReference("a", IntegerType)()
+ val b = AttributeReference("b", IntegerType)()
+ val clustered = ClusteredDistribution(Seq(a))
+
+ // Partitioned by [a, b], clustered on [a] alone. Both are grouped, so the only question is
+ // whether rows sharing `a` share a partition.
+ val merging = KeyedPartitioning(Seq(a, b), Seq(InternalRow(1, 1), InternalRow(1, 2)))
+ val notMerging = KeyedPartitioning(Seq(a, b), Seq(InternalRow(1, 1), InternalRow(2, 2)))
+ assert(merging.isGrouped && notMerging.isGrouped)
+
+ withSQLConf(SQLConf.V2_BUCKETING_ALLOW_KEYS_SUBSET_OF_PARTITION_KEYS.key -> "true") {
+ // a = 1 sits on two partitions, so this satisfies nothing until a GroupPartitionsExec
+ // projects the keys onto [a]. `keysMaySatisfy` is the question that says so.
+ checkSatisfied(merging, clustered, false)
+ assert(merging.keysMaySatisfy(clustered))
+
+ // Projecting here would merge no partition, so every `a` already sits on one and the
+ // partitioning satisfies as it stands. Keeping it beats projecting, since it still names `b`
+ // for a downstream operator to co-partition on.
+ checkSatisfied(notMerging, clustered, true)
+ }
+ }
+
+ test("SPARK-59289: satisfies accepts a partition expression that is itself a cluster key") {
+ val ts = AttributeReference("ts", IntegerType)()
+ val other = AttributeReference("other", IntegerType)()
+ val years = TransformExpression(TestYearsFunction, Seq(ts))
+ val partitioning = KeyedPartitioning(Seq(years), Seq(InternalRow(1), InternalRow(2)))
+ assert(partitioning.isGrouped)
+
+ // The clustering names the transform rather than the column it reads, so rows sharing
+ // `years(ts)` already sit on one partition and nothing has to be re-partitioned. The test that
+ // decides this reads the expression as well as its references, and it runs on the default
+ // configuration.
+ checkSatisfied(partitioning, ClusteredDistribution(Seq(years)), true)
+
+ // The `requireAllClusterKeys` arm has always accepted this shape, since it compares
+ // expressions rather than references, so the two arms agree now.
+ checkSatisfied(
+ partitioning, ClusteredDistribution(Seq(years), requireAllClusterKeys = true), true)
+
+ // Clustered on the column the transform reads, rows sharing `ts` share a partition too, since
+ // the partition expression is a function of it.
+ checkSatisfied(partitioning, ClusteredDistribution(Seq(ts)), true)
+
+ // Neither the expression nor its reference is a cluster key here, so this is refused.
+ checkSatisfied(partitioning, ClusteredDistribution(Seq(other)), false)
+ }
+
test("SPARK-56877: fromPartitionings reuses already-consistent nested collections") {
val x = AttributeReference("x", IntegerType)()
val y = AttributeReference("y", IntegerType)()
diff --git a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/ShuffleSpecSuite.scala b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/ShuffleSpecSuite.scala
index 1ee8002eb4b1..0db9c6dffd5f 100644
--- a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/ShuffleSpecSuite.scala
+++ b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/ShuffleSpecSuite.scala
@@ -27,6 +27,7 @@ import org.apache.spark.sql.internal.SQLConf
import org.apache.spark.sql.types.{DataType, IntegerType, LongType, StructType}
class ShuffleSpecSuite extends SparkFunSuite with SQLHelper {
+
private val passThrough_a_10 = ShufflePartitionIdPassThrough(DirectShufflePartitionID($"a"), 10)
private val passThrough_b_10 = ShufflePartitionIdPassThrough(DirectShufflePartitionID($"b"), 10)
private val passThrough_c_10 = ShufflePartitionIdPassThrough(DirectShufflePartitionID($"c"), 10)
@@ -39,6 +40,53 @@ class ShuffleSpecSuite extends SparkFunSuite with SQLHelper {
override def canonicalName(): String = "test.bucket"
}
+ test("SPARK-59289: createShuffleSpec keeps a member that only satisfies after a projection") {
+ val a = AttributeReference("a", IntegerType)()
+ val b = AttributeReference("b", IntegerType)()
+ val clustered = ClusteredDistribution(Seq(a))
+ // Grouped, but `a = 1` sits on two partitions, so projecting the keys onto [a] merges them and
+ // the member satisfies only once a `GroupPartitionsExec` has. Filtering the members on the
+ // strict `satisfies` would drop it and leave an empty collection, which its own `require`
+ // rejects.
+ val merging = KeyedPartitioning(
+ Seq(a, b), Seq(InternalRow(1, 1), InternalRow(1, 2), InternalRow(2, 1)))
+ assert(merging.isGrouped, "test setup: the member is grouped on its own keys")
+
+ withSQLConf(SQLConf.V2_BUCKETING_ALLOW_KEYS_SUBSET_OF_PARTITION_KEYS.key -> "true") {
+ assert(!merging.satisfies(clustered), "test setup: it does not serve as it stands")
+ val collection = PartitioningCollection(Seq(merging, merging))
+ val spec = collection.createShuffleSpec(clustered)
+ assert(spec.asInstanceOf[ShuffleSpecCollection].specs.size == 2)
+ // Each member's spec describes the projected layout the node would emit, one partition per
+ // distinct `a`.
+ assert(spec.flatten.map(_.numPartitions) == Seq(2, 2))
+ }
+ }
+
+ test("SPARK-59289: createShuffleSpec drops a keyed member that is not grouped") {
+ val a = AttributeReference("a", IntegerType)()
+ val clustered = ClusteredDistribution(Seq(a))
+ // A node would group this one too, but the admission set here is what a finished plan is
+ // checked against by `ValidateRequirements`, so it stays what the strict question admitted
+ // before a projection was allowed to answer it.
+ val ungrouped = KeyedPartitioning(Seq(a), Seq(InternalRow(1), InternalRow(1), InternalRow(2)))
+ val grouped = KeyedPartitioning(Seq(a), Seq(InternalRow(1), InternalRow(2), InternalRow(3)))
+ assert(!ungrouped.isGrouped && grouped.isGrouped, "test setup")
+
+ assert(!PartitioningCollection.maySatisfyAfterProjection(ungrouped, clustered))
+ assert(PartitioningCollection.maySatisfyAfterProjection(grouped, clustered))
+
+ // And through the filter itself, which is the predicate's one caller. The keyed member goes and
+ // the hash member stays, so the collection keeps a spec and its `require` is not tripped. The
+ // pairing is asked of a mixed collection rather than of two keyed members, because
+ // `checkKeyedPartitioningInvariant` forces one `KeyLayout` on all keyed members and `isGrouped`
+ // is therefore uniform across them: a collection cannot hold one of each.
+ val mixed = PartitioningCollection(Seq(ungrouped, HashPartitioning(Seq(a), 3)))
+ val specs = mixed.createShuffleSpec(clustered).asInstanceOf[ShuffleSpecCollection].specs
+ assert(specs.size == 1, s"only the hash member survives the filter, got $specs")
+ assert(specs.head.isInstanceOf[HashShuffleSpec], s"and it is the hash one, got $specs")
+ }
+
protected def checkCompatible(
left: ShuffleSpec,
right: ShuffleSpec,
diff --git a/sql/core/src/main/scala/org/apache/spark/sql/execution/datasources/v2/GroupPartitionsExec.scala b/sql/core/src/main/scala/org/apache/spark/sql/execution/datasources/v2/GroupPartitionsExec.scala
index 03b2c9618ffe..b32e842b35bf 100644
--- a/sql/core/src/main/scala/org/apache/spark/sql/execution/datasources/v2/GroupPartitionsExec.scala
+++ b/sql/core/src/main/scala/org/apache/spark/sql/execution/datasources/v2/GroupPartitionsExec.scala
@@ -30,7 +30,6 @@ import org.apache.spark.sql.catalyst.plans.physical.{IdentityReducer, KeyedParti
import org.apache.spark.sql.catalyst.util.{truncatedString, InternalRowComparableWrapper}
import org.apache.spark.sql.execution.{SafeForKWayMerge, SparkPlan, SQLExecution, UnaryExecNode}
import org.apache.spark.sql.execution.metric.{SQLMetric, SQLMetrics}
-import org.apache.spark.sql.types.DataType
import org.apache.spark.sql.vectorized.ColumnarBatch
/**
@@ -40,16 +39,36 @@ import org.apache.spark.sql.vectorized.ColumnarBatch
* where multiple input partitions share the same partition key. It's commonly used in
* storage-partitioned joins to align partitions from different sides of the join.
*
+ * Everything that says how the node was decided is `@transient`, since only the driver plans and
+ * the executors read the groups through [[GroupedPartitionCoalescer]] rather than through this
+ * node. The two partitionings are not, matching `ShuffleExchangeExec`'s, since they are what the
+ * node claims rather than how it arrived at the claim.
+ *
* @param child The child plan providing bucketed/partitioned input
+ * @param grouping What this node does to the child's partitions, derived once at planning time by
+ * `GroupPartitionsExec.apply`. See that factory for the rule about keeping it in
+ * step with the parameters it was derived from.
+ * @param plannedPartitioning What this node was planned to report, derived at planning time from
+ * `childPartitioning` and the grouping. Same rule. Reported only while
+ * the child still reports what it was planned over, see
+ * `outputPartitioning`.
+ * @param childPartitioning The child's partitioning this node was decided for. Kept so that a node
+ * handed a different child can say so, and in the case class product so
+ * that `QueryPlan.doCanonicalize` normalizes its exprIds along with
+ * `plannedPartitioning`'s, which is what keeps the comparison meaningful.
* @param joinKeyPositions Optional projection selecting a subset of the partitioning key positions,
* so that partitions sharing the projected key are coalesced. Used whenever
- * the operation's keys are a subset of the partition keys, either the join
+ * the cluster keys are a subset of the partition keys, either the join
* keys of a storage-partitioned join or the `PARTITION BY` and grouping
* keys of a single-child operator. The name is historical, the projection
* is not join-specific.
- * @param expectedPartitionKeys Optional sequence of expected partition key values and their
- * split counts
- * @param reducers Optional reducers to apply to partition keys for grouping compatibility
+ * @param expectedKeyCount How many partition keys the planner expected, when it aligned this node
+ * to a merged key set. The keys themselves live in `grouping`, so this
+ * carries no second copy of them.
+ * @param reducers Optional reducers to apply to partition keys for grouping compatibility. Kept as
+ * reducers rather than as their display names. A name embeds the exprId of the
+ * attribute it transforms, so it would break canonical equality the same way the
+ * reducers do. See `doCanonicalize`.
* @param distributePartitions When true, splits for a key are distributed across the expected
* partitions (padding with empty partitions). When false, all splits
* are replicated to every expected partition for that key.
@@ -64,69 +83,48 @@ import org.apache.spark.sql.vectorized.ColumnarBatch
*/
case class GroupPartitionsExec(
child: SparkPlan,
- @transient joinKeyPositions: Option[Seq[Int]] = None,
- @transient expectedPartitionKeys: Option[Seq[(InternalRowComparableWrapper, Int)]] = None,
- @transient reducers: Option[Seq[Option[KeyReducer]]] = None,
- @transient distributePartitions: Boolean = false,
- @transient enableSortedMerge: Boolean = false
+ @transient grouping: PartitionGrouping,
+ plannedPartitioning: Partitioning,
+ childPartitioning: Partitioning,
+ @transient joinKeyPositions: Option[Seq[Int]],
+ @transient expectedKeyCount: Option[Int],
+ @transient reducers: Option[Seq[Option[KeyReducer]]],
+ @transient distributePartitions: Boolean,
+ @transient enableSortedMerge: Boolean
) extends UnaryExecNode {
- // A `lazy val` because the planner asks a node for its partitioning many times, and this body
- // rebuilds every `KeyedPartitioning` in the child's on top of the already memoized `grouping`.
- // Read no live config here, or memoizing would freeze it.
- @transient override lazy val outputPartitioning: Partitioning = {
- child.outputPartitioning match {
- case p: Partitioning with Expression =>
- // There can be multiple `KeyedPartitioning`s in an output partitioning of a join, but they
- // can only differ in `expressions`, since they share one `KeyLayout` (enforced by
- // `PartitioningCollection`). So the grouping is computed once, and the layout it describes
- // is shared by the members below.
- // When reducers are applied, the stored reduced expressions are re-targeted at each
- // `KeyedPartitioning`'s own key attribute and reported instead of the original ones. Their
- // data types match the reduced partition keys for the identity-vs-transform and
- // single-side-transform reducers; for the both-sides-reduce shape no single transform
- // describes the keys, so the reduce marks it (see `KeyedShuffleSpec.reducersBothWays`).
- //
- // A marked claim pins undeclared rows to hash(key) % numPartitions (see [[KeyLayout]]'s
- // `mayContainUnknownPartitionKeys`). Only an identity grouping keeps that relationship: a
- // reorder, a coalesce, or a resize moves those rows, and a projection or reduction rewrites
- // the keys the claim speaks for (see `identityGrouping`). Clearing only the marker would
- // misreport the undeclared rows that remain, so give up the keyed partitioning at the
- // physical output count (one per group, padding included) that a parent's
- // `PartitioningCollection` requires for uniformity. The give-up deliberately under-reports:
- // the node still physically groups the partitions but no longer claims a keyed layout, so a
- // join planned over it does not see its required distribution satisfied and a plan
- // containing it does not pass `ValidateRequirements`. `identityGrouping` is a lazy val, so
- // repeated `outputPartitioning` calls scan it at most once.
- if (PartitioningCollection.keyedMarkerOf(p).contains(true) && !identityGrouping) {
- UnknownPartitioning(grouping.partitions.size)
- } else {
- // One instance for every member, so they share it by reference. It already carries the
- // child's marker, and the guard above is what lets that carry over.
- val layout = grouping.layout
- p.transform {
- case k: KeyedPartitioning =>
- val projectedExpressions = joinKeyPositions.fold(k.expressions)(_.map(k.expressions))
- val effectiveExpressions = reducers match {
- case Some(exprs) =>
- assert(projectedExpressions.length == exprs.length)
- projectedExpressions.zip(exprs).map {
- case (expr, Some(KeyReducer(_, reduced))) =>
- // `reduced` came from the one member `checkKeyGroupCompatible` paired
- // this side on, which need not be the member being rewritten. The keys are
- // reduced once, from the shared key rows, so `reduced` describes them
- // whichever member this is, and only the key attribute is re-targeted.
- reduced.withReference(expr.references.head)
- case (expr, None) => expr
- }
- case None => projectedExpressions
- }
- KeyedPartitioning(effectiveExpressions, layout)
- }.asInstanceOf[Partitioning]
- }
- case o => o
+ /**
+ * The layout this node was planned to produce, but only while its child still reports the one it
+ * was planned over.
+ *
+ * A node is decided for one child partitioning: `grouping` indexes that child's partitions and
+ * `plannedPartitioning` rebuilds its keyed members on top of the grouping. A rule that hands this
+ * node a child reporting something else invalidates both, so the keyed claim is dropped and only
+ * the physical output count is reported. `ValidateRequirements` then finds the parent's
+ * distribution unsatisfied and `AdaptiveSparkPlanExec` reverts the rewrite, which is what an
+ * `AQEShuffleReadExec` landing over a keyed shuffle stage relies on. Only an `AQEShuffleReadRule`
+ * is validated that way, so `checkChildStillMatches` covers the rest at execution.
+ *
+ * Re-deriving instead would apply a recipe chosen for one pairing to a different child, yielding
+ * a claim nothing validated against the other side. It would also buy nothing today: no rule is
+ * known to report a *different* `KeyedPartitioning`, so the reachable outcomes are an equal one,
+ * where this check passes, and `UnknownPartitioning`, where re-deriving reports the same thing.
+ *
+ * The comparison is by reference for a child that reports the same object, which the columnar and
+ * codegen wrappers do. `PlanAdaptiveDynamicPruningFilters` rebuilds `BatchScanExec`, so there it
+ * compares the partition keys by value, and reads equal only while the connector returns the same
+ * input partitions for the same scan.
+ *
+ * Asked on the read rather than in `withNewChildInternal` because canonicalization rebuilds this
+ * node over a canonicalized child whose partitioning cannot be read at all: a canonicalized
+ * `BatchScanExec` throws from `reportedKeyedPartitioning`.
+ */
+ @transient override lazy val outputPartitioning: Partitioning =
+ if (child.outputPartitioning == childPartitioning) {
+ plannedPartitioning
+ } else {
+ UnknownPartitioning(grouping.partitions.size)
}
- }
override def doCanonicalize(): SparkPlan = {
// `KeyReducer` is a plain case class, not an `Expression`, so plan canonicalization does not
@@ -153,179 +151,17 @@ case class GroupPartitionsExec(
})
}
- /**
- * Aligns partitions based on `expectedPartitionKeys` and clustering mode.
- *
- * Returns the aligned groups, whether their keys ended up unique, and two counts, both in
- * input partition reads relative to the baseline of every input being read exactly once.
- * The pruned count is the reads that never happen: inputs of a key the alignment never
- * references. The join proved such keys cannot produce output, e.g. an inner join keeps
- * only the intersection. Which keys are expected is orthogonal to the mode: an
- * `OrderedDistribution` producer expects the child's own keys and so never prunes, while a
- * join producer can prune in either mode. The replicated count is the reads that happen
- * again: in the replicate mode of partial clustering every expected partition of a held key
- * re-reads all its splits, counted beyond the first pass (3 splits over 2 slots count 3).
- * Total input reads = `numInputPartitions` - pruned + replicated.
- */
- private def alignToExpectedKeys(
- keyMap: Map[InternalRowComparableWrapper, Seq[Int]],
- numInputPartitions: Int) = {
- var isGrouped = true
- var numReplicatedPartitionReads = 0
- // Splits the alignment references, accumulated over the expected keys. Every producer of
- // `expectedPartitionKeys` deduplicates the keys, so no split is counted twice here.
- var numMatchedPartitions = 0
- val alignedPartitions = expectedPartitionKeys.get.flatMap { case (key, numSplits) =>
- // Every producer derives the split counts from a `groupBy` size or the literal 1; a
- // non-positive count would emit a different partition count for the key than the other
- // side expects, breaking the pairing this alignment exists for.
- assert(numSplits > 0, s"expected partition key split count must be positive: $numSplits")
- if (numSplits > 1) isGrouped = false
- val splits = keyMap.getOrElse(key, Seq.empty)
- numMatchedPartitions += splits.size
- if (distributePartitions) {
- // Distribute splits across expected partitions, padding with empty sequences
- val paddedSplits = splits.map(Seq(_)).padTo(numSplits, Seq.empty)
- paddedSplits.map((key, _))
- } else {
- // The slots beyond the first re-read the whole group. A key this side does not hold
- // has no splits to re-read, so the product is 0 and no explicit guard is needed.
- numReplicatedPartitionReads += (numSplits - 1) * splits.size
- // Replicate all splits to each expected partition
- Seq.fill(numSplits)((key, splits))
- }
- }
- // The keyMap groups partition every input index, so the pruned inputs are the total minus
- // the matched.
- val numPrunedPartitions = numInputPartitions - numMatchedPartitions
- (alignedPartitions, isGrouped, numPrunedPartitions, numReplicatedPartitionReads)
- }
-
- /**
- * Groups and sorts partitions by their keys in ascending order. The sort must match
- * `KeyedPartitioning.toGrouped`, which is why both use
- * `KeyedPartitioning.groupedKeyRowOrdering` -- see its documentation for the contract.
- */
- private def groupAndSortByKeys(
- keyMap: Map[InternalRowComparableWrapper, Seq[Int]],
- dataTypes: Seq[DataType]) = {
- val keyOrdering = KeyedPartitioning.groupedKeyRowOrdering(dataTypes)
- keyMap.toSeq.sorted(keyOrdering.on((t: (InternalRowComparableWrapper, _)) => t._1.row))
- }
-
- /**
- * Computes the grouped partitions by:
- * 1. Projecting partition keys if joinKeyPositions is specified
- * 2. Reducing keys if reducers are specified
- * 3. Grouping input partition indices by their (possibly projected/reduced) keys
- * 4. Sorting or distributing based on whether partial clustering is enabled
- *
- * `isCollapsed` says whether the output stands for more than one of the child's partition keys.
- * Two things set it: the child's own flag, and a merge this node performs.
- */
- @transient private lazy val grouping: PartitionGrouping = {
- // There must be a `KeyedPartitioning` in the child's output partitioning, as a
- // `GroupPartitionsExec` node is added to a plan only in that case. Any member will do, see
- // `outputPartitioning` above.
- val childKp = child.outputPartitioning
- .asInstanceOf[Partitioning with Expression]
- .collectFirst { case k: KeyedPartitioning => k }
- .getOrElse(
- throw new SparkException("GroupPartitionsExec requires a child with KeyedPartitioning"))
-
- // Project partition keys if join key positions are specified
- val (projectedDataTypes, projectedKeys) =
- joinKeyPositions.fold(
- (childKp.keyDataTypes, childKp.partitionKeys)
- )(childKp.projectKeys)
-
- // Reduce keys if reducers are specified
- val (reducedDataTypes, reducedKeys) = reducers.fold((projectedDataTypes, projectedKeys))(
- KeyedPartitioning.reduceKeys(projectedKeys, projectedDataTypes, _))
-
- val keyToPartitionIndices = reducedKeys.zipWithIndex.groupMap(_._1)(_._2)
-
- val (partitions, isGrouped, numPrunedPartitions, numReplicatedPartitionReads) =
- if (expectedPartitionKeys.isDefined) {
- alignToExpectedKeys(keyToPartitionIndices, childKp.numPartitions)
- } else {
- (groupAndSortByKeys(keyToPartitionIndices, reducedDataTypes), true, 0, 0)
- }
-
- // Both cheap terms come first, so the scan below runs only where a merge is possible. A
- // grouping that left the keys as they are groups the child's own key values, and one of those
- // groups can only ever cover the one key it was built from.
- val keysChanged =
- joinKeyPositions.exists(_.length < childKp.expressions.length) || reducers.isDefined
- // `identityGrouping` asks the stronger question: a projection that only reorders the key
- // columns merges no key, but it still re-labels the groups into a different key space,
- // which no index alignment can undo. No producer of `joinKeyPositions` emits anything but
- // ascending positions today, so this only matters as defence in depth.
- val keysRewritten =
- joinKeyPositions.exists(_ != childKp.expressions.indices) || reducers.isDefined
- val isCollapsed = childKp.isCollapsed || keysChanged && {
- // The groups this node keeps are the ones that can merge keys of the child, and asking the
- // child's keys rather than its partitions is what tells such a merge from a source that
- // reports several splits per key.
- val keptGroups = expectedPartitionKeys match {
- case Some(expected) => expected.view.flatMap { case (key, _) =>
- keyToPartitionIndices.get(key)
- }
- case None => keyToPartitionIndices.values.view
- }
- val childKeys = childKp.partitionKeys.toArray
- keptGroups.exists { group =>
- val first = childKeys(group.head)
- group.tail.exists(childKeys(_) != first)
- }
- }
- // A `copy` of the child's layout rather than a fresh one, so the marker and anything the layout
- // grows later are carried without this having to name them. Built here, where the child is in
- // scope, so `outputPartitioning` has nothing left to re-apply.
- PartitionGrouping(
- partitions,
- childKp.layout.copy(
- partitionKeys = partitions.map(_._1),
- dataTypes = reducedDataTypes,
- isGrouped = isGrouped,
- isCollapsed = isCollapsed),
- keysRewritten, numPrunedPartitions, numReplicatedPartitionReads)
- }
-
- /**
- * Whether this node's grouping leaves the declared keys and every partition where they were:
- * no projection or reduction rewrote the keys, output partition i holds exactly input
- * partition i, and there is one output per input. That is the only grouping that keeps a
- * marked layout's undeclared rows at hash(key) % numPartitions. A projection or reduction
- * re-labels the groups into a different key space, so even a grouping whose indices line up
- * would pin the claim to keys it no longer declares; `keysRewritten` rejects it up front --
- * it covers a narrowing projection, a reordering one, and any reducer slot. A reducer slot
- * is treated as key-changing: a conforming self-reducer cannot rewrite a reachable key
- * value, so the give-up there loses at most an optimization. A grouping that drops trailing
- * declared keys still reads identity for every group it keeps, but the partition count
- * shrinks and the hash modulus with it. The `forall` stops at the first moved partition, so
- * a reorder or coalesce is rejected without a full scan.
- */
- @transient private lazy val identityGrouping: Boolean =
- !grouping.keysRewritten &&
- grouping.partitions.size == child.outputPartitioning.numPartitions &&
- grouping.partitions.iterator.zipWithIndex.forall {
- case ((_, Seq(single)), outputIndex) => single == outputIndex
- case _ => false
- }
-
- @transient lazy val groupedPartitions: Seq[(InternalRowComparableWrapper, Seq[Int])] =
- grouping.partitions
+ def groupedPartitions: Seq[(InternalRowComparableWrapper, Seq[Int])] = grouping.partitions
@transient private lazy val hasCoalescing: Boolean = groupedPartitions.exists(_._2.size > 1)
// All values are computed on the driver by `grouping`, so they are reported through
// `sendDriverMetrics` rather than task-side accumulators. Registration reads constructor
- // parameters only: replication needs an expected key with several slots, which the expected
- // keys themselves show. Pruning is registered over the whole alignment path; the ordering
- // producer expects the child's own keys and so never prunes, but no constructor parameter
- // separates it from the join producers that can. Coalescing can happen in any mode and
- // reports 0 when nothing merged.
+ // parameters only: replication needs an expected key with several slots, and the grouping's
+ // `isGrouped` is false exactly then. Pruning is registered over the whole alignment path; the
+ // ordering producer expects the child's own keys and so never prunes, but no constructor
+ // parameter separates it from the join producers that can. Coalescing can happen in any mode
+ // and reports 0 when nothing merged.
@transient override lazy val metrics: Map[String, SQLMetric] = Map(
"numInputPartitions" -> SQLMetrics.createMetric(sparkContext, "number of input partitions"),
"numPartitions" -> SQLMetrics.createMetric(sparkContext, "number of partitions"),
@@ -334,14 +170,14 @@ case class GroupPartitionsExec(
SQLMetrics.createMetric(sparkContext, "number of coalesced partitions"),
"maxPartitionsPerGroup" ->
SQLMetrics.createMetric(sparkContext, "max partitions per group")) ++ {
- if (expectedPartitionKeys.exists(_.exists(_._2 > 1)) && !distributePartitions) {
+ if (!grouping.isGrouped && !distributePartitions) {
Map("numReplicatedPartitionReads" -> SQLMetrics.createMetric(sparkContext,
"number of replicated input partition reads"))
} else {
Map.empty[String, SQLMetric]
}
} ++ {
- if (expectedPartitionKeys.isDefined) {
+ if (expectedKeyCount.isDefined) {
Map("numPrunedPartitions" ->
SQLMetrics.createMetric(sparkContext, "number of pruned input partitions"))
} else {
@@ -476,7 +312,24 @@ case class GroupPartitionsExec(
sparkContext, executionId, driverAccumUpdates.toSeq)
}
+ /**
+ * `grouping.partitions` indexes the child's partitions as of planning, so a child that no longer
+ * reports what this node was decided over would be coalesced on the wrong indices.
+ * `outputPartitioning` gives up its keyed claim in that case, which lets `ValidateRequirements`
+ * reject the plan, but only an `AQEShuffleReadRule`'s result is validated (see
+ * `AdaptiveSparkPlanExec.optimizeQueryStage`), so nothing catches a rewrite from any other rule.
+ * No rule is known to perform one; this makes the failure explicit rather than silent if one
+ * starts.
+ */
+ private def checkChildStillMatches(): Unit = {
+ if (child.outputPartitioning != childPartitioning) {
+ throw SparkException.internalError(
+ "GroupPartitionsExec's child no longer reports the partitioning it was planned over")
+ }
+ }
+
override protected def doExecute(): RDD[InternalRow] = {
+ checkChildStillMatches()
sendDriverMetrics()
if (groupedPartitions.isEmpty) {
sparkContext.emptyRDD
@@ -497,6 +350,7 @@ case class GroupPartitionsExec(
override def supportsColumnar: Boolean = child.supportsColumnar && !usesSortedMerge
override protected def doExecuteColumnar(): RDD[ColumnarBatch] = {
+ checkChildStillMatches()
sendDriverMetrics()
if (groupedPartitions.isEmpty) {
sparkContext.emptyRDD
@@ -561,34 +415,286 @@ case class GroupPartitionsExec(
val joinKeyStr = joinKeyPositions.map { p =>
s"JoinKeyPositions: ${truncatedString(p, "[", ", ", "]", joinKeyMaxFields)}"
}.iterator
- val expectedStr = expectedPartitionKeys.map(ks => s"ExpectedPartitionKeys: ${ks.size}")
+ val expectedStr = expectedKeyCount.map(n => s"ExpectedPartitionKeys: $n")
val reducersStr = reducers.map { seq =>
val names = seq.map(_.map(_.reducer.displayName()).getOrElse("identity"))
s"Reducers: ${truncatedString(names, "[", ", ", "]", joinKeyMaxFields)}"
}
val distributeStr = Iterator(s"DistributePartitions: $distributePartitions")
- // Rendered from the constructor field, as `DistributePartitions` above is. Not from
- // `usesSortedMerge`, because that forces `grouping`, which can throw, and this method feeds
- // `simpleString`, which `treeString` calls on error paths.
+ // Rendered from the constructor field, as `DistributePartitions` above is, and not from
+ // `usesSortedMerge`, which reads the child's ordering. This method feeds `simpleString`, which
+ // `treeString` calls on error paths, so it stays on what the node was built with.
val sortedMergeStr = Iterator(s"SortedMerge: $enableSortedMerge")
joinKeyStr ++ expectedStr ++ reducersStr ++ distributeStr ++ sortedMergeStr
}
}
/**
- * What a [[GroupPartitionsExec]] computes once and reports from several members: which of the
- * child's partitions each of its own is built from, and the layout that describes them. Every
- * member is given the same `layout` instance, which is what
- * `PartitioningCollection.fromPartitionings` needs to return them untouched. The last two fields
- * count the alignment's effect on the reads of the child's splits (see `alignToExpectedKeys`), and
- * are 0 outside the alignment path.
+ * What a [[GroupPartitionsExec]] does to its child's partitions.
+ *
+ * @param partitions the index groups the node emits, each with the key it stands for
+ * @param layout what the node reports about those groups. Every member of a
+ * [[PartitioningCollection]] is given this same instance, which is what
+ * `PartitioningCollection.fromPartitionings` needs to return them untouched.
+ * @param isIdentity whether the grouping leaves the declared keys and every partition where they
+ * were. Nothing rewrote the keys, output partition i holds exactly input
+ * partition i, and there is one output per input. That is the only grouping that
+ * keeps a marked layout's undeclared rows at hash(key) % numPartitions, so a
+ * projection, a reduction or a dropped trailing key all fail it: each moves the
+ * claim into a different key space or changes the modulus. A reducer slot counts
+ * as key-changing even where a conforming self-reducer could not rewrite a
+ * reachable key value, so the give-up there loses at most an optimization.
+ * @param numPrunedPartitions the alignment's effect on the reads of the child's splits, 0 outside
+ * the alignment path. See `alignToExpectedKeys`.
+ * @param numReplicatedPartitionReads as above.
*/
-private case class PartitionGrouping(
+private[sql] case class PartitionGrouping(
partitions: Seq[(InternalRowComparableWrapper, Seq[Int])],
layout: KeyLayout,
- keysRewritten: Boolean,
+ isIdentity: Boolean,
numPrunedPartitions: Int,
- numReplicatedPartitionReads: Int)
+ numReplicatedPartitionReads: Int) {
+
+ def isGrouped: Boolean = layout.isGrouped
+}
+
+private[sql] object GroupPartitionsExec {
+
+ /**
+ * Builds a node over `child`, deriving `grouping` and `plannedPartitioning` from the parameters.
+ *
+ * **Both are derived, and neither `copy` nor the generated `apply` re-derives them**, so a change
+ * to `child`, `joinKeyPositions`, `expectedPartitionKeys` (stored as `expectedKeyCount`),
+ * `reducers` or `distributePartitions` has to come back through here. `enableSortedMerge` is not
+ * an input to either, which is why `tryEnableSortedMerge` may `copy` it.
+ *
+ * Two other `copy` calls in this file are deliberate. `withNewChildInternal` carries both fields
+ * over a child rewrite, and a child that turns out to report something else is what
+ * `outputPartitioning` answers for, so the carried pair is never reported as if it still held.
+ * And `doCanonicalize` rewrites `reducers` on what `super.doCanonicalize()` returned, which has
+ * already normalized the exprIds in both partitioning fields, and the rewrite touches neither.
+ */
+ def apply(
+ child: SparkPlan,
+ joinKeyPositions: Option[Seq[Int]] = None,
+ expectedPartitionKeys: Option[Seq[(InternalRowComparableWrapper, Int)]] = None,
+ reducers: Option[Seq[Option[KeyReducer]]] = None,
+ distributePartitions: Boolean = false,
+ enableSortedMerge: Boolean = false): GroupPartitionsExec = {
+ // There must be a `KeyedPartitioning` in the child's output partitioning, as a
+ // `GroupPartitionsExec` node is added to a plan only in that case.
+ val childPartitioning = child.outputPartitioning
+ // Any member will do, see `computeOutputPartitioning`.
+ val childKp = PartitioningCollection.representativeOf(childPartitioning).getOrElse(
+ throw new SparkException("GroupPartitionsExec requires a child with KeyedPartitioning"))
+ // `representativeOf` found one, so the partitioning is an expression tree.
+ val childExpr = childPartitioning.asInstanceOf[Partitioning with Expression]
+ val grouping = computeGrouping(
+ childKp, joinKeyPositions, expectedPartitionKeys, reducers, distributePartitions)
+ GroupPartitionsExec(child, grouping,
+ computeOutputPartitioning(childExpr, grouping, joinKeyPositions, reducers), childPartitioning,
+ joinKeyPositions, expectedPartitionKeys.map(_.size), reducers, distributePartitions,
+ enableSortedMerge)
+ }
+
+ /**
+ * What a node with this `grouping` over `child` reports. Derived once, at planning time, because
+ * this rebuilds every `KeyedPartitioning` of the child's on top of the grouping, and the planner
+ * asks a node for its partitioning many times. Reads no live config, or storing it would freeze
+ * one.
+ */
+ private def computeOutputPartitioning(
+ p: Partitioning with Expression,
+ grouping: PartitionGrouping,
+ joinKeyPositions: Option[Seq[Int]],
+ reducers: Option[Seq[Option[KeyReducer]]]): Partitioning = {
+ // There can be multiple `KeyedPartitioning`s in an output partitioning of a join, but they
+ // can only differ in `expressions`, since they share one `KeyLayout` (enforced by
+ // `PartitioningCollection`). So the grouping is computed once, and the layout it describes
+ // is shared by the members below.
+ // When reducers are applied, the stored reduced expressions are re-targeted at each
+ // `KeyedPartitioning`'s own key attribute and reported instead of the original ones. Their
+ // data types match the reduced partition keys for the identity-vs-transform and
+ // single-side-transform reducers; for the both-sides-reduce shape no single transform
+ // describes the keys, so the reduce marks it (see `KeyedShuffleSpec.reducersBothWays`).
+ //
+ // A marked claim pins undeclared rows to hash(key) % numPartitions (see [[KeyLayout]]'s
+ // `mayContainUnknownPartitionKeys`), and only an identity grouping keeps that relationship (see
+ // `PartitionGrouping.isIdentity`). Clearing the marker alone would misreport the undeclared
+ // rows that remain, so the keyed partitioning goes and only the physical output count is
+ // reported, one per group with padding included, which is the count a parent's
+ // `PartitioningCollection` needs for uniformity. `EnsureRequirements` asks this before it
+ // commits to a pairing and falls back to a shuffle when it happens.
+ //
+ // The marker read off `p` is the same bit the `else` branch publishes through
+ // `grouping.layout`, since `computeGrouping` copies the child's layout without touching it. A
+ // change to that copy has to move this guard with it.
+ if (PartitioningCollection.keyedMarkerOf(p).contains(true) && !grouping.isIdentity) {
+ UnknownPartitioning(grouping.partitions.size)
+ } else {
+ // One instance for every member, so they share it by reference. It already carries the
+ // child's marker, and the guard above is what lets that carry over.
+ val layout = grouping.layout
+ p.transform {
+ case k: KeyedPartitioning =>
+ val projectedExpressions = joinKeyPositions.fold(k.expressions)(_.map(k.expressions))
+ val effectiveExpressions = reducers match {
+ case Some(exprs) =>
+ assert(projectedExpressions.length == exprs.length)
+ projectedExpressions.zip(exprs).map {
+ case (expr, Some(KeyReducer(_, reduced))) =>
+ // `reduced` came from the one member `checkKeyGroupCompatible` paired
+ // this side on, which need not be the member being rewritten. The keys are
+ // reduced once, from the shared key rows, so `reduced` describes them
+ // whichever member this is, and only the key attribute is re-targeted.
+ reduced.withReference(expr.references.head)
+ case (expr, None) => expr
+ }
+ case None => projectedExpressions
+ }
+ KeyedPartitioning(effectiveExpressions, layout)
+ }.asInstanceOf[Partitioning]
+ }
+ }
+
+ /**
+ * Aligns partitions based on `expectedPartitionKeys` and clustering mode.
+ *
+ * Returns the aligned groups, whether their keys ended up unique, and two counts, both in
+ * input partition reads relative to the baseline of every input being read exactly once.
+ * The pruned count is the reads that never happen: inputs of a key the alignment never
+ * references. The join proved such keys cannot produce output, e.g. an inner join keeps
+ * only the intersection. Which keys are expected is orthogonal to the mode: an
+ * `OrderedDistribution` producer expects the child's own keys and so never prunes, while a
+ * join producer can prune in either mode. The replicated count is the reads that happen
+ * again: in the replicate mode of partial clustering every expected partition of a held key
+ * re-reads all its splits, counted beyond the first pass (3 splits over 2 slots count 3).
+ * Total input reads = `numInputPartitions` - pruned + replicated.
+ */
+ private def alignToExpectedKeys(
+ keyMap: Map[InternalRowComparableWrapper, Seq[Int]],
+ expectedPartitionKeys: Seq[(InternalRowComparableWrapper, Int)],
+ distributePartitions: Boolean,
+ numInputPartitions: Int) = {
+ var isGrouped = true
+ var numReplicatedPartitionReads = 0
+ // Splits the alignment references, accumulated over the expected keys. Every producer of
+ // `expectedPartitionKeys` deduplicates the keys, so no split is counted twice here.
+ var numMatchedPartitions = 0
+ val alignedPartitions = expectedPartitionKeys.flatMap { case (key, numSplits) =>
+ // Every producer derives the split counts from a `groupBy` size or the literal 1; a
+ // non-positive count would emit a different partition count for the key than the other
+ // side expects, breaking the pairing this alignment exists for.
+ assert(numSplits > 0, s"expected partition key split count must be positive: $numSplits")
+ if (numSplits > 1) isGrouped = false
+ val splits = keyMap.getOrElse(key, Seq.empty)
+ numMatchedPartitions += splits.size
+ if (distributePartitions) {
+ // Distribute splits across expected partitions, padding with empty sequences
+ val paddedSplits = splits.map(Seq(_)).padTo(numSplits, Seq.empty)
+ paddedSplits.map((key, _))
+ } else {
+ // The slots beyond the first re-read the whole group. A key this side does not hold
+ // has no splits to re-read, so the product is 0 and no explicit guard is needed.
+ numReplicatedPartitionReads += (numSplits - 1) * splits.size
+ // Replicate all splits to each expected partition
+ Seq.fill(numSplits)((key, splits))
+ }
+ }
+ // The keyMap's groups partition the input indices between them, so the pruned inputs are the
+ // total minus the matched.
+ val numPrunedPartitions = numInputPartitions - numMatchedPartitions
+ (alignedPartitions, isGrouped, numPrunedPartitions, numReplicatedPartitionReads)
+ }
+
+ /**
+ * Computes the grouped partitions by:
+ * 1. Projecting partition keys if joinKeyPositions is specified
+ * 2. Reducing keys if reducers are specified
+ * 3. Grouping input partition indices by their (possibly projected/reduced) keys
+ * 4. Sorting or distributing based on whether partial clustering is enabled
+ *
+ * `isCollapsed` says whether the output stands for more than one of the child's partition keys.
+ * Two things set it: the child's own flag, and a merge this node performs.
+ */
+ private def computeGrouping(
+ childKp: KeyedPartitioning,
+ joinKeyPositions: Option[Seq[Int]],
+ expectedPartitionKeys: Option[Seq[(InternalRowComparableWrapper, Int)]],
+ reducers: Option[Seq[Option[KeyReducer]]],
+ distributePartitions: Boolean): PartitionGrouping = {
+ // Project partition keys if join key positions are specified
+ val (projectedDataTypes, projectedKeys) =
+ joinKeyPositions.fold(
+ (childKp.keyDataTypes, childKp.partitionKeys)
+ )(childKp.projectKeys)
+
+ // Reduce keys if reducers are specified
+ val (reducedDataTypes, reducedKeys) = reducers.fold((projectedDataTypes, projectedKeys))(
+ KeyedPartitioning.reduceKeys(projectedKeys, projectedDataTypes, _))
+
+ val keyToPartitionIndices = reducedKeys.zipWithIndex.groupMap(_._1)(_._2)
+
+ val (partitions, isGrouped, numPrunedPartitions, numReplicatedPartitionReads) =
+ expectedPartitionKeys match {
+ case Some(expected) =>
+ alignToExpectedKeys(
+ keyToPartitionIndices, expected, distributePartitions, childKp.numPartitions)
+ case None =>
+ // Ascending by key. The sort must match `KeyedPartitioning.toGrouped`, which is why both
+ // go through `KeyedPartitioning.groupedKeyRowOrdering`, whose documentation holds the
+ // contract.
+ val keyOrdering = KeyedPartitioning.groupedKeyRowOrdering(reducedDataTypes)
+ val sorted = keyToPartitionIndices.toSeq
+ .sorted(keyOrdering.on((t: (InternalRowComparableWrapper, _)) => t._1.row))
+ (sorted, true, 0, 0)
+ }
+
+ // A projection that only reorders the key columns merges no key, but it still re-labels the
+ // groups into a different key space, which no index alignment can undo, so `isIdentity` reads
+ // this rather than the narrower "dropped a position" test. No producer of `joinKeyPositions`
+ // emits anything but ascending positions today, so the difference is defence in depth. The
+ // cheap term also gates the scan below: a grouping that left the keys as they are groups the
+ // child's own key values, and one of those groups can only ever cover the one key it was built
+ // from.
+ val keysRewritten =
+ joinKeyPositions.exists(_ != childKp.expressions.indices) || reducers.isDefined
+ val isCollapsed = childKp.isCollapsed || keysRewritten && {
+ // The groups this node keeps are the ones that can merge keys of the child, and asking the
+ // child's keys rather than its partitions is what tells such a merge from a source that
+ // reports several splits per key.
+ val keptGroups = expectedPartitionKeys match {
+ case Some(expected) => expected.view.flatMap { case (key, _) =>
+ keyToPartitionIndices.get(key)
+ }
+ case None => keyToPartitionIndices.values.view
+ }
+ val childKeys = childKp.partitionKeys.toArray
+ keptGroups.exists { group =>
+ val first = childKeys(group.head)
+ group.tail.exists(childKeys(_) != first)
+ }
+ }
+ // The `forall` stops at the first moved partition, so a reorder or a coalesce is rejected
+ // without a full scan, and the two cheap terms come before it.
+ val isIdentity = !keysRewritten && partitions.size == childKp.numPartitions &&
+ partitions.iterator.zipWithIndex.forall {
+ case ((_, Seq(single)), outputIndex) => single == outputIndex
+ case _ => false
+ }
+ // A `copy` of the child's layout rather than a fresh one, so the marker and anything the layout
+ // grows later are carried without this having to name them. Built here, where the child is in
+ // scope, so `computeOutputPartitioning` has nothing left to re-apply.
+ PartitionGrouping(
+ partitions,
+ childKp.layout.copy(
+ partitionKeys = partitions.map(_._1),
+ dataTypes = reducedDataTypes,
+ isGrouped = isGrouped,
+ isCollapsed = isCollapsed),
+ isIdentity, numPrunedPartitions, numReplicatedPartitionReads)
+ }
+}
/**
* A PartitionCoalescer that groups partitions according to a pre-computed grouping plan.
diff --git a/sql/core/src/main/scala/org/apache/spark/sql/execution/exchange/EnsureRequirements.scala b/sql/core/src/main/scala/org/apache/spark/sql/execution/exchange/EnsureRequirements.scala
index a23d85883496..96186699bc2c 100644
--- a/sql/core/src/main/scala/org/apache/spark/sql/execution/exchange/EnsureRequirements.scala
+++ b/sql/core/src/main/scala/org/apache/spark/sql/execution/exchange/EnsureRequirements.scala
@@ -70,250 +70,37 @@ case class EnsureRequirements(
shuffleOrigin: ShuffleOrigin): Seq[SparkPlan] = {
assert(requiredChildDistributions.length == originalChildren.length)
assert(requiredChildOrderings.length == originalChildren.length)
- // Get the indexes of children which have specified distribution requirements and need to be
- // co-partitioned.
- val childrenIndexes = requiredChildDistributions.zipWithIndex.filter {
- case (_: ClusteredDistribution, _) => true
- case _ => false
- }.map(_._2)
- // A co-partitioning operator gets its projected-key `GroupPartitionsExec` from the multi-child
- // block below, not from here. See `clusterKeyPositions`.
- val isCoPartitioned = childrenIndexes.length > 1
- // Ensure that the operator's children satisfy their output distribution requirements.
- var children = originalChildren.zip(requiredChildDistributions).map {
- case (child, distribution) =>
- // Ask what the child's partitioning still needs to satisfy the distribution
- val (otherSatisfies, keyed) =
- splitKeyedPartitionings(child.outputPartitioning, distribution, isCoPartitioned)
-
- // If a non-KeyedPartitioning already satisfies, no changes needed
- if (otherSatisfies) {
- child
- } else {
- keyed match {
- case Some(resolution) =>
- (distribution, resolution) match {
- case (o: OrderedDistribution, _) =>
- // OrderedDistribution requires grouped KeyedPartitioning with sorted keys
- // according to the distribution's ordering.
- val satisfyingKeyedPartitioning = resolution.fold(identity, _._1)
- // The single-column invariant in KeyedPartitioning.supportsExpressions guarantees
- // one attribute per partition expression.
- val attrs = satisfyingKeyedPartitioning.expressions.flatMap(_.references)
- val keyRowOrdering = RowOrdering.create(o.ordering, attrs)
- val keyOrdering = keyRowOrdering.on((t: InternalRowComparableWrapper) => t.row)
- val keys = satisfyingKeyedPartitioning.partitionKeys
- // An empty zip is vacuously sorted, which is the answer for a single key.
- if (keys.zip(keys.drop(1)).forall { case (k1, k2) => keyOrdering.lteq(k1, k2) }) {
- child
- } else {
- // Use distributePartitions to spread splits across expected partitions
- val sortedGroupedKeys = keys
- .groupBy(identity).view.mapValues(_.size)
- .toSeq.sortBy(_._1)(keyOrdering)
- GroupPartitionsExec(child,
- expectedPartitionKeys = Some(sortedGroupedKeys),
- distributePartitions = true
- )
- }
-
- // A KeyedPartitioning satisfies the distribution and a node would change nothing
- case (_, scala.Left(_)) =>
- child
-
- // A KeyedPartitioning satisfies the distribution only after a GroupPartitionsExec:
- // to coalesce duplicate partition keys, to project the partition keys down to the
- // operation keys, or both. The positions to project to come from whichever member
- // of the child's partitioning leaves the most partitions.
- case (_, scala.Right((_, positions))) =>
- GroupPartitionsExec(child, joinKeyPositions = positions)
- }
- case None =>
- // No partitioning satisfies - need broadcast or shuffle
- val numPartitions = distribution.requiredNumPartitions
- .getOrElse(conf.numShufflePartitions)
- distribution match {
- case BroadcastDistribution(mode) =>
- BroadcastExchangeExec(mode, child)
- case _: StatefulOpClusteredDistribution =>
- ShuffleExchangeExec(
- distribution.createPartitioning(numPartitions), child,
- REQUIRED_BY_STATEFUL_OPERATOR)
- case _ =>
- ShuffleExchangeExec(
- distribution.createPartitioning(numPartitions), child, shuffleOrigin)
- }
- }
- }
+ // What each child has to satisfy to line up with its siblings, in child order, and nothing for
+ // a child that answers for itself. Only a `ClusteredDistribution` asks to be co-partitioned,
+ // and only against another one, so a lone clustered child is not in here either: it stands
+ // alone like a child that wants a broadcast or nothing.
+ val clustered = requiredChildDistributions.map {
+ case required: ClusteredDistribution => Some(required)
+ case _ => None
}
-
- // Special case: if all sides of the join are single partition and it's physical size less than
- // or equal spark.sql.maxSinglePartitionBytes.
- val preferSinglePartition = childrenIndexes.forall { i =>
- children(i).outputPartitioning == SinglePartition &&
- children(i).logicalLink
- .forall(_.stats.sizeInBytes <= conf.getConf(SQLConf.MAX_SINGLE_PARTITION_BYTES))
+ val isCoPartitioned = clustered.count(_.isDefined) > 1
+ val coPartitioned: Seq[Option[ClusteredDistribution]] =
+ if (isCoPartitioned) clustered else Seq.fill(clustered.length)(None)
+
+ // Two paths, kept apart. A child that has to line up with another cannot be resolved on its
+ // own. Whether it needs a `GroupPartitionsExec`, and on which keys, depends on what the other
+ // side turns out to offer. So this loop resolves only the children that answer for themselves,
+ // and `coPartitionChildren` owns the rest end to end.
+ val resolved = originalChildren.lazyZip(requiredChildDistributions).lazyZip(coPartitioned).map {
+ case (child, _, Some(_)) => child
+ case (child, distribution, None) =>
+ resolveChild(child, distribution, shuffleOrigin)
}
- // If there are more than one children, we'll need to check partitioning & distribution of them
- // and see if extra shuffles are necessary.
- if (childrenIndexes.length > 1 && !preferSinglePartition) {
- val specs = childrenIndexes.map(i => {
- val requiredDist = requiredChildDistributions(i)
- assert(requiredDist.isInstanceOf[ClusteredDistribution],
- s"Expected ClusteredDistribution but found ${requiredDist.getClass.getSimpleName}")
- i -> children(i).outputPartitioning.createShuffleSpec(
- requiredDist.asInstanceOf[ClusteredDistribution])
- }).toMap
-
- // Find out the shuffle spec that gives better parallelism. Currently this is done by
- // picking the spec with the largest number of partitions.
- //
- // NOTE: this is not optimal for the case when there are more than 2 children. Consider:
- // (10, 10, 11)
- // where the number represent the number of partitions for each child, it's better to pick 10
- // here since we only need to shuffle one side - we'd need to shuffle two sides if we pick 11.
- //
- // However this should be sufficient for now since in Spark nodes with multiple children
- // always have exactly 2 children.
-
- // Whether we should consider `spark.sql.shuffle.partitions` and ensure enough parallelism
- // during shuffle. To achieve a good trade-off between parallelism and shuffle cost, we only
- // consider the minimum parallelism iff ALL children need to be re-shuffled.
- //
- // A child needs to be re-shuffled iff either one of below is true:
- // 1. It can't create partitioning by itself, i.e., `canCreatePartitioning` returns false
- // (as for the case of `RangePartitioning`), therefore it needs to be re-shuffled
- // according to other shuffle spec.
- // 2. It already has `ShuffleExchangeLike`, so we can re-use existing shuffle without
- // introducing extra shuffle.
- //
- // On the other hand, in scenarios such as:
- // HashPartitioning(5) <-> HashPartitioning(6)
- // while `spark.sql.shuffle.partitions` is 10, we'll only re-shuffle the left side and make it
- // HashPartitioning(6).
- val shouldConsiderMinParallelism = specs.forall(p =>
- !p._2.canCreatePartitioning || children(p._1).isInstanceOf[ShuffleExchangeLike]
- )
- // Choose all the specs that can be used to shuffle other children
- val candidateSpecs = specs.filter { case (index, spec) =>
- spec.canCreatePartitioning &&
- (!shouldConsiderMinParallelism ||
- children(index).outputPartitioning.numPartitions >= conf.defaultNumShufflePartitions)
- }
- val bestSpecOpt = if (candidateSpecs.isEmpty) {
- None
- } else {
- // When choosing specs, we should consider those children with no `ShuffleExchangeLike` node
- // first. For instance, if we have:
- // A: (No_Exchange, 100) <---> B: (Exchange, 120)
- // it's better to pick A and change B to (Exchange, 100) instead of picking B and insert a
- // new shuffle for A.
- val candidateSpecsWithoutShuffle = candidateSpecs.filter { case (k, _) =>
- !children(k).isInstanceOf[ShuffleExchangeLike]
- }
- val finalCandidateSpecs = if (candidateSpecsWithoutShuffle.nonEmpty) {
- candidateSpecsWithoutShuffle
- } else {
- candidateSpecs
- }
- // Pick the spec with the best parallelism. For a collection that is the best any member
- // offers, since reading one member's count would depend on the enumeration order.
- Some(finalCandidateSpecs.values.maxBy(_.flatten.map(_.numPartitions).max))
- }
-
- // Check if the following conditions are satisfied:
- // 1. There are exactly two children (e.g., join). Note that Spark doesn't support
- // multi-way join at the moment, so this check should be sufficient.
- // 2. All children are of the compatible key group partitioning or
- // compatible shuffle partition id pass through partitioning
- // If both are true, skip shuffle.
- val areChildrenCompatible = parent.isDefined &&
- children.length == 2 && childrenIndexes.length == 2 && {
- val left = children.head
- val right = children(1)
-
- // key group compatibility check
- val newChildren = checkKeyGroupCompatible(
- parent.get, left, right, requiredChildDistributions)
- if (newChildren.isDefined) {
- children = newChildren.get
- true
- } else {
- // If key group check fails, check ShufflePartitionIdPassThrough compatibility
- checkShufflePartitionIdPassThroughCompatible(
- left, right, requiredChildDistributions)
- }
- }
-
- // A `ShuffleSpecCollection` answers `isCompatibleWith` if *any* of its members does, so the
- // collection alone does not say which member the sides agreed on. The projection pushed into
- // a compatible child and the partitioning built for a re-shuffled child both have to come
- // from one member, otherwise the sides end up grouped on different keys, or on a key set the
- // child does not even have. Pick that member once, preferring the finest when several
- // qualify. Only the branch that shuffles a child reads these, hence `lazy`.
- lazy val matchedIndexes = bestSpecOpt.toSeq.flatMap { best =>
- childrenIndexes.filter(i => best.isCompatibleWith(specs(i)))
- }
- lazy val bestMemberOpt = bestSpecOpt.flatMap { best =>
- val matchedMembers = matchedIndexes.map(i => specs(i).flatten)
- // No member serving every matched child means there is no layout to align them on, so they
- // all take the ordinary shuffle. That needs three or more clustered children, since with
- // two the member that reported the match serves both, and no operator has three today.
- best.flatten
- .filter(m => matchedMembers.forall(_.exists(m.isCompatibleWith)))
- .maxByOption(_.numPartitions)
- }
-
- children = children.zip(requiredChildDistributions).zipWithIndex.map {
- case ((child, _), idx) if areChildrenCompatible ||
- !childrenIndexes.contains(idx) =>
- child
- case ((child, dist), idx) =>
- if (bestMemberOpt.isDefined && matchedIndexes.contains(idx)) {
- // The positions come from this child's own matching member, since they index into its
- // own partition expressions -- the chosen best member only says which member of it the
- // two sides agreed on.
- val bestMember = bestMemberOpt.get
- specs(idx).flatten.find(bestMember.isCompatibleWith) match {
- // If `areChildrenCompatible` is false, we can still perform SPJ
- // by shuffling the other side based on join keys (see the else case below).
- // Hence we need to ensure that after this call, the outputPartitioning of the
- // partitioned side's BatchScanExec is grouped by join keys to match,
- // and we do that by pushing down the join keys
- case Some(KeyedShuffleSpec(_, _, Some(joinKeyPositions))) =>
- withJoinKeyPositions(child, joinKeyPositions)
- case _ => child
- }
- } else {
- val newPartitioning = bestMemberOpt.map { bestMember =>
- // Use the best spec to create a new partitioning to re-shuffle this child
- val clustering = dist.asInstanceOf[ClusteredDistribution].clustering
- bestMember.createPartitioning(clustering)
- }.getOrElse {
- // No best spec available, so we create default partitioning from the required
- // distribution
- val numPartitions = dist.requiredNumPartitions
- .getOrElse(conf.numShufflePartitions)
- dist.createPartitioning(numPartitions)
- }
-
- child match {
- case s: ShuffleExchangeExec =>
- s.copy(outputPartitioning = newPartitioning)
- case gpe: GroupPartitionsExec =>
- // Strip every grouping this rule inserted (they can stack on a re-run): a
- // replicating one repeats every row, so none of them may feed the shuffle.
- ShuffleExchangeExec(newPartitioning, unwrapGroupPartitions(gpe))
- case _ => ShuffleExchangeExec(newPartitioning, child)
- }
- }
- }
+ val distributed = if (isCoPartitioned) {
+ coPartitionChildren(parent, resolved, coPartitioned, shuffleOrigin)
+ } else {
+ resolved
}
// Now that we've performed any necessary shuffles, add sorts to guarantee output orderings:
- children = children.zip(requiredChildOrderings).map { case (child, requiredOrdering) =>
+ distributed.zip(requiredChildOrderings).map { case (child, requiredOrdering) =>
// If child.outputOrdering already satisfies the requiredOrdering, we do not need to sort.
if (SortOrder.orderingSatisfies(child.outputOrdering, requiredOrdering)) {
child
@@ -327,8 +114,307 @@ case class EnsureRequirements(
.getOrElse(SortExec(requiredOrdering, global = false, child = child))
}
}
+ }
+
+ /**
+ * What `child` needs to satisfy `distribution` on its own: nothing, a [[GroupPartitionsExec]], a
+ * broadcast, or a shuffle.
+ */
+ private def resolveChild(
+ child: SparkPlan,
+ distribution: Distribution,
+ shuffleOrigin: ShuffleOrigin): SparkPlan = {
+ // Ask what the child's partitioning still needs to satisfy the distribution
+ val (otherSatisfies, keyed) =
+ splitKeyedPartitionings(child.outputPartitioning, distribution)
+
+ // If a non-KeyedPartitioning already satisfies, no changes needed
+ if (otherSatisfies) {
+ child
+ } else {
+ keyed match {
+ case Some(resolution) =>
+ (distribution, resolution) match {
+ case (o: OrderedDistribution, _) =>
+ // OrderedDistribution requires grouped KeyedPartitioning with sorted keys
+ // according to the distribution's ordering.
+ val satisfyingKeyedPartitioning = resolution.fold(identity, _._1)
+ // The single-column invariant in KeyedPartitioning.supportsExpressions guarantees
+ // one attribute per partition expression.
+ val attrs = satisfyingKeyedPartitioning.expressions.flatMap(_.references)
+ val keyRowOrdering = RowOrdering.create(o.ordering, attrs)
+ val keyOrdering = keyRowOrdering.on((t: InternalRowComparableWrapper) => t.row)
+ val keys = satisfyingKeyedPartitioning.partitionKeys
+ // An empty zip is vacuously sorted, which is the answer for a single key.
+ if (keys.zip(keys.drop(1)).forall { case (k1, k2) => keyOrdering.lteq(k1, k2) }) {
+ child
+ } else {
+ // Use distributePartitions to spread splits across expected partitions
+ val sortedGroupedKeys = keys
+ .groupBy(identity).view.mapValues(_.size)
+ .toSeq.sortBy(_._1)(keyOrdering)
+ GroupPartitionsExec(child,
+ expectedPartitionKeys = Some(sortedGroupedKeys),
+ distributePartitions = true
+ )
+ }
+
+ // A KeyedPartitioning satisfies the distribution and a node would change nothing
+ case (_, scala.Left(_)) =>
+ child
+
+ // A KeyedPartitioning satisfies the distribution only after a GroupPartitionsExec:
+ // to coalesce duplicate partition keys, to project the partition keys down to the
+ // cluster keys, or both. The positions to project to come from whichever member
+ // of the child's partitioning leaves the most partitions.
+ case (_, scala.Right((_, positions))) =>
+ GroupPartitionsExec(child, joinKeyPositions = positions)
+ }
- children
+ case None =>
+ // No partitioning satisfies - need broadcast or shuffle
+ val numPartitions = distribution.requiredNumPartitions
+ .getOrElse(conf.numShufflePartitions)
+ distribution match {
+ case BroadcastDistribution(mode) =>
+ BroadcastExchangeExec(mode, child)
+ case _: StatefulOpClusteredDistribution =>
+ ShuffleExchangeExec(
+ distribution.createPartitioning(numPartitions), child,
+ REQUIRED_BY_STATEFUL_OPERATOR)
+ case _ =>
+ ShuffleExchangeExec(
+ distribution.createPartitioning(numPartitions), child, shuffleOrigin)
+ }
+ }
+ }
+ }
+
+ /**
+ * Resolves each co-partitioned child on its own, which is what is left once nothing is arranged
+ * between them.
+ */
+ private def resolveEachChild(
+ children: Seq[SparkPlan],
+ coPartitioned: Seq[Option[ClusteredDistribution]],
+ shuffleOrigin: ShuffleOrigin): Seq[SparkPlan] = children.zip(coPartitioned).map {
+ case (child, required) => required.fold(child)(resolveChild(child, _, shuffleOrigin))
+ }
+
+ /**
+ * Decides the children an operator co-partitions, together, because neither side's answer stands
+ * on its own.
+ *
+ * Three shapes need nothing arranged between the children, and every one of them still resolves
+ * each child on its own: a child can owe its distribution a [[GroupPartitionsExec]] or a
+ * partition count whether or not it lines up with its siblings.
+ * 1. Every side is a single small partition, so they line up whatever they hold.
+ * 2. The sources report layouts a storage-partitioned join can align, which
+ * `checkKeyGroupCompatible` decides and builds end to end.
+ * 3. Both sides pass shuffle partition ids through, on compatible specs.
+ *
+ * Failing all three, `shuffleToCoPartition` shuffles whichever children are not aligned onto one
+ * that is.
+ */
+ private def coPartitionChildren(
+ parent: Option[SparkPlan],
+ children: Seq[SparkPlan],
+ coPartitioned: Seq[Option[ClusteredDistribution]],
+ shuffleOrigin: ShuffleOrigin): Seq[SparkPlan] = {
+ // Every way of lining the children up as they are still needs this, and only the shuffle below
+ // reads more than it, hence `lazy`: the storage-partitioned join plans from the children as
+ // their sources report them, so when it succeeds nothing here is asked for.
+ lazy val resolved = resolveEachChild(children, coPartitioned, shuffleOrigin)
+
+ // Special case: if all sides of the join are single partition and their physical size is at
+ // most spark.sql.maxSinglePartitionBytes.
+ val preferSinglePartition = children.zip(coPartitioned).forall {
+ case (child, Some(_)) =>
+ child.outputPartitioning == SinglePartition &&
+ child.logicalLink
+ .forall(_.stats.sizeInBytes <= conf.getConf(SQLConf.MAX_SINGLE_PARTITION_BYTES))
+ case _ => true
+ }
+
+ if (preferSinglePartition) {
+ // Nothing to arrange between them, but each still has to satisfy its own requirement. A
+ // `SinglePartition` child does unless the distribution asks for a partition count, which a
+ // stateful operator's does.
+ resolved
+ } else {
+ // The two checks below decide on a pair: the operator, and what each of its children has to
+ // satisfy. Spark doesn't support multi-way join at the moment, so a parent that
+ // co-partitions has exactly two children and both of them are in the decision.
+ val linedUp = (parent, coPartitioned) match {
+ case (Some(operator), Seq(Some(leftRequired), Some(rightRequired))) =>
+ // key group compatibility check
+ checkKeyGroupCompatible(
+ operator, children.head, leftRequired, children(1), rightRequired)
+ // If key group check fails, check ShufflePartitionIdPassThrough compatibility. That
+ // one reads the children once each has satisfied its distribution on its own.
+ .orElse(Option.when(checkShufflePartitionIdPassThroughCompatible(
+ resolved.head, leftRequired, resolved(1), rightRequired))(resolved))
+ case _ => None
+ }
+ linedUp.getOrElse(shuffleToCoPartition(resolved, coPartitioned))
+ }
+ }
+
+ /**
+ * The layout the co-partitioned children are lined up on, and the member each of them pairs with
+ * it. A child with no pair is one that has to be shuffled onto `member`.
+ */
+ private case class CoPartitionTarget(
+ member: LeafShuffleSpec,
+ pairedMembers: Seq[Option[LeafShuffleSpec]])
+
+ /**
+ * Lines the co-partitioned children up by shuffle, which is what is left once no way of taking
+ * them as they are has worked. One child's layout is picked and the others are shuffled onto it.
+ *
+ * The children arrive having each satisfied its distribution on its own.
+ */
+ private def shuffleToCoPartition(
+ children: Seq[SparkPlan],
+ coPartitioned: Seq[Option[ClusteredDistribution]]): Seq[SparkPlan] = {
+ // One spec per co-partitioned child, in child order, and nothing for a child that is not in
+ // the decision.
+ val specs = children.zip(coPartitioned).map { case (child, required) =>
+ required.map(child.outputPartitioning.createShuffleSpec)
+ }
+ val target = pickCoPartitionTarget(children, specs)
+ // Nothing pairs when no child can serve as the layout, and then each of them is shuffled below
+ // on its own required distribution.
+ val pairedMembers = target.map(_.pairedMembers).getOrElse(Seq.fill(children.length)(None))
+
+ children.lazyZip(coPartitioned).lazyZip(pairedMembers).map {
+ case (child, None, _) =>
+ child
+
+ // The positions come from this child's own paired member, since they index into its own
+ // partition expressions -- the layout picked only says which member of it the two sides
+ // agreed on.
+ //
+ // The storage-partitioned join above declined, but one can still be had by shuffling the
+ // other side onto this one's keys (see the last case below). So the partitioned side's scan
+ // has to end up grouped by those keys, which is what pushing the positions in does. They
+ // index into the child's own report, which already carries whatever projection
+ // `resolveChild` gave it, so `withJoinKeyPositions` composes the two rather than replacing.
+ case (child, Some(_), Some(KeyedShuffleSpec(_, _, Some(joinKeyPositions)))) =>
+ withJoinKeyPositions(child, joinKeyPositions)
+
+ // Paired as it stands, so there is nothing to shuffle and nothing to push in.
+ case (child, Some(_), Some(_)) =>
+ child
+
+ case (child, Some(required), None) =>
+ val newPartitioning = target.map { picked =>
+ // Use the picked layout to create a new partitioning to re-shuffle this child
+ picked.member.createPartitioning(required.clustering)
+ }.getOrElse {
+ // No layout was picked, so we create default partitioning from the required distribution
+ val numPartitions = required.requiredNumPartitions
+ .getOrElse(conf.numShufflePartitions)
+ required.createPartitioning(numPartitions)
+ }
+
+ child match {
+ case s: ShuffleExchangeExec =>
+ s.copy(outputPartitioning = newPartitioning)
+ case gpe: GroupPartitionsExec =>
+ // Strip every grouping this rule inserted (they can stack on a re-run): a
+ // replicating one repeats every row, so none of them may feed the shuffle.
+ ShuffleExchangeExec(newPartitioning, peelGroupPartitions(gpe))
+ case _ => ShuffleExchangeExec(newPartitioning, child)
+ }
+ }
+ }
+
+ /**
+ * Picks the layout to line the co-partitioned children up on. It is one of their own, so that at
+ * least the child offering it keeps its partitioning and only the others are shuffled. `None`
+ * when no child can serve, and then they all take a shuffle.
+ *
+ * Find out the shuffle spec that gives better parallelism. A child with no `ShuffleExchangeLike`
+ * node comes first, and the largest number of partitions decides among those.
+ *
+ * NOTE: this is not optimal for the case when there are more than 2 children. Consider:
+ * (10, 10, 11)
+ * where each number is that child's partition count, it's better to pick 10
+ * here since we only need to shuffle one side - we'd need to shuffle two sides if we pick 11.
+ *
+ * However this should be sufficient for now since in Spark nodes with multiple children
+ * always have exactly 2 children.
+ */
+ private def pickCoPartitionTarget(
+ children: Seq[SparkPlan],
+ specs: Seq[Option[ShuffleSpec]]): Option[CoPartitionTarget] = {
+ // Whether we should consider `spark.sql.shuffle.partitions` and ensure enough parallelism
+ // during shuffle. To achieve a good trade-off between parallelism and shuffle cost, we only
+ // consider the minimum parallelism iff ALL children need to be re-shuffled.
+ //
+ // A child needs to be re-shuffled iff either of the following is true:
+ // 1. It can't create partitioning by itself, i.e., `canCreatePartitioning` returns false
+ // (as for the case of `RangePartitioning`), therefore it needs to be re-shuffled
+ // according to another child's shuffle spec.
+ // 2. It already has `ShuffleExchangeLike`, so we can re-use existing shuffle without
+ // introducing extra shuffle.
+ //
+ // On the other hand, in scenarios such as:
+ // HashPartitioning(5) <-> HashPartitioning(6)
+ // while `spark.sql.shuffle.partitions` is 10, we'll only re-shuffle the left side and make it
+ // HashPartitioning(6).
+ val shouldConsiderMinParallelism = children.zip(specs).forall { case (child, spec) =>
+ spec.forall(!_.canCreatePartitioning) || child.isInstanceOf[ShuffleExchangeLike]
+ }
+ // Choose all the specs that can be used to shuffle other children
+ val candidateSpecs = children.zip(specs).collect {
+ case (child, Some(spec)) if spec.canCreatePartitioning &&
+ (!shouldConsiderMinParallelism ||
+ child.outputPartitioning.numPartitions >= conf.defaultNumShufflePartitions) =>
+ child -> spec
+ }
+ // Rank on two things at once. A child with no `ShuffleExchangeLike` node comes first, since
+ // keeping it costs nothing. For instance, if we have:
+ // A: (No_Exchange, 100) <---> B: (Exchange, 120)
+ // it's better to pick A and change B to (Exchange, 100) instead of picking B and insert a
+ // new shuffle for A. Then the best parallelism decides, and for a collection that is the best
+ // any member offers, since a collection has no count of its own.
+ //
+ // What the winner contributes is its members, the alternatives the layout is picked from below.
+ // Empty when no child can serve as the layout.
+ val bestMembers: Seq[LeafShuffleSpec] = candidateSpecs.maxByOption { case (child, spec) =>
+ (!child.isInstanceOf[ShuffleExchangeLike], spec.flatten.map(_.numPartitions).max)
+ }.toSeq.flatMap(_._2.flatten)
+
+ // A `ShuffleSpecCollection` answers `isCompatibleWith` if *any* of its members does, so the
+ // winner alone does not say which member the sides agreed on. The projection pushed into a
+ // paired child and the partitioning built for a re-shuffled child both have to come from one
+ // member, otherwise the sides end up grouped on different keys, or on a key set the child does
+ // not even have. So what is picked here is the pairing, not a member per side.
+ //
+ // Per member of the winner, the member each child pairs with it, in child order.
+ val childMembers: Seq[Seq[LeafShuffleSpec]] = specs.map(_.toSeq.flatMap(_.flatten))
+ val pairings: Seq[(LeafShuffleSpec, Seq[Option[LeafShuffleSpec]])] = bestMembers.map { member =>
+ member -> childMembers.map(_.find(member.isCompatibleWith))
+ }
+ // Which children the winner reaches at all, over all of its members.
+ val reached: Seq[Boolean] = pairings.map(_._2).transpose.map(_.exists(_.isDefined))
+ // The member picked has to pair with every child the winner reaches. A child it does not
+ // reach, and a child that is not in the decision, are shuffled whichever member wins, so
+ // neither asks for anything here. None surviving means there is no layout to align them on, so
+ // they all take the ordinary shuffle. That needs three or more clustered children, since with
+ // two the member that reported the match serves both, and no operator has three today.
+ //
+ // Ranked by parallelism, preferring the finest.
+ pairings
+ .filter { case (_, paired) =>
+ paired.zip(reached).forall { case (pairedMember, isReached) =>
+ pairedMember.isDefined || !isReached
+ }
+ }
+ .maxByOption { case (member, _) => member.numPartitions }
+ .map { case (member, paired) => CoPartitionTarget(member, paired) }
}
private def hasKeyedPartitioning(p: Partitioning): Boolean = p match {
@@ -502,13 +588,14 @@ case class EnsureRequirements(
private def checkKeyGroupCompatible(
parent: SparkPlan,
left: SparkPlan,
+ leftRequired: ClusteredDistribution,
right: SparkPlan,
- requiredChildDistribution: Seq[Distribution]): Option[Seq[SparkPlan]] = {
+ rightRequired: ClusteredDistribution): Option[Seq[SparkPlan]] = {
parent match {
case smj: SortMergeJoinExec =>
- checkKeyGroupCompatible(left, right, smj.joinType, requiredChildDistribution)
+ checkKeyGroupCompatible(left, leftRequired, right, rightRequired, smj.joinType)
case sj: ShuffledHashJoinExec =>
- checkKeyGroupCompatible(left, right, sj.joinType, requiredChildDistribution)
+ checkKeyGroupCompatible(left, leftRequired, right, rightRequired, sj.joinType)
case _ =>
None
}
@@ -516,60 +603,61 @@ case class EnsureRequirements(
private def checkKeyGroupCompatible(
left: SparkPlan,
+ leftRequired: ClusteredDistribution,
right: SparkPlan,
- joinType: JoinType,
- requiredChildDistribution: Seq[Distribution]): Option[Seq[SparkPlan]] = {
- assert(requiredChildDistribution.length == 2)
-
- var newLeft = left
- var newRight = right
+ rightRequired: ClusteredDistribution,
+ joinType: JoinType): Option[Seq[SparkPlan]] = {
+ // Plan from the children as their sources report them, stripping any grouping this rule put
+ // there: the one the distribution step above just added, and on a re-run the aligned one an
+ // earlier pass left behind. Everything below then lives in one index space, the source's raw
+ // partition keys, so the positions, the reducers and the merged keys all mean one thing. This
+ // is also what lets the node be built once, here, instead of being placed as a guess and
+ // rewritten.
+ val rawLeft = peelGroupPartitions(left)
+ val rawRight = peelGroupPartitions(right)
+
+ // Peeling something off means an earlier run of this rule already settled a pairing here, and
+ // re-deciding it does not give the same answer. This one plans from the sources again, on an
+ // input that by then holds the keyed shuffle that run inserted, so the pairing sees two keyed
+ // sides where the first run saw one and aligns both to a merged key set they already hold.
+ // Keeping what arrived is what makes the rule idempotent.
+ //
+ // Three terms. Nothing was peeled on a plan this rule has not seen, so the question is not even
+ // asked there and the pairing below decides as it always did. Partially clustered distribution
+ // is excluded because it pushes even for two children that line up, assigning per-key slot
+ // counts against skew, which only the push branch builds. And the pair has to be one this rule
+ // would settle on anyway.
+ val keepArrivedPairing = ((left ne rawLeft) || (right ne rawRight)) &&
+ !conf.v2BucketingPartiallyClusteredDistributionEnabled &&
+ alreadyCoPartitioned(left, leftRequired, right, rightRequired)
+ if (keepArrivedPairing) {
+ return Some(Seq(left, right))
+ }
- def candidatesFor(plan: SparkPlan, required: Distribution): Seq[KeyedShuffleSpec] =
- required match {
- case cd: ClusteredDistribution => createKeyedShuffleSpecs(plan.outputPartitioning, cd)
- case _ => Nil
- }
- val leftCandidates = candidatesFor(left, requiredChildDistribution.head)
- val rightCandidates = candidatesFor(right, requiredChildDistribution(1))
+ val leftCandidates = candidatesFor(rawLeft, leftRequired)
+ val rightCandidates = candidatesFor(rawRight, rightRequired)
if (leftCandidates.isEmpty || rightCandidates.isEmpty) return None
- // A spec carries no `joinKeyPositions` exactly when its partitioning is the child's own member,
- // so this asks whether `compatibleAsIs` below can hold, i.e. whether the pair needs no
- // `GroupPartitionsExec` on either side. That is not the last word on the node: the push branch
- // inserts one whenever it runs, and partially clustered distribution makes it run even for a
- // pair that is compatible as it stands.
+ // The two sides are co-partitioned as they stand when each spec still describes its own
+ // source's layout, so no projection narrowed either. A side needing the plain grouping node
+ // below is not a reason to push anything. That node only coalesces the splits the source
+ // reports for one key.
def bothUnprojected(l: KeyedShuffleSpec, r: KeyedShuffleSpec): Boolean =
l.joinKeyPositions.isEmpty && r.joinKeyPositions.isEmpty
- // Whether the merged key list below may be narrowed to what the join type allows. A marked
- // layout is left alone: only an identity regrouping keeps its claim (see
- // `GroupPartitionsExec`), and losing it costs the pair its join at the gate at the end of this
- // method.
- //
- // Filtering is then the only thing that can shrink the merged list *below* the marked side's
- // own declared keys. The merging arms take the union, and `KeyedShuffleSpec.areKeysCompatible`
- // pairs a marked layout only with one whose keys are a subset of its declared keys, so the
- // union is that side's own key set. The count its hash is taken modulo survives the dedup
- // because a marked layout is always grouped: `canCreatePartitioning` is the only producer of
- // the marker and it refuses an ungrouped one. A reduce is the other way a merged list comes
- // out smaller, and it cannot happen here, since the marked arm of `areKeysCompatible` admits
- // only positions holding the same transform function and `reducersBothWays` finds nothing to
- // reduce between those.
+ // Whether the merged key list below may be narrowed to what the join type allows. Not when
+ // either side is marked. Narrowing drops groups that side holds, so its regrouping stops being
+ // the identity, and `GroupPartitionsExec` gives up a marked claim it does not regroup
+ // identically. That costs the pair its join at the gate at the end of this method, which is a
+ // poor trade for pruning a few groups.
//
- // What filtering does instead: an intersection with a strictly smaller partner, or the
- // one-sided arm that keeps the *other* side's keys, drops groups the marked side holds, and
- // the regrouping stops being the identity. The pair would then trade its whole join for
- // pruning those groups.
+ // Narrowing is the only thing here that can shrink the list below a marked side's own keys: the
+ // merging arms take the union, and `KeyedShuffleSpec.areKeysCompatible` pairs a marked layout
+ // only with one whose keys are a subset of its own.
//
- // Sorting is the other way a regrouping stops being the identity, and is not addressed here.
- // `mergeAndDedupPartitions` sorts, so a marked layout whose declared order is not the sorted
- // one is relabelled even where the set is unchanged. Handing it its own list verbatim looks
- // like the same fix and is not, because `KeyedPartitioning.createShuffleSpec` sorts through
- // `toGrouped` under `v2BucketingAllowKeysSubsetOfPartitionKeys` while it hands a marked layout
- // back unprojected: the two children would hold one partitioning and report two specs that
- // `describesSameKeys` calls different, and `ValidateRequirements` rejects the join this method
- // just allowed. Measured on the generated sweep in `EnsureRequirementsSuite`, cell
- // `left=id/12 right=id/312/marked Inner`.
+ // Sorting is the other way a regrouping stops being the identity, and this does not address it.
+ // `mergeAndDedupPartitions` sorts, so a marked side whose declared order is not the sorted one
+ // is relabelled even where the key set is unchanged.
val partitionFilter = conf.getConf(SQLConf.V2_BUCKETING_PARTITION_FILTER_ENABLED)
def filtersKeys(l: KeyedPartitioning, r: KeyedPartitioning): Boolean =
partitionFilter && !l.mayContainUnknownPartitionKeys && !r.mayContainUnknownPartitionKeys
@@ -592,7 +680,7 @@ case class EnsureRequirements(
// Each side may offer several members, and the right one is the one the other side can pair
// with, which neither side can tell on its own. So pick the pair rather than a member per side,
// and rank the pairs that agree on the keys by the parallelism they offer, the same trade
- // `ensureDistributionAndOrdering` makes between children when it picks `bestSpecOpt`.
+ // `pickCoPartitionTarget` makes between children when it picks the layout to shuffle onto.
//
// Two things keep `rank` from being what the join actually gets, both on the merging arms.
// `InnerLike` and `LeftSemi` intersect under `v2BucketingPartitionFilterEnabled`, unless
@@ -623,9 +711,6 @@ case class EnsureRequirements(
val leftPartitioning = leftSpec.partitioning
val rightPartitioning = rightSpec.partitioning
- // We don't need to alter the existing or add new `GroupPartitionsExec` when the child
- // partitionings are not modified (projected) in specs and left and right side partitionings are
- // compatible with each other.
val compatibleAsIs =
bothUnprojected(leftSpec, rightSpec) && leftSpec.isCompatibleWith(rightSpec)
// Entering the push branch is not the same as taking it. The keys agree for this pair by
@@ -636,7 +721,16 @@ case class EnsureRequirements(
(!compatibleAsIs || conf.v2BucketingPartiallyClusteredDistributionEnabled) &&
(conf.v2BucketingPushPartValuesEnabled ||
conf.v2BucketingAllowKeysSubsetOfPartitionKeys)
- if (pushCommonValues) {
+ // Neither route lines the two sides up, so there is no pairing to commit to. Asked here rather
+ // than after the push branch, which is the only thing below that does any work.
+ if (!compatibleAsIs && !pushCommonValues) {
+ return None
+ }
+ // What the push branch builds, when it runs. Empty otherwise, and then each side gets a plain
+ // grouping node instead, which it needs exactly when its source reports more than one partition
+ // per key. Building both eagerly would derive a grouping the push branch throws away, and that
+ // is one hash per partition key.
+ val pushed = Option.when(pushCommonValues) {
// Partition expressions are compatible. Regardless of whether partition values
// match from both sides of children, we can calculate a superset of partition values and
// push-down to respective data sources so they can adjust their output partitioning by
@@ -723,16 +817,10 @@ case class EnsureRequirements(
logInfo(log"Skipping partially clustered distribution as it cannot be applied for " +
log"join type '${MDC(LogKeys.JOIN_TYPE, joinType)}'")
} else {
- // The pre-alignment plan of each side and the grouping this rule inserted over it,
- // are read once: the statistics and the original partition keys below come from the
- // plan, the positions projecting them from the grouping.
- val leftGrouping = innermostGroupPartition(left)
- val rightGrouping = innermostGroupPartition(right)
- val unwrappedLeft = leftGrouping.map(_._1.child).getOrElse(left)
- val unwrappedRight = rightGrouping.map(_._1.child).getOrElse(right)
-
- val leftLink = unwrappedLeft.logicalLink
- val rightLink = unwrappedRight.logicalLink
+ // The statistics and the original partition keys come from the pre-alignment plans,
+ // which is what both sides already are here.
+ val leftLink = rawLeft.logicalLink
+ val rightLink = rawRight.logicalLink
replicateLeftSide = if (
leftLink.isDefined && rightLink.isDefined &&
@@ -752,16 +840,14 @@ case class EnsureRequirements(
leftLink.get.stats.sizeInBytes < rightLink.get.stats.sizeInBytes
} else {
// As a simple heuristic, we pick the side with fewer partitions to apply the
- // grouping & replication of partitions. The counts read the
- // pre-alignment plans, for the same reason the statistics do: on a re-run both
- // aligned reports hold the same number of keys, so comparing them decides nothing.
- // This also changes a first pass, which compared the aligned report's distinct
- // keys rather than the splits behind them.
+ // grouping & replication of partitions. The counts read the pre-alignment plans,
+ // for the same reason the statistics do. An aligned report holds the merged keys, so
+ // comparing two of them decides nothing.
logInfo("Using number of partitions to determine which side of join " +
"to fully cluster partition values")
- PartitioningCollection.numKeyedPartitions(unwrappedLeft.outputPartitioning)
+ PartitioningCollection.numKeyedPartitions(rawLeft.outputPartitioning)
.getOrElse(leftPartKeys.size) <
- PartitioningCollection.numKeyedPartitions(unwrappedRight.outputPartitioning)
+ PartitioningCollection.numKeyedPartitions(rawRight.outputPartitioning)
.getOrElse(rightPartKeys.size)
}
@@ -769,7 +855,7 @@ case class EnsureRequirements(
// Similar to skewed join, we need to check the join type to see whether replication
// of partitions can be applied. For instance, replication should not be allowed for
- // the left-hand side of a left outer join.
+ // the left-hand side of a right outer join.
if (replicateLeftSide && !canReplicateLeft) {
logInfo(log"Left-hand side is picked but cannot be applied to join type " +
log"'${MDC(LogKeys.JOIN_TYPE, joinType)}'. Skipping partially clustered " +
@@ -782,29 +868,21 @@ case class EnsureRequirements(
replicateRightSide = false
} else {
// In partially clustered distribution, we should use un-grouped partition values.
- // The child and the positions projecting its keys come from the same grouping:
- // the keys from the node's child, the positions from the node itself, falling back
- // to the spec's when there is no grouping. Like in `applyGroupPartitions`, the
- // node's positions were computed against the raw partition keys, while the spec's
- // were computed against the node's already projected report on a re-run.
+ // The child that keeps its splits and the positions projecting its keys both come
+ // from the raw side. The positions are the spec's, and the spec was built from that
+ // same raw report.
val (partiallyClusteredChild, partiallyClusteredPositions) =
if (replicateLeftSide) {
- (unwrappedRight,
- rightGrouping.flatMap(_._1.joinKeyPositions)
- .orElse(rightSpec.joinKeyPositions))
+ (rawRight, rightSpec.joinKeyPositions)
} else {
- (unwrappedLeft,
- leftGrouping.flatMap(_._1.joinKeyPositions)
- .orElse(leftSpec.joinKeyPositions))
+ (rawLeft, leftSpec.joinKeyPositions)
}
- // The pre-alignment plan of the side that keeps its splits: its partitioning
- // still holds the original partition keys, one per input split.
- val originalPartitioning =
- partiallyClusteredChild.outputPartitioning.asInstanceOf[Expression]
- // `outputPartitioning` is either a `PartitioningCollection` or a `KeyedPartitioning`
- // otherwise `createKeyedShuffleSpecs()` would have returned nothing.
- val originalKeyedPartitioning =
- originalPartitioning.collectFirst { case k: KeyedPartitioning => k }.get
+ // The side that keeps its splits still holds the original partition keys, one per
+ // input split. `outputPartitioning` is either a `PartitioningCollection` or a
+ // `KeyedPartitioning`, otherwise `createKeyedShuffleSpecs()` would have returned
+ // nothing.
+ val originalKeyedPartitioning = PartitioningCollection
+ .representativeOf(partiallyClusteredChild.outputPartitioning).get
val projectedOriginalPartitionKeys = partiallyClusteredPositions
.fold(originalKeyedPartitioning.partitionKeys)(
originalKeyedPartitioning.projectKeys(_)._2)
@@ -824,10 +902,13 @@ case class EnsureRequirements(
}
// Now we need to push-down the common partition information to the `GroupPartitionsExec`s.
- newLeft = applyGroupPartitions(left, leftSpec.joinKeyPositions, mergedPartitionKeys,
- leftReducers, distributePartitions = applyPartialClustering && !replicateLeftSide)
- newRight = applyGroupPartitions(right, rightSpec.joinKeyPositions, mergedPartitionKeys,
- rightReducers, distributePartitions = applyPartialClustering && !replicateRightSide)
+ (
+ GroupPartitionsExec(rawLeft, leftSpec.joinKeyPositions,
+ Some(mergedPartitionKeys), leftReducers,
+ distributePartitions = applyPartialClustering && !replicateLeftSide),
+ GroupPartitionsExec(rawRight, rightSpec.joinKeyPositions,
+ Some(mergedPartitionKeys), rightReducers,
+ distributePartitions = applyPartialClustering && !replicateRightSide))
}
// The pairing is only worth committing to if both children still declare the same aligned key
@@ -846,18 +927,18 @@ case class EnsureRequirements(
// `KeyLayout.describesSameKeys` asks exactly that, and it compares the key types as well as
// the rows.
//
- // Only the push branch rebuilds the children, so only it has to be asked. Where it did not run,
- // the children are the ones the pairing read: `KeyedShuffleSpec.isCompatibleWith` already ends
- // in `describesSameKeys`, and all keyed members of a `PartitioningCollection` share one
- // `KeyLayout`, so whichever member the spec matched on declares what the representative does.
+ // Both routes to `newLeft`/`newRight` build, so both are asked. On the base this was the push
+ // branch's question alone, because the other route left the children exactly as the pairing
+ // read them. Here `groupIfNeeded` can wrap a side that is not grouped, and that node gives up
+ // the claim for the same reason the pushed one does.
+ val (newLeft, newRight) =
+ pushed.getOrElse((groupIfNeeded(rawLeft), groupIfNeeded(rawRight)))
def declaredLayout(plan: SparkPlan): Option[KeyLayout] =
PartitioningCollection.representativeOf(plan.outputPartitioning).map(_.layout)
- def sidesDeclareSameKeys: Boolean =
- (declaredLayout(newLeft), declaredLayout(newRight)) match {
- case (Some(left), Some(right)) => left.describesSameKeys(right)
- case _ => false
- }
- val committed = if (pushCommonValues) sidesDeclareSameKeys else compatibleAsIs
+ val committed = (declaredLayout(newLeft), declaredLayout(newRight)) match {
+ case (Some(left), Some(right)) => left.describesSameKeys(right)
+ case _ => false
+ }
// Announced here rather than where the branch runs, since the gate can still discard what it
// built, and a log that names a pushdown should name one that happens.
if (pushCommonValues) {
@@ -871,143 +952,164 @@ case class EnsureRequirements(
Option.when(committed)(Seq(newLeft, newRight))
}
+ /**
+ * Whether the two children satisfy their distributions and line up with each other as they
+ * arrive, so that the pairing has nothing to add.
+ *
+ * Close to what `ValidateRequirements` asks of a finished plan, but not the same question, and
+ * the difference is deliberate. This goes through `createKeyedShuffleSpecs`, so it also applies
+ * `REQUIRE_ALL_CLUSTER_KEYS_FOR_CO_PARTITION`, admits a member on `keysMaySatisfy`, and looks at
+ * keyed members only. The per-side half is the validator's: `satisfies`, which is strict, so a
+ * child that still needs a node answers no.
+ *
+ * Both sides also have to answer with an unprojected spec. A projected one describes the layout a
+ * [[GroupPartitionsExec]] would emit rather than the one the child has, so two sides can agree
+ * through their projections while their partitions do not line up at all.
+ */
+ private def alreadyCoPartitioned(
+ left: SparkPlan,
+ leftRequired: ClusteredDistribution,
+ right: SparkPlan,
+ rightRequired: ClusteredDistribution): Boolean = {
+ def unprojectedSpecs(plan: SparkPlan, required: ClusteredDistribution): Seq[KeyedShuffleSpec] =
+ if (plan.outputPartitioning.satisfies(required)) {
+ candidatesFor(plan, required).filter(_.joinKeyPositions.isEmpty)
+ } else {
+ Nil
+ }
+ val leftSpecs = unprojectedSpecs(left, leftRequired)
+ val rightSpecs = unprojectedSpecs(right, rightRequired)
+ leftSpecs.exists(l => rightSpecs.exists(l.isCompatibleWith))
+ }
+
private def checkShufflePartitionIdPassThroughCompatible(
left: SparkPlan,
+ leftRequired: ClusteredDistribution,
right: SparkPlan,
- requiredChildDistribution: Seq[Distribution]): Boolean = {
+ rightRequired: ClusteredDistribution): Boolean = {
(left.outputPartitioning, right.outputPartitioning) match {
case (p1: ShufflePartitionIdPassThrough, p2: ShufflePartitionIdPassThrough) =>
- assert(requiredChildDistribution.length == 2)
- val leftSpec = p1.createShuffleSpec(
- requiredChildDistribution.head.asInstanceOf[ClusteredDistribution])
- val rightSpec = p2.createShuffleSpec(
- requiredChildDistribution(1).asInstanceOf[ClusteredDistribution])
- leftSpec.isCompatibleWith(rightSpec)
+ p1.createShuffleSpec(leftRequired).isCompatibleWith(p2.createShuffleSpec(rightRequired))
case _ =>
false
}
}
/**
- * The innermost `GroupPartitionsExec` reachable from `plan` by descending only through nodes
- * this rule itself inserted above it, together with a function rebuilding the traversed local
- * sorts over a replacement node. `None` when no `GroupPartitionsExec` is reachable.
+ * The plan a co-partitioned child's source reports, with every grouping and local sort this rule
+ * put over it peeled off. `plan` itself when it carries none.
*
- * The descent only traverses a `GroupPartitionsExec` and a *local* `SortExec`. That bound is a
- * decision, not an omission: a `GroupPartitionsExec` hidden behind any other node belongs to a
- * different operator, and reusing it would move that operator's alignment. Instrumentation of
- * the descent over `KeyGroupedPartitioningSuite` found these non-`SortExec` shapes hiding a
- * node: `Project > SortMergeJoin > Sort > GroupPartitions` and `Project > Filter > Window >
- * WindowGroupLimit > GroupPartitions`, where refusing to descend is right every time. A global
- * `SortExec` also stops the descent: it requires `OrderedDistribution`, which a
- * `KeyedPartitioning` can satisfy (behind `spark.sql.sources.v2.bucketing.sorting.enabled`)
- * through a `GroupPartitionsExec` built to emit the partition keys in sorted order, and
- * reusing that node for a join would destroy the ordering it exists to provide.
- */
- private def innermostGroupPartition(
- plan: SparkPlan): Option[(GroupPartitionsExec, SparkPlan => SparkPlan)] = plan match {
- case g: GroupPartitionsExec =>
- // When groupings stack, the outer one is the wrap this invocation's distribution step
- // just added; the one below is inherited from an earlier pass and owns the alignment to
- // preserve. Keep the descent below the outer node and drop it.
- innermostGroupPartition(g.child).orElse(Some((g, identity[SparkPlan])))
- case s: SortExec if !s.global =>
- innermostGroupPartition(s.child).map { case (g, rebuild) =>
- (g, (newChild: SparkPlan) => s.withNewChildren(Seq(rebuild(newChild))))
- }
- case _ => None
- }
-
- /**
- * Rewrites the innermost `GroupPartitionsExec` in `plan` with `f` and drops any redundant
- * grouping stacked above it, per the descent of [[innermostGroupPartition]]. Returns `None`
- * when `plan` holds no `GroupPartitionsExec`, leaving it to the caller to create one.
+ * The grouping peeled here is one an earlier pass left behind, not one this pass put on. The
+ * per-child step skips co-partitioned children entirely, so nothing of this pass's is under
+ * there when `checkKeyGroupCompatible` asks. The shuffle step, the other caller, can see both.
+ * `EnsureRequirements` is re-run on plans it already produced, since `AdaptiveSparkPlanExec`
+ * builds one instance of this rule, and `ConvertSortMergeJoinToShuffledHashJoin` and
+ * `OptimizeSkewedJoin` hand the whole tree back to it after rewriting some other join, all within
+ * one `queryStagePreparationRules` pass. So a join child can arrive as
+ * `GroupPartitionsExec(SortExec(GroupPartitionsExec(scan)))`, and planning from anything but the
+ * scan would derive the alignment from an already aligned layout and duplicate rows.
*
- * This is what makes the rule idempotent for storage-partitioned joins. `EnsureRequirements`
- * is re-run on plans it already produced: `AdaptiveSparkPlanExec` builds one instance of this
- * rule, and `ConvertSortMergeJoinToShuffledHashJoin` and `OptimizeSkewedJoin` hand the whole
- * tree back to it after rewriting some other join, all within one
- * `queryStagePreparationRules` pass. A join child then arrives as
- * `SortExec(GroupPartitionsExec(...))` rather than a bare scan, and the distribution step adds
- * a plain `GroupPartitionsExec` on top, because a partially clustered `KeyedPartitioning`
- * reports `isGrouped = false` by design and so is only satisfied "after grouping". Rewriting
- * that outer node instead of the one below it re-derives the alignment from an already-aligned
- * layout and duplicates rows; descending to the innermost node and dropping what sits above it
- * reproduces the plan a single pass would have produced.
+ * The descent only traverses a `GroupPartitionsExec` and a *local* `SortExec`. That bound is a
+ * decision, not an omission: a node hidden behind anything else belongs to a different operator,
+ * and peeling it would undo that operator's alignment. A global `SortExec` stops the descent for
+ * the same reason. It requires `OrderedDistribution`, which a `KeyedPartitioning` can satisfy
+ * (behind `spark.sql.sources.v2.bucketing.sorting.enabled`) through a node built to emit the keys
+ * in sorted order, and peeling that node would destroy the ordering it exists to provide.
*
- * Dropping a grouping is safe because only `applyGroupPartitions` calls this, reached from
- * `checkKeyGroupCompatible`, which runs for joins alone: every `GroupPartitionsExec` a join
- * child carries is this rule's own. A single-child operator genuinely needs its non-grouped
- * input grouped and takes the wrap in the children loop instead; `withJoinKeyPositions`, which
- * other multi-child operators reach, does not reuse at depth.
- */
- private[exchange] def rewriteGroupPartitions(plan: SparkPlan)(
- f: GroupPartitionsExec => GroupPartitionsExec): Option[SparkPlan] =
- innermostGroupPartition(plan).map { case (g, rebuild) =>
- val rewritten = f(g)
- rewritten.copyTagsFrom(g)
- rebuild(rewritten)
- }
-
- /**
- * Unwraps the groupings and local sorts this rule inserted over a child, down to the
- * pre-alignment plan, per the descent of [[innermostGroupPartition]]. Peeling one level stops
- * at the local sort this rule added, leaving the earlier pass's alignment in place.
- */
- private def unwrapGroupPartitions(plan: SparkPlan): SparkPlan =
- innermostGroupPartition(plan).map(_._1.child).getOrElse(plan)
-
- /**
- * Applies or updates `GroupPartitionsExec` with the given parameters.
+ * A local sort that is peeled off is re-added by the ordering step at the end of
+ * `ensureDistributionAndOrdering`, which is what put it there in the first place.
*
- * Reuses the node this rule inserted over the join child in an earlier pass, per the descent
- * of [[innermostGroupPartition]], and creates a new one when the child carries none.
+ * The two callers are `checkKeyGroupCompatible` and the shuffle step, both on the co-partitioned
+ * path, so every `GroupPartitionsExec` this reaches is one the rule put there itself. A
+ * single-child operator genuinely needs its non-grouped input grouped and keeps the wrap
+ * `resolveChild` gave it. `withJoinKeyPositions`, which other multi-child operators reach, does
+ * not descend at all.
*/
- private def applyGroupPartitions(
- plan: SparkPlan,
- joinKeyPositions: Option[Seq[Int]],
- mergedPartitionKeys: Seq[(InternalRowComparableWrapper, Int)],
- reducers: Option[Seq[Option[KeyReducer]]],
- distributePartitions: Boolean): SparkPlan = {
- rewriteGroupPartitions(plan) { g =>
- g.copy(
- joinKeyPositions = g.joinKeyPositions.orElse(joinKeyPositions),
- expectedPartitionKeys = Some(mergedPartitionKeys),
- // Unlike `joinKeyPositions`, these need no `orElse`. A re-run with reducers never reaches
- // here. Both sides then report the same reduced keys, so `compatibleAsIs` holds and the
- // push branch is skipped.
- reducers = reducers,
- distributePartitions = distributePartitions)
- }.getOrElse {
- GroupPartitionsExec(plan, joinKeyPositions, Some(mergedPartitionKeys), reducers,
- distributePartitions)
+ private[exchange] def peelGroupPartitions(plan: SparkPlan): SparkPlan = {
+ // `None` unless a `GroupPartitionsExec` is actually down there. A local sort is only this
+ // rule's to drop when it sits over one, otherwise it is the user's `sortWithinPartitions` and
+ // peeling it would lose an ordering nothing puts back.
+ def peel(p: SparkPlan): Option[SparkPlan] = p match {
+ case g: GroupPartitionsExec => Some(peel(g.child).getOrElse(g.child))
+ case s: SortExec if !s.global => peel(s.child)
+ case _ => None
}
+ peel(plan).getOrElse(plan)
}
/**
- * Applies join key positions to a plan by wrapping or updating GroupPartitionsExec.
+ * Applies join key positions to a plan by rebuilding a plain grouping node, or by wrapping
+ * anything else in a new one.
*
- * Unlike `applyGroupPartitions`, this does not descend: it serves every multi-child operator,
+ * Unlike `peelGroupPartitions`, this does not descend. It serves every multi-child operator,
* not just joins, so a `GroupPartitionsExec` below the top is not known to be this rule's own.
*/
private[exchange] def withJoinKeyPositions(plan: SparkPlan, positions: Seq[Int]): SparkPlan = {
plan match {
- case g: GroupPartitionsExec =>
- val newGroupPartitions = g.copy(joinKeyPositions = Some(positions))
+ // Only a plain grouping is rebuilt. An aligned one carries a merged key count, a reducer or
+ // a replication, none of which this rebuild reproduces, so it is wrapped below instead.
+ case g: GroupPartitionsExec
+ if g.expectedKeyCount.isEmpty && g.reducers.isEmpty && !g.distributePartitions =>
+ // Rebuilt rather than copied: the positions are an input to the node's grouping, and a
+ // `copy` would keep the grouping derived from the old ones.
+ //
+ // `positions` index the layout `g` reports, while `g.child` holds the raw partition
+ // expressions, so they are composed rather than replaced. The two index spaces differ
+ // whenever `g` already projects, which happens on two paths. `resolveChild` projects a
+ // co-partitioned child onto its cluster keys before the pairing declines, and the two
+ // derivations disagree about which positions those are. `positionsCoveringClusterKeys`
+ // also keeps an expression that *is* a cluster key, where `KeyedShuffleSpec.keyPositions`
+ // reads an expression's reference. And a re-run reads the positions off a report an
+ // earlier pass already projected.
+ val composed = g.joinKeyPositions.fold(positions)(old => positions.map(old))
+ val newGroupPartitions =
+ GroupPartitionsExec(g.child, Some(composed), enableSortedMerge = g.enableSortedMerge)
newGroupPartitions.copyTagsFrom(g)
newGroupPartitions
+ // Everything else is wrapped, an aligned grouping included. `positions` index what `plan`
+ // reports, which is exactly what the node built here projects, so the two line up with no
+ // composition. The base replaced a node's positions with a `copy` instead, which neither
+ // composes nor re-derives the grouping, so it had no case to tell apart.
case _ => GroupPartitionsExec(plan, joinKeyPositions = Some(positions))
}
}
+ /** `plan` under a plain grouping node, or `plan` itself when its source is already grouped. */
+ private def groupIfNeeded(plan: SparkPlan): SparkPlan = {
+ // The source is already grouped when it reports one partition per key, and then there is
+ // nothing to coalesce. Every keyed member of a partitioning shares one layout, so any of them
+ // answers for the plan.
+ val sourceIsGrouped =
+ PartitioningCollection.representativeOf(plan.outputPartitioning).exists(_.isGrouped)
+ if (sourceIsGrouped) plan else GroupPartitionsExec(plan)
+ }
+
+ /** The specs `plan` can offer for `required`. */
+ private def candidatesFor(
+ plan: SparkPlan,
+ required: ClusteredDistribution): Seq[KeyedShuffleSpec] =
+ createKeyedShuffleSpecs(plan.outputPartitioning, required)
+
/**
- * Every [[KeyedShuffleSpec]] the input partitioning can offer for the given distribution, one per
- * [[KeyedPartitioning]] in it that satisfies it and passes the co-partition key requirement
- * below. That requirement is on by default and is what usually leaves a collection with a single
- * candidate. A [[PartitioningCollection]] yields them in member order, nested collections
- * included, and the caller picks. Returning only the first would decide by enumeration order
- * which member the join is planned on, and only the caller comparing the two sides knows which
- * member pairs with the other side's.
+ * Every spec a co-partitioned child can offer for the given distribution, one per
+ * [[KeyedPartitioning]] in its partitioning that can serve it and passes the co-partition key
+ * requirement below. That requirement is on by default and is what usually leaves a collection
+ * with a single candidate. A [[PartitioningCollection]] yields them in member order, nested
+ * collections included, and the caller picks. Returning only the first would decide by
+ * enumeration order which member the join is planned on, and only the caller comparing the two
+ * sides knows which member pairs with the other side's.
+ *
+ * A spec describes what the child's [[KeyedPartitioning]] reports once this rule has grouped it.
+ * The question is `keysMaySatisfy` rather than `satisfies`, because the caller plans from the
+ * child as the source reports it, before any `GroupPartitionsExec` of this rule's. A source that
+ * reports several splits per partition key is not grouped, so it does not `satisfy` a
+ * `ClusteredDistribution` until the node coalesces them, and gating on `satisfies` here would
+ * refuse the very shape storage-partitioned join exists for.
+ *
+ * The spec is built from `toGrouped` for the same reason, but only for a source that is not
+ * grouped: the join is then planned against the layout the node will emit, one partition per
+ * distinct key, in the order `GroupPartitionsExec` sorts them. A grouped source gets no node, so
+ * its spec keeps its own key order.
*/
private def createKeyedShuffleSpecs(
partitioning: Partitioning,
@@ -1016,28 +1118,29 @@ case class EnsureRequirements(
// The config requires all the cluster keys to be covered by the partition keys, to avoid
// the skew of joining on keys that are coarser than the join keys. Key order and duplicated
// cluster keys don't matter.
- def allClusterKeysCovered: Boolean = {
+ def allClusterKeysCovered: Boolean =
// The single-column invariant in KeyedPartitioning.supportsExpressions guarantees one
// attribute per partition expression.
- val attributes = partitioning.expressions.flatMap(_.references)
- distribution.clustering.forall(c => attributes.exists(_.semanticEquals(c)))
- }
-
- if (partitioning.satisfies(distribution) &&
- (!SQLConf.get.getConf(SQLConf.REQUIRE_ALL_CLUSTER_KEYS_FOR_CO_PARTITION) ||
- allClusterKeysCovered)) {
- Some(partitioning.createShuffleSpec(distribution))
+ distribution.allClusterKeysAmong(partitioning.expressions.flatMap(_.references))
+
+ // The coverage requirement is a comparison of expressions, while `keysMaySatisfy` can end in
+ // a projection of the partition keys, so the cheap question is asked first. The requirement
+ // is on by default and turns most members away.
+ if ((!SQLConf.get.getConf(SQLConf.REQUIRE_ALL_CLUSTER_KEYS_FOR_CO_PARTITION) ||
+ allClusterKeysCovered) && partitioning.keysMaySatisfy(distribution)) {
+ // `toGrouped` both dedups and sorts, and only a `GroupPartitionsExec` performs either. A
+ // source that already reports one partition per key gets no node, so its own key order is
+ // what the join will see and claiming the sorted one would be a lie. This is the whole
+ // reason the two cases are told apart here rather than always grouping.
+ val grouped = if (partitioning.isGrouped) partitioning else partitioning.toGrouped
+ Some(grouped.createShuffleSpec(distribution))
} else {
None
}
}
- partitioning match {
- case p: KeyedPartitioning => tryCreate(p).toSeq
- case PartitioningCollection(partitionings) =>
- partitionings.flatMap(createKeyedShuffleSpecs(_, distribution))
- case _ => Nil
- }
+ PartitioningCollection.flatten(partitioning).collect { case k: KeyedPartitioning => k }
+ .flatMap(tryCreate)
}
/**
@@ -1097,51 +1200,6 @@ case class EnsureRequirements(
result.toSeq
}
- /**
- * The positions of `kp`'s partition expressions that are operation keys of `distribution`, and so
- * have to survive a projection. All of them when nothing needs projecting.
- *
- * Under `v2BucketingAllowKeysSubsetOfPartitionKeys` a [[KeyedPartitioning]] may be grouped on
- * more keys than the operation requires, in which case partitions sharing an operation key are
- * still separate. A partition expression is an operation key in two ways:
- *
- * - one of its *references* is a cluster key. This is the form `keysSatisfy` and
- * `KeyedShuffleSpec.keyPositions` both use, where a `bucket(4, a)` transform covers the
- * cluster key `a`.
- * - the expression *itself* is a cluster key. This is what keeps a position whose expression is
- * clustered on while its references are not, as for a `years(ts)` under a clustering that
- * names `years(ts)` rather than `ts`.
- *
- * Returns every position for a co-partitioned operator. There the multi-child block owns the
- * projection, a storage-partitioned join through `checkKeyGroupCompatible` and anything else
- * through `withJoinKeyPositions`. Projecting here as well would leave that block deriving
- * positions from an already projected partitioning and applying them to the unprojected partition
- * expressions.
- *
- * An empty result means no partition expression covers an operation key, so there is nothing to
- * project onto. That is the answer for a member that cannot satisfy `distribution`, which is why
- * the caller only asks for members that can. It also happens for a member that can. One whose
- * expressions have no references at all makes every `keysSatisfy` branch vacuously true, and
- * nothing at `KeyedPartitioning` construction rejects that. The caller skips such a member rather
- * than project it to no position, which would collapse every partition into one.
- *
- * Keeping a position is only sound because `keysSatisfy`'s subset branch also requires
- * `expressions.forall(_.references.size == 1)`. A kept expression is then a function of a single
- * cluster key, so coalescing on the projected keys cannot put rows that share an operation key on
- * different partitions.
- */
- private def clusterKeyPositions(
- kp: KeyedPartitioning,
- distribution: Distribution,
- isCoPartitioned: Boolean): BitSet = distribution match {
- case c: ClusteredDistribution if !isCoPartitioned =>
- kp.expressions.zipWithIndex.collect {
- case (e, i) if c.clustering.exists(_.semanticEquals(e)) ||
- e.references.exists(ref => c.clustering.exists(_.semanticEquals(ref))) => i
- }.to(BitSet)
- case _ => kp.expressions.indices.to(BitSet)
- }
-
/**
* Splits a partitioning into the two questions the caller acts on, in this order:
*
@@ -1158,189 +1216,182 @@ case class EnsureRequirements(
*
* At most one `KeyedPartitioning` comes back, because the caller acts on a single one. Whichever
* it takes, the child then satisfies the distribution and the rest of its partitioning is
- * irrelevant. A partitioning that satisfies the distribution can still come back as a `Right`,
- * because `satisfies` over-claims under `v2BucketingAllowKeysSubsetOfPartitionKeys`.
+ * irrelevant. A member that satisfies as it stands always comes back as a `Left`, since
+ * `satisfies` is the strict question.
*
* That is the point of classifying by what still has to happen to the data rather than by how the
* partitioning was built. An already grouped `KeyedPartitioning` can still need a
* `GroupPartitionsExec`, because `v2BucketingAllowKeysSubsetOfPartitionKeys` lets it be grouped
- * on more keys than the operation requires, and `isGrouped` only tells whether the *full*
+ * on more keys than the distribution requires, and `isGrouped` only tells whether the *full*
* partition keys are unique. Keeping both reasons in one answer leaves the caller a single
* `ClusteredDistribution` arm that inserts the node, and one place that decides the projection.
*
* @param partitioning The partitioning to split
* @param distribution The distribution to satisfy
- * @param isCoPartitioned Whether the parent operator co-partitions more than one child, in which
- * case the projection is not done here (see `clusterKeyPositions`)
*/
private def splitKeyedPartitionings(
partitioning: Partitioning,
- distribution: Distribution,
- isCoPartitioned: Boolean): (Boolean, Option[KeyedResolution]) = {
+ distribution: Distribution): (Boolean, Option[KeyedResolution]) = {
val flattened = PartitioningCollection.flatten(partitioning)
if (flattened.exists(p => !p.isInstanceOf[KeyedPartitioning] && p.satisfies(distribution))) {
(true, None)
} else {
val keyed = flattened.collect { case k: KeyedPartitioning => k }
- (false, resolveKeyedPartitioning(keyed, distribution, isCoPartitioned))
+ (false, resolveKeyedPartitioning(keyed, distribution))
}
}
+ /**
+ * A [[KeyedPartitioning]] that can satisfy the distribution, and how it gets there.
+ *
+ * @param satisfiesAsIs whether it satisfies with no [[GroupPartitionsExec]] at all
+ * @param positions the partition expression positions covering a cluster key, which is what a
+ * node would project it to
+ */
+ private case class AdmittedMember(
+ partitioning: KeyedPartitioning,
+ satisfiesAsIs: Boolean,
+ positions: BitSet)
+
/**
* How one of `keyedPartitionings` can satisfy `distribution`, or `None` when none of them can.
* See `splitKeyedPartitionings`, which is the only caller.
*/
private def resolveKeyedPartitioning(
keyedPartitionings: Seq[KeyedPartitioning],
- distribution: Distribution,
- isCoPartitioned: Boolean): Option[KeyedResolution] = {
- // `KeyedPartitioning.numPartitionsProjectedOn` allocates a row per input partition and hashes
- // it with an uncached `hashCode`, so the answer is memoized. It is free for a position set that
- // keeps every position, which is the common shape on the default config, where nothing narrows
- // the positions and the node is inserted only to coalesce duplicate keys.
- //
- // The position set is the whole memo key. The projection reads each key value at
- // `KeyedPartitioning.keyDataTypes`, the types the keys were built with, and every member of a
- // child's partitioning shares the same keys, so the same position set projects to the same
- // count whichever member is asked. Reading the values at the *expressions'* types would not
- // have that property, and would not even be sound. A reducer can rewrite the keys onto another
- // key space while a member keeps reporting the expressions it was built from.
- val projectedNumPartitions = mutable.Map.empty[BitSet, Int]
- def numPartitionsAfter(kp: KeyedPartitioning, positions: BitSet): Int =
- projectedNumPartitions.getOrElseUpdate(
- positions, kp.numPartitionsProjectedOn(positions.toSeq))
-
+ distribution: Distribution): Option[KeyedResolution] = {
// Which members can satisfy the distribution at all, and which of their partition expression
- // positions are operation keys. Nothing here touches a partition key.
+ // positions cover a cluster key. Nothing here touches a partition key.
//
// Both questions are asked, because neither implies the other. `satisfies` is the strict one,
// and it also enforces `requiredNumPartitions`. `keysMaySatisfy` ignores the count and allows a
- // `GroupPartitionsExec` to coalesce duplicate partition keys. A non-grouped member always needs
- // that node, since `satisfies0` gates a `ClusteredDistribution` on `isGrouped`.
+ // `GroupPartitionsExec` to coalesce duplicate partition keys. Neither subsumes the other:
+ // `keysMaySatisfy` only ever answers the keyed questions, so it says no to the `AllTuples` and
+ // `UnspecifiedDistribution` that `satisfies` inherits from `Partitioning`, while a non-grouped
+ // member needs a node and so fails `satisfies`.
//
- // The two overlap on the key matching, and asking the strict one first keeps that to a single
- // matching for every member that is admitted.
+ // Both go through `keysSatisfy` for a `ClusteredDistribution`, so it can be derived twice, but
+ // only for a member this loop then rejects. Every other case short-circuits: a non-grouped one
+ // never reaches it through `satisfies0`, a wrong partition count stops before `satisfies0`, and
+ // when either `keysSatisfy` or `keysCanSatisfy`'s projection question says yes the `||` above
+ // stops. What is left is a grouped member whose keys match neither way, and the second
+ // derivation there reads a partition key only in the shape where the two position derivations
+ // disagree, an expression that *is* a cluster key while its references are not.
//
// The positions are only computed for a member that can satisfy. For one that cannot, no
- // position would be covered, and an empty set means something else there (see
- // `clusterKeyPositions`).
+ // position would be covered, and an empty set means something else there.
val admitted = keyedPartitionings.flatMap { k =>
val satisfies = k.satisfies(distribution)
if (satisfies || k.keysMaySatisfy(distribution)) {
- val positions = clusterKeyPositions(k, distribution, isCoPartitioned)
+ // Every position survives when the distribution names no cluster keys, since then
+ // nothing needs projecting. Keeping a position is only sound because `keysSatisfy`'s
+ // subset branch also requires one reference per expression, so a kept expression is a
+ // function of a single cluster key and coalescing on the projected keys cannot put rows
+ // that share a cluster key on different partitions.
+ val positions = distribution match {
+ case c: ClusteredDistribution => k.positionsCoveringClusterKeys(c)
+ case _ => k.expressions.indices.to(BitSet)
+ }
// A member covering no position is skipped rather than projected onto nothing, which would
- // collapse every partition into one. See `clusterKeyPositions`.
- Option.when(positions.nonEmpty || k.expressions.isEmpty)((k, satisfies, positions))
+ // collapse every partition into one. It happens for a member that cannot satisfy at all,
+ // and for one whose expressions have no references, which makes every `keysSatisfy` branch
+ // vacuously true and which nothing at construction rejects.
+ Option.when(positions.nonEmpty || k.expressions.isEmpty)(
+ AdmittedMember(k, satisfies, positions))
} else {
None
}
}
- // A node is pointless when a member satisfies and nothing is left for the node to do, which
- // holds in two ways. Either the projection drops no position, so `satisfies` is not the
- // over-claim this fix is about. That is also the only shape `UnspecifiedDistribution` and
- // `AllTuples` ever reach, the two `nonGroupedSatisfies` covers, because `clusterKeyPositions`
- // returns every position for them. Or a position is dropped but the projection merges nothing,
- // so every operation key already lives on a single partition. Keeping the member is then better
- // than projecting. Both describe the same number of partitions, and only the member still names
- // the dropped keys, which lets a downstream operator co-partition on them too.
- //
- // `numPartitions` is the count to compare against in the second case. There the distribution is
- // a `ClusteredDistribution`, so `satisfies` went through `isGrouped && keysSatisfy`, and a
- // grouped partitioning has distinct keys, leaving the node nothing to coalesce.
- //
- // The first form is asked of every member before the second, because answering it costs no key
- // work at all. A member that narrows would otherwise pay a projection that a later
- // full-coverage member makes pointless.
- val satisfiedAsIs = admitted
- .find { case (k, satisfies, positions) =>
- satisfies && positions.size == k.expressions.length
- }
- .orElse(admitted.find { case (k, satisfies, positions) =>
- satisfies && numPartitionsAfter(k, positions) == k.numPartitions
- })
- .map(_._1)
-
- if (satisfiedAsIs.isDefined) {
- // A member that needs no node settles the child, whatever the candidates would have offered.
- // `Left` and `Right` are qualified throughout, because `catalyst.expressions` has its own.
- satisfiedAsIs.map(scala.Left(_))
- } else {
- // Every admitted member needs a node, and every one of them satisfies the distribution once
- // it has one, so what is left is which one to build it from. They are the candidates, keyed
- // by the positions the node would project them to.
- //
- // One entry per distinct position set is enough, and the first member wins. The same set
- // projects to the same keys whichever member applies it, because `PartitioningCollection`
- // guarantees its members share the `partitionKeys` reference and their arity, so position `i`
- // addresses the same key column in all of them.
- //
- // `GroupPartitionsExec` re-derives the member independently, with a `collectFirst` over its
- // child's partitioning, so the member recorded here and the one used at execution agree only
- // because of that same guarantee, `PartitioningCollection.checkKeyedPartitioningInvariant`
- // and the value-equality interning in `fromPartitionings` behind it. Relaxing the invariant
- // means changing both places together, not just this one. What the members may still differ
- // in is how their key types are named, since the collection only requires them to describe
- // one key space. That does not reach the keys, which are shared.
- //
- // The order is the child's, so when two sets leave the same number of partitions, the one
- // from the member the child reports first wins. That tie is the only thing the order decides,
- // and either winner satisfies the distribution. The two project to different keys though, so
- // the choice is visible in the plan.
- val candidates = admitted.map { case (k, _, positions) => k -> positions }.distinctBy(_._2)
-
- // A required partition count comes first, because a node derives its count from the keys it
- // is handed rather than from the operator. It filters the candidates rather than vetoing the
- // winner. One that would land on the required count must not lose to one that cannot honour
- // it and send the whole child to a shuffle instead.
- //
- // A member with fewer partitions than the count is refused without projecting anything, since
- // a projection merges partitions and never splits them.
- val eligible = distribution.requiredNumPartitions match {
- case Some(n) => candidates.filter { case (k, ps) =>
- k.numPartitions >= n && numPartitionsAfter(k, ps) == n
- }
- case None => candidates
- }
- if (eligible.isEmpty) {
- // Either no member was admitted at all, or no projection leaves the required count. Both
- // send the caller to a shuffle, which can honour it.
- None
- } else {
- // Among the rest the choice is plan quality. Take the projection leaving the most
- // partitions.
+ // A node is pointless when a member satisfies, and that is the whole test.
+ // `KeyedPartitioning.satisfies` is strict, so it answers `false` for a member that only
+ // satisfies once a node has projected its keys.
+ admitted.find(_.satisfiesAsIs) match {
+ case Some(member) =>
+ // A member that needs no node settles the child, whatever the candidates would have
+ // offered. `Left` and `Right` are qualified throughout, because `catalyst.expressions` has
+ // its own.
+ Some(scala.Left(member.partitioning))
+
+ case None =>
+ // Every admitted member needs a node, and every one of them satisfies the distribution
+ // once it has one, so what is left is which one to build it from. They are the candidates,
+ // keyed by the positions the node would project them to.
//
- // A position set contained in another one is dropped without ranking it. Projecting to
- // fewer positions can merge partitions but never split them, so a contained set can never
- // leave more partitions than the set containing it, and can only tie. Dropping it therefore
- // costs no parallelism, and on a tie it settles the choice toward the wider set, which
- // still names the keys the narrower one would have dropped.
+ // One entry per distinct position set is enough, and the first member wins. The same set
+ // projects to the same keys whichever member applies it, because `PartitioningCollection`
+ // guarantees its members share the `partitionKeys` reference and their arity, so position
+ // `i` addresses the same key column in all of them.
//
- // It saves projections too, though only for the members that do not satisfy. The loop above
- // already counted every narrowing set of a satisfying member, to decide whether that member
- // needed a node at all. Either way the projection is the expensive step here, since
- // `KeyedPartitioning.projectKeys` allocates a row per input partition and
- // `InternalRowComparableWrapper.hashCode` is uncached, and the containment test is not.
- // That test is quadratic in the number of *distinct position sets*, not in the number of
- // members, both are small, and each pair is an int compare that rejects most of them, then
- // a word compare on a `BitSet`. Nothing in it touches a partition key.
- val maximal = eligible.filter { case (_, positions) =>
- !eligible.exists { case (_, o) => o.size > positions.size && positions.subsetOf(o) }
+ // `GroupPartitionsExec` re-derives the member independently, through
+ // `PartitioningCollection.representativeOf`, so the member recorded here and the one used
+ // at execution agree only because of that same guarantee,
+ // `PartitioningCollection.checkKeyedPartitioningInvariant` and the value-equality interning
+ // in `fromPartitionings` behind it. Relaxing the invariant means changing both places
+ // together, not just this one. What the members may still differ in is how their key types
+ // are named, since the collection only requires them to describe one key space. That does
+ // not reach the keys, which are shared.
+ //
+ // The order is the child's, so when two sets leave the same number of partitions, the one
+ // from the member the child reports first wins. That tie is the only thing the order
+ // decides, and either winner satisfies the distribution. The two project to different keys
+ // though, so the choice is visible in the plan.
+ val candidates = admitted.map(m => m.partitioning -> m.positions).distinctBy(_._2)
+
+ // A required partition count comes first, because a node derives its count from the keys
+ // it is handed rather than from the operator. It filters the candidates rather than
+ // vetoing the winner. One that would land on the required count must not lose to one that
+ // cannot honour it and send the whole child to a shuffle instead.
+ //
+ // A member with fewer partitions than the count is refused without projecting anything,
+ // since a projection merges partitions and never splits them.
+ val eligible = distribution.requiredNumPartitions match {
+ case Some(n) => candidates.filter { case (k, ps) =>
+ k.numPartitions >= n && k.numPartitionsProjectedOn(ps) == n
+ }
+ case None => candidates
+ }
+ if (eligible.isEmpty) {
+ // Either no member was admitted at all, or no projection leaves the required count. Both
+ // send the caller to a shuffle, which can honour it.
+ None
+ } else {
+ // Among the rest the choice is plan quality. Take the projection leaving the most
+ // partitions.
+ //
+ // A position set contained in another one is dropped without ranking it. Projecting to
+ // fewer positions can merge partitions but never split them, so a contained set can
+ // never leave more partitions than the set containing it, and can only tie. Dropping it
+ // therefore costs no parallelism, and on a tie it settles the choice toward the wider
+ // set, which still names the keys the narrower one would have dropped.
+ //
+ // It saves projections, and the projection is the expensive step here, since
+ // `KeyedPartitioning.projectKeys` allocates a row per input partition and
+ // `InternalRowComparableWrapper.hashCode` is uncached, while the containment test is
+ // not. That test is quadratic in the number of *distinct position sets*, not in the
+ // number of members, both are small, and each pair is an int compare that rejects most
+ // of them, then a word compare on a `BitSet`. Nothing in it touches a partition key.
+ val maximal = eligible.filter { case (_, positions) =>
+ !eligible.exists { case (_, o) => o.size > positions.size && positions.subsetOf(o) }
+ }
+ // With one candidate left there is nothing to rank, and no count is needed either. That
+ // is the ordinary shape on the default config, so it is worth not projecting for it. A
+ // required count settles it too, since the filter above kept only the sets leaving
+ // exactly that many, so every survivor ties and `maxBy` would return the first anyway.
+ val (kp, positions) =
+ if (maximal.size == 1 || distribution.requiredNumPartitions.isDefined) {
+ maximal.head
+ } else {
+ maximal.maxBy { case (k, ps) => k.numPartitionsProjectedOn(ps) }
+ }
+
+ // Satisfied after a node, whether that node has to coalesce duplicate partition keys,
+ // project down to the cluster keys, or both. Every member that reaches here needs one,
+ // since a member satisfying as it stands was taken by the arm above.
+ Some(scala.Right(
+ (kp, Option.when(positions.size < kp.expressions.length)(positions.toSeq))))
}
- // With one candidate left there is nothing to rank, and no count is needed either. That is
- // the ordinary shape on the default config, so it is worth not projecting for it.
- val (kp, positions) =
- if (maximal.size == 1) maximal.head
- else maximal.maxBy { case (k, ps) => numPartitionsAfter(k, ps) }
-
- // Satisfied after a node, whether that node has to coalesce duplicate partition keys,
- // project down to the operation keys, or both. A `kp` that satisfies lands here too when
- // the projection does merge partitions, which is exactly where `satisfies` over-claims:
- // rows sharing an operation key are spread over partitions it reports as clustered.
- Some(scala.Right(
- (kp, Option.when(positions.size < kp.expressions.length)(positions.toSeq))))
- }
}
}
diff --git a/sql/core/src/test/scala/org/apache/spark/sql/connector/KeyGroupedPartitioningSuite.scala b/sql/core/src/test/scala/org/apache/spark/sql/connector/KeyGroupedPartitioningSuite.scala
index 077c58eec686..c49b3c3e9210 100644
--- a/sql/core/src/test/scala/org/apache/spark/sql/connector/KeyGroupedPartitioningSuite.scala
+++ b/sql/core/src/test/scala/org/apache/spark/sql/connector/KeyGroupedPartitioningSuite.scala
@@ -45,7 +45,7 @@ import org.apache.spark.sql.execution.{
UnionExec,
WholeStageCodegenExec}
import org.apache.spark.sql.execution.datasources.v2.{BatchScanExec, DataSourceV2ScanRelation, GroupPartitionsExec}
-import org.apache.spark.sql.execution.exchange.{ReusedExchangeExec, ShuffleExchangeExec, ShuffleExchangeLike, ValidateRequirements}
+import org.apache.spark.sql.execution.exchange.{EnsureRequirements, ReusedExchangeExec, ShuffleExchangeExec, ShuffleExchangeLike, ValidateRequirements}
import org.apache.spark.sql.execution.joins.{ShuffledHashJoinExec, ShuffledJoin, SortMergeJoinExec}
import org.apache.spark.sql.execution.metric.SQLMetricsTestUtils
import org.apache.spark.sql.execution.ui.SparkPlanGraphNode
@@ -1344,7 +1344,13 @@ class KeyGroupedPartitioningSuite
attr: AttributeReference,
otherAttr: AttributeReference,
reducer: Reducer[_, _]): GroupPartitionsExec = {
- val child = new LocalTableScanExec(Seq(attr), Nil, None, false)
+ // A `GroupPartitionsExec` is only built over a child that reports a `KeyedPartitioning`,
+ // and it derives its grouping from that child at construction, so the scan is wrapped in
+ // one. The key list is empty, which keeps the grouping trivial: this test is about the
+ // reducers' exprIds, not about what the node does to any partition.
+ val child = ShuffleExchangeExec(
+ KeyedPartitioning(Seq(attr), Nil),
+ new LocalTableScanExec(Seq(attr), Nil, None, false))
val reduced = TransformExpression(BucketFunction, Seq(otherAttr), Some(2))
GroupPartitionsExec(child,
reducers = Some(Seq(Some(physical.KeyReducer(reducer, reduced)))))
@@ -1369,7 +1375,9 @@ class KeyGroupedPartitioningSuite
attr: AttributeReference,
dt: AttributeReference,
otherAttr: AttributeReference): GroupPartitionsExec = {
- val child = new LocalTableScanExec(Seq(attr, dt), Nil, None, false)
+ val child = ShuffleExchangeExec(
+ KeyedPartitioning(Seq(attr, dt), Nil),
+ new LocalTableScanExec(Seq(attr, dt), Nil, None, false))
val reduced = TransformExpression(BucketFunction, Seq(otherAttr), Some(2))
GroupPartitionsExec(child,
reducers = Some(Seq(None, Some(physical.KeyReducer(BucketReducer(2), reduced)))))
@@ -6131,7 +6139,7 @@ class KeyGroupedPartitioningSuite
test("SPARK-58988: v2 bucketed table with subset join keys joining v1 table") {
// The v2 table is partitioned by an extra identity key `dt` plus `bucket(16, c1)`, while the
- // join is only on `c1`. allowKeysSubsetOfPartitionKeys lets the operation key `c1` be a subset
+ // join is only on `c1`. allowKeysSubsetOfPartitionKeys lets the cluster key `c1` be a subset
// of the partition keys `[dt, bucket(16, c1)]`, so EnsureRequirements projects the keyed side
// to `[bucket(16, c1)]`. v2BucketingShuffleEnabled then re-shuffles only the v1 side using that
// projected KeyedPartitioning. ShuffledJoin wraps the two output partitionings into a
@@ -6221,7 +6229,7 @@ class KeyGroupedPartitioningSuite
// Every partition holds a distinct k1, so rows sharing (k1, k2, k3) share a partition and the
// left member satisfies the window's distribution as it is. Projecting the right member to
// (k2, k3) would merge the two partitions holding (9, 9) instead, for nothing. The member that
- // needs no node has to win even though the other one covers more operation keys.
+ // needs no node has to win even though the other one covers more cluster keys.
val cols = Array(
Column.create("k1", IntegerType),
Column.create("k2", IntegerType),
@@ -6624,12 +6632,12 @@ class KeyGroupedPartitioningSuite
val groupPartitions =
collectAllGroupPartitions(sql(query).queryExecution.executedPlan)
assert(groupPartitions.map(_.joinKeyPositions) == Seq(Some(Seq(0))),
- "the GroupPartitionsExec must project to the operation key [id], not only coalesce the " +
+ "the GroupPartitionsExec must project to the cluster key [id], not only coalesce the " +
"duplicate (id, name) splits")
}
}
- test("SPARK-58968: no GroupPartitionsExec when projecting to the operation keys coalesces " +
+ test("SPARK-58968: no GroupPartitionsExec when projecting to the cluster keys coalesces " +
"nothing") {
// Every id has exactly one name, so projecting KeyedPartitioning([id, name]) down to [id]
// leaves the same number of partitions. Every id already lives on a single partition, so the
@@ -8316,6 +8324,176 @@ class KeyGroupedPartitioningSuite
}
}
+ test("SPARK-59289: a grouping over a keyed shuffle stage survives an AQE round") {
+ // `GroupPartitionsExec` carries its grouping and its reported partitioning as constructor
+ // fields, so a child rewrite no longer re-derives them. AQE is where a child gets rewritten
+ // under a node that is already planned, so this runs the shape under it with every shuffle
+ // read rule on: the second join's grouping sits over the first join, whose own right leg is
+ // a keyed shuffle stage.
+ //
+ // What this does NOT do is get a rewrite applied to that stage, and the reason is structural.
+ // `CoalesceShufflePartitions` only coalesces a group whose leaves are all query stages, and
+ // `OptimizeShuffleWithLocalRead` needs the stage to be a broadcast join's own probe side. A
+ // storage-partitioned join always keeps one side as a scan, which is neither. So this test
+ // still passes with the gate in `GroupPartitionsExec.outputPartitioning` removed: it is
+ // coverage of the SPJ-under-AQE shape, and the gate itself is pinned by
+ // `GroupPartitionsExecSuite`'s "the keyed claim goes when the child no longer reports what
+ // was planned", which does fail without it.
+ val cols = Array(Column.create("id", IntegerType), Column.create("data", StringType))
+ createTable("aqeka", cols, Array(identity("id")))
+ createTable("aqekb", cols, Array(identity("id")))
+ sql("INSERT INTO testcat.ns.aqeka VALUES (1, 'a1'), (2, 'a2'), (3, 'a3'), (4, 'a4')")
+ sql("INSERT INTO testcat.ns.aqekb VALUES (1, 'b1'), (2, 'b2'), (3, 'b3')")
+
+ withTable("aqept") {
+ sql("CREATE TABLE aqept (id INT, data STRING) USING parquet")
+ sql("INSERT INTO aqept VALUES (1,'p1'),(2,'p2'),(3,'p3'),(4,'p4'),(5,'p5')")
+
+ val query =
+ """
+ |SELECT j.id, b.data
+ |FROM (
+ | SELECT a.id AS id FROM testcat.ns.aqeka a JOIN aqept t ON a.id = t.id
+ |) j
+ |JOIN testcat.ns.aqekb b ON j.id = b.id
+ |""".stripMargin
+ val expected = Seq(Row(1, "b1"), Row(2, "b2"), Row(3, "b3"))
+
+ // The broadcast threshold is off so both joins stay shuffle joins, which is what keeps the
+ // keyed shuffle and the grouping in the plan at all.
+ Seq(false, true).foreach { aqeEnabled =>
+ withSQLConf(
+ SQLConf.V2_BUCKETING_SHUFFLE_ENABLED.key -> "true",
+ SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> aqeEnabled.toString,
+ SQLConf.COALESCE_PARTITIONS_ENABLED.key -> "true",
+ SQLConf.COALESCE_PARTITIONS_MIN_PARTITION_NUM.key -> "1",
+ SQLConf.LOCAL_SHUFFLE_READER_ENABLED.key -> "true",
+ "spark.sql.autoBroadcastJoinThreshold" -> "-1") {
+ val df = sql(query)
+ checkAnswer(df, expected)
+ val plan = df.queryExecution.executedPlan
+ assert(ValidateRequirements.validate(plan),
+ s"aqe=$aqeEnabled: the executed plan must satisfy every required distribution:\n$plan")
+
+ // The shape the test exists for. Without these the assertions above would pass on a
+ // plan that had lost the storage-partitioned join entirely.
+ val groupings = collectAllGroupPartitions(plan)
+ assert(groupings.size == 2,
+ s"aqe=$aqeEnabled: the second join groups both of its sides:\n$plan")
+ groupings.foreach { grouping =>
+ assert(grouping.outputPartitioning.isInstanceOf[physical.KeyedPartitioning],
+ s"aqe=$aqeEnabled: each still claims the layout it was planned for:\n$plan")
+ }
+ val keyed = collectAllShuffles(plan)
+ .filter(_.outputPartitioning.isInstanceOf[physical.KeyedPartitioning])
+ assert(keyed.size == 1,
+ s"aqe=$aqeEnabled: one keyed shuffle, under the grouping:\n$plan")
+ }
+ }
+ }
+ }
+
+ test("SPARK-59289: a second pass leaves a storage-partitioned join this rule planned alone") {
+ // `EnsureRequirements` runs again on a plan it produced: it sits in the preparation batch
+ // `AdaptiveSparkPlanExec` re-applies to every re-planned query stage. This PR decides the
+ // co-partitioned child once, so a second pass has to recognise its own work rather than peel
+ // it apart and rebuild something else, and `keepArrivedPairing` is that recognition. It is an
+ // explicit decision here, not a property of reusing a node the old code found at depth, so it
+ // gets asserted rather than measured.
+ //
+ // One query per way the rule can plan a storage-partitioned join, including a partially
+ // clustered one so the replicating path runs. Each case also pins the shape it exercises:
+ // idempotency over a plan the rule left alone proves nothing.
+ val rule = new EnsureRequirements()
+ val idCols = Array(Column.create("id", IntegerType), Column.create("data", StringType))
+ val deptCols = Array(Column.create("id", IntegerType), Column.create("dept", IntegerType),
+ Column.create("data", StringType))
+ createTable("ip1", idCols, Array(identity("id")))
+ createTable("ip2", idCols, Array(identity("id")))
+ createTable("ip3", idCols, Array(identity("id")))
+ createTable("ip4", deptCols, Array(identity("id"), identity("dept")))
+ sql("INSERT INTO testcat.ns.ip1 VALUES (1, 'x1'), (2, 'x2'), (3, 'x3')")
+ sql("INSERT INTO testcat.ns.ip2 VALUES (1, 'y1'), (2, 'y2'), (3, 'y3')")
+ // Key 1 twice, so it holds two splits and the side is not grouped. `createTable` puts one row
+ // per split, and that is what partially clustered distribution replicates the other side
+ // against. The key sets also differ ({1,2,3} vs {1,2,4}), which is what the push branch is for.
+ sql("INSERT INTO testcat.ns.ip3 VALUES (1, 'z1'), (1, 'z1b'), (2, 'z2'), (4, 'z4')")
+ sql("INSERT INTO testcat.ns.ip4 VALUES (1, 10, 'w1'), (2, 20, 'w2'), (3, 30, 'w3')")
+
+ withTable("ippt") {
+ sql("CREATE TABLE ippt (id INT, data STRING) USING parquet")
+ sql("INSERT INTO ippt VALUES (1,'p1'),(2,'p2'),(3,'p3')")
+
+ val common = Seq(
+ SQLConf.V2_BUCKETING_ENABLED.key -> "true",
+ SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
+ "spark.sql.autoBroadcastJoinThreshold" -> "-1")
+
+ val cases = Seq(
+ ("aligned as they stand",
+ Seq.empty[(String, String)],
+ "SELECT a.id FROM testcat.ns.ip1 a JOIN testcat.ns.ip2 b ON a.id = b.id",
+ (p: SparkPlan) =>
+ assert(collectAllShuffles(p).isEmpty && collectAllGroupPartitions(p).isEmpty,
+ "the two sides already line up, so the rule adds nothing")),
+ ("pushed common partition values",
+ Seq(SQLConf.V2_BUCKETING_PUSH_PART_VALUES_ENABLED.key -> "true"),
+ "SELECT a.id FROM testcat.ns.ip1 a JOIN testcat.ns.ip3 b ON a.id = b.id",
+ (p: SparkPlan) => {
+ assert(collectAllShuffles(p).isEmpty, "the merged keys are pushed, not shuffled")
+ assert(collectAllGroupPartitions(p).size == 2, "one grouping a side")
+ }),
+ ("partially clustered",
+ Seq(SQLConf.V2_BUCKETING_PUSH_PART_VALUES_ENABLED.key -> "true",
+ SQLConf.V2_BUCKETING_PARTIALLY_CLUSTERED_DISTRIBUTION_ENABLED.key -> "true"),
+ "SELECT a.id FROM testcat.ns.ip1 a JOIN testcat.ns.ip3 b ON a.id = b.id",
+ (p: SparkPlan) =>
+ assert(collectAllGroupPartitions(p).exists(_.distributePartitions),
+ "one side keeps its splits while the other is replicated across them")),
+ ("one side shuffled onto the other's keys",
+ Seq(SQLConf.V2_BUCKETING_SHUFFLE_ENABLED.key -> "true"),
+ "SELECT a.id FROM testcat.ns.ip1 a JOIN ippt t ON a.id = t.id",
+ (p: SparkPlan) =>
+ assert(collectAllShuffles(p).count(
+ _.outputPartitioning.isInstanceOf[physical.KeyedPartitioning]) == 1,
+ "the plain side is shuffled onto the keyed one")),
+ ("join keys a subset of the partition keys",
+ Seq(SQLConf.V2_BUCKETING_ALLOW_KEYS_SUBSET_OF_PARTITION_KEYS.key -> "true",
+ SQLConf.REQUIRE_ALL_CLUSTER_KEYS_FOR_CO_PARTITION.key -> "false"),
+ // `dept` is selected so column pruning keeps it: without it the scan reports a layout
+ // already narrowed to `id` and there is no subset left for the rule to project.
+ "SELECT a.id, a.dept FROM testcat.ns.ip4 a JOIN testcat.ns.ip1 b ON a.id = b.id",
+ (p: SparkPlan) =>
+ assert(collectAllGroupPartitions(p).exists(_.joinKeyPositions.isDefined),
+ s"the two-key side is projected onto the join key:\n${p.treeString}")),
+ // The shape `keepArrivedPairing` exists for, and the only one of these that needs it: a
+ // projecting grouping over the keyed side and a keyed shuffle over the other. On a second
+ // pass the peel hands the pairing a raw left that projects again, so it stops looking
+ // co-partitioned as it stands, and both sides get aligned to a key set they already hold.
+ ("a projecting grouping beside a keyed shuffle",
+ Seq(SQLConf.V2_BUCKETING_SHUFFLE_ENABLED.key -> "true",
+ SQLConf.V2_BUCKETING_ALLOW_KEYS_SUBSET_OF_PARTITION_KEYS.key -> "true",
+ SQLConf.REQUIRE_ALL_CLUSTER_KEYS_FOR_CO_PARTITION.key -> "false"),
+ "SELECT a.id, a.dept FROM testcat.ns.ip4 a JOIN ippt t ON a.id = t.id",
+ (p: SparkPlan) => {
+ assert(collectAllGroupPartitions(p).exists(_.joinKeyPositions.isDefined),
+ s"the keyed side keeps its own layout with a projection:\n${p.treeString}")
+ assert(collectAllShuffles(p).count(
+ _.outputPartitioning.isInstanceOf[physical.KeyedPartitioning]) == 1,
+ s"and the plain side is shuffled onto it:\n${p.treeString}")
+ }))
+
+ cases.foreach { case (name, confs, query, checkShape) =>
+ withSQLConf(common ++ confs: _*) {
+ val planned = rule.apply(sql(query).queryExecution.sparkPlan)
+ checkShape(planned)
+ assert(rule.apply(planned) == planned,
+ s"$name: a second pass must leave this rule's own plan alone:\n${planned.treeString}")
+ }
+ }
+ }
+ }
+
test("SPARK-59050: SPJ: regrouping a marked layout must not keep the unknown-keyed claim") {
// The union declares keys in child order [3, 4, 1, 2]; the first join one-side-shuffles rt's
// out-of-set id=5 onto it at hash(5) % 4 and marks the layout. The second join aligns that
diff --git a/sql/core/src/test/scala/org/apache/spark/sql/execution/datasources/v2/GroupPartitionsExecSuite.scala b/sql/core/src/test/scala/org/apache/spark/sql/execution/datasources/v2/GroupPartitionsExecSuite.scala
index 69686ba1420f..e653f46241e7 100644
--- a/sql/core/src/test/scala/org/apache/spark/sql/execution/datasources/v2/GroupPartitionsExecSuite.scala
+++ b/sql/core/src/test/scala/org/apache/spark/sql/execution/datasources/v2/GroupPartitionsExecSuite.scala
@@ -17,7 +17,7 @@
package org.apache.spark.sql.execution.datasources.v2
-import org.apache.spark.SparkContext
+import org.apache.spark.{SparkContext, SparkException}
import org.apache.spark.rdd.RDD
import org.apache.spark.sql.catalyst.InternalRow
import org.apache.spark.sql.catalyst.expressions.{Ascending, Attribute, AttributeReference, SortOrder, TransformExpression}
@@ -28,6 +28,7 @@ import org.apache.spark.sql.execution.{DummySparkPlan, LeafExecNode, SafeForKWay
import org.apache.spark.sql.internal.SQLConf
import org.apache.spark.sql.test.SharedSparkSession
import org.apache.spark.sql.types.{DataType, IntegerType, LongType}
+import org.apache.spark.sql.vectorized.ColumnarBatch
class GroupPartitionsExecSuite extends SharedSparkSession {
@@ -351,8 +352,8 @@ class GroupPartitionsExecSuite extends SharedSparkSession {
}
test("SPARK-59050: a grouping that rewrites the declared keys drops the claim") {
- // `identityGrouping` also asks whether the grouping rewrote the keys: the claim the node
- // goes on to declare lives in the projected or reduced key space, while the child's
+ // `PartitionGrouping.isIdentity` also asks whether the grouping rewrote the keys. The keys the
+ // node goes on to declare live in the projected or reduced key space, while the child's
// undeclared rows still sit at hash(originalKey) % numPartitions. A reducer slot, a
// narrowing projection, or a reordering projection therefore gives up the claim even when
// every group keeps its index and the count is unchanged. A conforming self-reducer cannot
@@ -639,14 +640,64 @@ class GroupPartitionsExecSuite extends SharedSparkSession {
assert(gpe.metrics("numEmptyPartitions").value === 0)
assert(gpe.metrics("numPrunedPartitions").value === 0)
}
+
+ test("SPARK-59289: the keyed claim goes when the child no longer reports what was planned") {
+ val childKp = KeyedPartitioning(Seq(exprA), Seq(row(1), row(1), row(2)))
+ val gpe = GroupPartitionsExec(DummySparkPlan(outputPartitioning = childKp))
+ assert(gpe.outputPartitioning.isInstanceOf[KeyedPartitioning],
+ "test setup: the node was planned over a keyed child and claims a keyed layout")
+ assert(gpe.outputPartitioning.numPartitions === 2, "test setup: the two 1s are grouped")
+
+ // A wrapper that passes the child's partitioning through keeps the claim, which is every
+ // rewrite the columnar and codegen rules perform.
+ val sameKp = gpe.withNewChildren(
+ Seq(DummySparkPlan(outputPartitioning = childKp))).asInstanceOf[GroupPartitionsExec]
+ assert(sameKp.outputPartitioning === gpe.outputPartitioning)
+
+ // An `AQEShuffleReadExec` over a keyed shuffle stage reports `UnknownPartitioning`, and a
+ // one-mapper-per-task local read reports the pre-shuffle partitioning. Either way the grouping
+ // indexes partitions the child no longer has, so the node stops claiming a keyed layout and
+ // `ValidateRequirements` refuses the plan, which is what makes AQE revert the rewrite.
+ Seq(
+ UnknownPartitioning(4),
+ KeyedPartitioning(Seq(exprA), Seq(row(1), row(2), row(3))),
+ KeyedPartitioning(Seq(exprB), Seq(row(1), row(1), row(2)))
+ ).foreach { changed =>
+ val rebuilt = gpe.withNewChildren(
+ Seq(DummySparkPlan(outputPartitioning = changed))).asInstanceOf[GroupPartitionsExec]
+ assert(rebuilt.outputPartitioning === UnknownPartitioning(2),
+ s"a child reporting $changed invalidates the grouping, so the claim goes")
+ assert(rebuilt.plannedPartitioning === gpe.outputPartitioning,
+ "what it was planned to report is still carried, it is just no longer reported")
+
+ // Giving up the claim is only half of it. `ValidateRequirements` rejects such a plan, but
+ // `AdaptiveSparkPlanExec.optimizeQueryStage` validates an `AQEShuffleReadRule`'s result and
+ // nothing else, so execution refuses rather than coalescing the new child on the old indices.
+ // Both paths are checked, since each has its own call.
+ val e = intercept[SparkException](rebuilt.execute())
+ assert(e.getMessage.contains("no longer reports the partitioning it was planned over"))
+
+ val columnarPlanned = GroupPartitionsExec(
+ DummyLeafSparkPlan(outputPartitioning = childKp, supportsColumnar = true))
+ val columnarRebuilt = columnarPlanned.withNewChildren(Seq(
+ DummyLeafSparkPlan(outputPartitioning = changed, supportsColumnar = true)))
+ .asInstanceOf[GroupPartitionsExec]
+ assert(columnarRebuilt.supportsColumnar, "test setup: the columnar path is the one taken")
+ val ce = intercept[SparkException](columnarRebuilt.executeColumnar())
+ assert(ce.getMessage.contains("no longer reports the partitioning it was planned over"))
+ }
+ }
}
private case class DummyLeafSparkPlan(
override val outputOrdering: Seq[SortOrder] = Nil,
- override val outputPartitioning: Partitioning = UnknownPartitioning(0)
+ override val outputPartitioning: Partitioning = UnknownPartitioning(0),
+ override val supportsColumnar: Boolean = false
) extends LeafExecNode with SafeForKWayMerge {
override protected def doExecute(): RDD[InternalRow] =
throw new UnsupportedOperationException
+ override protected def doExecuteColumnar(): RDD[ColumnarBatch] =
+ throw new UnsupportedOperationException
override def output: Seq[Attribute] = Seq.empty
}
diff --git a/sql/core/src/test/scala/org/apache/spark/sql/execution/exchange/EnsureRequirementsSuite.scala b/sql/core/src/test/scala/org/apache/spark/sql/execution/exchange/EnsureRequirementsSuite.scala
index ad7e93664b01..83e3e07dcb44 100644
--- a/sql/core/src/test/scala/org/apache/spark/sql/execution/exchange/EnsureRequirementsSuite.scala
+++ b/sql/core/src/test/scala/org/apache/spark/sql/execution/exchange/EnsureRequirementsSuite.scala
@@ -1070,10 +1070,10 @@ class EnsureRequirementsSuite extends SharedSparkSession {
case SortMergeJoinExec(_, _, _, _,
SortExec(_, _,
GroupPartitionsExec(DummySparkPlan(_, _, left: KeyedPartitioning, _, _),
- _, _, _, _, _), _),
+ _, _, _, _, _, _, _, _), _),
SortExec(_, _,
GroupPartitionsExec(DummySparkPlan(_, _, right: KeyedPartitioning, _, _),
- _, _, _, _, _), _),
+ _, _, _, _, _, _, _, _), _),
_) =>
assert(left.expressions === Seq(bucket(4, exprB), bucket(8, exprC)))
assert(right.expressions === Seq(bucket(4, exprC), bucket(8, exprB)))
@@ -1094,10 +1094,10 @@ class EnsureRequirementsSuite extends SharedSparkSession {
case SortMergeJoinExec(_, _, _, _,
SortExec(_, _,
GroupPartitionsExec(DummySparkPlan(_, _, left: PartitioningCollection, _, _),
- _, _, _, _, _), _),
+ _, _, _, _, _, _, _, _), _),
SortExec(_, _,
GroupPartitionsExec(DummySparkPlan(_, _, right: KeyedPartitioning, _, _),
- _, _, _, _, _), _),
+ _, _, _, _, _, _, _, _), _),
_) =>
assert(left.partitionings.length == 2)
assert(left.partitionings.head.isInstanceOf[KeyedPartitioning])
@@ -1129,10 +1129,10 @@ class EnsureRequirementsSuite extends SharedSparkSession {
case SortMergeJoinExec(_, _, _, _,
SortExec(_, _,
GroupPartitionsExec(DummySparkPlan(_, _, left: PartitioningCollection, _, _),
- _, _, _, _, _), _),
+ _, _, _, _, _, _, _, _), _),
SortExec(_, _,
GroupPartitionsExec(DummySparkPlan(_, _, right: PartitioningCollection, _, _),
- _, _, _, _, _), _),
+ _, _, _, _, _, _, _, _), _),
_) =>
assert(left.partitionings.length == 2)
assert(left.partitionings.head.isInstanceOf[KeyedPartitioning])
@@ -1737,7 +1737,7 @@ class EnsureRequirementsSuite extends SharedSparkSession {
val plannedLeft = EnsureRequirements.apply(leftOuter)
assert(plannedLeft.collect { case s: ShuffleExchangeExec => s }.isEmpty,
"every pairing agrees on the keys, so neither side is shuffled whichever one wins")
- assert(groupPartitionsNodes(plannedLeft).map(_.expectedPartitionKeys.map(_.size)) ===
+ assert(groupPartitionsNodes(plannedLeft).map(_.expectedKeyCount) ===
Seq(Some(6), Some(6)),
"the join runs on the surviving side's best member, not on the dropped side's")
@@ -1747,7 +1747,7 @@ class EnsureRequirementsSuite extends SharedSparkSession {
val plannedRight = EnsureRequirements.apply(rightOuter)
assert(plannedRight.collect { case s: ShuffleExchangeExec => s }.isEmpty,
"and neither side is shuffled here either")
- assert(groupPartitionsNodes(plannedRight).map(_.expectedPartitionKeys.map(_.size)) ===
+ assert(groupPartitionsNodes(plannedRight).map(_.expectedKeyCount) ===
Seq(Some(8), Some(8)),
"the surviving side is the right one now, so its best member decides")
}
@@ -1784,7 +1784,7 @@ class EnsureRequirementsSuite extends SharedSparkSession {
// onto the default partitioning.
assert(planned.collect { case s: ShuffleExchangeExec => s }.isEmpty,
"the second member pairs with the other side, so neither side is shuffled")
- assert(groupPartitionsNodes(planned).map(_.expectedPartitionKeys.map(_.size)) ===
+ assert(groupPartitionsNodes(planned).map(_.expectedKeyCount) ===
Seq(Some(3), Some(3)),
"both sides are pushed the union of the two key sets")
}
@@ -1832,7 +1832,7 @@ class EnsureRequirementsSuite extends SharedSparkSession {
KeyedPartitioning(Seq(exprKey), Seq(InternalRow(1), InternalRow(2), InternalRow(3))))
// `requiredNumPartitions` is a hard requirement - `Partitioning.satisfies` refuses to satisfy a
// distribution whose partition count differs, and neither `keysSatisfy` nor
- // `nonGroupedSatisfies` checks it on its own. A stateful streaming operator asks for this shape
+ // `satisfies0` checks it on its own. A stateful streaming operator asks for this shape
// through `StatefulOperatorPartitioning.getCompatibleDistribution`.
val parent = parentRequiring(
child,
@@ -1856,13 +1856,13 @@ class EnsureRequirementsSuite extends SharedSparkSession {
assert(EnsureRequirements.apply(parent).children.head eq child)
}
- test("SPARK-58968: a partitioning that covers no operation key is shuffled, not projected") {
+ test("SPARK-58968: a partitioning that covers no cluster key is shuffled, not projected") {
val exprKey = AttributeReference("k", IntegerType)()
// Nothing at `KeyedPartitioning` construction requires a partition expression to reference a
// column. A DSv2 scan cannot report one that does not, because `supportsExpressions` refuses
// it, but no other producer is held to that, so a reference-free expression is possible here.
//
- // Such a partitioning has no attributes to check against the operation keys, which makes
+ // Such a partitioning has no attributes to check against the cluster keys, which makes
// `keysSatisfy` vacuously true, and it covers no position to project onto. Projecting to
// no position at all would put every row on a single partition, so the child has to be
// shuffled.
@@ -1911,9 +1911,9 @@ class EnsureRequirementsSuite extends SharedSparkSession {
}
test("SPARK-58968: a transform position is kept when its reference is a cluster key") {
- // `clusterKeyPositions` keeps a position two ways. The other tests all keep plain attributes,
- // which the expression-level test matches on its own, so this is the one that turns on the
- // reference-level test: `bucket(4, a)` is not a cluster key, its reference `a` is.
+ // `positionsCoveringClusterKeys` keeps a position two ways. The other tests all keep plain
+ // attributes, which the expression-level test matches on its own, so this is the one that
+ // turns on the reference-level test: `bucket(4, a)` is not a cluster key, its reference `a` is.
//
// It is also the shape the soundness argument is about. `keysSatisfy`'s subset branch requires
// every expression to have a single reference, so a kept expression is a function of one
@@ -1979,7 +1979,7 @@ class EnsureRequirementsSuite extends SharedSparkSession {
"groups") {
val exprN = AttributeReference("n", IntegerType)()
val exprI = AttributeReference("i", IntegerType)()
- // Three partitions on (n, i), and projecting to the operation key [i] leaves two, which is
+ // Three partitions on (n, i), and projecting to the cluster key [i] leaves two, which is
// what the distribution asks for. It mirrors the test below, where the projected count misses
// the requirement and we shuffle. Here it matches and the node is the right answer.
val keys = Seq(InternalRow(1, 1), InternalRow(2, 1), InternalRow(3, 2))
@@ -1992,7 +1992,7 @@ class EnsureRequirementsSuite extends SharedSparkSession {
withSQLConf(SQLConf.V2_BUCKETING_ALLOW_KEYS_SUBSET_OF_PARTITION_KEYS.key -> "true") {
val newChild = EnsureRequirements.apply(parent).children.head
assert(groupPartitionsNodes(newChild).map(_.joinKeyPositions) ==
- Seq(Some(Seq(1))), "expected a node projecting to the operation key [i]")
+ Seq(Some(Seq(1))), "expected a node projecting to the cluster key [i]")
assert(newChild.collect { case s: ShuffleExchangeExec => s }.isEmpty, "no shuffle needed")
assert(newChild.outputPartitioning.numPartitions == 2)
}
@@ -2019,7 +2019,7 @@ class EnsureRequirementsSuite extends SharedSparkSession {
test("SPARK-58968: a projection that would break requiredNumPartitions falls back to a shuffle") {
val exprN = AttributeReference("n", IntegerType)()
val exprI = AttributeReference("i", IntegerType)()
- // Partitioned by (n, i) with three partitions. Projecting to the operation key [i] leaves two.
+ // Partitioned by (n, i) with three partitions. Projecting to the cluster key [i] leaves two.
val keys = Seq(InternalRow(1, 1), InternalRow(2, 1), InternalRow(3, 2))
val child = new DummySparkPlanWithBatchScanChild(
outputPartitioning = KeyedPartitioning(Seq(exprN, exprI), keys))
@@ -2158,13 +2158,13 @@ class EnsureRequirementsSuite extends SharedSparkSession {
}
}
- test("SPARK-58968: the candidate covering the most operation keys wins") {
+ test("SPARK-58968: the candidate covering the most cluster keys wins") {
// Partition keys are (a, <second key column>, y). Projecting to the first position alone
// leaves 2 partitions, projecting to the first two leaves 3.
val keys = Seq(
InternalRow(1, 1, 1), InternalRow(1, 1, 2), InternalRow(1, 2, 3), InternalRow(2, 2, 4))
// Two members of one collection name the second key column differently. `x` is not a cluster
- // key and `b` is, so they disagree on how many operation keys they cover, one against two.
+ // key and `b` is, so they disagree on how many cluster keys they cover, one against two.
// Only the wider one keeps partitions that share an `a` but differ in `b` apart, which is why
// the widest coverage is picked rather than the first member. `copy` keeps the `partitionKeys`
// reference `PartitioningCollection` requires its members to share.
@@ -2179,14 +2179,14 @@ class EnsureRequirementsSuite extends SharedSparkSession {
val newChild = EnsureRequirements.apply(parent).children.head
val gpes = groupPartitionsNodes(newChild)
assert(gpes.map(_.joinKeyPositions) == Seq(Some(Seq(0, 1))),
- "the projection must come from the member covering both operation keys")
+ "the projection must come from the member covering both cluster keys")
assert(gpes.map(_.groupedPartitions.size) == Seq(3))
}
}
test("SPARK-58968: the candidate whose projection leaves the most partitions wins") {
// The first key column has 2 distinct values, the second 3. Both members below cover one
- // operation key, so the coverage prefilter keeps both and the projected counts decide.
+ // cluster key, so the coverage prefilter keeps both and the projected counts decide.
val keys = Seq(
InternalRow(1, 5, 1), InternalRow(1, 6, 2), InternalRow(2, 7, 3), InternalRow(2, 7, 4))
// The member leaving fewer partitions comes first, so taking the first, or the fewest, gives
@@ -2209,7 +2209,7 @@ class EnsureRequirementsSuite extends SharedSparkSession {
test("SPARK-58968: equally covering candidates follow the child's own order") {
// Projecting to either of the first two key columns leaves 2 partitions, so the two members
- // below cover one operation key each and their projections are equally good. Nothing ranks
+ // below cover one cluster key each and their projections are equally good. Nothing ranks
// them. The choice is still visible in the plan, because they project to different keys, so it
// follows the order the child reports its partitionings in.
val keys = Seq(
@@ -2333,43 +2333,31 @@ class EnsureRequirementsSuite extends SharedSparkSession {
}
}
- test("SPARK-58996: only a local sort is looked through when reusing GroupPartitionsExec") {
+ test("SPARK-58996: only a local sort is looked through when peeling GroupPartitionsExec") {
// A global `SortExec` requires `OrderedDistribution`, which a `KeyedPartitioning` can satisfy
// (behind `spark.sql.sources.v2.bucketing.sorting.enabled`) through a `GroupPartitionsExec`
- // built to emit the partition keys in sorted order. Reusing that node for a join would
- // overwrite its `expectedPartitionKeys` and clear `distributePartitions`, destroying the
+ // built to emit the partition keys in sorted order. Peeling that node off would destroy the
// ordering it exists to provide. Only a local sort may be looked through.
val leaf = DummySparkPlan(
outputPartitioning = KeyedPartitioning(Seq(exprA), Seq(InternalRow(1), InternalRow(2))))
val gpe = GroupPartitionsExec(leaf)
val ordering = Seq(SortOrder(exprA, Ascending))
- def mark(g: GroupPartitionsExec): GroupPartitionsExec = g.copy(distributePartitions = true)
- // A bare GroupPartitionsExec is rewritten in place.
- EnsureRequirements.rewriteGroupPartitions(gpe)(mark) match {
- case Some(g: GroupPartitionsExec) => assert(g.distributePartitions)
- case other => fail(s"expected a rewritten GroupPartitionsExec, got $other")
- }
+ // A bare GroupPartitionsExec is peeled off.
+ assert(EnsureRequirements.peelGroupPartitions(gpe) === leaf)
- // A local sort is looked through and the GroupPartitionsExec below it is rewritten.
+ // A local sort is looked through and the GroupPartitionsExec below it is peeled off too.
val localSort = SortExec(ordering, global = false, gpe)
- EnsureRequirements.rewriteGroupPartitions(localSort)(mark) match {
- case Some(SortExec(_, false, g: GroupPartitionsExec, _)) => assert(g.distributePartitions)
- case other => fail(s"expected the local sort to be looked through, got $other")
- }
+ assert(EnsureRequirements.peelGroupPartitions(localSort) === leaf)
- // A grouping stacked over another is dropped and the node below is rewritten.
- EnsureRequirements.rewriteGroupPartitions(GroupPartitionsExec(localSort))(mark) match {
- case Some(SortExec(_, false, g: GroupPartitionsExec, _)) =>
- assert(g.distributePartitions, "the stacked grouping must be dropped and the node " +
- "below it rewritten")
- case other => fail(s"expected the stacked grouping to be dropped, got $other")
- }
+ // A grouping stacked over another is peeled off with everything below it.
+ assert(EnsureRequirements.peelGroupPartitions(GroupPartitionsExec(localSort)) === leaf,
+ "a stacked grouping must be peeled off down to the pre-alignment plan")
- // A global sort is not looked through, so the caller wraps instead of reusing.
+ // A global sort stops the descent, so the plan comes back untouched.
val globalSort = SortExec(ordering, global = true, gpe)
- assert(EnsureRequirements.rewriteGroupPartitions(globalSort)(mark).isEmpty,
- "a GroupPartitionsExec below a global sort must never be reused")
+ assert(EnsureRequirements.peelGroupPartitions(globalSort) === globalSort,
+ "a GroupPartitionsExec below a global sort must never be peeled off")
}
test("SPARK-58996: withJoinKeyPositions reuses only a topmost GroupPartitionsExec") {
@@ -2402,27 +2390,37 @@ class EnsureRequirementsSuite extends SharedSparkSession {
}
}
+ test("SPARK-59289: an aligned grouping is wrapped by withJoinKeyPositions, not rebuilt") {
+ // The rebuild reads `g.child` and reproduces a plain grouping, which is neither a merged key
+ // count, nor a reducer, nor a replication. So a node carrying one of those is wrapped instead:
+ // the positions index what it reports, and that is what the node built over it projects.
+ //
+ // The rebuild is this change's: the base replaced a node's positions with a `copy`, which
+ // re-derives nothing and so had no case to tell apart. A re-run can hand this site an aligned
+ // node, and a planner crash would be the wrong answer where a sound plan is available.
+ val leaf = DummySparkPlan(outputPartitioning =
+ KeyedPartitioning(Seq(exprA, exprB), Seq(InternalRow(1, 1), InternalRow(1, 1))))
+ val aligned = GroupPartitionsExec(leaf, expectedPartitionKeys = Some(Seq(
+ (InternalRowComparableWrapper(InternalRow(1, 1), Seq(exprA, exprB)), 2))))
+ assert(aligned.expectedKeyCount.isDefined, "test setup: this is an aligned node")
+
+ EnsureRequirements.withJoinKeyPositions(aligned, Seq(0)) match {
+ case g: GroupPartitionsExec =>
+ assert(g.joinKeyPositions === Some(Seq(0)))
+ assert(g.child eq aligned, "the aligned node keeps its merge and stays below the new one")
+ case other => fail(s"expected a wrapping GroupPartitionsExec, got $other")
+ }
+ }
+
test("SPARK-58996: reusing a GroupPartitionsExec keeps its tags") {
// Tags are instance state that a `copy` does not carry, so every rewrite must copy them
- // back onto the new node.
+ // back onto the new node. The join path no longer rewrites a node, it peels the old one off
+ // and builds a fresh one, so only the non-join path is left to check.
val tag = TreeNodeTag[String]("test tag")
val leaf = DummySparkPlan(
outputPartitioning = KeyedPartitioning(Seq(exprA), Seq(InternalRow(1), InternalRow(2))))
val gpe = GroupPartitionsExec(leaf)
gpe.setTagValue(tag, "kept")
- val ordering = Seq(SortOrder(exprA, Ascending))
-
- // The join path: a bare node and one behind a local sort.
- EnsureRequirements.rewriteGroupPartitions(gpe)(_.copy(distributePartitions = true)) match {
- case Some(g: GroupPartitionsExec) => assert(g.getTagValue(tag) === Some("kept"))
- case other => fail(s"expected a rewritten GroupPartitionsExec, got $other")
- }
- EnsureRequirements.rewriteGroupPartitions(SortExec(ordering, global = false, gpe))(
- _.copy(distributePartitions = true)) match {
- case Some(SortExec(_, false, g: GroupPartitionsExec, _)) =>
- assert(g.getTagValue(tag) === Some("kept"))
- case other => fail(s"expected the local sort to be looked through, got $other")
- }
// The non-join path: a topmost node is rewritten in place.
EnsureRequirements.withJoinKeyPositions(gpe, Seq(0)) match {
@@ -2546,10 +2544,10 @@ class EnsureRequirementsSuite extends SharedSparkSession {
// is legitimate. See the aggregate and window cases in `KeyGroupedPartitioningSuite`.
//
// With one child the multi-child block never runs, so this does not exercise
- // `rewriteGroupPartitions`: it pins the intentional non-idempotence of the children loop's
+ // the peel: it pins the intentional non-idempotence of the children loop's
// wrap for single-child operators. If that wrap were "generalized" into a reuse of the node
// below, the returned child would stay non-grouped and this assertion would fail, which is
- // exactly what the `rewriteGroupPartitions` scaladoc argues must not happen.
+ // exactly what the `peelGroupPartitions` scaladoc argues must not happen.
val leaf = DummySparkPlan(
outputPartitioning = KeyedPartitioning(
Seq(exprA), Seq(InternalRow(1), InternalRow(1), InternalRow(2))))
@@ -2732,7 +2730,7 @@ class EnsureRequirementsSuite extends SharedSparkSession {
assert(planned.collect { case s: ShuffleExchangeExec => s }.isEmpty,
s"$joinType: a marked pair keeps its storage-partitioned join either way:\n" +
planned.treeString)
- assert(groupPartitionsNodes(planned).map(_.expectedPartitionKeys.map(_.size)) ===
+ assert(groupPartitionsNodes(planned).map(_.expectedKeyCount) ===
Seq(Some(3), Some(3)),
s"$joinType: both sides are pushed the marked side's three keys:\n" +
planned.treeString)
@@ -2744,6 +2742,185 @@ class EnsureRequirementsSuite extends SharedSparkSession {
}
}
+ test("SPARK-59289: a grouped side is paired on its own key order, not a sorted one") {
+ // Both sides are grouped, so neither gets a node to reorder anything, and the left's keys are
+ // not sorted. Planning the pairing against `toGrouped`, which sorts, would claim an order the
+ // left does not have: the two would look compatible, the left would keep its own report and
+ // the right would keep the sorted one, and the join would carry two `KeyedPartitioning`s over
+ // different keys. `toGrouped` is therefore only for a source that is not grouped.
+ val unsorted = Seq(InternalRow(3), InternalRow(4), InternalRow(1), InternalRow(2))
+ val sorted = Seq(InternalRow(1), InternalRow(2), InternalRow(3), InternalRow(4))
+ val left = DummySparkPlan(outputPartitioning = KeyedPartitioning(Seq(exprA), unsorted))
+ val right = DummySparkPlan(outputPartitioning = KeyedPartitioning(Seq(exprB), sorted))
+ val smj = SortMergeJoinExec(exprA :: Nil, exprB :: Nil, Inner, None, left, right)
+
+ withSQLConf(SQLConf.V2_BUCKETING_ENABLED.key -> "true") {
+ val planned = EnsureRequirements.apply(smj)
+ val declared = planned.children.map { child =>
+ child.outputPartitioning.asInstanceOf[Expression]
+ .collectFirst { case k: KeyedPartitioning => k.partitionKeys }
+ }
+ assert(declared.forall(_.isDefined), s"both sides stay keyed:\n${planned.treeString}")
+ assert(declared.head == declared(1),
+ s"both sides must declare one key sequence:\n${planned.treeString}")
+ }
+ }
+
+ test("SPARK-59289: pushing join key positions into a node re-derives its grouping") {
+ // The positions are an input to the node's grouping, so `withJoinKeyPositions` rebuilds through
+ // the factory. A `copy` would keep the grouping the old positions produced, and nothing about
+ // the node would look wrong.
+ val keys = Seq(InternalRow(1, 1), InternalRow(1, 2))
+ val leaf = DummySparkPlan(
+ outputPartitioning = KeyedPartitioning(Seq(exprA, exprB), keys))
+ val coalescing = GroupPartitionsExec(leaf)
+ assert(coalescing.outputPartitioning.numPartitions == 2, "test setup: nothing merged yet")
+
+ val projected = EnsureRequirements.withJoinKeyPositions(coalescing, Seq(0))
+ assert(projected.outputPartitioning.numPartitions == 1,
+ "projecting [a, b] onto [a] merges the two partitions that share a = 1")
+ }
+
+ test("SPARK-59289: single-partition children still honour a required partition count") {
+ // Both sides are already `SinglePartition` and small, so there is no co-partitioning to
+ // arrange. Each child still has to satisfy its own requirement, and a stateful operator's
+ // `ClusteredDistribution` carries a partition count that one partition does not meet.
+ val logicalPlan = StatsTestPlan(Nil, 1L, AttributeMap.empty, Some(1L))
+ val left = DummySparkPlan(outputPartitioning = SinglePartition)
+ left.setLogicalLink(logicalPlan)
+ val right = DummySparkPlan(outputPartitioning = SinglePartition)
+ right.setLogicalLink(logicalPlan)
+ val parent = DummySparkPlan(
+ children = Seq(left, right),
+ requiredChildDistribution = Seq(
+ ClusteredDistribution(Seq(exprA), requiredNumPartitions = Some(5)),
+ ClusteredDistribution(Seq(exprC), requiredNumPartitions = Some(5))),
+ requiredChildOrdering = Seq(Nil, Nil))
+
+ val planned = EnsureRequirements.apply(parent)
+ assert(ValidateRequirements.validate(planned),
+ s"each child must satisfy its own distribution:\n${planned.treeString}")
+ }
+
+ test("SPARK-59289: a local sort with no grouping under it is left alone") {
+ // `peelGroupPartitions` peels the local sorts this rule added over a grouping. A sort with no
+ // grouping beneath it is the user's `sortWithinPartitions`, and the ordering step only puts
+ // back the ordering the operator required, so peeling it would lose that ordering for good.
+ val keys = Seq(InternalRow(1), InternalRow(2))
+ val leaf = DummySparkPlan(outputPartitioning = KeyedPartitioning(Seq(exprA), keys))
+ val userSort = SortExec(Seq(SortOrder(exprB, Ascending)), global = false, leaf)
+ assert(EnsureRequirements.peelGroupPartitions(userSort) === userSort)
+
+ // Over a grouping it is this rule's own, and both come off.
+ val ruleSort = SortExec(Seq(SortOrder(exprB, Ascending)), global = false,
+ GroupPartitionsExec(leaf))
+ assert(EnsureRequirements.peelGroupPartitions(ruleSort) === leaf)
+ }
+
+ test("SPARK-59289: a partitioning is never projected onto no position") {
+ // The co-partitioned path takes its projection positions from `KeyedShuffleSpec.keyPositions`,
+ // which maps an expression's single *reference* onto the clustering. `keysSatisfy` also
+ // accepts an expression that *is* a cluster key, through
+ // `KeyedPartitioning.positionsCoveringClusterKeys`. This is the shape where the two disagree:
+ // the join keys name `years(ts)`, so the spec is built, and then no position covers a cluster
+ // key.
+ //
+ // Projecting onto no position coalesces every partition into one. Before the guard in
+ // `createShuffleSpec` this planned as a storage-partitioned join over a single partition per
+ // side, two `GroupPartitionsExec`s and no shuffle, which is correct and ruinous. The spec now
+ // comes back unprojected, `areKeysCompatible` refuses it, and the join takes the shuffle.
+ val exprTs = AttributeReference("ts", IntegerType)()
+ val transform = years(exprTs)
+ val keys = Seq(InternalRow(1), InternalRow(2))
+ val left = DummySparkPlan(outputPartitioning = KeyedPartitioning(Seq(transform), keys))
+ val right = DummySparkPlan(outputPartitioning = KeyedPartitioning(Seq(transform), keys))
+ val smj = SortMergeJoinExec(transform :: Nil, transform :: Nil, Inner, None, left, right)
+ withSQLConf(
+ SQLConf.V2_BUCKETING_ENABLED.key -> "true",
+ SQLConf.REQUIRE_ALL_CLUSTER_KEYS_FOR_CO_PARTITION.key -> "false",
+ SQLConf.V2_BUCKETING_ALLOW_KEYS_SUBSET_OF_PARTITION_KEYS.key -> "true") {
+ val planned = EnsureRequirements.apply(smj)
+ assert(groupPartitionsNodes(planned).isEmpty,
+ "a grouping here could only be the one that collapses both sides onto a single partition")
+ assert(planned.collect { case s: ShuffleExchangeExec => s }.size == 2,
+ "neither side can serve the distribution, so both are shuffled")
+ }
+ }
+
+ test("SPARK-59289: a second pass leaves a pairing this rule already made alone") {
+ val aL = AttributeReference("aL", IntegerType)()
+ val bL = AttributeReference("bL", IntegerType)()
+ val bR = AttributeReference("bR", IntegerType)()
+ // The left is keyed on (aL, bL) and the join is on bL alone, so the left's spec projects onto
+ // position 1, and the right, which reports nothing, is shuffled onto that layout. The first
+ // pass therefore ends with a projecting grouping node over the left and a keyed shuffle over
+ // the right. That is the shape the second pass used to re-pair: peeling the node hands the
+ // pairing a raw left that projects again, so it stopped being co-partitioned as it stands and
+ // both sides were aligned to a merged key set they already held.
+ val leftKeys = Seq(InternalRow(1, 10), InternalRow(2, 20))
+ val left = new DummySparkPlanWithBatchScanChild(
+ outputPartitioning = KeyedPartitioning(Seq(aL, bL), leftKeys))
+ val right = DummySparkPlan(outputPartitioning = UnknownPartitioning(3))
+
+ withSQLConf(
+ SQLConf.V2_BUCKETING_SHUFFLE_ENABLED.key -> "true",
+ SQLConf.V2_BUCKETING_ALLOW_KEYS_SUBSET_OF_PARTITION_KEYS.key -> "true",
+ SQLConf.REQUIRE_ALL_CLUSTER_KEYS_FOR_CO_PARTITION.key -> "false") {
+ val smj = SortMergeJoinExec(Seq(bL), Seq(bR), Inner, None, left, right)
+ val planned = EnsureRequirements.apply(smj)
+ assert(groupPartitionsNodes(planned).map(_.joinKeyPositions) === Seq(Some(Seq(1))),
+ "test setup: the left keeps its own layout with a projection")
+ assert(planned.collect { case s: ShuffleExchangeExec => s }.size == 1,
+ "test setup: the right is shuffled onto it")
+
+ assert(EnsureRequirements.apply(planned) == planned,
+ "the rule must leave a plan it has already paired alone")
+ }
+ }
+
+ test("SPARK-59289: pushed positions compose with the ones a node already carries") {
+ val aL = AttributeReference("aL", IntegerType)()
+ val cL = AttributeReference("cL", IntegerType)()
+ val tsL = AttributeReference("tsL", IntegerType)()
+ val tsR = AttributeReference("tsR", IntegerType)()
+ val aR = AttributeReference("aR", IntegerType)()
+ // Partitioned by [bucket(4, cL), years(tsL), aL] and clustered on [years(tsL), aL], so the two
+ // position derivations disagree twice over. `positionsCoveringClusterKeys` keeps 1 and 2,
+ // because `years(tsL)` *is* a clustering key while `cL` is not named at all.
+ // `KeyedShuffleSpec.keyPositions` reads an expression's reference instead, so over the
+ // projected report [years(tsL), aL] it keeps only position 1, `tsL` being no clustering key of
+ // its own.
+ //
+ // The right side reports nothing, so the pairing declines and the shuffle step pushes that 1
+ // into the node the per-child step already built. Read as a raw position it means
+ // `years(tsL)`, and the join would run grouped on the wrong column. Composed through the
+ // node's own [1, 2] it means `aL`, which is what the clustering asked for.
+ // Projecting onto 1 and 2 merges the first two, so the source does not satisfy as it stands
+ // and the per-child step really does put a projecting node there.
+ val keys = Seq(InternalRow(1, 1, 1), InternalRow(2, 1, 1), InternalRow(3, 2, 2))
+ val left = new DummySparkPlanWithBatchScanChild(
+ outputPartitioning =
+ KeyedPartitioning(Seq(bucket(4, cL), years(tsL), aL), keys))
+ val right = DummySparkPlan(outputPartitioning = UnknownPartitioning(3))
+ val parent = DummySparkPlan(
+ children = Seq(left, right),
+ requiredChildDistribution = Seq(
+ ClusteredDistribution(Seq(years(tsL), aL)), ClusteredDistribution(Seq(tsR, aR))),
+ requiredChildOrdering = Seq(Nil, Nil))
+
+ withSQLConf(
+ SQLConf.V2_BUCKETING_ENABLED.key -> "true",
+ SQLConf.V2_BUCKETING_SHUFFLE_ENABLED.key -> "true",
+ SQLConf.REQUIRE_ALL_CLUSTER_KEYS_FOR_CO_PARTITION.key -> "false",
+ SQLConf.V2_BUCKETING_ALLOW_KEYS_SUBSET_OF_PARTITION_KEYS.key -> "true") {
+ val planned = EnsureRequirements.apply(parent)
+ val reported = planned.children.head.outputPartitioning.asInstanceOf[Expression]
+ .collectFirst { case k: KeyedPartitioning => k.expressions }
+ assert(reported.contains(Seq(aL)),
+ s"the left must end up grouped on aL, not on years(tsL), got $reported")
+ }
+ }
+
private def anyGpeEnabled(plan: SparkPlan): Boolean =
plan.collectFirst { case gpe: GroupPartitionsExec if gpe.enableSortedMerge => true }.isDefined
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@spark.apache.org
For additional commands, e-mail: commits-help@spark.apache.org