Skip to content

Commit 62d3725

Browse files
buraksennkosiew
authored andcommitted
fix(proto): serialize Global/LocalLimitExec required_ordering (apache#24183)
## Which issue does this PR close? - Closes apache#24173 ## Rationale for this change `GlobalLimitExec`/`LocalLimitExec` `required_ordering` is not serialized, so a roundtrip loses the only record that a pushed-down `LIMIT` is order-sensitive. Re-running `LimitPushdown` on the decoded plan then sets `preserve_order: false` on the scan, which is free to read files out of order — `ORDER BY ... LIMIT` can return the wrong rows. ## What changes are included in this PR? - Add `required_ordering` to `GlobalLimitExecNode` (field 4) and `LocalLimitExecNode` (field 3); empty list means `None` - New `optional_ordering_try_to_proto`/`optional_ordering_try_from_proto` helpers in `physical-expr-common`, also reused by `SymmetricHashJoinExec` serde which hand-rolled the same pattern - Preserve `required_ordering` in both execs' `with_new_children` ## Are these changes tested? Yes new tests that would fail on main if not fixed ## Are there any user-facing changes? No
1 parent 8c1441b commit 62d3725

9 files changed

Lines changed: 322 additions & 58 deletions

File tree

‎datafusion/core/tests/physical_optimizer/enforce_sorting.rs‎

Lines changed: 52 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@ use arrow::datatypes::{DataType, SchemaRef};
3434
use datafusion_common::config::{ConfigOptions, CsvOptions};
3535
use datafusion_common::tree_node::{TreeNode, TransformedResult};
3636
use datafusion_common::{create_array, DataFusionError, NullEquality, Result, TableReference};
37-
use datafusion_datasource::file_scan_config::FileScanConfigBuilder;
37+
use datafusion_datasource::file_scan_config::{FileScanConfig, FileScanConfigBuilder};
3838
use datafusion_datasource::source::DataSourceExec;
3939
use datafusion_expr_common::operator::Operator;
4040
use datafusion_expr::{JoinType, SortExpr};
@@ -57,6 +57,8 @@ use datafusion_physical_optimizer::sanity_checker::SanityCheckPlan;
5757
use datafusion_physical_optimizer::enforce_sorting::replace_with_order_preserving_variants::{replace_with_order_preserving_variants, OrderPreservationContext};
5858
use datafusion_physical_optimizer::enforce_sorting::sort_pushdown::{SortPushDown, assign_initial_requirements, pushdown_sorts};
5959
use datafusion_physical_optimizer::ensure_requirements::EnsureRequirements;
60+
use datafusion_physical_optimizer::limit_pushdown::LimitPushdown;
61+
use datafusion_physical_optimizer::projection_pushdown::ProjectionPushdown;
6062
use datafusion_physical_optimizer::output_requirements::OutputRequirementExec;
6163
use datafusion_physical_optimizer::PhysicalOptimizerRule;
6264
use datafusion::prelude::*;
@@ -2297,6 +2299,55 @@ async fn test_remove_unnecessary_spm2() -> Result<()> {
22972299
Ok(())
22982300
}
22992301

2302+
#[test]
2303+
fn test_spm_fetch_preserves_ordering_through_child_rewrite() -> Result<()> {
2304+
let schema = create_test_schema()?;
2305+
let ordering: LexOrdering = [sort_expr("non_nullable_col", &schema)].into();
2306+
let source = parquet_exec_with_sort(Arc::clone(&schema), vec![ordering.clone()]);
2307+
let projection = projection_exec(
2308+
vec![
2309+
(col("nullable_col", &schema)?, "nullable_col".to_string()),
2310+
(
2311+
col("non_nullable_col", &schema)?,
2312+
"non_nullable_col".to_string(),
2313+
),
2314+
],
2315+
source,
2316+
)?;
2317+
let plan = sort_preserving_merge_exec_with_fetch(ordering.clone(), projection, 100);
2318+
2319+
let optimized = PlanWithCorrespondingSort::new_default(plan)
2320+
.transform_up(ensure_sorting)?
2321+
.data;
2322+
let optimized = check_integrity(optimized)?.plan;
2323+
let limit = optimized
2324+
.downcast_ref::<LocalLimitExec>()
2325+
.expect("SPM fetch should become a local limit");
2326+
assert_eq!(limit.fetch(), 100);
2327+
assert_eq!(limit.required_ordering().as_ref(), Some(&ordering));
2328+
2329+
let config = ConfigOptions::new();
2330+
let optimized = ProjectionPushdown::new().optimize(optimized, &config)?;
2331+
let limit = optimized
2332+
.downcast_ref::<LocalLimitExec>()
2333+
.expect("projection rewrite should retain the local limit");
2334+
assert_eq!(limit.required_ordering().as_ref(), Some(&ordering));
2335+
assert!(limit.input().is::<DataSourceExec>());
2336+
2337+
let optimized = LimitPushdown::new().optimize(optimized, &config)?;
2338+
let source = optimized
2339+
.downcast_ref::<DataSourceExec>()
2340+
.expect("limit should be pushed into the parquet scan");
2341+
let config = source
2342+
.data_source()
2343+
.downcast_ref::<FileScanConfig>()
2344+
.expect("parquet scan should use FileScanConfig");
2345+
assert_eq!(config.limit, Some(100));
2346+
assert!(config.preserve_order);
2347+
2348+
Ok(())
2349+
}
2350+
23002351
#[tokio::test]
23012352
async fn test_change_wrong_sorting() -> Result<()> {
23022353
let schema = create_test_schema()?;

‎datafusion/physical-expr-common/src/sort_expr.rs‎

Lines changed: 21 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -265,7 +265,8 @@ pub fn sort_exprs_try_to_proto<E: std::borrow::Borrow<PhysicalSortExpr>>(
265265
/// [`LexRequirement`], because callers differ in what an empty list means:
266266
/// `LexOrdering::new` / `LexRequirement::new` return `None` for it, which is
267267
/// "no ordering declared" for a scan and an error for an operator that requires
268-
/// one.
268+
/// one. Callers with the former convention can use
269+
/// [`optional_ordering_try_from_proto`] instead.
269270
///
270271
/// [`PhysicalSortExprNode`]: datafusion_proto_models::protobuf::PhysicalSortExprNode
271272
#[cfg(feature = "proto")]
@@ -279,6 +280,25 @@ pub fn sort_exprs_try_from_proto(
279280
.collect()
280281
}
281282

283+
/// Serialize an optional [`LexOrdering`], encoding `None` as an empty list.
284+
#[cfg(feature = "proto")]
285+
pub fn optional_ordering_try_to_proto(
286+
ordering: Option<&LexOrdering>,
287+
ctx: &crate::physical_expr::proto_encode::PhysicalExprEncodeCtx<'_>,
288+
) -> Result<Vec<datafusion_proto_models::protobuf::PhysicalSortExprNode>> {
289+
sort_exprs_try_to_proto(ordering.into_iter().flatten(), ctx)
290+
}
291+
292+
/// Counterpart of [`optional_ordering_try_to_proto`]: an empty list decodes
293+
/// as `None`.
294+
#[cfg(feature = "proto")]
295+
pub fn optional_ordering_try_from_proto(
296+
nodes: &[datafusion_proto_models::protobuf::PhysicalSortExprNode],
297+
ctx: &crate::physical_expr::proto_decode::PhysicalExprDecodeCtx<'_>,
298+
) -> Result<Option<LexOrdering>> {
299+
Ok(LexOrdering::new(sort_exprs_try_from_proto(nodes, ctx)?))
300+
}
301+
282302
impl PartialEq for PhysicalSortExpr {
283303
fn eq(&self, other: &Self) -> bool {
284304
self.options == other.options && self.expr.eq(&other.expr)

‎datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs‎

Lines changed: 10 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -461,13 +461,17 @@ pub fn ensure_sorting(
461461
} else if is_sort_preserving_merge(&requirements.plan)
462462
&& child_node.plan.output_partitioning().partition_count() <= 1
463463
{
464-
// This `SortPreservingMergeExec` is unnecessary, input already has a
465-
// single partition and no fetch is required.
466-
let mut child_node = requirements.children.swap_remove(0);
464+
// This `SortPreservingMergeExec` is unnecessary because its input has a
465+
// single partition.
466+
let child_node = requirements.children.swap_remove(0);
467467
if let Some(fetch) = requirements.plan.fetch() {
468-
// Add the limit exec if the original SPM had a fetch:
469-
child_node.plan =
470-
Arc::new(LocalLimitExec::new(Arc::clone(&child_node.plan), fetch));
468+
let mut limit = LocalLimitExec::new(Arc::clone(&child_node.plan), fetch);
469+
limit.set_required_ordering(requirements.plan.output_ordering().cloned());
470+
return Ok(Transformed::yes(PlanContext::new(
471+
Arc::new(limit),
472+
false,
473+
vec![child_node],
474+
)));
471475
}
472476
return Ok(Transformed::yes(child_node));
473477
}

‎datafusion/physical-plan/src/joins/symmetric_hash_join.rs‎

Lines changed: 18 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -709,20 +709,16 @@ impl ExecutionPlan for SymmetricHashJoinExec {
709709
})
710710
.transpose()?;
711711
let expr_ctx = ctx.expr_ctx();
712-
let encode_sort_exprs =
713-
|exprs: Option<&LexOrdering>| -> Result<Vec<protobuf::PhysicalSortExprNode>> {
714-
exprs.map_or_else(
715-
|| Ok(vec![]),
716-
|exprs| {
717-
datafusion_physical_expr_common::sort_expr::sort_exprs_try_to_proto(
718-
exprs.iter(),
719-
&expr_ctx,
720-
)
721-
},
722-
)
723-
};
724-
let left_sort_exprs = encode_sort_exprs(self.left_sort_exprs())?;
725-
let right_sort_exprs = encode_sort_exprs(self.right_sort_exprs())?;
712+
let left_sort_exprs =
713+
datafusion_physical_expr_common::sort_expr::optional_ordering_try_to_proto(
714+
self.left_sort_exprs(),
715+
&expr_ctx,
716+
)?;
717+
let right_sort_exprs =
718+
datafusion_physical_expr_common::sort_expr::optional_ordering_try_to_proto(
719+
self.right_sort_exprs(),
720+
&expr_ctx,
721+
)?;
726722

727723
Ok(Some(protobuf::PhysicalPlanNode {
728724
physical_plan_type: Some(
@@ -886,20 +882,16 @@ impl SymmetricHashJoinExec {
886882
))
887883
})
888884
.transpose()?;
889-
let decode_sort_exprs = |sort_exprs: &[protobuf::PhysicalSortExprNode],
890-
schema: &Schema|
891-
-> Result<Option<LexOrdering>> {
892-
let sort_exprs =
893-
datafusion_physical_expr_common::sort_expr::sort_exprs_try_from_proto(
894-
sort_exprs,
895-
&ctx.expr_ctx(schema),
896-
)?;
897-
Ok(LexOrdering::new(sort_exprs))
898-
};
899885
let left_sort_exprs =
900-
decode_sort_exprs(&sym_join.left_sort_exprs, left_schema.as_ref())?;
886+
datafusion_physical_expr_common::sort_expr::optional_ordering_try_from_proto(
887+
&sym_join.left_sort_exprs,
888+
&ctx.expr_ctx(left_schema.as_ref()),
889+
)?;
901890
let right_sort_exprs =
902-
decode_sort_exprs(&sym_join.right_sort_exprs, right_schema.as_ref())?;
891+
datafusion_physical_expr_common::sort_expr::optional_ordering_try_from_proto(
892+
&sym_join.right_sort_exprs,
893+
&ctx.expr_ctx(right_schema.as_ref()),
894+
)?;
903895

904896
Self::try_new(
905897
left,

0 commit comments

Comments
 (0)