Skip to content

Commit c5f9d3e

Browse files
committed
perf: avoid quadratic metadata merging in union schemas
Select the output field before merging metadata so non-nullable inputs do not repeat the merge for every candidate. Preserve metadata precedence and cover the fallback with execution tests and scaling benchmarks. Generated-by: OpenAI Codex
1 parent cfc6594 commit c5f9d3e

1 file changed

Lines changed: 103 additions & 27 deletions

File tree

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

Lines changed: 103 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,7 @@ use crate::statistics::{ChildStats, StatisticsArgs};
4646
use crate::stream::ObservedStream;
4747
use crate::{ChildrenPropertiesMode, ReplaceChildrenOptions, validate_child_count};
4848

49-
use arrow::datatypes::{Field, Metadata, Schema, SchemaRef};
49+
use arrow::datatypes::{Metadata, Schema, SchemaRef};
5050
use arrow::record_batch::RecordBatch;
5151
use datafusion_common::config::ConfigOptions;
5252
use datafusion_common::stats::NdvFallback;
@@ -983,8 +983,8 @@ fn union_schema(inputs: &[Arc<dyn ExecutionPlan>]) -> Result<SchemaRef> {
983983
let first_schema = inputs[0].schema();
984984

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

1019-
// Coerce metadata and nullability across all inputs
1020-
1021-
inputs
1019+
// Select the first nullable field, or the first field if none are
1020+
// nullable, before merging metadata. Otherwise, each non-nullable
1021+
// candidate would repeat the full metadata merge.
1022+
let (input_idx, input) = inputs
10221023
.iter()
10231024
.enumerate()
1024-
.map(|(input_idx, input)| {
1025-
let field = input.schema().field(i).clone();
1026-
let mut metadata = field.metadata().clone();
1027-
1028-
let other_metadatas = inputs
1029-
.iter()
1030-
.enumerate()
1031-
.filter(|(other_idx, _)| *other_idx != input_idx)
1032-
.flat_map(|(_, other_input)| {
1033-
other_input.schema().field(i).metadata().clone().into_iter()
1034-
});
1035-
1036-
metadata.extend(other_metadatas);
1037-
field.with_metadata(metadata)
1038-
})
1039-
.find_or_first(Field::is_nullable)
1040-
// We can unwrap this because if inputs was empty, this would've already panic'ed when we
1041-
// indexed into inputs[0].
1042-
.unwrap()
1043-
.with_name(base_field.name())
1025+
.find_or_first(|(_, input)| input.schema().field(i).is_nullable())
1026+
// Empty inputs are rejected above.
1027+
.unwrap();
1028+
let field = input.schema().field(i).clone();
1029+
let mut metadata = field.metadata().clone();
1030+
1031+
// Preserve precedence: the selected field's metadata comes first,
1032+
// followed by the other inputs in their original order.
1033+
let other_metadatas = inputs
1034+
.iter()
1035+
.enumerate()
1036+
.filter(|(other_idx, _)| *other_idx != input_idx)
1037+
.flat_map(|(_, other_input)| {
1038+
other_input.schema().field(i).metadata().clone().into_iter()
1039+
});
1040+
metadata.extend(other_metadatas);
1041+
field.with_metadata(metadata).with_name(base_field.name())
10441042
})
10451043
.collect::<Vec<_>>();
10461044

@@ -1132,7 +1130,7 @@ mod tests {
11321130
use crate::test::{self, TestMemoryExec};
11331131

11341132
use arrow::compute::SortOptions;
1135-
use arrow::datatypes::DataType;
1133+
use arrow::datatypes::{DataType, Field};
11361134
use datafusion_common::SplitPoint;
11371135
use datafusion_common::stats::Precision;
11381136
use datafusion_common::{ColumnStatistics, ScalarValue};
@@ -1738,6 +1736,84 @@ mod tests {
17381736
Ok(())
17391737
}
17401738

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

0 commit comments

Comments
 (0)