Skip to content

Commit d040501

Browse files
fix: Derive Substrait intersection nullability from every input (#25091)
## Which issue does this PR close? - Closes #25042. ## Rationale for this change The Substrait consumer derived all three intersection schemas from the primary input alone, so a field the intersection makes required stayed nullable in the logical output schema. The [Set Operation rules] give intersections a different rule: for the multiset intersections a field is required as soon as any input requires it, and for `INTERSECTION_PRIMARY` it is nullable only when it is nullable in the primary input and in at least one secondary input. `from_set_rel` builds intersections with `LogicalPlanBuilder::intersect`, which compiles to a left semi join and therefore keeps the left input's nullability. [Set Operation rules]: https://substrait.io/relations/logical_relations/#set-operation ## What changes are included in this PR? Intersections now go through a small helper that gives the result `left AND right` nullability per field. The join matches nulls with nulls (`NullEquality::NullEqualsNull`) on every field, so a left row holding a null in some field only survives when the right input holds a null there too — a field is nullable in the result only when both inputs make it nullable. Applied to each step, that single rule reproduces both spec rules: - the multiset intersections chain pairwise, so the result is required when any input requires it; - for `INTERSECTION_PRIMARY` the right side is the union of the secondary inputs, whose field is nullable exactly when some secondary makes it nullable, which yields "nullable in the primary and in at least one secondary". How the narrowing is built matters, because it has to hold in the physical plan too, not only in the logical schema. When the right input requires a field that the left input leaves nullable, the intersection is built as an inner join (nulls equal nulls) against the distinct right rows, and that field is read from the right side: - matched rows hold equal values, so the result rows are unchanged; - the field is non-nullable because its source column is, and the logical and the physical planner both derive that from the input schema, so the logical schema, the physical plan and the batches agree without any schema override; - joining against distinct right rows keeps each left row at most once, as the semi join does (and the left side is still made distinct unless `is_all`). A field is only read from the right side when its type matches the left's; its metadata does not matter, since metadata is no part of nullability. The result should still describe the left input, so where the inputs' metadata disagree the left's wins: a column read from the right is aliased with the left field's metadata, and an inner join's schema lets the left input's schema metadata win (in the logical and in the physical plan alike). Keys that only the right input carries, on a field or on the schema, are merged into the result. When nothing needs narrowing, the plan is exactly the one `LogicalPlanBuilder::intersect` builds today, so the common all-nullable case is untouched. Unions and the `MINUS` operations are not affected. ## What is the testing strategy for this PR? New test `intersect_nullability` in `datafusion/substrait/tests/cases/logical_plans.rs`, with three plans added under `tests/testdata/test_plans/`. They intersect three tables carrying the same six columns (`?` marks nullable, `~` marks `NULLABILITY_UNSPECIFIED`, which the consumer reads as nullable): ``` primary a? b? c? d? e? f? secondary a b c? d? e~ f~ secondary a b? c d? e? f ``` | Operation | Result | | --- | --- | | `INTERSECTION_PRIMARY` | `a, b?, c?, d?, e?, f?` | | `INTERSECTION_MULTISET` | `a, b, c, d?, e?, f` | | `INTERSECTION_MULTISET_ALL` | `a, b, c, d?, e?, f` | Columns `e` and `f` pin the unspecified-nullability boundary: if it were read as required, `e` would come out required for the multiset intersections and `f` for `INTERSECTION_PRIMARY`. The tables are given rows, including nulls, and for each plan the test checks that the logical schema, the physical plan's schema and the schema of every collected batch are equal, and checks the result rows. It fails on `main` (`a?` where `a` is expected), and the physical-schema check also fails against a narrowing done with a logical-only `Projection`. Each plan also runs a second time over tables with differing schema and field metadata: the secondary tables share their metadata, which differs from the primary's and adds a key the primary lacks. That run checks that the primary's metadata wins on the keys the tables disagree on, and that the logical schema, the physical plan's schema and the collected batches' schemas agree. It fails without the metadata handling (`a?` where `a` is expected). The secondary tables share their metadata on purpose: a `Union` of inputs with differing field metadata can report different metadata in its logical and in its physical schema. That is independent of this change (plain SQL, `SELECT a FROM t1 UNION ALL SELECT a FROM t2`, shows it on a checkout without it), and I have not root-caused it. With the spec's full input pattern from the issue (`R` = required, `N` = nullable), both the logical and the physical schema now match the expected column: ``` primary: R R R R N N N N secondary 1: R R N N R R N N secondary 2: R N R N R N R N INTERSECTION_PRIMARY R R R R R N N N INTERSECTION_MULTISET R R R R R R R N INTERSECTION_MULTISET_ALL R R R R R R R N ``` The existing `datafusion-substrait` suite passes unchanged, including the intersection roundtrip tests, and a Substrait round trip of the sqllogictest files that use `INTERSECT` gives the same output as `main`. ## Are there any user-facing changes? Intersections consumed from Substrait now report a narrower, spec-conforming nullability. No public API changes. One note for reviewers: the same narrowing would apply to SQL `INTERSECT`, since `LogicalPlanBuilder::intersect` keeps the left nullability for every caller. I kept this change inside the Substrait consumer to match the scope of the issue and to avoid changing SQL plans in the same PR. If you would rather see the rule live in `LogicalPlanBuilder`, I am happy to move it. --------- Co-authored-by: Claude Sonnet 5 <[email protected]>
1 parent d1790f2 commit d040501

5 files changed

Lines changed: 955 additions & 9 deletions

File tree

‎datafusion/substrait/src/logical_plan/consumer/rel/set_rel.rs‎

Lines changed: 133 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -16,8 +16,12 @@
1616
// under the License.
1717

1818
use crate::logical_plan::consumer::SubstraitConsumer;
19-
use datafusion::common::{not_impl_err, substrait_err};
20-
use datafusion::logical_expr::{LogicalPlan, LogicalPlanBuilder};
19+
use datafusion::arrow::datatypes::Field;
20+
use datafusion::common::{JoinType, NullEquality, not_impl_err, substrait_err};
21+
use datafusion::logical_expr::{
22+
Cast, Expr, LogicalPlan, LogicalPlanBuilder, requalify_sides_if_needed,
23+
};
24+
use std::sync::Arc;
2125
use substrait::proto::set_rel::SetOp;
2226
use substrait::proto::{Rel, SetRel};
2327

@@ -31,7 +35,7 @@ pub async fn from_set_rel(
3135
match set.op() {
3236
SetOp::UnionAll => union_rels(consumer, &set.inputs, true).await,
3337
SetOp::UnionDistinct => union_rels(consumer, &set.inputs, false).await,
34-
SetOp::IntersectionPrimary => LogicalPlanBuilder::intersect(
38+
SetOp::IntersectionPrimary => intersect_rel(
3539
consumer.consume_rel(&set.inputs[0]).await?,
3640
union_rels(consumer, &set.inputs[1..], true).await?,
3741
false,
@@ -77,16 +81,137 @@ async fn intersect_rels(
7781
let mut rel = consumer.consume_rel(&rels[0]).await?;
7882

7983
for input in &rels[1..] {
80-
rel = LogicalPlanBuilder::intersect(
81-
rel,
82-
consumer.consume_rel(input).await?,
83-
is_all,
84-
)?;
84+
rel = intersect_rel(rel, consumer.consume_rel(input).await?, is_all)?;
8585
}
8686

8787
Ok(rel)
8888
}
8989

90+
/// Intersects two relations, giving the result the nullability the Substrait
91+
/// [Set Operation rules] prescribe.
92+
///
93+
/// [`LogicalPlanBuilder::intersect`] compiles an intersection into a left semi
94+
/// join, so on its own the result keeps the left input's nullability. The join
95+
/// matches nulls with nulls, so a left row holding a null in some field only
96+
/// survives when the right input holds a null there too. A field is therefore
97+
/// nullable in the result only when it is nullable in *both* inputs.
98+
///
99+
/// Applied to each step of a chain, that gives the spec's rule for the multiset
100+
/// intersections - a field is required when any input requires it. For
101+
/// `INTERSECTION_PRIMARY` the right side is the union of the secondary inputs,
102+
/// whose field is nullable exactly when some secondary input makes it nullable,
103+
/// so the same rule yields "nullable in the primary input and in at least one
104+
/// secondary input".
105+
///
106+
/// When the right input requires a field the left input leaves nullable, the
107+
/// intersection is built as an inner join against the distinct right rows
108+
/// instead, and that field is read from the right side. Matched rows hold equal
109+
/// values, so the result is unchanged, and the field is non-nullable because
110+
/// its source is: the logical and the physical planner both derive that from
111+
/// the input schema, so the plan, the physical plan and the batches agree.
112+
/// Joining against distinct right rows keeps each left row at most once, as the
113+
/// semi join does.
114+
///
115+
/// Differing metadata does not change which path is taken. A column read from
116+
/// the right is cast to an explicit target field carrying the left field's
117+
/// metadata; an explicit-field cast target's metadata is used exactly as
118+
/// given rather than merged into the source's, so this drops a key only the
119+
/// right field carried and keeps the left field's metadata exactly. A
120+
/// `Field`'s own metadata travels with it through any later rewrite, so this
121+
/// holds for the plan this function returns and for any rewrite of it.
122+
///
123+
/// Schema-level (as opposed to per-field) metadata gets no such treatment:
124+
/// [`build_join_schema`](datafusion::logical_expr::build_join_schema) merges
125+
/// the two inputs' schema metadata with the left's value winning a
126+
/// conflicting key, and that merged map is what the projection built on top
127+
/// of the join reports - the same as the semi join
128+
/// [`LogicalPlanBuilder::intersect`] takes for the cases this function
129+
/// doesn't rewrite. A key only the right input's schema carries can
130+
/// therefore still appear in the result's schema-level metadata.
131+
///
132+
/// [Set Operation rules]: https://substrait.io/relations/logical_relations/#set-operation
133+
fn intersect_rel(
134+
left: LogicalPlan,
135+
right: LogicalPlan,
136+
is_all: bool,
137+
) -> datafusion::common::Result<LogicalPlan> {
138+
let left_fields = left.schema().fields();
139+
let right_fields = right.schema().fields();
140+
// A field is read from the right side when the left leaves it nullable and
141+
// the right requires it. Its metadata does not matter here: it is read from
142+
// the right with the left field's metadata substituted for its own.
143+
let from_right: Vec<bool> = left_fields
144+
.iter()
145+
.zip(right_fields.iter())
146+
.map(|(left, right)| {
147+
left.is_nullable()
148+
&& !right.is_nullable()
149+
&& left.data_type() == right.data_type()
150+
})
151+
.collect();
152+
153+
// `intersect` also reports inputs of different widths.
154+
if left_fields.len() != right_fields.len() || !from_right.contains(&true) {
155+
return LogicalPlanBuilder::intersect(left, right, is_all);
156+
}
157+
158+
let (left, right, _) = requalify_sides_if_needed(
159+
LogicalPlanBuilder::from(left),
160+
LogicalPlanBuilder::from(right),
161+
)?;
162+
let left = if is_all { left } else { left.distinct()? };
163+
let right = right.distinct()?.build()?;
164+
165+
let left_columns = left.schema().columns();
166+
let right_columns = right.schema().columns();
167+
let exprs = left
168+
.schema()
169+
.fields()
170+
.iter()
171+
.zip(&left_columns)
172+
.zip(&right_columns)
173+
.zip(&from_right)
174+
.map(|(((field, left), right), from_right)| {
175+
if *from_right {
176+
// `alias_qualified_with_metadata` would not do: `Expr::Alias`'s
177+
// field derivation extends the aliased expression's own
178+
// metadata with the alias's, so a key only the right column
179+
// carries would survive alongside the left field's metadata.
180+
// An explicit-field `Cast` target's metadata is instead used
181+
// exactly as given, in both the logical and the physical
182+
// plan, so casting to the left field's type (already proven
183+
// equal to the right's) and metadata drops the right's own
184+
// metadata outright. The qualifier and name still need
185+
// `alias_qualified` on top, since a `Cast`'s own field is not
186+
// renamed to its target field's name.
187+
let target_field = Arc::new(
188+
Field::new(&left.name, field.data_type().clone(), false)
189+
.with_metadata(field.metadata().clone()),
190+
);
191+
Expr::Cast(Cast::new_from_field(
192+
Box::new(Expr::Column(right.clone())),
193+
target_field,
194+
))
195+
.alias_qualified(left.relation.clone(), &left.name)
196+
} else {
197+
Expr::Column(left.clone())
198+
}
199+
})
200+
.collect::<Vec<_>>();
201+
202+
let joined = left
203+
.join_detailed(
204+
right,
205+
JoinType::Inner,
206+
(left_columns, right_columns),
207+
None,
208+
NullEquality::NullEqualsNull,
209+
)?
210+
.build()?;
211+
212+
LogicalPlanBuilder::from(joined).project(exprs)?.build()
213+
}
214+
90215
async fn except_rels(
91216
consumer: &impl SubstraitConsumer,
92217
rels: &[Rel],

0 commit comments

Comments
 (0)