Skip to content

Commit 79b4d33

Browse files
committed
fix: walk an adaptive cache's final plan and keep the streamed order through semi joins
Review feedback on the streamed order that a native outer hash join declares on its probe input. The serde walk that decides whether a cache or checkpoint can be trusted now: - reads the final plan of an adaptive cached plan, as Spark's cache scan does, since the adaptive plan reports no order itself and the walk stopped there; - follows only the streamed side of a hash join, and counts an outer join as declared only when it sent its order and its probe input is a scan in its own native plan; - no longer trusts a leaf that reports an order unless it is a scan or a range, which covers an RDD checkpoint whose plan is gone. The planner now walks through right semi, anti and mark hash joins as well as inner ones, since DataFusion builds their probe indices in ascending order whether or not the probe declares an order. Only a right outer join depends on the declaration. Tests cover a cached NOT IN with AQE off and on, through Spark's cache scan and through the native one, a checkpointed NOT IN, an outer join over a cache written by a declared outer join and by one over a sample, an outer join over a semi join, a NOT IN below an inner join's build side, and a broadcast outer join over a sorted cache with default settings. The test that compared Comet with itself now compares against the rows.
1 parent 2e0fb63 commit 79b4d33

4 files changed

Lines changed: 538 additions & 154 deletions

File tree

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

Lines changed: 84 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -2981,10 +2981,19 @@ impl PhysicalPlanner {
29812981
if plan.is::<ScanExec>() || plan.is::<ShuffleScanExec>() {
29822982
return true;
29832983
}
2984-
// DataFusion reports every right hash join as keeping its probe order, but keeps it only
2985-
// when the probe declares one, and no input on this path declares an order.
2984+
// DataFusion reports every right hash join as keeping its probe order, but a right outer
2985+
// join keeps it only when the probe declares one, and no input on this path declares an
2986+
// order. An inner join emits its matches probe row by probe row, and a right semi, anti or
2987+
// mark join builds its probe indices in ascending order, so none of them depends on a
2988+
// declaration. Any other join type keeps no probe order at all.
29862989
if let Some(join) = plan.downcast_ref::<HashJoinExec>() {
2987-
if join.join_type() != &DFJoinType::Inner {
2990+
if !matches!(
2991+
join.join_type(),
2992+
DFJoinType::Inner
2993+
| DFJoinType::RightSemi
2994+
| DFJoinType::RightAnti
2995+
| DFJoinType::RightMark
2996+
) {
29882997
return false;
29892998
}
29902999
}
@@ -6190,11 +6199,13 @@ mod tests {
61906199
assert_eq!("ProjectionExec", probe.children()[0].name());
61916200
}
61926201

6193-
#[test]
6194-
fn hash_join_declares_no_order_over_an_operator_that_may_move_rows() {
6195-
let hash_join = |join_type: spark_operator::JoinType,
6196-
build_side: spark_operator::BuildSide,
6197-
null_aware_anti_join: bool| Operator {
6202+
/// A hash join over two scans, for use as the probe input of the join under test.
6203+
fn hash_join_over_scans(
6204+
join_type: spark_operator::JoinType,
6205+
build_side: spark_operator::BuildSide,
6206+
null_aware_anti_join: bool,
6207+
) -> Operator {
6208+
Operator {
61986209
children: vec![create_scan(), create_scan()],
61996210
op_struct: Some(OpStruct::HashJoin(spark_operator::HashJoin {
62006211
left_join_keys: vec![create_bound_reference(0)],
@@ -6205,33 +6216,82 @@ mod tests {
62056216
..Default::default()
62066217
})),
62076218
..Default::default()
6208-
};
6209-
for probe_input in [
6219+
}
6220+
}
6221+
6222+
#[test]
6223+
fn hash_join_declares_order_through_joins_that_keep_probe_order() {
6224+
// An inner join emits its matches probe row by probe row, and a right semi, anti or mark
6225+
// join emits its probe indices in ascending order. None of them depends on the probe
6226+
// declaring an order, so the order Spark reports for the outer join's streamed side
6227+
// still holds above them.
6228+
use datafusion::common::JoinType as DF;
6229+
use spark_operator::BuildSide::{BuildLeft, BuildRight};
6230+
use spark_operator::JoinType::{Existence, Inner, LeftAnti, LeftSemi};
6231+
for (join_type, build_side, planned_type) in [
6232+
(Inner, BuildLeft, DF::Inner),
6233+
(Inner, BuildRight, DF::Inner),
6234+
(LeftSemi, BuildRight, DF::RightSemi),
6235+
(LeftAnti, BuildRight, DF::RightAnti),
6236+
(Existence, BuildRight, DF::RightMark),
6237+
] {
6238+
let operator = sorted_outer_hash_join(
6239+
spark_operator::JoinType::RightOuter,
6240+
BuildLeft,
6241+
vec![
6242+
create_scan(),
6243+
hash_join_over_scans(join_type, build_side, false),
6244+
],
6245+
);
6246+
let (_, _, planned) = PhysicalPlanner::default()
6247+
.create_plan(&operator, &mut vec![], 1)
6248+
.unwrap();
6249+
let probe = planned_hash_join(&planned.native_plan).right();
6250+
assert_eq!(
6251+
"SortedInputExec",
6252+
probe.name(),
6253+
"{join_type:?} {build_side:?}"
6254+
);
6255+
let declared = planned_hash_join(probe.children()[0]);
6256+
assert_eq!(&planned_type, declared.join_type());
6257+
}
6258+
}
6259+
6260+
#[test]
6261+
fn hash_join_declares_no_order_over_an_operator_that_may_move_rows() {
6262+
use spark_operator::BuildSide::{BuildLeft, BuildRight};
6263+
use spark_operator::JoinType::{FullOuter, LeftAnti, LeftSemi, RightOuter};
6264+
for (probe_input, reason) in [
62106265
// Comet builds a null-aware anti join on Spark's streamed side, so its output is not
62116266
// in the order Spark reports for it.
6212-
hash_join(
6213-
spark_operator::JoinType::LeftAnti,
6214-
spark_operator::BuildSide::BuildRight,
6215-
true,
6267+
(
6268+
hash_join_over_scans(LeftAnti, BuildRight, true),
6269+
"a null-aware anti join",
62166270
),
62176271
// A right join whose probe declares no order moves its unmatched rows, although
62186272
// DataFusion reports it as keeping its probe order.
6219-
hash_join(
6220-
spark_operator::JoinType::RightOuter,
6221-
spark_operator::BuildSide::BuildLeft,
6222-
false,
6273+
(
6274+
hash_join_over_scans(RightOuter, BuildLeft, false),
6275+
"a right outer join",
6276+
),
6277+
// The remaining types keep no probe order at all: a left semi join built on the left
6278+
// emits build rows, and a full outer join emits its unmatched build rows last.
6279+
(
6280+
hash_join_over_scans(LeftSemi, BuildLeft, false),
6281+
"a left semi join",
6282+
),
6283+
(
6284+
hash_join_over_scans(FullOuter, BuildLeft, false),
6285+
"a full outer join",
62236286
),
62246287
] {
6225-
let operator = sorted_outer_hash_join(
6226-
spark_operator::JoinType::RightOuter,
6227-
spark_operator::BuildSide::BuildLeft,
6228-
vec![create_scan(), probe_input],
6229-
);
6288+
let operator =
6289+
sorted_outer_hash_join(RightOuter, BuildLeft, vec![create_scan(), probe_input]);
62306290
let (_, _, planned) = PhysicalPlanner::default()
62316291
.create_plan(&operator, &mut vec![], 1)
62326292
.unwrap();
62336293
let probe = planned_hash_join(&planned.native_plan).right();
6234-
assert_eq!("HashJoinExec", probe.name());
6294+
assert_eq!("HashJoinExec", probe.name(), "{reason}");
62356295
}
62366296
}
62376297

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

Lines changed: 68 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -40,9 +40,10 @@ import org.apache.spark.sql.comet.execution.arrow.{CometArrowStream, CometNative
4040
import org.apache.spark.sql.comet.execution.shuffle.CometShuffleExchangeExec
4141
import org.apache.spark.sql.comet.util.Utils
4242
import org.apache.spark.sql.execution._
43-
import org.apache.spark.sql.execution.adaptive.{AQEShuffleReadExec, BroadcastQueryStageExec, QueryStageExec, ShuffleQueryStageExec}
43+
import org.apache.spark.sql.execution.adaptive.{AdaptiveSparkPlanExec, AQEShuffleReadExec, BroadcastQueryStageExec, QueryStageExec, ShuffleQueryStageExec}
4444
import org.apache.spark.sql.execution.aggregate.{BaseAggregateExec, HashAggregateExec, ObjectHashAggregateExec, SortAggregateExec}
4545
import org.apache.spark.sql.execution.columnar.InMemoryTableScanExec
46+
import org.apache.spark.sql.execution.datasources.v2.DataSourceV2ScanExecBase
4647
import org.apache.spark.sql.execution.exchange.ReusedExchangeExec
4748
import org.apache.spark.sql.execution.joins.{BroadcastHashJoinExec, BroadcastNestedLoopJoinExec, HashJoin, ShuffledHashJoinExec, SortMergeJoinExec}
4849
import org.apache.spark.sql.execution.metric.{SQLMetric, SQLMetrics}
@@ -2884,7 +2885,8 @@ trait CometHashJoin {
28842885
// of such a join can reach this one through a cache, as a JVM input that the native planner
28852886
// cannot look behind. Declaring the order there would let an operator above rely on it, an
28862887
// 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+
// when such a join feeds the streamed side with no sort in between, or when a leaf reports
2889+
// an order that cannot be checked; see mayReportFalseOrder.
28882890
//
28892891
// Declaring any order makes DataFusion keep the probe rows in place, so the longest prefix
28902892
// of the order that Comet can express is enough. Nothing here can tell whether an operator
@@ -2929,28 +2931,82 @@ trait CometHashJoin {
29292931
}
29302932
}
29312933

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.
2934+
// Whether the order that `plan` reports may be false, because something that feeds it with no
2935+
// sort in between cannot be relied on to keep it. Comet's hash joins report the order of their
2936+
// streamed side, which Spark's own joins keep, but three Comet joins do not always: the
2937+
// null-aware anti join, which Comet builds on its streamed side; an outer join that runs as
2938+
// DataFusion's right outer join, which keeps its probe rows in place only if the planner
2939+
// declared an order on its probe input; and the nested loop join, which DataFusion runs build
2940+
// row by build row. So does a leaf that reports an order from state this walk cannot check, an
2941+
// RDD checkpointed from a plan that is gone for one.
2942+
//
2943+
// The walk follows the order, so a hash join, which passes on only its streamed side's, is
2944+
// walked through that side alone. A cache reports the order of the plan that wrote it, and the
2945+
// walk goes on into that plan, picked as Spark's scan picks it: an adaptive plan reports no
2946+
// order, but the scan reads the final plan behind it once there is one. While CometExecRule
2947+
// converts a plan, a native plan's JVM inputs sit behind a CometScanWrapper, a leaf, so the
2948+
// walk looks through that too.
29382949
private def mayReportFalseOrder(plan: SparkPlan): Boolean = plan match {
2950+
case adaptive: AdaptiveSparkPlanExec if adaptive.isFinalPlan =>
2951+
mayReportFalseOrder(adaptive.executedPlan)
29392952
case _ if plan.outputOrdering.isEmpty => false
29402953
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
29452954
case _: CometBroadcastNestedLoopJoinExec => true
2955+
case join: CometBroadcastHashJoinExec if join.isNullAwareAntiJoin => true
2956+
case join: CometBroadcastHashJoinExec =>
2957+
hashJoinMayReportFalseOrder(
2958+
join.nativeOp,
2959+
join.joinType,
2960+
join.buildSide,
2961+
join.left,
2962+
join.right)
2963+
case join: CometHashJoinExec =>
2964+
hashJoinMayReportFalseOrder(
2965+
join.nativeOp,
2966+
join.joinType,
2967+
join.buildSide,
2968+
join.left,
2969+
join.right)
2970+
case join: HashJoin =>
2971+
mayReportFalseOrder(if (join.buildSide == BuildRight) join.left else join.right)
29462972
case wrapper: CometScanWrapper => mayReportFalseOrder(wrapper.originalPlan)
29472973
case scan: CometInMemoryTableScanExec =>
29482974
mayReportFalseOrder(scan.originalPlan.relation.cachedPlan)
29492975
case scan: InMemoryTableScanExec => mayReportFalseOrder(scan.relation.cachedPlan)
29502976
case stage: QueryStageExec => mayReportFalseOrder(stage.plan)
2977+
// A scan reports an order that Spark already relies on.
2978+
case _: DataSourceScanExec | _: DataSourceV2ScanExecBase | _: RangeExec | _: CometLeafExec =>
2979+
false
2980+
case _ if plan.children.isEmpty => true
29512981
case _ => plan.children.exists(mayReportFalseOrder)
29522982
}
29532983

2984+
// Whether a Comet hash join that reports an order may not keep it. Only the streamed side's
2985+
// order reaches the join's output, so a false order on the build side is of no concern, and an
2986+
// outer join of the two shapes has to have declared the order on its probe input as well.
2987+
private def hashJoinMayReportFalseOrder(
2988+
nativeOp: Operator,
2989+
joinType: JoinType,
2990+
buildSide: BuildSide,
2991+
left: SparkPlan,
2992+
right: SparkPlan): Boolean = {
2993+
val (streamed, streamedIndex) = if (buildSide == BuildRight) (left, 0) else (right, 1)
2994+
mayReportFalseOrder(streamed) ||
2995+
(runsAsRightOuterJoin(joinType, buildSide) && !declaresStreamedOrder(nativeOp, streamedIndex))
2996+
}
2997+
2998+
// Whether the native planner declares the streamed order on the probe input of the join that
2999+
// `nativeOp` describes. It does so when the serde sent the order and the probe input reads from
3000+
// the JVM, which is the case when the join's plan has a scan there. A native operator over that
3001+
// scan is declared as well, as far as the native walk goes, but that is for the planner to say,
3002+
// so it counts as not declared.
3003+
private def declaresStreamedOrder(nativeOp: Operator, streamedIndex: Int): Boolean =
3004+
nativeOp.getHashJoin.getStreamedSortOrdersCount > 0 &&
3005+
nativeOp.getChildrenCount > streamedIndex && {
3006+
val probe = nativeOp.getChildren(streamedIndex)
3007+
probe.hasScan || probe.hasShuffleScan
3008+
}
3009+
29543010
// A left outer join built on the right and a right outer join built on the left both run as
29553011
// DataFusion's right outer join, which keeps its unmatched probe rows in place only when the
29563012
// probe input declares an order.

0 commit comments

Comments
 (0)