You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by zh...@apache.org on 2026/04/23 07:49:17 UTC
(datafusion) branch skip-map-expressions-empty-extension created (now 6370a75f8c)
This is an automated email from the ASF dual-hosted git repository.
zhuqi-lucas pushed a change to branch skip-map-expressions-empty-extension
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at 6370a75f8c Skip map_expressions rebuild for Extension nodes with empty expressions
This branch includes the following new commits:
new 6370a75f8c Skip map_expressions rebuild for Extension nodes with empty expressions
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: Skip map_expressions rebuild for Extension nodes with empty expressions
Posted by zh...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
zhuqi-lucas pushed a commit to branch skip-map-expressions-empty-extension
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit 6370a75f8c5fd39fb9d28321831bace90bfaf715
Author: Qi Zhu <82...@qq.com>
AuthorDate: Fri Apr 17 23:17:37 2026 +0800
Skip map_expressions rebuild for Extension nodes with empty expressions
When an Extension node has no expressions, `map_expressions` was still
cloning all inputs and calling `with_exprs_and_inputs` to reconstruct
the node — wasted work since there are no expressions to transform.
This adds an early return that skips the expensive clone + rebuild when
`node.expressions()` is empty, which is common for Extension nodes like
view matching candidates (OneOf) that carry multiple children but no
expressions.
Benchmark results (criterion, `datafusion-expr` micro-benchmark):
| Children | no_expr (optimized) | with_expr (rebuild) | Speedup |
|----------|--------------------|--------------------|---------|
| 1 | 24 ns | 167 ns | 7x |
| 3 | 23 ns | 192 ns | 8x |
| 5 | 23 ns | 181 ns | 8x |
| 10 | 24 ns | 216 ns | 9x |
The `no_expr` path is constant time regardless of children count,
while `with_expr` scales with the number of children (clone cost).
In a real optimizer pipeline with ~15 rules traversing a plan with
OneOf(5 candidates), this saves ~2.4 us per optimization pass.
---
Cargo.lock | 1 +
datafusion/expr/Cargo.toml | 5 +
datafusion/expr/benches/map_expressions.rs | 251 ++++++++++++++++++++++++++
datafusion/expr/src/logical_plan/tree_node.rs | 34 ++--
4 files changed, 280 insertions(+), 11 deletions(-)
diff --git a/Cargo.lock b/Cargo.lock
index 5a76c063bb..e84bb0489d 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -2198,6 +2198,7 @@ dependencies = [
"arrow-schema",
"async-trait",
"chrono",
+ "criterion",
"ctor",
"datafusion-common",
"datafusion-doc",
diff --git a/datafusion/expr/Cargo.toml b/datafusion/expr/Cargo.toml
index 8cec01feb3..e48281642e 100644
--- a/datafusion/expr/Cargo.toml
+++ b/datafusion/expr/Cargo.toml
@@ -63,9 +63,14 @@ serde_json = { workspace = true }
sqlparser = { workspace = true, optional = true }
[dev-dependencies]
+criterion = { workspace = true }
ctor = { workspace = true }
env_logger = { workspace = true }
insta = { workspace = true }
# Makes sure `test_display_pg_json` behaves in a consistent way regardless of
# feature unification with dependencies
serde_json = { workspace = true, features = ["preserve_order"] }
+
+[[bench]]
+name = "map_expressions"
+harness = false
diff --git a/datafusion/expr/benches/map_expressions.rs b/datafusion/expr/benches/map_expressions.rs
new file mode 100644
index 0000000000..47e8add1b9
--- /dev/null
+++ b/datafusion/expr/benches/map_expressions.rs
@@ -0,0 +1,251 @@
+// 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.
+
+//! Micro-benchmark for `LogicalPlan::map_expressions` on Extension nodes.
+//!
+//! Extension nodes can have many children but no expressions. When
+//! `expressions()` returns empty, `map_expressions` should skip the
+//! expensive clone-all-inputs + `with_exprs_and_inputs` rebuild.
+
+use arrow::datatypes::{DataType, Field, Schema};
+use criterion::{BenchmarkId, Criterion, criterion_group, criterion_main};
+use datafusion_common::tree_node::Transformed;
+use datafusion_common::{DFSchema, DFSchemaRef, Result};
+use datafusion_expr::{Expr, Extension, LogicalPlan, UserDefinedLogicalNodeCore, col};
+use std::fmt;
+use std::hash::{Hash, Hasher};
+use std::sync::Arc;
+
+// ---------------------------------------------------------------------------
+// Extension node with NO expressions (e.g. OneOf in view matching)
+// ---------------------------------------------------------------------------
+
+#[derive(Debug, Clone)]
+struct NoExprExtension {
+ children: Vec<LogicalPlan>,
+ schema: DFSchemaRef,
+}
+
+impl PartialEq for NoExprExtension {
+ fn eq(&self, other: &Self) -> bool {
+ self.children.len() == other.children.len()
+ }
+}
+impl Eq for NoExprExtension {}
+
+impl Hash for NoExprExtension {
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ self.children.len().hash(state);
+ }
+}
+
+impl PartialOrd for NoExprExtension {
+ fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
+ Some(self.children.len().cmp(&other.children.len()))
+ }
+}
+
+impl UserDefinedLogicalNodeCore for NoExprExtension {
+ fn name(&self) -> &str {
+ "NoExprExtension"
+ }
+ fn inputs(&self) -> Vec<&LogicalPlan> {
+ self.children.iter().collect()
+ }
+ fn schema(&self) -> &DFSchemaRef {
+ &self.schema
+ }
+ fn expressions(&self) -> Vec<Expr> {
+ vec![] // Key: no expressions
+ }
+ fn fmt_for_explain(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ write!(f, "NoExprExtension(children={})", self.children.len())
+ }
+ fn with_exprs_and_inputs(
+ &self,
+ _: Vec<Expr>,
+ inputs: Vec<LogicalPlan>,
+ ) -> Result<Self> {
+ Ok(Self {
+ children: inputs,
+ schema: Arc::clone(&self.schema),
+ })
+ }
+}
+
+// ---------------------------------------------------------------------------
+// Extension node WITH expressions (control group)
+// ---------------------------------------------------------------------------
+
+#[derive(Debug, Clone)]
+struct WithExprExtension {
+ children: Vec<LogicalPlan>,
+ exprs: Vec<Expr>,
+ schema: DFSchemaRef,
+}
+
+impl PartialEq for WithExprExtension {
+ fn eq(&self, other: &Self) -> bool {
+ self.children.len() == other.children.len()
+ && self.exprs.len() == other.exprs.len()
+ }
+}
+impl Eq for WithExprExtension {}
+
+impl Hash for WithExprExtension {
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ self.children.len().hash(state);
+ self.exprs.len().hash(state);
+ }
+}
+
+impl PartialOrd for WithExprExtension {
+ fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
+ Some(
+ self.children
+ .len()
+ .cmp(&other.children.len())
+ .then(self.exprs.len().cmp(&other.exprs.len())),
+ )
+ }
+}
+
+impl UserDefinedLogicalNodeCore for WithExprExtension {
+ fn name(&self) -> &str {
+ "WithExprExtension"
+ }
+ fn inputs(&self) -> Vec<&LogicalPlan> {
+ self.children.iter().collect()
+ }
+ fn schema(&self) -> &DFSchemaRef {
+ &self.schema
+ }
+ fn expressions(&self) -> Vec<Expr> {
+ self.exprs.clone()
+ }
+ fn fmt_for_explain(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ write!(
+ f,
+ "WithExprExtension(children={}, exprs={})",
+ self.children.len(),
+ self.exprs.len()
+ )
+ }
+ fn with_exprs_and_inputs(
+ &self,
+ exprs: Vec<Expr>,
+ inputs: Vec<LogicalPlan>,
+ ) -> Result<Self> {
+ Ok(Self {
+ children: inputs,
+ exprs,
+ schema: Arc::clone(&self.schema),
+ })
+ }
+}
+
+// ---------------------------------------------------------------------------
+// Helpers
+// ---------------------------------------------------------------------------
+
+fn build_schema(num_cols: usize) -> DFSchemaRef {
+ let fields: Vec<Field> = (0..num_cols)
+ .map(|i| Field::new(format!("col_{i}"), DataType::Utf8, true))
+ .collect();
+ Arc::new(DFSchema::try_from(Schema::new(fields)).unwrap())
+}
+
+fn build_child(schema: &DFSchemaRef) -> LogicalPlan {
+ LogicalPlan::EmptyRelation(datafusion_expr::EmptyRelation {
+ produce_one_row: false,
+ schema: Arc::clone(schema),
+ })
+}
+
+fn build_no_expr_plan(num_children: usize, num_cols: usize) -> LogicalPlan {
+ let schema = build_schema(num_cols);
+ let children: Vec<LogicalPlan> =
+ (0..num_children).map(|_| build_child(&schema)).collect();
+ LogicalPlan::Extension(Extension {
+ node: Arc::new(NoExprExtension {
+ children,
+ schema: Arc::clone(&schema),
+ }),
+ })
+}
+
+fn build_with_expr_plan(num_children: usize, num_cols: usize) -> LogicalPlan {
+ let schema = build_schema(num_cols);
+ let children: Vec<LogicalPlan> =
+ (0..num_children).map(|_| build_child(&schema)).collect();
+ let exprs: Vec<Expr> = (0..3).map(|i| col(format!("col_{i}"))).collect();
+ LogicalPlan::Extension(Extension {
+ node: Arc::new(WithExprExtension {
+ children,
+ exprs,
+ schema: Arc::clone(&schema),
+ }),
+ })
+}
+
+// ---------------------------------------------------------------------------
+// Benchmarks
+// ---------------------------------------------------------------------------
+
+fn benchmark_map_expressions(c: &mut Criterion) {
+ let mut group = c.benchmark_group("map_expressions_extension");
+
+ let num_cols = 40;
+
+ for num_children in [1, 3, 5, 10] {
+ let no_expr_plan = build_no_expr_plan(num_children, num_cols);
+ let with_expr_plan = build_with_expr_plan(num_children, num_cols);
+
+ group.bench_with_input(
+ BenchmarkId::new("no_expr", num_children),
+ &no_expr_plan,
+ |b, plan| {
+ b.iter(|| {
+ let result = plan
+ .clone()
+ .map_expressions(|expr| Ok(Transformed::no(expr)))
+ .unwrap();
+ std::hint::black_box(result);
+ });
+ },
+ );
+
+ group.bench_with_input(
+ BenchmarkId::new("with_expr", num_children),
+ &with_expr_plan,
+ |b, plan| {
+ b.iter(|| {
+ let result = plan
+ .clone()
+ .map_expressions(|expr| Ok(Transformed::no(expr)))
+ .unwrap();
+ std::hint::black_box(result);
+ });
+ },
+ );
+ }
+
+ group.finish();
+}
+
+criterion_group!(benches, benchmark_map_expressions);
+criterion_main!(benches);
diff --git a/datafusion/expr/src/logical_plan/tree_node.rs b/datafusion/expr/src/logical_plan/tree_node.rs
index a1285510da..77991db1bf 100644
--- a/datafusion/expr/src/logical_plan/tree_node.rs
+++ b/datafusion/expr/src/logical_plan/tree_node.rs
@@ -584,17 +584,29 @@ impl LogicalPlan {
.map_elements(f)?
.update_data(|expr| LogicalPlan::Sort(Sort { expr, input, fetch })),
LogicalPlan::Extension(Extension { node }) => {
- // would be nice to avoid this copy -- maybe can
- // update extension to just observer Exprs
- let exprs = node.expressions().map_elements(f)?;
- let plan = LogicalPlan::Extension(Extension {
- node: UserDefinedLogicalNode::with_exprs_and_inputs(
- node.as_ref(),
- exprs.data,
- node.inputs().into_iter().cloned().collect::<Vec<_>>(),
- )?,
- });
- Transformed::new(plan, exprs.transformed, exprs.tnr)
+ let raw_exprs = node.expressions();
+ if raw_exprs.is_empty() {
+ // No expressions to transform — skip expensive clone of
+ // all inputs and reconstruction via with_exprs_and_inputs.
+ Transformed::no(LogicalPlan::Extension(Extension { node }))
+ } else {
+ // TODO: a more general optimization would be to change
+ // `UserDefinedLogicalNode::expressions()` to return
+ // references (`&[Expr]`) instead of cloned `Vec<Expr>`,
+ // and only clone + rebuild when the transform actually
+ // modifies an expression. This would avoid the clone +
+ // `with_exprs_and_inputs` rebuild even for non-empty
+ // expression lists when the transform is a no-op.
+ let exprs = raw_exprs.map_elements(f)?;
+ let plan = LogicalPlan::Extension(Extension {
+ node: UserDefinedLogicalNode::with_exprs_and_inputs(
+ node.as_ref(),
+ exprs.data,
+ node.inputs().into_iter().cloned().collect::<Vec<_>>(),
+ )?,
+ });
+ Transformed::new(plan, exprs.transformed, exprs.tnr)
+ }
}
LogicalPlan::TableScan(TableScan {
table_name,
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org