You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/09/02 14:29:45 UTC

(datafusion) 01/01: perf: Avoid cloning EquivalenceProperties in ordering satisfaction checks (#24800)

This is an automated email from the ASF dual-hosted git repository.

github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-24800-406c0c668cb679f96b0406ef4a6837fd5d3bff64
in repository https://gitbox.apache.org/repos/asf/datafusion.git

commit bce3c27f88c45e0aae52fab08fb5f36c48d809e6
Author: Jay Zhan <ja...@gmail.com>
AuthorDate: Wed Sep 2 14:29:00 2026 +0000

    perf: Avoid cloning EquivalenceProperties in ordering satisfaction checks (#24800)
    
    ## Which issue does this PR close?
    
    - Closes #.
    
    ## Rationale for this change
    
    Physical planning asks "is this ordering already satisfied?" constantly
    — sort
    removal, `EnforceSorting`, `EnforceDistribution`, and the requirement
    checks for
    windows, joins and aggregates all call into
    `EquivalenceProperties::ordering_satisfy`,
    `ordering_satisfy_requirement` and
    `extract_common_sort_prefix`.
    
    Each of those calls deep-clones the entire `EquivalenceProperties` —
    every
    equivalence class, every equivalent ordering, and the normalized
    ordering cache —
    before doing anything else, even when it never modifies the copy.
    
    The clone exists for a real reason: as the check walks a multi-key
    ordering left
    to right, it registers each satisfied key as a constant so the next key
    is
    evaluated within that key's tie group. That mutates state, so it needs
    its own
    copy. But two cases pay for it and get nothing back:
    
    1. **A single-key check never mutates anything.** There is no "next key"
    to set up
    for, so the whole clone is wasted. This is the most common shape of
    these calls.
    2. **The last key of *any* check registers constants nobody reads.**
    After the
    final key is verified, the code still calls
    `add_satisfied_key_constants`,
    which rebuilds the ordering cache and re-runs ordering discovery — and
    then the
       object is dropped.
    
    ## What changes are included in this PR?
    
    Two changes in `EquivalenceProperties`, to
    `ordering_satisfy_requirement` and
    `common_sort_prefix_length` (the latter backs `ordering_satisfy`,
    `extract_common_sort_prefix` and `reorder`):
    
    - **Clone on first write instead of up front.** The loop borrows `self`
    and clones
    only when it actually needs to register a constant. Single-key checks
    never
      clone at all.
    - **Skip the registration after the last key.** Nothing reads it.
    
    Plus a new criterion benchmark, `equivalence_properties`, covering these
    entry
    points.
    
    This only changes *when* the copy is made — the results of these
    functions are
    unchanged.
    
    ## Metrics
    
    Apple M4 Pro, rustc 1.97.0, criterion. All changes significant at p =
    0.00.
    
    Properties under test: 3 equivalent orderings (`[c0,c1,c2,c3]`,
    `[c4,c5]`, `[c6]`)
    and a varying number of equivalence classes.
    
    **At 8 equivalence classes:**
    
    | benchmark | before | after | change |
    |---|---:|---:|---|
    | `ordering_satisfy` — 1 key | 2.72 µs | 0.41 µs | **−84.9%** |
    | `ordering_satisfy` — 1 key, unsatisfied | 1.47 µs | 0.41 µs |
    **−72.5%** |
    | `ordering_satisfy_requirement` — 1 key | 2.70 µs | 0.36 µs |
    **−86.3%** |
    | `ordering_satisfy_requirement` — 4 keys | 7.15 µs | 6.07 µs | −13.8% |
    | `ordering_satisfy` — 4 keys | 6.99 µs | 6.20 µs | −11.6% |
    | `extract_common_sort_prefix` — 4 keys | 7.22 µs | 6.38 µs | −9.2% |
    
    **How it scales** (`ordering_satisfy`, 1 key):
    
    | equivalence classes | before | after | change |
    |---:|---:|---:|---|
    | 2 | 2.44 µs | 0.43 µs | −82.5% |
    | 8 | 2.72 µs | 0.41 µs | −84.9% |
    | 32 | 4.63 µs | 0.41 µs | **−90.8%** |
    
    Reading the tables: for an *N*-key check the work goes from
    `1 clone + N registrations` to `(N > 1 ? 1 : 0) clones + (N − 1)
    registrations`.
    
    - **1-key checks** drop both the clone and the registration. Note the
    "after"
    column is flat at ~0.41 µs regardless of how many equivalence classes
    exist —
      with the clone gone, the check no longer scales with the size of the
    equivalence group at all. The "before" column does, which is why the win
    grows
      from −82% to −91%.
    - **Multi-key checks** still clone once and save one of *N*
    registrations. Since a
    registration rebuilds the ordering cache and re-runs ordering discovery,
    that
    single saved call is worth 9–14% here, rising to −37.8% for `4_keys` at
    32
      classes.
    
    ### Reproducing
    
    The benchmark is included in this PR, so reverting just the one source
    file gives
    you the baseline:
    
    ```bash
    # baseline: this PR's parent version of the file, with the new benchmark kept
    git checkout HEAD^ -- datafusion/physical-expr/src/equivalence/properties/mod.rs
    cargo bench -p datafusion-physical-expr --bench equivalence_properties -- --save-baseline before
    
    # with the change
    git checkout HEAD -- datafusion/physical-expr/src/equivalence/properties/mod.rs
    cargo bench -p datafusion-physical-expr --bench equivalence_properties -- --baseline before
    ```
    
    The second run prints criterion's own `change: [...] (p = ...)` line per
    benchmark.
    
    ## Are these changes tested?
    
    No new correctness tests: this does not change what any of these
    functions
    return, so existing coverage is the right check. Covered by the
    `equivalence`
    unit tests in `datafusion/physical-expr` and, for plan-shape
    regressions, by
    sqllogictest — these functions decide whether a `SortExec` can be
    removed, so a
    behavior change would surface as a diff in an `EXPLAIN` plan.
    
    Full workspace suite
    (`--features
    avro,json,backtrace,extended_tests,recursive_protection,parquet_encryption`):
    10,981 passed, 0 failed, and all 505 sqllogictest files pass.
    `./dev/rust_lint.sh`
    is clean.
    
    ## Are there any user-facing changes?
    
    No. No public API or behavior changes — planning is just faster.
---
 datafusion/physical-expr/Cargo.toml                |   4 +
 .../benches/equivalence_properties.rs              | 169 +++++++++++++++++++++
 .../src/equivalence/properties/mod.rs              |  31 +++-
 3 files changed, 199 insertions(+), 5 deletions(-)

diff --git a/datafusion/physical-expr/Cargo.toml b/datafusion/physical-expr/Cargo.toml
index 0588a77723..9b0ae96c4f 100644
--- a/datafusion/physical-expr/Cargo.toml
+++ b/datafusion/physical-expr/Cargo.toml
@@ -105,3 +105,7 @@ name = "string_concat"
 
 [package.metadata.cargo-machete]
 ignored = ["half"]
+
+[[bench]]
+harness = false
+name = "equivalence_properties"
diff --git a/datafusion/physical-expr/benches/equivalence_properties.rs b/datafusion/physical-expr/benches/equivalence_properties.rs
new file mode 100644
index 0000000000..6993b1056d
--- /dev/null
+++ b/datafusion/physical-expr/benches/equivalence_properties.rs
@@ -0,0 +1,169 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! Benchmarks for the ordering satisfaction checks on [`EquivalenceProperties`].
+//!
+//! These are called repeatedly during physical optimization (sort removal,
+//! `EnforceSorting`, `EnforceDistribution`, and the requirement checks for
+//! windows, joins and aggregates), so their cost shows up directly in planning
+//! time.
+//!
+//! # Scope
+//!
+//! These measure the satisfaction check itself, not the cost of assembling its
+//! arguments. The sort expressions, requirements and orderings are built once,
+//! up front. Because the checks take their input by value, each iteration gets a
+//! fresh copy from the untimed setup step of `iter_batched`; only the call is
+//! timed. Any copying the check does internally is part of what is measured.
+//!
+//! The benchmarks are parameterized by the number of equivalence classes, since
+//! that -- not the schema width, which sits behind an `Arc` -- is what these
+//! checks carry around.
+
+use std::sync::Arc;
+
+use arrow::compute::SortOptions;
+use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
+use criterion::{BatchSize, BenchmarkId, Criterion, criterion_group, criterion_main};
+use datafusion_physical_expr::expressions::Column;
+use datafusion_physical_expr::{
+    EquivalenceProperties, LexOrdering, PhysicalExpr, PhysicalSortExpr,
+    PhysicalSortRequirement,
+};
+
+fn schema(n_cols: usize) -> SchemaRef {
+    Arc::new(Schema::new(
+        (0..n_cols)
+            .map(|i| Field::new(format!("c{i}"), DataType::Int32, true))
+            .collect::<Vec<_>>(),
+    ))
+}
+
+fn col(i: usize) -> Arc<dyn PhysicalExpr> {
+    Arc::new(Column::new(&format!("c{i}"), i))
+}
+
+fn asc(i: usize) -> PhysicalSortExpr {
+    PhysicalSortExpr::new(col(i), SortOptions::default())
+}
+
+/// Properties with three equivalent orderings and `n_classes` equivalence
+/// classes, i.e. roughly what a scan feeding a join and a window function looks
+/// like. Columns `c0..c7` carry the orderings; the equivalence classes are built
+/// from the columns above them.
+fn properties(n_classes: usize) -> EquivalenceProperties {
+    let schema = schema(8 + 2 * n_classes);
+    let mut props = EquivalenceProperties::new(schema);
+    props.add_orderings([
+        vec![asc(0), asc(1), asc(2), asc(3)],
+        vec![asc(4), asc(5)],
+        vec![asc(6)],
+    ]);
+    for i in 0..n_classes {
+        props
+            .add_equal_conditions(col(8 + 2 * i), col(9 + 2 * i))
+            .unwrap();
+    }
+    props
+}
+
+fn bench_ordering_satisfaction(c: &mut Criterion) {
+    let mut group = c.benchmark_group("equivalence_properties");
+
+    // Built once; see the "Scope" note at the top of this file.
+    let one_key = vec![asc(0)];
+    // `c7` leads none of the orderings, so this exits on the first key.
+    let one_key_unsatisfied = vec![asc(7)];
+    let four_keys = (0..4).map(asc).collect::<Vec<_>>();
+    let four_key_ordering = LexOrdering::new(four_keys.clone()).unwrap();
+    let one_req = vec![PhysicalSortRequirement::new(col(0), None)];
+    let four_reqs = (0..4)
+        .map(|i| PhysicalSortRequirement::new(col(i), None))
+        .collect::<Vec<_>>();
+
+    for n_classes in [2, 8, 32] {
+        let props = properties(n_classes);
+
+        // A single sort key: the most common shape by far.
+        group.bench_function(
+            BenchmarkId::new("ordering_satisfy/1_key", n_classes),
+            |b| {
+                b.iter_batched(
+                    || one_key.clone(),
+                    |keys| props.ordering_satisfy(keys).unwrap(),
+                    BatchSize::SmallInput,
+                )
+            },
+        );
+        group.bench_function(
+            BenchmarkId::new("ordering_satisfy/1_key_unsatisfied", n_classes),
+            |b| {
+                b.iter_batched(
+                    || one_key_unsatisfied.clone(),
+                    |keys| props.ordering_satisfy(keys).unwrap(),
+                    BatchSize::SmallInput,
+                )
+            },
+        );
+        // Four sort keys: exercises the per-key constant registration.
+        group.bench_function(
+            BenchmarkId::new("ordering_satisfy/4_keys", n_classes),
+            |b| {
+                b.iter_batched(
+                    || four_keys.clone(),
+                    |keys| props.ordering_satisfy(keys).unwrap(),
+                    BatchSize::SmallInput,
+                )
+            },
+        );
+        group.bench_function(
+            BenchmarkId::new("ordering_satisfy_requirement/1_key", n_classes),
+            |b| {
+                b.iter_batched(
+                    || one_req.clone(),
+                    |reqs| props.ordering_satisfy_requirement(reqs).unwrap(),
+                    BatchSize::SmallInput,
+                )
+            },
+        );
+        group.bench_function(
+            BenchmarkId::new("ordering_satisfy_requirement/4_keys", n_classes),
+            |b| {
+                b.iter_batched(
+                    || four_reqs.clone(),
+                    |reqs| props.ordering_satisfy_requirement(reqs).unwrap(),
+                    BatchSize::SmallInput,
+                )
+            },
+        );
+        group.bench_function(
+            BenchmarkId::new("extract_common_sort_prefix/4_keys", n_classes),
+            |b| {
+                b.iter_batched(
+                    || four_key_ordering.clone(),
+                    |ordering| props.extract_common_sort_prefix(ordering).unwrap(),
+                    BatchSize::SmallInput,
+                )
+            },
+        );
+    }
+
+    group.finish();
+}
+
+criterion_group!(benches, bench_ordering_satisfaction);
+criterion_main!(benches);
diff --git a/datafusion/physical-expr/src/equivalence/properties/mod.rs b/datafusion/physical-expr/src/equivalence/properties/mod.rs
index 08c05efe0c..c68157fecb 100644
--- a/datafusion/physical-expr/src/equivalence/properties/mod.rs
+++ b/datafusion/physical-expr/src/equivalence/properties/mod.rs
@@ -640,8 +640,13 @@ impl EquivalenceProperties {
             return Ok(true);
         }
         let schema = self.schema();
-        let mut eq_properties = self.clone();
-        for element in normal_reqs {
+        // Registering satisfied keys as constants mutates the state, so it
+        // needs an owned copy -- but only from the second requirement onwards.
+        // Single-element requirements (the common case) never pay for the clone.
+        let last_idx = normal_reqs.len() - 1;
+        let mut owned = None::<Self>;
+        for (idx, element) in normal_reqs.into_iter().enumerate() {
+            let eq_properties = owned.as_ref().unwrap_or(self);
             // Check whether given requirement is satisfied:
             let ExprProperties {
                 sort_properties, ..
@@ -658,10 +663,16 @@ impl EquivalenceProperties {
             if !satisfy {
                 return Ok(false);
             }
+            if idx == last_idx {
+                // Nothing left to check, so no need to update the state:
+                break;
+            }
             // Treat satisfied keys (and the sub-expressions they pin down) as
             // constants in subsequent iterations. See
             // [`Self::add_satisfied_key_constants`] for the rationale.
-            eq_properties.add_satisfied_key_constants(element.expr)?;
+            owned
+                .get_or_insert_with(|| self.clone())
+                .add_satisfied_key_constants(element.expr)?;
         }
         Ok(true)
     }
@@ -718,8 +729,12 @@ impl EquivalenceProperties {
             return Ok(full_length);
         }
         let schema = self.schema();
-        let mut eq_properties = self.clone();
+        // Registering satisfied keys as constants mutates the state, so it
+        // needs an owned copy -- but only from the second sort expression
+        // onwards. Single-element orderings never pay for the clone.
+        let mut owned = None::<Self>;
         for (idx, element) in normal_ordering.into_iter().enumerate() {
+            let eq_properties = owned.as_ref().unwrap_or(self);
             // Check whether given ordering is satisfied:
             let ExprProperties {
                 sort_properties, ..
@@ -739,10 +754,16 @@ impl EquivalenceProperties {
                 // many we've satisfied so far:
                 return Ok(idx);
             }
+            if idx + 1 == full_length {
+                // Nothing left to check, so no need to update the state:
+                break;
+            }
             // Treat satisfied keys (and the sub-expressions they pin down) as
             // constants in subsequent iterations. See
             // [`Self::add_satisfied_key_constants`] for the rationale.
-            eq_properties.add_satisfied_key_constants(Arc::clone(&element.expr))?;
+            owned
+                .get_or_insert_with(|| self.clone())
+                .add_satisfied_key_constants(Arc::clone(&element.expr))?;
         }
         // All sort expressions are satisfied, return full length:
         Ok(full_length)


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org