Skip to content

Commit 47794ff

Browse files
authored
Improve planning speed: Fast path for union_schema when all children share a schema (apache#24389)
## Which issue does this close? Complements apache#19792. Fits with the wide-`UnionExec` planning-cost work, but originates from an InfluxDB issue. ## Rationale for this change `union_schema` builds the output schema for `UnionExec` and `InterleaveExec` by coercing field metadata and nullability across **every** child. That merge is quadratic in the number of children: for each output field it walks all inputs, and for each input it walks *every other* input to union field-level metadata. For a union of `n` children with `f` fields the construction cost is `O(n^2 * f)` (worse when fields carry metadata). For narrow unions this is insignificant. It matters when a plan fans a single source out into many identical-schema children and unions them back together -- e.g. a union assembled from repartitioned copies of the same input. An instance like this occurred with InfluxDB: every child schema was the same, so the merge, guaranteed to reproduce the first child's schema, unnecessarily incurred the planning latency penalty from `O(n^2 * f)` complexity. ### Relationship to apache#19792 `UnionExec` construction has two quadratic halves: - **`with_new_children` / `PlanProperties`** -- addressed by apache#19792 (`with_new_children_and_same_properties`, `Arc<PlanProperties>`, the properties fast path). Already on `main`. - **`union_schema`** -- *not* covered by apache#19792 and still quadratic on `main`. This PR complements it by making `union_schema` skip the merge when it can't change the result. It deliberately doesn't touch `with_new_children`; that path is already handled. ## What changes are included? A fast path at the top of `union_schema`: after taking `inputs[0].schema()`, if every remaining child's schema is either the **same allocation** (`Arc::ptr_eq`) or **structurally equal** (`==`) to the first, return the first schema immediately. Otherwise we fall through to the existing full merge, so behavior for genuinely heterogeneous unions is byte-for-byte unchanged. ```rust let first_schema = inputs[0].schema(); if inputs[1..].iter().all(|input| { let schema = input.schema(); Arc::ptr_eq(&schema, &first_schema) || schema == first_schema }) { return Ok(first_schema); } ``` `InterleaveExec` shares `union_schema`, so it gets the same speedup for free. ## On the cost of the deep compare... The natural objection (which came up before this PR): **doesn't the deep `==` make the *unequal* case slower?** I'll paraphrase the prior conclusions, risking verbosity to avoid rehashing the discussion. Spoiler: it's not an issue. - The equal case avoids the merge, and its check is cheap. The shared-`Arc` case is settled by pointer comparison. The distinct-but-equal case runs `Schema::eq`, which is allocation-free and short-circuits on the first difference. Benchmarks show a small loss versus a pointer-equality-only control (the theoretical floor) but it still beats the full merge by a wide margin, and that advantage grows with schema complexity. - The adversarial worst case is bounded. The one shape where the scan is pure overhead is `last_differs`: children `0..n-1` are equal and the last diverges, so we scan `n` schemas, fail on the last, then merge anyway. That's a single linear `==` pass bounded by the merge that follows -- a constant fraction, not another factor of `n` -- and it takes *thousands* of near-identical children differing only in the last to hit. - Ordinary unequal unions fail fast. `SELECT a ... UNION ALL SELECT b ...` differs at field 0, so `==` rejects on the first field (see `names_differ`). And `UnionExec::try_new` already rejects misaligned children, so the only divergence `union_schema` ever sees is top-level (caught in the first pass). ## Benchmark results New bench `datafusion/physical-plan/benches/union_schema.rs` measures `UnionExec::try_new` construction over a flat schema and a nested/struct schema, for the four child shapes above. Run interleaved (baseline / patched alternated per cell) on a fixed-clock T2D VM. ### `union_schema` construction (lower is better) | scenario | n | baseline (ms) | patched (ms) | change | |---|---|---|---|---| | union_exec_try_new/shared_arc | 100 | 0.263 | 0.042 | 6.2× | | union_exec_try_new/shared_arc | 1000 | 2.60 | 0.429 | 6.1× | | union_exec_try_new/shared_arc | 4000 | 10.5 | 1.74 | 6.0× | | union_exec_try_new/content_equal | 100 | 0.262 | 0.042 | 6.2× | | union_exec_try_new/content_equal | 1000 | 2.61 | 0.433 | 6.0× | | union_exec_try_new/content_equal | 4000 | 10.5 | 1.74 | 6.0× | | union_exec_try_new/last_differs | 4000 | ~98 | ~97 | flat (±1.5%) | | union_exec_try_new/names_differ | 4000 | ~87 | ~87 | flat (±1%) | | union_exec_try_new_nested/content_equal | 1000 | 2.68 | 0.431 | 6.2× | | union_exec_try_new_nested/content_equal | 4000 | 10.8 | 1.73 | 6.2× | The `last_differs` (adversarial: N-1 children equal, deep compare then full merge) and `names_differ` (typical unequal: fails on the first field) cells were re-measured with tight per-cell interleaving (baseline/patched adjacent, 4 rounds) to control for variance: both are within ±1.5%, straddling zero. Interpretation: the **deep compare cost isn't observable end to end**. ### End-to-end planning: no regression (`sql_planner`) `cargo bench --bench sql_planner` (TPC-H + ClickBench) run baseline vs patched on the fixed-clock T2D VM. Every case lands within ±1% -- run-to-run noise -- with no case regressing beyond that noise. Notable rows, including the union-heavy `sorted_union` cases the fast path is meant to help: | case | baseline (ms) | patched (ms) | |---|---|---| | physical_plan_tpcds_all | 995.9 ± 1.4 | 991.9 ± 1.9 | | physical_plan_tpch_all | 60.4 ± 0.2 | 60.3 ± 0.1 | | physical_sorted_union_order_by_50 | 349.9 ± 2.4 | 346.3 ± 2.7 | | physical_sorted_union_order_by_10 | 12.3 ± 0.03 | 12.2 ± 0.07 | | physical_select_all_from_1000 | 30.8 ± 0.25 | 30.7 ± 0.08 | The full TPC-H q1-q22 and ClickBench sets are all flat (ratio is 1.00-1.01 in both directions). Separately, interleaving tests per-cell (baseline and patched back-to-back, so run-to-run variance -- e.g. thermal -- cancels rather than favoring one) for `physical_join_distinct` + eight ClickBench queries (4 rounds) confirmed the same thing: patched and baseline straddle zero; no systematic regression from the deep compare. ## Testing - `cargo test -p datafusion-physical-plan --lib union` -- all pass, including a new `test_union_schema_fast_path_content_equal` that exercises the `==` branch with pointer-distinct-but-equal schemas and asserts the result matches the shared schema (i.e. identical to the slow-path merge). - `cargo clippy -p datafusion-physical-plan --lib -- -D warnings` -- clean. - `cargo bench --bench union_schema` -- compiles and runs. ## Are there any user-facing changes? No: planning-time performance change only, results and schema are identical. --------- Signed-off-by: Reid Kaufmann <[email protected]>
1 parent bb45fb8 commit 47794ff

3 files changed

Lines changed: 209 additions & 0 deletions

File tree

‎datafusion/physical-plan/Cargo.toml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -108,6 +108,10 @@ tokio = { workspace = true, features = [
108108
harness = false
109109
name = "partial_ordering"
110110

111+
[[bench]]
112+
harness = false
113+
name = "union_schema"
114+
111115
[[bench]]
112116
harness = false
113117
name = "spill_io"
Lines changed: 159 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,159 @@
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+
//! Benchmark for `UnionExec` construction cost as a function of child count.
19+
//!
20+
//! Scenarios (run against a flat and a nested/struct schema):
21+
//! - `shared_arc`: every child returns the same `Arc<Schema>`
22+
//! - `content_equal`: pointer-distinct but identical schemas per child
23+
//! - `last_differs`: all children equal except extra metadata on the last
24+
//! child's last top-level field. Worst case for the equality fast path:
25+
//! the scan runs, fails on the final child, then the full merge runs anyway.
26+
//! - `names_differ`: the first field is renamed in every child but the first,
27+
//! the common real-world unequal union where equality fails immediately.
28+
29+
use std::collections::HashMap;
30+
use std::sync::Arc;
31+
32+
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
33+
use criterion::{BenchmarkId, Criterion, criterion_group, criterion_main};
34+
use datafusion_physical_plan::ExecutionPlan;
35+
use datafusion_physical_plan::empty::EmptyExec;
36+
use datafusion_physical_plan::union::UnionExec;
37+
38+
const NUM_FIELDS: usize = 10;
39+
const NESTED_CHILDREN: usize = 5;
40+
const METADATA_PER_FIELD: usize = 2;
41+
42+
fn metadata(tag: &str, i: usize) -> HashMap<String, String> {
43+
(0..METADATA_PER_FIELD)
44+
.map(|m| (format!("key_{m}"), format!("value_{tag}_{i}_{m}")))
45+
.collect()
46+
}
47+
48+
fn flat_schema() -> Schema {
49+
let fields: Vec<Field> = (0..NUM_FIELDS)
50+
.map(|i| {
51+
Field::new(format!("col_{i}"), DataType::Int64, true)
52+
.with_metadata(metadata("f", i))
53+
})
54+
.collect();
55+
Schema::new(fields)
56+
}
57+
58+
fn nested_schema() -> Schema {
59+
let fields: Vec<Field> = (0..NUM_FIELDS)
60+
.map(|i| {
61+
let children: Vec<Field> = (0..NESTED_CHILDREN)
62+
.map(|c| {
63+
Field::new(format!("sub_{i}_{c}"), DataType::Int64, true)
64+
.with_metadata(metadata("n", i * NESTED_CHILDREN + c))
65+
})
66+
.collect();
67+
Field::new(format!("col_{i}"), DataType::Struct(children.into()), true)
68+
.with_metadata(metadata("s", i))
69+
})
70+
.collect();
71+
Schema::new(fields)
72+
}
73+
74+
/// Clone `schema` with extra metadata on its last field. Divergence must stay
75+
/// at the top level: differing nested fields change the field `DataType`
76+
/// itself, which `UnionExec::try_new` rejects ("Schemas have to be aligned").
77+
fn divergent(schema: &Schema) -> Schema {
78+
let mut fields: Vec<Field> =
79+
schema.fields().iter().map(|f| f.as_ref().clone()).collect();
80+
let last = fields.pop().unwrap();
81+
let mut md = last.metadata().clone();
82+
md.insert("divergent".to_string(), "true".to_string());
83+
fields.push(last.with_metadata(md));
84+
Schema::new(fields)
85+
}
86+
87+
fn child(schema: SchemaRef) -> Arc<dyn ExecutionPlan> {
88+
Arc::new(EmptyExec::new(schema))
89+
}
90+
91+
fn children_shared_arc(schema: &Schema, n: usize) -> Vec<Arc<dyn ExecutionPlan>> {
92+
let schema: SchemaRef = Arc::new(schema.clone());
93+
(0..n).map(|_| child(Arc::clone(&schema))).collect()
94+
}
95+
96+
fn children_content_equal(schema: &Schema, n: usize) -> Vec<Arc<dyn ExecutionPlan>> {
97+
(0..n).map(|_| child(Arc::new(schema.clone()))).collect()
98+
}
99+
100+
/// First child keeps `schema`; the rest rename the first field — the common
101+
/// real-world unequal union (`SELECT a .. UNION ALL SELECT b ..`), where any
102+
/// equality check fails immediately.
103+
fn children_names_differ(schema: &Schema, n: usize) -> Vec<Arc<dyn ExecutionPlan>> {
104+
let mut fields: Vec<Field> =
105+
schema.fields().iter().map(|f| f.as_ref().clone()).collect();
106+
let first = fields.remove(0);
107+
let renamed = first.clone().with_name(format!("renamed_{}", first.name()));
108+
fields.insert(0, renamed);
109+
let alt = Schema::new(fields);
110+
let mut children = vec![child(Arc::new(schema.clone()))];
111+
children.extend((1..n).map(|_| child(Arc::new(alt.clone()))));
112+
children
113+
}
114+
115+
fn children_last_differs(schema: &Schema, n: usize) -> Vec<Arc<dyn ExecutionPlan>> {
116+
let mut children = children_content_equal(schema, n - 1);
117+
children.push(child(Arc::new(divergent(schema))));
118+
children
119+
}
120+
121+
fn bench_union_construction(c: &mut Criterion) {
122+
for (suffix, schema, sizes) in [
123+
("", flat_schema(), &[100usize, 1000, 4000][..]),
124+
("_nested", nested_schema(), &[1000, 4000][..]),
125+
] {
126+
let mut group = c.benchmark_group(format!("union_exec_try_new{suffix}"));
127+
for &n in sizes {
128+
let shared = children_shared_arc(&schema, n);
129+
let content = children_content_equal(&schema, n);
130+
let differs = children_last_differs(&schema, n);
131+
132+
group.bench_with_input(
133+
BenchmarkId::new("shared_arc", n),
134+
&shared,
135+
|b, ch| b.iter(|| UnionExec::try_new(ch.clone()).unwrap()),
136+
);
137+
group.bench_with_input(
138+
BenchmarkId::new("content_equal", n),
139+
&content,
140+
|b, ch| b.iter(|| UnionExec::try_new(ch.clone()).unwrap()),
141+
);
142+
group.bench_with_input(
143+
BenchmarkId::new("last_differs", n),
144+
&differs,
145+
|b, ch| b.iter(|| UnionExec::try_new(ch.clone()).unwrap()),
146+
);
147+
let names = children_names_differ(&schema, n);
148+
group.bench_with_input(
149+
BenchmarkId::new("names_differ", n),
150+
&names,
151+
|b, ch| b.iter(|| UnionExec::try_new(ch.clone()).unwrap()),
152+
);
153+
}
154+
group.finish();
155+
}
156+
}
157+
158+
criterion_group!(benches, bench_union_construction);
159+
criterion_main!(benches);

‎datafusion/physical-plan/src/union.rs‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -916,6 +916,22 @@ fn union_schema(inputs: &[Arc<dyn ExecutionPlan>]) -> Result<SchemaRef> {
916916
}
917917

918918
let first_schema = inputs[0].schema();
919+
920+
// Fast path: when every input already shares the first input's schema, the
921+
// field-by-field metadata/nullability merge below is redundant work that
922+
// scales as O(n^2 * fields). This is common in practice: unions built from
923+
// repartitioned copies of the same plan (e.g. observed in InfluxDB) hand us
924+
// children that all carry the exact same schema. A pointer-equality check
925+
// catches the shared-`Arc` case for free, and a content `==` comparison
926+
// catches distinct-but-equal schemas; both let us return early and hand back
927+
// the first schema unchanged.
928+
if inputs[1..].iter().all(|input| {
929+
let schema = input.schema();
930+
Arc::ptr_eq(&schema, &first_schema) || schema == first_schema
931+
}) {
932+
return Ok(first_schema);
933+
}
934+
919935
let first_field_count = first_schema.fields().len();
920936

921937
// validate that all inputs have the same number of fields
@@ -1627,6 +1643,36 @@ mod tests {
16271643
Ok(())
16281644
}
16291645

1646+
#[test]
1647+
fn test_union_schema_fast_path_content_equal() -> Result<()> {
1648+
// Inputs whose schemas are pointer-distinct but structurally equal must
1649+
// take the content-equality (`==`) fast path and still produce a schema
1650+
// equal to the shared one, matching the slow-path merge exactly.
1651+
let schema = create_test_schema()?;
1652+
let distinct: SchemaRef = Arc::new((*schema).clone());
1653+
// Guard the branch under test: these must NOT be the same allocation, so
1654+
// the fast path is reached via `==` rather than `Arc::ptr_eq`.
1655+
assert!(!Arc::ptr_eq(&schema, &distinct));
1656+
1657+
let memory_exec1 =
1658+
Arc::new(TestMemoryExec::try_new(&[], Arc::clone(&schema), None)?);
1659+
let memory_exec2 =
1660+
Arc::new(TestMemoryExec::try_new(&[], Arc::clone(&distinct), None)?);
1661+
let memory_exec3 =
1662+
Arc::new(TestMemoryExec::try_new(&[], Arc::clone(&distinct), None)?);
1663+
1664+
// Capture the first child's schema before it is moved into the union.
1665+
let first_input_schema = memory_exec1.schema();
1666+
let union_plan =
1667+
UnionExec::try_new(vec![memory_exec1, memory_exec2, memory_exec3])?;
1668+
1669+
// The fast path returns the first child's schema Arc unchanged. Assert
1670+
// pointer equality (not just `==`): a slow-path merge would build a new,
1671+
// merely-equal Schema, so only ptr-eq proves the merge was skipped.
1672+
assert!(Arc::ptr_eq(&union_plan.schema(), &first_input_schema));
1673+
Ok(())
1674+
}
1675+
16301676
#[test]
16311677
fn test_union_schema_mismatch() {
16321678
// Test that UnionExec properly rejects inputs with different field counts

0 commit comments

Comments
 (0)