Skip to content

Commit 7ca68cf

Browse files
authored
perf: avoid quadratic metadata merging in union schemas (apache#26790)
## Which issue does this PR close? Related to apache#17261. Complements the fast path for equal schemas added in apache#24389. Benchmark coverage is reviewed in apache#26791. This PR is stacked on its benchmark-only commit `cfc6594b5`; the [optimization-only diff](apache/datafusion@cfc6594...c5f9d3e) contains the schema change and regression test. ## Rationale for this change Constructing a union with unequal input schemas can take quadratic time in the number of children. The fallback merges every input's field metadata before checking whether that candidate field is nullable. With non-nullable fields, the same full merge is repeated for every child. Select the first nullable field (or the first field when none are nullable) before merging metadata. This makes the fallback linear in child count for a fixed number of fields and metadata entries per input. The shared helper also serves `InterleaveExec`. ## What changes are included in this PR? - Merge metadata once per output field, preserving the selected field, leftmost name, and existing metadata conflict precedence. - Add a test that constructs and executes unions with non-nullable inputs, first/middle/last nullable inputs, conflicting and distinct metadata keys, and checks output rows. ## What is the testing strategy for this PR? Benchmarks use upstream `c18e5d974` plus the benchmark extension, Rust 1.99.1, `release-nonlto`, and an Apple M5 Pro. The table averages two interleaved runs per binary, with 20 Criterion samples per run. Schemas have 10 fields and two metadata entries per field. | Non-nullable schema case | Children | Upstream | Patched | Speedup | | --- | ---: | ---: | ---: | ---: | | Last child's metadata differs | 10 | 141 µs | 62 µs | 2.3× | | Last child's metadata differs | 100 | 9.24 ms | 0.66 ms | 14.1× | | Last child's metadata differs | 1,000 | 877 ms | 7.40 ms | 118.6× | | Field names differ | 10 | 140 µs | 60 µs | 2.3× | | Field names differ | 100 | 9.38 ms | 0.66 ms | 14.3× | | Field names differ | 1,000 | 866 ms | 7.36 ms | 117.6× | The controls with nullable fields or equal schemas at 4,000 children varied from -0.8% to +6.3% on this shared machine. Background builds affected some measurements, so the larger SQL cases with sorted unions were also checked in a tighter alternating sequence, with four runs per binary: | SQL planning case | Upstream | Patched | Change | | --- | ---: | ---: | ---: | | 50 columns, Int64 | 38.61 ms | 38.40 ms | -0.5% | | 50 columns, UInt64 | 139.48 ms | 139.63 ms | +0.1% | These results establish the constructor improvement independently of apache#17261; they do not establish an improvement in the SQL planning workloads. The original extended logical-planning benchmark only calls logical optimization and does not exercise this physical schema helper. To run the benchmark cases from apache#26791: ```sh cargo bench --profile release-nonlto -p datafusion-physical-plan --bench union_schema -- union_exec_try_new_non_nullable ``` ## Are there any user-facing changes? Faster construction of unions and interleaves with unequal schemas and non-nullable fields. Schema behavior and public APIs are preserved. AI assistance: OpenAI Codex.
1 parent 8f77b41 commit 7ca68cf

2 files changed

Lines changed: 110 additions & 30 deletions

File tree

‎datafusion/physical-plan/benches/union_schema.rs‎

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,9 @@
1212
//! the scan runs, fails on the final child, then the full merge runs anyway.
1313
//! - `names_differ`: the first field is renamed in every child but the first,
1414
//! the common real-world unequal union where equality fails immediately.
15+
//!
16+
//! The non-nullable cases also require scanning all children to determine
17+
//! output nullability, rather than stopping at the first nullable field.
1518
1619
use std::collections::HashMap;
1720
use std::sync::Arc;
@@ -32,10 +35,10 @@ fn metadata(tag: &str, i: usize) -> HashMap<String, String> {
3235
.collect()
3336
}
3437

35-
fn flat_schema() -> Schema {
38+
fn flat_schema(nullable: bool) -> Schema {
3639
let fields: Vec<Field> = (0..NUM_FIELDS)
3740
.map(|i| {
38-
Field::new(format!("col_{i}"), DataType::Int64, true)
41+
Field::new(format!("col_{i}"), DataType::Int64, nullable)
3942
.with_metadata(metadata("f", i))
4043
})
4144
.collect();
@@ -107,8 +110,9 @@ fn children_last_differs(schema: &Schema, n: usize) -> Vec<Arc<dyn ExecutionPlan
107110

108111
fn bench_union_construction(c: &mut Criterion) {
109112
for (suffix, schema, sizes) in [
110-
("", flat_schema(), &[100usize, 1000, 4000][..]),
113+
("", flat_schema(true), &[100usize, 1000, 4000][..]),
111114
("_nested", nested_schema(), &[1000, 4000][..]),
115+
("_non_nullable", flat_schema(false), &[10, 100, 1000][..]),
112116
] {
113117
let mut group = c.benchmark_group(format!("union_exec_try_new{suffix}"));
114118
for &n in sizes {

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

Lines changed: 103 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@ use crate::statistics::{ChildStats, StatisticsArgs};
3333
use crate::stream::ObservedStream;
3434
use crate::{ChildrenPropertiesMode, ReplaceChildrenOptions, validate_child_count};
3535

36-
use arrow::datatypes::{Field, Metadata, Schema, SchemaRef};
36+
use arrow::datatypes::{Metadata, Schema, SchemaRef};
3737
use arrow::record_batch::RecordBatch;
3838
use datafusion_common::config::ConfigOptions;
3939
use datafusion_common::stats::NdvFallback;
@@ -970,8 +970,8 @@ fn union_schema(inputs: &[Arc<dyn ExecutionPlan>]) -> Result<SchemaRef> {
970970
let first_schema = inputs[0].schema();
971971

972972
// Fast path: when every input already shares the first input's schema, the
973-
// field-by-field metadata/nullability merge below is redundant work that
974-
// scales as O(n^2 * fields). This is common in practice: unions built from
973+
// field-by-field metadata/nullability merge below is redundant work.
974+
// This is common in practice: unions built from
975975
// repartitioned copies of the same plan (e.g. observed in InfluxDB) hand us
976976
// children that all carry the exact same schema. A pointer-equality check
977977
// catches the shared-`Arc` case for free, and a content `==` comparison
@@ -1003,31 +1003,29 @@ fn union_schema(inputs: &[Arc<dyn ExecutionPlan>]) -> Result<SchemaRef> {
10031003
// which also uses the left side names.
10041004
let base_field = first_schema.field(i).clone();
10051005

1006-
// Coerce metadata and nullability across all inputs
1007-
1008-
inputs
1006+
// Select the first nullable field, or the first field if none are
1007+
// nullable, before merging metadata. Otherwise, each non-nullable
1008+
// candidate would repeat the full metadata merge.
1009+
let (input_idx, input) = inputs
10091010
.iter()
10101011
.enumerate()
1011-
.map(|(input_idx, input)| {
1012-
let field = input.schema().field(i).clone();
1013-
let mut metadata = field.metadata().clone();
1014-
1015-
let other_metadatas = inputs
1016-
.iter()
1017-
.enumerate()
1018-
.filter(|(other_idx, _)| *other_idx != input_idx)
1019-
.flat_map(|(_, other_input)| {
1020-
other_input.schema().field(i).metadata().clone().into_iter()
1021-
});
1022-
1023-
metadata.extend(other_metadatas);
1024-
field.with_metadata(metadata)
1025-
})
1026-
.find_or_first(Field::is_nullable)
1027-
// We can unwrap this because if inputs was empty, this would've already panic'ed when we
1028-
// indexed into inputs[0].
1029-
.unwrap()
1030-
.with_name(base_field.name())
1012+
.find_or_first(|(_, input)| input.schema().field(i).is_nullable())
1013+
// Empty inputs are rejected above.
1014+
.unwrap();
1015+
let field = input.schema().field(i).clone();
1016+
let mut metadata = field.metadata().clone();
1017+
1018+
// Preserve precedence: the selected field's metadata comes first,
1019+
// followed by the other inputs in their original order.
1020+
let other_metadatas = inputs
1021+
.iter()
1022+
.enumerate()
1023+
.filter(|(other_idx, _)| *other_idx != input_idx)
1024+
.flat_map(|(_, other_input)| {
1025+
other_input.schema().field(i).metadata().clone().into_iter()
1026+
});
1027+
metadata.extend(other_metadatas);
1028+
field.with_metadata(metadata).with_name(base_field.name())
10311029
})
10321030
.collect::<Vec<_>>();
10331031

@@ -1119,7 +1117,7 @@ mod tests {
11191117
use crate::test::{self, TestMemoryExec};
11201118

11211119
use arrow::compute::SortOptions;
1122-
use arrow::datatypes::DataType;
1120+
use arrow::datatypes::{DataType, Field};
11231121
use datafusion_common::SplitPoint;
11241122
use datafusion_common::stats::Precision;
11251123
use datafusion_common::{ColumnStatistics, ScalarValue};
@@ -1725,6 +1723,84 @@ mod tests {
17251723
Ok(())
17261724
}
17271725

1726+
#[tokio::test]
1727+
async fn test_union_schema_metadata_and_nullability() -> Result<()> {
1728+
use arrow::array::Int32Array;
1729+
1730+
// Field metadata from the selected field is merged first, followed by
1731+
// the other inputs in order. Schema metadata always follows input order.
1732+
for (nullability, expected_field_value) in [
1733+
([false, false, false], "input2"),
1734+
([true, false, false], "input2"),
1735+
([false, true, false], "input2"),
1736+
([false, false, true], "input1"),
1737+
([true, true, true], "input2"),
1738+
] {
1739+
let inputs = nullability
1740+
.iter()
1741+
.enumerate()
1742+
.map(|(i, &nullable)| {
1743+
let metadata = Metadata::from([
1744+
("shared".to_owned(), format!("input{i}")),
1745+
(format!("only{i}"), "kept".to_owned()),
1746+
]);
1747+
let field =
1748+
Field::new(format!("value{i}"), DataType::Int32, nullable)
1749+
.with_metadata(metadata.clone());
1750+
let schema =
1751+
Arc::new(Schema::new_with_metadata(vec![field], metadata));
1752+
let batch = RecordBatch::try_new(
1753+
Arc::clone(&schema),
1754+
vec![Arc::new(Int32Array::from(vec![i as i32]))],
1755+
)?;
1756+
let input: Arc<dyn ExecutionPlan> =
1757+
TestMemoryExec::try_new_exec(&[vec![batch]], schema, None)?;
1758+
Ok(input)
1759+
})
1760+
.collect::<Result<Vec<_>>>()?;
1761+
1762+
let expected_metadata = Metadata::from([
1763+
("shared".to_owned(), expected_field_value.to_owned()),
1764+
("only0".to_owned(), "kept".to_owned()),
1765+
("only1".to_owned(), "kept".to_owned()),
1766+
("only2".to_owned(), "kept".to_owned()),
1767+
]);
1768+
let mut expected_schema_metadata = expected_metadata.clone();
1769+
expected_schema_metadata.insert("shared".to_owned(), "input2".to_owned());
1770+
let expected_schema = Arc::new(Schema::new_with_metadata(
1771+
vec![
1772+
Field::new("value0", DataType::Int32, nullability.contains(&true))
1773+
.with_metadata(expected_metadata),
1774+
],
1775+
expected_schema_metadata,
1776+
));
1777+
1778+
let union = UnionExec::try_new(inputs)?;
1779+
assert_eq!(union.schema(), expected_schema, "{nullability:?}");
1780+
let batches = collect(union, Arc::new(TaskContext::default())).await?;
1781+
datafusion_common::assert_batches_sorted_eq!(
1782+
[
1783+
"+--------+",
1784+
"| value0 |",
1785+
"+--------+",
1786+
"| 0 |",
1787+
"| 1 |",
1788+
"| 2 |",
1789+
"+--------+"
1790+
],
1791+
&batches
1792+
);
1793+
for batch in batches {
1794+
assert_eq!(
1795+
batch.schema().fields(),
1796+
expected_schema.fields(),
1797+
"{nullability:?}"
1798+
);
1799+
}
1800+
}
1801+
Ok(())
1802+
}
1803+
17281804
#[test]
17291805
fn test_union_schema_mismatch() {
17301806
// Test that UnionExec properly rejects inputs with different field counts

0 commit comments

Comments
 (0)