Skip to content

Commit 2e0fb63

Browse files
committed
fix: send no streamed order when a Comet join that may move rows produces it
A cache reports the order of the plan that wrote it, so the output of a native null-aware anti join, an outer hash join whose probe order the native planner did not declare, or a nested loop join can reach an outer hash join as a JVM input whose reported order does not hold. Declaring that order put the aggregates above the join in sorted mode over unsorted rows, which split groups. CometHashJoin.doConvert now walks down the streamed side, through CometScanWrapper and into the plan that wrote any cache it reads, and sends no order when such a join produces it with no sort in between.
1 parent 2f95eef commit 2e0fb63

2 files changed

Lines changed: 292 additions & 19 deletions

File tree

‎spark/src/main/scala/org/apache/spark/sql/comet/operators.scala‎

Lines changed: 44 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,7 @@ import org.apache.spark.sql.comet.util.Utils
4242
import org.apache.spark.sql.execution._
4343
import org.apache.spark.sql.execution.adaptive.{AQEShuffleReadExec, BroadcastQueryStageExec, QueryStageExec, ShuffleQueryStageExec}
4444
import org.apache.spark.sql.execution.aggregate.{BaseAggregateExec, HashAggregateExec, ObjectHashAggregateExec, SortAggregateExec}
45+
import org.apache.spark.sql.execution.columnar.InMemoryTableScanExec
4546
import org.apache.spark.sql.execution.exchange.ReusedExchangeExec
4647
import org.apache.spark.sql.execution.joins.{BroadcastHashJoinExec, BroadcastNestedLoopJoinExec, HashJoin, ShuffledHashJoinExec, SortMergeJoinExec}
4748
import org.apache.spark.sql.execution.metric.{SQLMetric, SQLMetrics}
@@ -2876,12 +2877,22 @@ trait CometHashJoin {
28762877
// output is not in the order Spark reports for it, and the planner declares no order above
28772878
// it.
28782879
//
2880+
// The order Spark reports can be false to begin with. A Comet join that may move its
2881+
// streamed rows reports it all the same: the null-aware anti join, a right outer join like
2882+
// this one whose probe input declared no order, and the nested loop join, which keeps the
2883+
// order of neither input. A cache reports the order of the plan that wrote it, so the rows
2884+
// of such a join can reach this one through a cache, as a JVM input that the native planner
2885+
// cannot look behind. Declaring the order there would let an operator above rely on it, an
2886+
// aggregate in sorted mode for instance, which then splits groups. So nothing is declared
2887+
// when such a join feeds the streamed side with no sort in between.
2888+
//
28792889
// Declaring any order makes DataFusion keep the probe rows in place, so the longest prefix
28802890
// of the order that Comet can express is enough. Nothing here can tell whether an operator
28812891
// above relies on the order, so a join whose first key Comet cannot express stays in Spark.
2892+
val streamed = if (join.buildSide == BuildRight) join.left else join.right
28822893
val streamedSortOrders = (join.joinType, join.buildSide) match {
2883-
case (LeftOuter, BuildRight) | (RightOuter, BuildLeft) if join.outputOrdering.nonEmpty =>
2884-
val streamed = if (join.buildSide == BuildRight) join.left else join.right
2894+
case (LeftOuter, BuildRight) | (RightOuter, BuildLeft)
2895+
if join.outputOrdering.nonEmpty && !mayReportFalseOrder(streamed) =>
28852896
val orders = join.outputOrdering.iterator
28862897
.map(exprToProto(_, streamed.output))
28872898
.takeWhile(_.isDefined)
@@ -2917,6 +2928,37 @@ trait CometHashJoin {
29172928
None
29182929
}
29192930
}
2931+
2932+
// Whether a Comet join that may move its streamed rows, while reporting Spark's order for
2933+
// them, feeds the order that `plan` reports with no sort in between. Whether an outer join
2934+
// declared the order on its probe input is up to the native planner, so every one built that
2935+
// way counts. A cache reports the order of the plan that wrote it, so the walk goes on into
2936+
// that plan. While CometExecRule converts a plan, a native plan's JVM inputs sit behind a
2937+
// CometScanWrapper, a leaf, so the walk looks through that too.
2938+
private def mayReportFalseOrder(plan: SparkPlan): Boolean = plan match {
2939+
case _ if plan.outputOrdering.isEmpty => false
2940+
case _: SortExec | _: CometSortExec => false
2941+
case join: CometBroadcastHashJoinExec
2942+
if join.isNullAwareAntiJoin || runsAsRightOuterJoin(join.joinType, join.buildSide) =>
2943+
true
2944+
case join: CometHashJoinExec if runsAsRightOuterJoin(join.joinType, join.buildSide) => true
2945+
case _: CometBroadcastNestedLoopJoinExec => true
2946+
case wrapper: CometScanWrapper => mayReportFalseOrder(wrapper.originalPlan)
2947+
case scan: CometInMemoryTableScanExec =>
2948+
mayReportFalseOrder(scan.originalPlan.relation.cachedPlan)
2949+
case scan: InMemoryTableScanExec => mayReportFalseOrder(scan.relation.cachedPlan)
2950+
case stage: QueryStageExec => mayReportFalseOrder(stage.plan)
2951+
case _ => plan.children.exists(mayReportFalseOrder)
2952+
}
2953+
2954+
// A left outer join built on the right and a right outer join built on the left both run as
2955+
// DataFusion's right outer join, which keeps its unmatched probe rows in place only when the
2956+
// probe input declares an order.
2957+
private def runsAsRightOuterJoin(joinType: JoinType, buildSide: BuildSide): Boolean =
2958+
(joinType, buildSide) match {
2959+
case (LeftOuter, BuildRight) | (RightOuter, BuildLeft) => true
2960+
case _ => false
2961+
}
29202962
}
29212963

29222964
case class CometBroadcastNestedLoopJoinExec(

‎spark/src/test/scala/org/apache/comet/exec/CometJoinSuite.scala‎

Lines changed: 248 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -31,11 +31,12 @@ import org.apache.spark.sql.catalyst.TableIdentifier
3131
import org.apache.spark.sql.catalyst.analysis.UnresolvedRelation
3232
import org.apache.spark.sql.catalyst.expressions.{And, Ascending, AttributeReference, BoundReference, Descending, DynamicPruningExpression, InterpretedOrdering, IsNotNull, SortDirection, SortOrder}
3333
import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight, BuildSide}
34-
import org.apache.spark.sql.catalyst.plans.Inner
34+
import org.apache.spark.sql.catalyst.plans.{Inner, LeftOuter}
3535
import org.apache.spark.sql.catalyst.plans.logical.Join
36-
import org.apache.spark.sql.comet.{CometBroadcastExchangeExec, CometBroadcastHashJoinExec, CometBroadcastNestedLoopJoinExec, CometFilterExec, CometHashJoinExec, CometNativeScanExec, CometProjectExec, CometSortExec, CometSortMergeJoinExec, CometSparkToColumnarExec, CometUnionExec, CometWindowExec}
36+
import org.apache.spark.sql.comet.{CometBroadcastExchangeExec, CometBroadcastHashJoinExec, CometBroadcastNestedLoopJoinExec, CometFilterExec, CometHashJoinExec, CometInMemoryTableScanExec, CometNativeScanExec, CometProjectExec, CometSortExec, CometSortMergeJoinExec, CometSparkToColumnarExec, CometUnionExec, CometWindowExec}
3737
import org.apache.spark.sql.execution.{ColumnarToRowTransition, InputAdapter, LocalTableScanExec, SortExec, SparkPlan, WholeStageCodegenExec}
3838
import org.apache.spark.sql.execution.adaptive.{AdaptiveSparkPlanExec, AQEShuffleReadExec, QueryStageExec}
39+
import org.apache.spark.sql.execution.columnar.InMemoryTableScanExec
3940
import org.apache.spark.sql.execution.datasources.SchemaColumnConvertNotSupportedException
4041
import org.apache.spark.sql.execution.exchange.{ReusedExchangeExec, ShuffleExchangeLike}
4142
import org.apache.spark.sql.execution.joins.{ShuffledHashJoinExec, SortMergeJoinExec}
@@ -2472,29 +2473,259 @@ class CometJoinSuite extends CometTestBase {
24722473
|FROM (SELECT * FROM cached WHERE k NOT IN (SELECT _1 FROM excl)) a
24732474
|LEFT JOIN small b ON a.k = b._1
24742475
|GROUP BY a.k""".stripMargin
2475-
def rows(): Seq[(Int, Long, Long, Long)] =
2476-
sql(query)
2477-
.collect()
2478-
.map(r => (r.getInt(0), r.getLong(1), r.getLong(2), r.getLong(3)))
2479-
.toSeq
2480-
.sorted
2481-
val cometRows = rows()
2482-
// withSQLConf returns Unit on Spark 3.x, so Spark's rows are assigned inside it.
2483-
var sparkRows = Seq.empty[(Int, Long, Long, Long)]
2484-
withSQLConf(CometConf.COMET_ENABLED.key -> "false") {
2485-
sparkRows = rows()
2486-
}
2476+
checkEachKeyGroupedOnce(query)
2477+
} finally {
2478+
spark.catalog.clearCache()
2479+
spark.catalog.dropTempView("cached")
2480+
}
2481+
}
2482+
}
2483+
}
2484+
}
2485+
}
2486+
2487+
test("an outer hash join over a cache of a NOT IN keeps each group once") {
2488+
// The same NOT IN as the test above, but cached, so its rows reach the outer join from the
2489+
// JVM. The cache reports the order Spark reports for the null-aware anti join, which its rows
2490+
// are not in, and the outer join's probe input is then a plain JVM input as far as the native
2491+
// plan can see. The order must not be declared there either. A cached plan that AQE runs
2492+
// reports no order, so AQE is off here, as Spark 3.4 has it for every cached plan by default.
2493+
withSQLConf(
2494+
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
2495+
SQLConf.SHUFFLE_PARTITIONS.key -> "2",
2496+
SQLConf.COLUMN_BATCH_SIZE.key -> "8",
2497+
CometConf.COMET_BATCH_SIZE.key -> "8",
2498+
CometConf.COMET_EXEC_IN_MEMORY_CACHE_ENABLED.key -> "true") {
2499+
withParquetTable((0 until 2000).map(i => ((i % 40) * 1000, i)), "big") {
2500+
withParquetTable(Seq(1000, 10000, 20000, 100000).map(x => Tuple1(Option(x))), "excl") {
2501+
withParquetTable((0 until 40 by 2).map(k => (k * 1000, k)), "small") {
2502+
try {
2503+
spark
2504+
.table("big")
2505+
.toDF("k", "v")
2506+
.repartition(2, $"k")
2507+
.sortWithinPartitions("k")
2508+
.cache()
2509+
.createOrReplaceTempView("cached")
2510+
spark.table("cached").count()
2511+
sql("SELECT * FROM cached WHERE k NOT IN (SELECT _1 FROM excl)")
2512+
.cache()
2513+
.createOrReplaceTempView("anti")
2514+
spark.table("anti").count()
2515+
val cachedPlan = cachedPlanOf(spark.table("anti"))
2516+
assert(
2517+
cachedPlan.exists {
2518+
case join: CometBroadcastHashJoinExec => join.isNullAwareAntiJoin
2519+
case _ => false
2520+
},
2521+
s"the cache was not written by a native NOT IN:\n$cachedPlan")
2522+
assert(
2523+
!partitionsInOrder(spark.table("anti"), keyOrder(Ascending)),
2524+
"the cached NOT IN rows are in order, so nothing here can split a group")
2525+
val query =
2526+
"""SELECT /*+ BROADCAST(b) */ a.k, count(*), sum(a.v), count(b._2)
2527+
|FROM anti a LEFT JOIN small b ON a.k = b._1
2528+
|GROUP BY a.k""".stripMargin
2529+
checkEachKeyGroupedOnce(query)
2530+
} finally {
2531+
spark.catalog.clearCache()
2532+
spark.catalog.dropTempView("anti")
2533+
spark.catalog.dropTempView("cached")
2534+
}
2535+
}
2536+
}
2537+
}
2538+
}
2539+
}
2540+
2541+
test("an outer hash join over a cache of an undeclared outer join keeps each group once") {
2542+
// The IN subquery's semi join sits between the sorted cache and the first outer join, and the
2543+
// native planner declares no order over a semi join, so that outer join moves its unmatched
2544+
// rows, and the cache it writes is out of the order it reports. The second outer join reads
2545+
// that cache as a JVM input and must not declare the order either.
2546+
withSQLConf(
2547+
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
2548+
SQLConf.SHUFFLE_PARTITIONS.key -> "2",
2549+
SQLConf.COLUMN_BATCH_SIZE.key -> "8",
2550+
CometConf.COMET_BATCH_SIZE.key -> "8",
2551+
CometConf.COMET_EXEC_IN_MEMORY_CACHE_ENABLED.key -> "true") {
2552+
withParquetTable((0 until 2000).map(i => ((i % 40) * 1000, i)), "big") {
2553+
withParquetTable((0 until 40).filter(_ % 7 != 3).map(k => Tuple1(k * 1000)), "incl") {
2554+
withParquetTable((0 until 40 by 2).map(k => (k * 1000, k)), "small") {
2555+
try {
2556+
spark
2557+
.table("big")
2558+
.toDF("k", "v")
2559+
.repartition(2, $"k")
2560+
.sortWithinPartitions("k")
2561+
.cache()
2562+
.createOrReplaceTempView("cached")
2563+
spark.table("cached").count()
2564+
sql("""SELECT /*+ BROADCAST(b) */ a.k, a.v, b._2 AS w
2565+
|FROM (SELECT * FROM cached WHERE k IN (SELECT _1 FROM incl)) a
2566+
|LEFT JOIN small b ON a.k = b._1""".stripMargin)
2567+
.cache()
2568+
.createOrReplaceTempView("joined")
2569+
spark.table("joined").count()
2570+
val cachedPlan = cachedPlanOf(spark.table("joined"))
24872571
assert(
2488-
cometRows.map(_._1).distinct.size == cometRows.size,
2489-
"a key is grouped twice")
2490-
assert(cometRows == sparkRows)
2572+
cachedPlan.exists {
2573+
case join: CometBroadcastHashJoinExec => join.joinType == LeftOuter
2574+
case _ => false
2575+
},
2576+
s"the cache was not written by a native outer join:\n$cachedPlan")
2577+
assert(
2578+
!partitionsInOrder(spark.table("joined"), keyOrder(Ascending)),
2579+
"the cached outer join rows are in order, so nothing here can split a group")
2580+
val query =
2581+
"""SELECT /*+ BROADCAST(c) */ j.k, count(*), sum(j.v), count(c._2)
2582+
|FROM joined j LEFT JOIN small c ON j.k = c._1
2583+
|GROUP BY j.k""".stripMargin
2584+
checkEachKeyGroupedOnce(query)
24912585
} finally {
24922586
spark.catalog.clearCache()
2587+
spark.catalog.dropTempView("joined")
24932588
spark.catalog.dropTempView("cached")
24942589
}
24952590
}
24962591
}
24972592
}
24982593
}
24992594
}
2595+
2596+
test("an outer hash join over a cache sorted above an outer hash join declares the order") {
2597+
// The sort in the plan that wrote the cache puts its rows in the order the cache reports,
2598+
// whatever the outer join below the sort did, so the second outer join declares that order.
2599+
// The sort is on (k, v), so Spark does not drop it as one the first join already satisfies.
2600+
withSQLConf(
2601+
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
2602+
SQLConf.SHUFFLE_PARTITIONS.key -> "2",
2603+
SQLConf.COLUMN_BATCH_SIZE.key -> "8",
2604+
CometConf.COMET_BATCH_SIZE.key -> "8",
2605+
CometConf.COMET_EXEC_IN_MEMORY_CACHE_ENABLED.key -> "true") {
2606+
withParquetTable((0 until 2000).map(i => ((i % 40) * 1000, i)), "big") {
2607+
withParquetTable((0 until 40 by 2).map(k => (k * 1000, k)), "small") {
2608+
try {
2609+
spark
2610+
.table("big")
2611+
.toDF("k", "v")
2612+
.repartition(2, $"k")
2613+
.sortWithinPartitions("k")
2614+
.cache()
2615+
.createOrReplaceTempView("cached")
2616+
spark.table("cached").count()
2617+
sql("""SELECT /*+ BROADCAST(b) */ a.k, a.v, b._2 AS w
2618+
|FROM cached a LEFT JOIN small b ON a.k = b._1""".stripMargin)
2619+
.sortWithinPartitions("k", "v")
2620+
.cache()
2621+
.createOrReplaceTempView("sorted_joined")
2622+
spark.table("sorted_joined").count()
2623+
val cachedPlan = cachedPlanOf(spark.table("sorted_joined"))
2624+
assert(
2625+
cachedPlan.exists {
2626+
case join: CometBroadcastHashJoinExec => join.joinType == LeftOuter
2627+
case _ => false
2628+
},
2629+
s"the cache was not written by a native outer join:\n$cachedPlan")
2630+
val df = sql("""SELECT /*+ BROADCAST(c) */ j.k, j.v, c._2
2631+
|FROM sorted_joined j LEFT JOIN small c ON j.k = c._1""".stripMargin)
2632+
.sortWithinPartitions("k")
2633+
val joins = df.queryExecution.executedPlan.collect {
2634+
case join: CometBroadcastHashJoinExec => join
2635+
}
2636+
assert(joins.size == 1, df.queryExecution.executedPlan)
2637+
assert(joins.head.nativeOp.getHashJoin.getStreamedSortOrdersCount > 0)
2638+
assert(partitionsInOrder(df, keyOrder(Ascending)))
2639+
var sparkRows = Seq.empty[Row]
2640+
withSQLConf(CometConf.COMET_ENABLED.key -> "false") {
2641+
sparkRows = df.collect().toSeq
2642+
}
2643+
QueryTest.sameRows(sparkRows, df.collect().toSeq).foreach(fail(_))
2644+
} finally {
2645+
spark.catalog.clearCache()
2646+
spark.catalog.dropTempView("sorted_joined")
2647+
spark.catalog.dropTempView("cached")
2648+
}
2649+
}
2650+
}
2651+
}
2652+
}
2653+
2654+
test("an outer hash join over a cache of a nested loop join keeps each group once") {
2655+
// DataFusion's nested loop join emits each probe batch's matches build row by build row, so
2656+
// it keeps the order of neither input, while Spark reports the streamed side's order for an
2657+
// inner one. The cache it writes reports that order, and the outer join reading the cache
2658+
// must not declare it.
2659+
withSQLConf(
2660+
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
2661+
SQLConf.SHUFFLE_PARTITIONS.key -> "2",
2662+
SQLConf.COLUMN_BATCH_SIZE.key -> "8",
2663+
CometConf.COMET_BATCH_SIZE.key -> "8",
2664+
CometConf.COMET_EXEC_IN_MEMORY_CACHE_ENABLED.key -> "true") {
2665+
withParquetTable((0 until 2000).map(i => ((i % 40) * 1000, i)), "big") {
2666+
withParquetTable(Seq(0, 1).map(Tuple1(_)), "two") {
2667+
withParquetTable((0 until 40 by 2).map(k => (k * 1000, k)), "small") {
2668+
try {
2669+
spark
2670+
.table("big")
2671+
.toDF("k", "v")
2672+
.repartition(2, $"k")
2673+
.sortWithinPartitions("k")
2674+
.cache()
2675+
.createOrReplaceTempView("cached")
2676+
spark.table("cached").count()
2677+
sql("""SELECT /*+ BROADCAST(t) */ a.k, a.v, t._1 AS x
2678+
|FROM cached a JOIN two t ON a.v % 2 <= t._1""".stripMargin)
2679+
.cache()
2680+
.createOrReplaceTempView("nlj")
2681+
spark.table("nlj").count()
2682+
val cachedPlan = cachedPlanOf(spark.table("nlj"))
2683+
assert(
2684+
cachedPlan.exists(_.isInstanceOf[CometBroadcastNestedLoopJoinExec]),
2685+
s"the cache was not written by a native nested loop join:\n$cachedPlan")
2686+
assert(
2687+
!partitionsInOrder(spark.table("nlj"), keyOrder(Ascending)),
2688+
"the cached nested loop join rows are in order, so nothing here can split a group")
2689+
checkEachKeyGroupedOnce(
2690+
"""SELECT /*+ BROADCAST(c) */ n.k, count(*), sum(n.v), count(c._2)
2691+
|FROM nlj n LEFT JOIN small c ON n.k = c._1
2692+
|GROUP BY n.k""".stripMargin)
2693+
} finally {
2694+
spark.catalog.clearCache()
2695+
spark.catalog.dropTempView("nlj")
2696+
spark.catalog.dropTempView("cached")
2697+
}
2698+
}
2699+
}
2700+
}
2701+
}
2702+
}
2703+
2704+
// Runs `query`, which groups by the integer key in its first column and returns three longs,
2705+
// with Comet and with Spark, and checks that Comet returns each key once and Spark's rows.
2706+
private def checkEachKeyGroupedOnce(query: String): Unit = {
2707+
def rows(): Seq[(Int, Long, Long, Long)] =
2708+
sql(query)
2709+
.collect()
2710+
.map(r => (r.getInt(0), r.getLong(1), r.getLong(2), r.getLong(3)))
2711+
.toSeq
2712+
.sorted
2713+
val cometRows = rows()
2714+
// withSQLConf returns Unit on Spark 3.x, so Spark's rows are assigned inside it.
2715+
var sparkRows = Seq.empty[(Int, Long, Long, Long)]
2716+
withSQLConf(CometConf.COMET_ENABLED.key -> "false") {
2717+
sparkRows = rows()
2718+
}
2719+
assert(cometRows.map(_._1).distinct.size == cometRows.size, "a key is grouped twice")
2720+
assert(cometRows == sparkRows)
2721+
}
2722+
2723+
// The physical plan that wrote the cache `df` reads.
2724+
private def cachedPlanOf(df: DataFrame): SparkPlan =
2725+
df.queryExecution.executedPlan
2726+
.collectFirst {
2727+
case scan: CometInMemoryTableScanExec => scan.originalPlan.relation.cachedPlan
2728+
case scan: InMemoryTableScanExec => scan.relation.cachedPlan
2729+
}
2730+
.getOrElse(fail(s"no cache scan in\n${df.queryExecution.executedPlan}"))
25002731
}

0 commit comments

Comments
 (0)