Skip to content

Commit 444cbfc

Browse files
goutamadwantOmega359
authored andcommitted
perf: reuse column normalization context across expressions (apache#25010)
## Which issue does this PR close? - Addresses fix (1) in apache#24777. Constructor-based logical-plan decoding remains separate. ## Rationale for this change Column normalization repeatedly collects fallback schemas and traverses the input plan for USING columns. Wide expression lists and projections repeat that work for the same immutable plan. ## What changes are included in this PR? - Introduce a private, lazy normalization context reused across columns and expression lists. - Share the context in sort normalization and validated projection construction, including wildcard expansion. - Keep already-qualified columns and expressions that do not need normalization on the existing fast path. - Add benchmarks for qualified and unqualified expressions and projection construction at several schema widths. ## What is the testing strategy for this PR? - Add `normalize_batch_schema_precedence`, `normalize_batch_using_join`, and `normalize_batch_skips_unused_plan_context` to cover schema precedence, USING joins, ambiguity/error order, sort options, and lazy handling of qualified columns and literals. - In balanced local `release-nonlto` runs, constructing a 2,000-column unqualified projection falls from about 100 ms to 35 ms. This measures projection construction, not full protobuf decoding; small controls remain noisy. - Reproduce with `cargo bench -p datafusion-expr --bench normalize_columns --profile release-nonlto`. - Focused expression and SQL tests pass. The required extended workspace test command also passes, including all 511 SQL logic-test files. - Expression-crate Clippy passes with all targets and features enabled. The complete documented `dev/rust_lint.sh` also passes, including strict workspace documentation checks. - Full-workspace Clippy with all features enabled hits the existing PostgreSQL decimal-formatting lint in apache#24974; the affected source is unchanged here. ## Are there any user-facing changes? No public API or name-resolution behavior changes are intended. Normalization reuses plan context instead of collecting it for each column; existing schema lookup costs remain.
1 parent b8c1506 commit 444cbfc

5 files changed

Lines changed: 249 additions & 32 deletions

File tree

‎Cargo.lock‎

Lines changed: 1 addition & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎datafusion/expr/Cargo.toml‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -69,9 +69,14 @@ serde_json = { workspace = true }
6969
sqlparser = { workspace = true, optional = true }
7070

7171
[dev-dependencies]
72+
criterion = { workspace = true }
7273
ctor = { workspace = true }
7374
env_logger = { workspace = true }
7475
insta = { workspace = true }
7576
# Makes sure `test_display_pg_json` behaves in a consistent way regardless of
7677
# feature unification with dependencies
7778
serde_json = { workspace = true, features = ["preserve_order"] }
79+
80+
[[bench]]
81+
name = "normalize_columns"
82+
harness = false
Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
use std::hint::black_box;
19+
20+
use arrow::datatypes::{DataType, Field, Schema};
21+
use criterion::{BenchmarkId, Criterion, criterion_group, criterion_main};
22+
use datafusion_expr::expr_rewriter::normalize_cols;
23+
use datafusion_expr::logical_plan::table_scan;
24+
use datafusion_expr::{Expr, LogicalPlanBuilder, col, lit};
25+
26+
fn normalize_columns(c: &mut Criterion) {
27+
let mut group = c.benchmark_group("normalize_columns");
28+
for width in [10, 100, 500, 2000] {
29+
let schema = Schema::new(
30+
(0..width)
31+
.map(|i| Field::new(format!("c{i}"), DataType::Int32, false))
32+
.collect::<Vec<_>>(),
33+
);
34+
let input = table_scan(Some("t"), &schema, None)
35+
.unwrap()
36+
.project(
37+
(0..width)
38+
.map(|i| (col(format!("t.c{i}")) + lit(1)).alias(format!("a{i}"))),
39+
)
40+
.unwrap()
41+
.build()
42+
.unwrap();
43+
44+
for qualified in [false, true] {
45+
let (input, qualifier) = if qualified {
46+
(
47+
LogicalPlanBuilder::from(input.clone())
48+
.alias("s")
49+
.unwrap()
50+
.build()
51+
.unwrap(),
52+
"s.",
53+
)
54+
} else {
55+
(input.clone(), "")
56+
};
57+
let exprs: Vec<Expr> = (0..width)
58+
.map(|i| {
59+
(col(format!("{qualifier}a{i}")) + lit(1)).alias(format!("b{i}"))
60+
})
61+
.collect();
62+
let kind = if qualified {
63+
"qualified"
64+
} else {
65+
"unqualified"
66+
};
67+
68+
group.bench_with_input(
69+
BenchmarkId::new(format!("expressions/{kind}"), width),
70+
&width,
71+
|b, _| {
72+
b.iter(|| {
73+
normalize_cols(black_box(exprs.clone()), black_box(&input))
74+
.unwrap()
75+
})
76+
},
77+
);
78+
group.bench_with_input(
79+
BenchmarkId::new(format!("projection/{kind}"), width),
80+
&width,
81+
|b, _| {
82+
b.iter(|| {
83+
LogicalPlanBuilder::from(black_box(input.clone()))
84+
.project(black_box(exprs.clone()))
85+
.unwrap()
86+
.build()
87+
.unwrap()
88+
})
89+
},
90+
);
91+
}
92+
}
93+
group.finish();
94+
}
95+
96+
criterion_group!(benches, normalize_columns);
97+
criterion_main!(benches);

‎datafusion/expr/src/expr_rewriter/mod.rs‎

Lines changed: 140 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ use std::sync::Arc;
2424

2525
use crate::expr::{Alias, Sort, Unnest};
2626
use crate::logical_plan::Projection;
27-
use crate::{Expr, ExprSchemable, LogicalPlan, LogicalPlanBuilder};
27+
use crate::{Expr, ExprSchemable, LogicalPlan};
2828

2929
use datafusion_common::TableReference;
3030
use datafusion_common::config::ConfigOptions;
@@ -64,20 +64,54 @@ pub trait FunctionRewrite: Debug {
6464
) -> Result<Transformed<Expr>>;
6565
}
6666

67-
/// Recursively call `LogicalPlanBuilder::normalize` on all [`Column`] expressions
68-
/// in the `expr` expression tree.
67+
/// Recursively normalize all [`Column`] expressions in the `expr` expression tree.
6968
pub fn normalize_col(expr: Expr, plan: &LogicalPlan) -> Result<Expr> {
70-
expr.transform(|expr| {
71-
Ok({
72-
if let Expr::Column(c) = expr {
73-
let col = LogicalPlanBuilder::normalize(plan, c)?;
74-
Transformed::yes(Expr::Column(col))
75-
} else {
76-
Transformed::no(expr)
77-
}
69+
ColumnNormalizer::new(plan).normalize(expr)
70+
}
71+
72+
/// Reuses the plan's normalization context across expressions. Initialize it
73+
/// lazily so literals and already-qualified columns need no plan traversal.
74+
pub(crate) struct ColumnNormalizer<'a> {
75+
plan: &'a LogicalPlan,
76+
context: Option<(Vec<&'a DFSchema>, Vec<HashSet<Column>>)>,
77+
}
78+
79+
impl<'a> ColumnNormalizer<'a> {
80+
pub(crate) fn new(plan: &'a LogicalPlan) -> Self {
81+
Self {
82+
plan,
83+
context: None,
84+
}
85+
}
86+
87+
#[inline]
88+
pub(crate) fn normalize_column(&mut self, column: Column) -> Result<Column> {
89+
if column.relation.is_some() {
90+
return Ok(column);
91+
}
92+
93+
let (fallback_schemas, using_columns) = match &mut self.context {
94+
Some(context) => context,
95+
context @ None => context.insert((
96+
self.plan.fallback_normalize_schemas(),
97+
self.plan.using_columns()?,
98+
)),
99+
};
100+
column.normalize_with_schemas_and_ambiguity_check(
101+
&[&[self.plan.schema()], fallback_schemas],
102+
using_columns,
103+
)
104+
}
105+
106+
pub(crate) fn normalize(&mut self, expr: Expr) -> Result<Expr> {
107+
expr.transform(|expr| match expr {
108+
Expr::Column(column) => self
109+
.normalize_column(column)
110+
.map(|column| Transformed::yes(Expr::Column(column))),
111+
_ => Ok(Transformed::no(expr)),
78112
})
79-
})
80-
.data()
113+
.data()
114+
}
81115
}
82116

83117
/// See [`Column::normalize_with_schemas_and_ambiguity_check`] for usage
@@ -118,21 +152,24 @@ pub fn normalize_cols(
118152
exprs: impl IntoIterator<Item = impl Into<Expr>>,
119153
plan: &LogicalPlan,
120154
) -> Result<Vec<Expr>> {
155+
let mut normalizer = ColumnNormalizer::new(plan);
121156
exprs
122157
.into_iter()
123-
.map(|e| normalize_col(e.into(), plan))
158+
.map(|e| normalizer.normalize(e.into()))
124159
.collect()
125160
}
126161

127162
pub fn normalize_sorts(
128163
sorts: impl IntoIterator<Item = impl Into<Sort>>,
129164
plan: &LogicalPlan,
130165
) -> Result<Vec<Sort>> {
166+
let mut normalizer = ColumnNormalizer::new(plan);
131167
sorts
132168
.into_iter()
133169
.map(|e| {
134170
let sort = e.into();
135-
normalize_col(sort.expr, plan)
171+
normalizer
172+
.normalize(sort.expr)
136173
.map(|expr| Sort::new(expr, sort.asc, sort.nulls_first))
137174
})
138175
.collect()
@@ -382,7 +419,7 @@ mod test {
382419

383420
use super::*;
384421
use crate::literal::lit_with_metadata;
385-
use crate::{Cast, col, lit};
422+
use crate::{Cast, LogicalPlanBuilder, col, lit};
386423
use arrow::datatypes::{DataType, Field, Schema};
387424
use datafusion_common::ScalarValue;
388425
use datafusion_common::tree_node::TreeNodeRewriter;
@@ -491,6 +528,93 @@ mod test {
491528
assert_eq!(error, expected);
492529
}
493530

531+
#[test]
532+
fn normalize_batch_schema_precedence() -> Result<()> {
533+
let schema = Schema::new(vec![
534+
Field::new("a", DataType::Int32, false),
535+
Field::new("b", DataType::Int32, false),
536+
]);
537+
let plan = crate::logical_plan::table_scan(Some("t"), &schema, None)?
538+
.project([col("t.a").alias("b")])?
539+
.build()?;
540+
let exprs = vec![col("b") + col("a"), col("other.missing"), lit(1)];
541+
let expected = vec![col("b") + col("t.a"), col("other.missing"), lit(1)];
542+
assert_eq!(super::normalize_cols(exprs.clone(), &plan)?, expected);
543+
assert_eq!(normalize_col(exprs[0].clone(), &plan)?, expected[0]);
544+
let sorts = exprs.into_iter().map(|e| e.sort(false, true));
545+
assert_eq!(
546+
normalize_sorts(sorts, &plan)?,
547+
expected
548+
.into_iter()
549+
.map(|e| e.sort(false, true))
550+
.collect::<Vec<_>>()
551+
);
552+
Ok(())
553+
}
554+
555+
#[test]
556+
fn normalize_batch_using_join() -> Result<()> {
557+
let schema = Schema::new(vec![
558+
Field::new("a", DataType::Int32, false),
559+
Field::new("b", DataType::Int32, false),
560+
]);
561+
let right =
562+
crate::logical_plan::table_scan(Some("right"), &schema, None)?.build()?;
563+
let plan = crate::logical_plan::table_scan(Some("left"), &schema, None)?
564+
.join_using(right, crate::JoinType::Inner, vec![Column::from_name("a")])?
565+
.build()?;
566+
assert_eq!(
567+
super::normalize_cols([col("a"), col("a") + col("right.a")], &plan)?,
568+
vec![col("left.a"), col("left.a") + col("right.a")]
569+
);
570+
let projected = LogicalPlanBuilder::from(plan.clone())
571+
.project([col("a").alias("key"), col("left.b").alias("value")])?
572+
.build()?;
573+
assert_eq!(
574+
projected.expressions(),
575+
vec![col("left.a").alias("key"), col("left.b").alias("value")]
576+
);
577+
let err = super::normalize_cols([col("a"), col("b"), col("missing")], &plan)
578+
.unwrap_err();
579+
assert!(
580+
err.strip_backtrace()
581+
.contains("Ambiguous reference to unqualified field b")
582+
);
583+
Ok(())
584+
}
585+
586+
#[test]
587+
fn normalize_batch_skips_unused_plan_context() -> Result<()> {
588+
let schema = Schema::new(vec![Field::new("a", DataType::Int32, false)]);
589+
let right =
590+
crate::logical_plan::table_scan(Some("right"), &schema, None)?.build()?;
591+
let mut plan = crate::logical_plan::table_scan(Some("left"), &schema, None)?
592+
.join_using(right, crate::JoinType::Inner, vec![Column::from_name("a")])?
593+
.build()?;
594+
// Invalid USING keys must only be inspected when an unqualified column
595+
// needs normalization, just as with a single expression.
596+
let LogicalPlan::Join(join) = &mut plan else {
597+
unreachable!()
598+
};
599+
join.on[0].0 = lit(1);
600+
assert!(plan.using_columns().is_err());
601+
assert!(super::normalize_cols(Vec::<Expr>::new(), &plan)?.is_empty());
602+
let exprs = vec![lit(1), col("left.a"), col("other.missing")];
603+
assert_eq!(super::normalize_cols(exprs.clone(), &plan)?, exprs);
604+
assert_eq!(normalize_col(col("left.a"), &plan)?, col("left.a"));
605+
assert_eq!(
606+
normalize_sorts([col("left.a").sort(true, false)], &plan)?,
607+
vec![col("left.a").sort(true, false)]
608+
);
609+
assert!(super::normalize_cols([col("left.a"), col("a")], &plan).is_err());
610+
let projected = LogicalPlanBuilder::from(plan.clone())
611+
.project([col("left.a")])?
612+
.build()?;
613+
assert_eq!(projected.expressions(), vec![col("left.a")]);
614+
assert!(LogicalPlanBuilder::from(plan).project([col("a")]).is_err());
615+
Ok(())
616+
}
617+
494618
#[test]
495619
fn unnormalize_cols() {
496620
let expr = col("tableA.a") + col("tableB.b");

‎datafusion/expr/src/logical_plan/builder.rs‎

Lines changed: 6 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,7 @@ use std::sync::Arc;
2626
use crate::dml::CopyTo;
2727
use crate::expr::{Alias, PlannedReplaceSelectItem, Sort as SortExpr};
2828
use crate::expr_rewriter::{
29-
coerce_plan_expr_for_schema, normalize_col,
29+
ColumnNormalizer, coerce_plan_expr_for_schema, normalize_col,
3030
normalize_col_with_schemas_and_ambiguity_check, normalize_cols, normalize_sorts,
3131
rewrite_sort_cols_by_aggs,
3232
};
@@ -1132,18 +1132,7 @@ impl LogicalPlanBuilder {
11321132
}
11331133

11341134
pub(crate) fn normalize(plan: &LogicalPlan, column: Column) -> Result<Column> {
1135-
if column.relation.is_some() {
1136-
// column is already normalized
1137-
return Ok(column);
1138-
}
1139-
1140-
let schema = plan.schema();
1141-
let fallback_schemas = plan.fallback_normalize_schemas();
1142-
let using_columns = plan.using_columns()?;
1143-
column.normalize_with_schemas_and_ambiguity_check(
1144-
&[&[schema], &fallback_schemas],
1145-
&using_columns,
1146-
)
1135+
ColumnNormalizer::new(plan).normalize_column(column)
11471136
}
11481137

11491138
/// Apply a join with on constraint and specified null equality.
@@ -2082,6 +2071,7 @@ fn project_with_validation(
20822071
) -> Result<LogicalPlan> {
20832072
let mut projected_expr = vec![];
20842073
let mut has_wildcard = false;
2074+
let mut normalizer = ColumnNormalizer::new(&plan);
20852075
for (e, validate) in expr {
20862076
let e = e.into();
20872077
match e {
@@ -2100,7 +2090,7 @@ fn project_with_validation(
21002090
for e in expanded {
21012091
if validate {
21022092
projected_expr
2103-
.push(columnize_expr(normalize_col(e, &plan)?, &plan)?)
2093+
.push(columnize_expr(normalizer.normalize(e)?, &plan)?)
21042094
} else {
21052095
projected_expr.push(e)
21062096
}
@@ -2122,15 +2112,15 @@ fn project_with_validation(
21222112
for e in expanded {
21232113
if validate {
21242114
projected_expr
2125-
.push(columnize_expr(normalize_col(e, &plan)?, &plan)?)
2115+
.push(columnize_expr(normalizer.normalize(e)?, &plan)?)
21262116
} else {
21272117
projected_expr.push(e)
21282118
}
21292119
}
21302120
}
21312121
SelectExpr::Expression(e) => {
21322122
if validate {
2133-
projected_expr.push(columnize_expr(normalize_col(e, &plan)?, &plan)?)
2123+
projected_expr.push(columnize_expr(normalizer.normalize(e)?, &plan)?)
21342124
} else {
21352125
projected_expr.push(e)
21362126
}

0 commit comments

Comments
 (0)