Skip to content

Commit f74ae8f

Browse files
committed
test: cover the right outer shape, an aggregate above the join and the fallback
From review of the hash join order declaration: - The join and cache tests also run a right outer join built on the left, which Comet does not swap, and compare rows as multisets, not sets. - A cache test groups by the key above the join, where the declared order puts both aggregates in sorted mode. - A join test covers the fallback when the streamed order cannot be serialized. - Planner tests cover declaring the order on the probe input for both shapes, and leaving a probe that already declares one alone. - SortedInputExec's doc says the declared order is visible above the join.
1 parent a6a251e commit f74ae8f

4 files changed

Lines changed: 257 additions & 37 deletions

File tree

‎native/core/src/execution/operators/sorted_input.rs‎

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -36,9 +36,12 @@ use datafusion::physical_plan::{
3636
/// sorted before it was cached for instance, but the `ScanExec` it arrives through declares none,
3737
/// and DataFusion's hash join keeps the unmatched probe rows of a right outer join in place only
3838
/// when the probe input declares an order. Otherwise it moves them after the matched rows of each
39-
/// batch, which loses an order Spark has already dropped a sort for. The planner puts this below
40-
/// that join's probe side with the order Spark reports for it, and nowhere else: an order that
41-
/// the whole native plan could see would also change how DataFusion's aggregates group.
39+
/// batch, which loses an order Spark has already dropped a sort for. The planner puts this only
40+
/// on that join's probe input, with the order Spark reports for it, but the join keeps the order
41+
/// in its own output, so the operators above it in the native plan see it too: an aggregate
42+
/// grouped by the key runs in sorted, streaming mode, and a sort aggregate takes the order as
43+
/// already satisfied. The order therefore has to be one Spark guarantees, since a wrong one gives
44+
/// wrong groups rather than only rows out of order.
4245
#[derive(Debug)]
4346
pub struct SortedInputExec {
4447
input: Arc<dyn ExecutionPlan>,

‎native/core/src/execution/planner.rs‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6072,6 +6072,100 @@ mod tests {
60726072
assert_eq!("ScanExec", hash_join_exec.children[1].native_plan.name());
60736073
}
60746074

6075+
/// The hash join in `plan`, under the projection that `swap_inputs` adds when Spark builds
6076+
/// on the right.
6077+
fn planned_hash_join(
6078+
plan: &Arc<dyn ExecutionPlan>,
6079+
) -> &datafusion::physical_plan::joins::HashJoinExec {
6080+
let join = if plan.is::<datafusion::physical_plan::projection::ProjectionExec>() {
6081+
plan.children()[0]
6082+
} else {
6083+
plan
6084+
};
6085+
join.downcast_ref::<datafusion::physical_plan::joins::HashJoinExec>()
6086+
.expect("a hash join")
6087+
}
6088+
6089+
fn sorted_outer_hash_join(
6090+
join_type: spark_operator::JoinType,
6091+
build_side: spark_operator::BuildSide,
6092+
children: Vec<Operator>,
6093+
) -> Operator {
6094+
Operator {
6095+
children,
6096+
op_struct: Some(OpStruct::HashJoin(spark_operator::HashJoin {
6097+
left_join_keys: vec![create_bound_reference(0)],
6098+
right_join_keys: vec![create_bound_reference(0)],
6099+
join_type: join_type as i32,
6100+
build_side: build_side as i32,
6101+
streamed_sort_orders: vec![create_sort_order(0, 3, false, true)],
6102+
..Default::default()
6103+
})),
6104+
..Default::default()
6105+
}
6106+
}
6107+
6108+
#[test]
6109+
fn hash_join_declares_streamed_order_on_probe_input() {
6110+
// The two outer joins Comet sends the streamed side's order for both run as DataFusion's
6111+
// right join, whose probe input is its right one, whichever side Spark builds on.
6112+
for (join_type, build_side) in [
6113+
(
6114+
spark_operator::JoinType::RightOuter,
6115+
spark_operator::BuildSide::BuildLeft,
6116+
),
6117+
(
6118+
spark_operator::JoinType::LeftOuter,
6119+
spark_operator::BuildSide::BuildRight,
6120+
),
6121+
] {
6122+
let operator =
6123+
sorted_outer_hash_join(join_type, build_side, vec![create_scan(), create_scan()]);
6124+
let (_, _, planned) = PhysicalPlanner::default()
6125+
.create_plan(&operator, &mut vec![], 1)
6126+
.unwrap();
6127+
let join = planned_hash_join(&planned.native_plan);
6128+
assert_eq!("ScanExec", join.left().name());
6129+
let probe = join.right();
6130+
let sorted = probe
6131+
.downcast_ref::<crate::execution::operators::SortedInputExec>()
6132+
.expect("the probe input declares the streamed side's order");
6133+
assert_eq!("ScanExec", sorted.children()[0].name());
6134+
assert_eq!(
6135+
"col_0@0 ASC",
6136+
probe.properties().output_ordering().unwrap().to_string()
6137+
);
6138+
// The join keeps the order in its own output, so the operators above it see it too.
6139+
assert!(planned.native_plan.properties().output_ordering().is_some());
6140+
}
6141+
}
6142+
6143+
#[test]
6144+
fn hash_join_keeps_probe_input_that_declares_an_order() {
6145+
// A probe input that already declares an order, such as a sort in the native plan, is
6146+
// left as it is.
6147+
let sort = Operator {
6148+
children: vec![create_scan()],
6149+
op_struct: Some(OpStruct::Sort(spark_operator::Sort {
6150+
sort_orders: vec![create_sort_order(0, 3, false, true)],
6151+
..Default::default()
6152+
})),
6153+
..Default::default()
6154+
};
6155+
let operator = sorted_outer_hash_join(
6156+
spark_operator::JoinType::RightOuter,
6157+
spark_operator::BuildSide::BuildLeft,
6158+
vec![create_scan(), sort],
6159+
);
6160+
let (_, _, planned) = PhysicalPlanner::default()
6161+
.create_plan(&operator, &mut vec![], 1)
6162+
.unwrap();
6163+
assert_eq!(
6164+
"SortExec",
6165+
planned_hash_join(&planned.native_plan).right().name()
6166+
);
6167+
}
6168+
60756169
#[tokio::test]
60766170
async fn spark_plan_dynamic_filter_preserves_metrics() {
60776171
use crate::execution::metrics::utils::to_native_metric_node;

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

Lines changed: 88 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -37,8 +37,9 @@ import org.apache.spark.{SparkConf, SparkException}
3737
import org.apache.spark.CometDriverPlugin
3838
import org.apache.spark.sql.{CometTestBase, DataFrame, Observation, QueryTest, Row}
3939
import org.apache.spark.sql.catalyst.expressions.{And, Attribute, AttributeReference, EqualTo, Expression, GreaterThan, GreaterThanOrEqual, LessThan, Literal}
40+
import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight, BuildSide}
4041
import org.apache.spark.sql.columnar.{CachedBatch, SimpleMetricsCachedBatch}
41-
import org.apache.spark.sql.comet.{CometBroadcastHashJoinExec, CometHashJoinExec, CometInMemoryTableScanExec, CometSortAggregateExec, CometSortExec, CometSortMergeJoinExec}
42+
import org.apache.spark.sql.comet.{CometBroadcastHashJoinExec, CometHashAggregateExec, CometHashJoinExec, CometInMemoryTableScanExec, CometSortAggregateExec, CometSortExec, CometSortMergeJoinExec}
4243
import org.apache.spark.sql.comet.execution.arrow.{ArrowCachedBatchSerializer, CometCachedBatchHelper}
4344
import org.apache.spark.sql.comet.execution.shuffle.CometCelebornShuffleManager
4445
import org.apache.spark.sql.comet.util.Utils
@@ -3292,9 +3293,10 @@ class CometInMemoryCacheSuite extends CometTestBase {
32923293
test("hash joins over a sorted cache keep the streamed side's order") {
32933294
// CometInMemoryTableScan reports the cached plan's sort order, so Spark drops the sort it
32943295
// would otherwise plan above a join that keeps that order. DataFusion's hash join keeps the
3295-
// unmatched probe rows of a left outer join built on the right in place only when the probe
3296-
// input declares an order, which the native scan over the cache does not, so the native join
3297-
// declares the cache's order on its probe input. An inner join never moves probe rows.
3296+
// unmatched probe rows of a left outer join built on the right, or of a right outer join built
3297+
// on the left, in place only when the probe input declares an order, which the native scan
3298+
// over the cache does not, so the native join declares the cache's order on its probe input.
3299+
// An inner join never moves probe rows.
32983300
withSQLConf(
32993301
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
33003302
SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "-1",
@@ -3308,11 +3310,21 @@ class CometInMemoryCacheSuite extends CometTestBase {
33083310
streamed.count()
33093311
val build = spark.table("small")
33103312

3311-
def query(hint: String, joinType: String): DataFrame =
3312-
streamed
3313-
.join(build.hint(hint), streamed("_1") === build("_1"), joinType)
3313+
def query(hint: String, joinType: String): DataFrame = {
3314+
val joined = if (joinType == "right_outer") {
3315+
build.hint(hint).join(streamed, build("_1") === streamed("_1"), joinType)
3316+
} else {
3317+
streamed.join(build.hint(hint), streamed("_1") === build("_1"), joinType)
3318+
}
3319+
joined
33143320
.select(streamed("_1").as("k"), streamed("_2").as("v"), build("_2").as("w"))
33153321
.sortWithinPartitions("k")
3322+
}
3323+
3324+
def joins(plan: SparkPlan): Seq[(Class[_], BuildSide)] = collect(plan) {
3325+
case j: CometHashJoinExec => (j.getClass, j.buildSide)
3326+
case j: CometBroadcastHashJoinExec => (j.getClass, j.buildSide)
3327+
}
33163328

33173329
def sortedPartitions(df: DataFrame): Array[Boolean] =
33183330
df.queryExecution.toRdd
@@ -3335,19 +3347,24 @@ class CometInMemoryCacheSuite extends CometTestBase {
33353347
"shuffle_hash" -> classOf[CometHashJoinExec],
33363348
"broadcast" -> classOf[CometBroadcastHashJoinExec]).foreach {
33373349
case (hint, joinClass) =>
3338-
val outer = query(hint, "left_outer")
3339-
val outerPlan = outer.queryExecution.executedPlan
3340-
assert(collect(outerPlan) { case j if j.getClass == joinClass => j }.size == 1)
3341-
assert(collect(outerPlan) { case s: CometInMemoryTableScanExec => s }.size == 1)
3342-
assert(sorts(outerPlan).isEmpty, outerPlan)
3343-
assert(outer.collect().toSet == outerRows.toSet)
3344-
assert(sortedPartitions(outer).forall(identity), outerPlan)
3350+
Seq("left_outer" -> BuildRight, "right_outer" -> BuildLeft).foreach {
3351+
case (joinType, buildSide) =>
3352+
val outer = query(hint, joinType)
3353+
val outerPlan = outer.queryExecution.executedPlan
3354+
assert(joins(outerPlan) == Seq((joinClass, buildSide)), outerPlan)
3355+
assert(collect(outerPlan) { case s: CometInMemoryTableScanExec =>
3356+
s
3357+
}.size == 1)
3358+
assert(sorts(outerPlan).isEmpty, outerPlan)
3359+
QueryTest.sameRows(outerRows, outer.collect().toSeq).foreach(fail(_))
3360+
assert(sortedPartitions(outer).forall(identity), outerPlan)
3361+
}
33453362

33463363
val inner = query(hint, "inner")
33473364
val innerPlan = inner.queryExecution.executedPlan
3348-
assert(collect(innerPlan) { case j if j.getClass == joinClass => j }.size == 1)
3365+
assert(joins(innerPlan) == Seq((joinClass, BuildRight)), innerPlan)
33493366
assert(sorts(innerPlan).isEmpty, innerPlan)
3350-
assert(inner.collect().toSet == innerRows.toSet)
3367+
QueryTest.sameRows(innerRows, inner.collect().toSeq).foreach(fail(_))
33513368
assert(sortedPartitions(inner).forall(identity), innerPlan)
33523369
}
33533370
} finally {
@@ -3357,4 +3374,59 @@ class CometInMemoryCacheSuite extends CometTestBase {
33573374
}
33583375
}
33593376
}
3377+
3378+
test("an aggregate on the key above a hash join over a sorted cache groups each key once") {
3379+
// The order the join declares on its probe input reaches past the join, so the aggregate
3380+
// above it in the same native plan groups in sorted, streaming mode. That is right while
3381+
// Spark's reported order holds, and a wrong order would split a key across groups, which only
3382+
// a comparison of the rows as a multiset catches. Small batches make each group span several.
3383+
withSQLConf(
3384+
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
3385+
SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "-1",
3386+
SQLConf.SHUFFLE_PARTITIONS.key -> "2",
3387+
SQLConf.COLUMN_BATCH_SIZE.key -> "8",
3388+
CometConf.COMET_BATCH_SIZE.key -> "8",
3389+
CometConf.COMET_EXEC_IN_MEMORY_CACHE_ENABLED.key -> "true") {
3390+
withParquetTable((0 until 2000).map(i => ((i % 40) * 1000, i)), "big") {
3391+
withParquetTable((0 until 40 by 2).map(m => (m * 1000, m)), "small") {
3392+
try {
3393+
val streamed =
3394+
spark.table("big").repartition(2, $"_1").sortWithinPartitions("_1").cache()
3395+
streamed.count()
3396+
val build = spark.table("small")
3397+
3398+
// Fifty rows per key, and a match in the build side for every even key.
3399+
val expected = (0 until 40).map { m =>
3400+
Row(m * 1000, 50L, 50L * m + 49000L, if (m % 2 == 0) 50L else 0L)
3401+
}
3402+
3403+
for {
3404+
hint <- Seq("shuffle_hash", "broadcast")
3405+
joinType <- Seq("left_outer", "right_outer")
3406+
} {
3407+
val joined = if (joinType == "right_outer") {
3408+
build.hint(hint).join(streamed, build("_1") === streamed("_1"), joinType)
3409+
} else {
3410+
streamed.join(build.hint(hint), streamed("_1") === build("_1"), joinType)
3411+
}
3412+
val df = joined
3413+
.groupBy(streamed("_1"))
3414+
.agg(count(lit(1)), sum(streamed("_2")), count(build("_2")))
3415+
val plan = df.queryExecution.executedPlan
3416+
assert(
3417+
collect(plan) { case j @ (_: CometHashJoinExec | _: CometBroadcastHashJoinExec) =>
3418+
j
3419+
}.size == 1,
3420+
plan)
3421+
assert(collect(plan) { case a: CometHashAggregateExec => a }.size == 2, plan)
3422+
assert(collect(plan) { case s: CometInMemoryTableScanExec => s }.size == 1, plan)
3423+
QueryTest.sameRows(expected, df.collect().toSeq).foreach(fail(_))
3424+
}
3425+
} finally {
3426+
spark.catalog.clearCache()
3427+
}
3428+
}
3429+
}
3430+
}
3431+
}
33603432
}

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

Lines changed: 69 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -26,11 +26,11 @@ import org.apache.hadoop.fs.Path
2626
import org.apache.parquet.hadoop.ParquetFileReader
2727
import org.apache.parquet.hadoop.util.HadoopInputFile
2828
import org.apache.spark.SparkException
29-
import org.apache.spark.sql.{CometTestBase, DataFrame, Row}
29+
import org.apache.spark.sql.{CometTestBase, DataFrame, QueryTest, Row}
3030
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, AttributeReference, DynamicPruningExpression, IsNotNull}
33-
import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight}
33+
import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight, BuildSide}
3434
import org.apache.spark.sql.catalyst.plans.Inner
3535
import org.apache.spark.sql.catalyst.plans.logical.Join
3636
import org.apache.spark.sql.comet.{CometBroadcastExchangeExec, CometBroadcastHashJoinExec, CometBroadcastNestedLoopJoinExec, CometFilterExec, CometHashJoinExec, CometNativeScanExec, CometProjectExec, CometSortExec, CometSortMergeJoinExec, CometSparkToColumnarExec, CometUnionExec, CometWindowExec}
@@ -2287,23 +2287,74 @@ class CometJoinSuite extends CometTestBase {
22872287
Row(k, i, if (k % 10 == 0) k / 10 else null)
22882288
}
22892289

2290-
Seq(
2291-
"shuffle_hash" -> classOf[CometHashJoinExec],
2292-
"broadcast" -> classOf[CometBroadcastHashJoinExec]).foreach {
2293-
case (hint, joinClass) =>
2294-
val df = streamed
2295-
.join(build.hint(hint), streamed("_1") === build("_1"), "left_outer")
2296-
.select(streamed("_1").as("k"), streamed("_2").as("v"), build("_2").as("w"))
2297-
.sortWithinPartitions("k")
2298-
val plan = df.queryExecution.executedPlan
2299-
assert(collect(plan) { case j if j.getClass == joinClass => j }.size == 1, plan)
2300-
assert(collect(plan) { case c: CometSparkToColumnarExec => c }.size == 1, plan)
2301-
assert(
2302-
collect(plan) { case s @ (_: CometSortExec | _: SortExec) => s }.isEmpty,
2303-
plan)
2304-
assert(df.collect().toSet == expected.toSet)
2305-
assert(sortedPartitions(df).forall(identity), plan)
2290+
// Both shapes run as DataFusion's right join: Comet swaps a join built on the right
2291+
// and leaves one built on the left as it is.
2292+
def outerJoin(hint: String, joinType: String): DataFrame = {
2293+
val joined = if (joinType == "left_outer") {
2294+
streamed.join(build.hint(hint), streamed("_1") === build("_1"), joinType)
2295+
} else {
2296+
build.hint(hint).join(streamed, build("_1") === streamed("_1"), joinType)
2297+
}
2298+
joined
2299+
.select(streamed("_1").as("k"), streamed("_2").as("v"), build("_2").as("w"))
2300+
.sortWithinPartitions("k")
23062301
}
2302+
2303+
for {
2304+
(hint, joinClass) <- Seq(
2305+
"shuffle_hash" -> classOf[CometHashJoinExec],
2306+
"broadcast" -> classOf[CometBroadcastHashJoinExec])
2307+
(joinType, buildSide) <- Seq("left_outer" -> BuildRight, "right_outer" -> BuildLeft)
2308+
} {
2309+
val df = outerJoin(hint, joinType)
2310+
val plan = df.queryExecution.executedPlan
2311+
val joins: Seq[(Class[_], BuildSide)] = collect(plan) {
2312+
case j: CometHashJoinExec => (j.getClass, j.buildSide)
2313+
case j: CometBroadcastHashJoinExec => (j.getClass, j.buildSide)
2314+
}
2315+
assert(joins == Seq((joinClass, buildSide)), plan)
2316+
assert(collect(plan) { case c: CometSparkToColumnarExec => c }.size == 1, plan)
2317+
assert(
2318+
collect(plan) { case s @ (_: CometSortExec | _: SortExec) => s }.isEmpty,
2319+
plan)
2320+
QueryTest.sameRows(expected, df.collect().toSeq).foreach(fail(_))
2321+
assert(sortedPartitions(df).forall(identity), plan)
2322+
}
2323+
} finally {
2324+
spark.catalog.clearCache()
2325+
}
2326+
}
2327+
}
2328+
}
2329+
}
2330+
2331+
test("an outer hash join stays in Spark when the streamed side's order cannot be expressed") {
2332+
// The native join keeps the streamed side's order only by declaring it on its probe input, so
2333+
// a join whose order Comet cannot serialize stays in Spark rather than lose the order. With
2334+
// Add disabled, Comet cannot serialize the order below.
2335+
withSQLConf(
2336+
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
2337+
SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "-1",
2338+
SQLConf.SHUFFLE_PARTITIONS.key -> "2",
2339+
CometConf.COMET_EXEC_IN_MEMORY_CACHE_ENABLED.key -> "false",
2340+
CometConf.COMET_CONVERT_FROM_IN_MEMORY_CACHE_ENABLED.key -> "true",
2341+
CometConf.getExprEnabledConfigKey("Add") -> "false") {
2342+
withParquetTable((0 until 1000).map(i => (i % 100, i)), "big") {
2343+
withParquetTable((0 until 10).map(i => (i * 10, i)), "small") {
2344+
try {
2345+
val streamed =
2346+
spark.table("big").repartition(2, $"_1").sortWithinPartitions($"_1" + 1).cache()
2347+
streamed.count()
2348+
val build = spark.table("small")
2349+
val (_, plan) = checkSparkAnswerAndFallbackReason(
2350+
streamed.join(
2351+
build.hint("shuffle_hash"),
2352+
streamed("_1") === build("_1"),
2353+
"left_outer"),
2354+
"the streamed side's sort order, which this outer join has to keep, cannot be " +
2355+
"expressed natively")
2356+
assert(collect(plan) { case j: ShuffledHashJoinExec => j }.size == 1, plan)
2357+
assert(collect(plan) { case j: CometHashJoinExec => j }.isEmpty, plan)
23072358
} finally {
23082359
spark.catalog.clearCache()
23092360
}

0 commit comments

Comments
 (0)