Skip to content

Commit 65f406f

Browse files
committed
fix: declare the order of a native range for the joins above it
Spark's RangeExec reports id ascending, or descending for a negative step, and Spark drops a sort above an outer hash join on that basis. The native range is a leaf with no JVM input, so the planner declared no order on the join's probe input and the join moved its unmatched rows. LazyMemoryExec::add_ordering leaves the cached output ordering of the plan properties stale in DataFusion 55, so the planner wraps the range in a SortedInputExec instead, which now reports its input's metrics.
1 parent 8e75130 commit 65f406f

4 files changed

Lines changed: 52 additions & 4 deletions

File tree

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

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@ use datafusion::common::{internal_err, Result};
2525
use datafusion::execution::TaskContext;
2626
use datafusion::physical_expr::{LexOrdering, PhysicalExpr};
2727
use datafusion::physical_plan::execution_plan::CardinalityEffect;
28+
use datafusion::physical_plan::metrics::MetricsSet;
2829
use datafusion::physical_plan::{
2930
apply_expression_roots, DisplayAs, DisplayFormatType, ExecutionPlan, ExecutionPlanProperties,
3031
PlanProperties, SendableRecordBatchStream,
@@ -101,6 +102,12 @@ impl ExecutionPlan for SortedInputExec {
101102
vec![true]
102103
}
103104

105+
/// The rows pass through, so the input's metrics are this operator's, and a range whose root
106+
/// this wraps still reports its output rows.
107+
fn metrics(&self) -> Option<MetricsSet> {
108+
self.input.metrics()
109+
}
110+
104111
fn cardinality_effect(&self) -> CardinalityEffect {
105112
CardinalityEffect::Equal
106113
}

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

Lines changed: 10 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -88,7 +88,7 @@ use datafusion::{
8888
prelude::SessionContext,
8989
};
9090
use datafusion_comet_operators::{
91-
range_exec, CometFilterExec, CometProjectionExec, ExpandExec, ExplodeExec,
91+
range_exec, range_sort_expr, CometFilterExec, CometProjectionExec, ExpandExec, ExplodeExec,
9292
PartitionedRankLimitExec, SampleExec, WindowFnKind,
9393
};
9494
use datafusion_comet_spark_expr::{
@@ -2065,18 +2065,25 @@ impl PhysicalPlanner {
20652065
}
20662066
OpStruct::RangeScan(range) => {
20672067
// A leaf with no JVM input: each task produces its own partition of the range.
2068-
let range: Arc<dyn ExecutionPlan> = Arc::new(range_exec(
2068+
let source: Arc<dyn ExecutionPlan> = Arc::new(range_exec(
20692069
range.start,
20702070
range.step,
20712071
range.num_elements,
20722072
range.num_slices,
20732073
self.partition,
20742074
self.session_ctx.copied_config().batch_size(),
20752075
)?);
2076+
// The range's order is real, and Spark's `RangeExec` reports it, so declare it
2077+
// for the operators above, a hash join in particular: see `SortedInputExec`.
2078+
let ordering = LexOrdering::new([range_sort_expr(range.step)]);
2079+
let source: Arc<dyn ExecutionPlan> = match ordering {
2080+
Some(ordering) => Arc::new(SortedInputExec::new(source, ordering)),
2081+
None => source,
2082+
};
20762083
Ok((
20772084
vec![],
20782085
vec![],
2079-
Arc::new(SparkPlan::new(spark_plan.plan_id, range, vec![])),
2086+
Arc::new(SparkPlan::new(spark_plan.plan_id, source, vec![])),
20802087
))
20812088
}
20822089
OpStruct::Sample(sample) => {

‎native/operators/src/lib.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -37,6 +37,6 @@ pub use expand::ExpandExec;
3737
pub use explode::ExplodeExec;
3838
pub use filter::CometFilterExec;
3939
pub use projection::CometProjectionExec;
40-
pub use range::range_exec;
40+
pub use range::{range_exec, range_sort_expr};
4141
pub use rank_limit::{PartitionedRankLimitExec, WindowFnKind};
4242
pub use sample::SampleExec;

‎native/operators/src/range.rs‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,8 +16,11 @@
1616
// under the License.
1717

1818
use arrow::array::{Int64Array, RecordBatch};
19+
use arrow::compute::SortOptions;
1920
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
2021
use datafusion::common::Result;
22+
use datafusion::physical_expr::expressions::Column;
23+
use datafusion::physical_expr::PhysicalSortExpr;
2124
use datafusion::physical_plan::memory::{LazyBatchGenerator, LazyMemoryExec};
2225
use datafusion::physical_plan::Partitioning;
2326
use parking_lot::RwLock;
@@ -58,6 +61,23 @@ pub fn range_exec(
5861
Ok(exec)
5962
}
6063

64+
/// The order a range's values come out in. They are `partition_start + i * step` and never
65+
/// overflow, so they ascend for a positive step and descend for a negative one, which is the order
66+
/// Spark's `RangeExec` reports.
67+
///
68+
/// `LazyMemoryExec::add_ordering` does not refresh the plan properties' cached output ordering in
69+
/// DataFusion 55, so `output_ordering()` would still be `None` after it. The planner declares this
70+
/// order by wrapping the range in a `SortedInputExec` instead.
71+
pub fn range_sort_expr(step: i64) -> PhysicalSortExpr {
72+
PhysicalSortExpr::new(
73+
Arc::new(Column::new("id", 0)),
74+
SortOptions {
75+
descending: step < 0,
76+
nulls_first: step > 0,
77+
},
78+
)
79+
}
80+
6181
/// The first value of partition `partition` and the number of values in it, computed the way
6282
/// Spark's `RangeExec` does (`initRange` in its generated code): in `BigInteger` arithmetic, with
6383
/// the partition's start and end clamped to the `Long` range.
@@ -247,6 +267,20 @@ mod tests {
247267
assert_eq!(collect(i64::MIN, step, n, 1, 1000).await, expected);
248268
}
249269

270+
#[tokio::test]
271+
async fn test_sort_expr_matches_the_values() {
272+
for step in [1i64, 3, -1, -7] {
273+
let n = num_elements(0, 100 * step, step);
274+
let values = collect(0, step, n, 2, 8).await;
275+
let expr = range_sort_expr(step);
276+
assert_eq!(expr.options.descending, step < 0, "step {step}");
277+
let mut sorted = values.clone();
278+
sorted.sort_by_key(|v| if expr.options.descending { -v } else { *v });
279+
// Both partitions are in order, and the partitions follow each other.
280+
assert_eq!(values, sorted, "step {step}");
281+
}
282+
}
283+
250284
#[test]
251285
fn test_partition_bounds() {
252286
// range(0, 10, 1, 3): Spark puts 3, 3 and 4 values in the three partitions.

0 commit comments

Comments
 (0)