Skip to content

Commit b319bb9

Browse files
fix: Derive Substrait intersection nullability from every input
The Substrait consumer derived all three intersection schemas from the primary input alone, so a field that the intersection makes required stayed nullable in the logical output schema. Narrow an intersection's nullability to `left AND right` per field. The left semi join it compiles to matches nulls with nulls, so a field is nullable in the result only when both inputs make it nullable, which reproduces the spec's rule for the multiset intersections and, because the right side is the union of the secondary inputs, for the primary intersection as well. Closes apache#25042.
1 parent 1fb8980 commit b319bb9

5 files changed

Lines changed: 604 additions & 8 deletions

File tree

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

Lines changed: 80 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -16,8 +16,9 @@
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::common::{DFSchema, not_impl_err, substrait_err};
20+
use datafusion::logical_expr::{Expr, LogicalPlan, LogicalPlanBuilder, Projection};
21+
use std::sync::Arc;
2122
use substrait::proto::set_rel::SetOp;
2223
use substrait::proto::{Rel, SetRel};
2324

@@ -31,7 +32,7 @@ pub async fn from_set_rel(
3132
match set.op() {
3233
SetOp::UnionAll => union_rels(consumer, &set.inputs, true).await,
3334
SetOp::UnionDistinct => union_rels(consumer, &set.inputs, false).await,
34-
SetOp::IntersectionPrimary => LogicalPlanBuilder::intersect(
35+
SetOp::IntersectionPrimary => intersect_rel(
3536
consumer.consume_rel(&set.inputs[0]).await?,
3637
union_rels(consumer, &set.inputs[1..], true).await?,
3738
false,
@@ -77,16 +78,87 @@ async fn intersect_rels(
7778
let mut rel = consumer.consume_rel(&rels[0]).await?;
7879

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

8784
Ok(rel)
8885
}
8986

87+
/// Intersects two relations, giving the result the nullability the Substrait
88+
/// [Set Operation rules] prescribe.
89+
///
90+
/// [`LogicalPlanBuilder::intersect`] compiles an intersection into a left semi
91+
/// join, so on its own the result keeps the left input's nullability. The join
92+
/// matches nulls with nulls, so a left row holding a null in some field only
93+
/// survives when the right input holds a null there too. A field is therefore
94+
/// nullable in the result only when it is nullable in *both* inputs.
95+
///
96+
/// Applied to each step of a chain, that gives the spec's rule for the multiset
97+
/// intersections - a field is required when any input requires it. For
98+
/// `INTERSECTION_PRIMARY` the right side is the union of the secondary inputs,
99+
/// whose field is nullable exactly when some secondary input makes it nullable,
100+
/// so the same rule yields "nullable in the primary input and in at least one
101+
/// secondary input".
102+
///
103+
/// [Set Operation rules]: https://substrait.io/relations/logical_relations/#set-operation
104+
fn intersect_rel(
105+
left: LogicalPlan,
106+
right: LogicalPlan,
107+
is_all: bool,
108+
) -> datafusion::common::Result<LogicalPlan> {
109+
let right_nullability: Vec<bool> = right
110+
.schema()
111+
.fields()
112+
.iter()
113+
.map(|field| field.is_nullable())
114+
.collect();
115+
116+
let plan = LogicalPlanBuilder::intersect(left, right, is_all)?;
117+
118+
// `intersect` has already checked that both sides have the same width.
119+
let narrowed: Vec<bool> = plan
120+
.schema()
121+
.fields()
122+
.iter()
123+
.zip(&right_nullability)
124+
.map(|(field, right_nullable)| field.is_nullable() && !right_nullable)
125+
.collect();
126+
127+
if !narrowed.contains(&true) {
128+
return Ok(plan);
129+
}
130+
131+
let qualified_fields = plan
132+
.schema()
133+
.iter()
134+
.zip(&narrowed)
135+
.map(|((qualifier, field), narrow)| {
136+
let field = if *narrow {
137+
Arc::new(field.as_ref().clone().with_nullable(false))
138+
} else {
139+
Arc::clone(field)
140+
};
141+
(qualifier.cloned(), field)
142+
})
143+
.collect();
144+
let schema = Arc::new(DFSchema::new_with_metadata(
145+
qualified_fields,
146+
plan.schema().metadata().clone(),
147+
)?);
148+
149+
let exprs = plan
150+
.schema()
151+
.columns()
152+
.into_iter()
153+
.map(Expr::Column)
154+
.collect();
155+
Ok(LogicalPlan::Projection(Projection::try_new_with_schema(
156+
exprs,
157+
Arc::new(plan),
158+
schema,
159+
)?))
160+
}
161+
90162
async fn except_rels(
91163
consumer: &impl SubstraitConsumer,
92164
rels: &[Rel],

‎datafusion/substrait/tests/cases/logical_plans.rs‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -229,6 +229,50 @@ mod tests {
229229
Ok(())
230230
}
231231

232+
#[tokio::test]
233+
async fn intersect_nullability() -> Result<()> {
234+
// Substrait's set operation rules derive an intersection's nullability from
235+
// every input, not only the primary one. Each plan below intersects three
236+
// tables carrying the same four columns, with these nullabilities
237+
// (`?` marks a nullable column):
238+
//
239+
// primary a? b? c? d?
240+
// secondary a b c? d?
241+
// secondary a b? c d?
242+
for (file, expected) in [
243+
// Nullable in the primary input and in at least one secondary input.
244+
("intersect_primary_mixed_nullability", "a, b?, c?, d?"),
245+
// Required as soon as any input requires it.
246+
("intersect_multiset_mixed_nullability", "a, b, c, d?"),
247+
("intersect_multiset_all_mixed_nullability", "a, b, c, d?"),
248+
] {
249+
let proto_plan =
250+
read_json(&format!("tests/testdata/test_plans/{file}.substrait.json"));
251+
let ctx = add_plan_schemas_to_ctx(SessionContext::new(), &proto_plan)?;
252+
let plan = from_substrait_plan(&ctx.state(), &proto_plan).await?;
253+
254+
let nullability = plan
255+
.schema()
256+
.fields()
257+
.iter()
258+
.map(|field| {
259+
format!(
260+
"{}{}",
261+
field.name(),
262+
if field.is_nullable() { "?" } else { "" }
263+
)
264+
})
265+
.collect::<Vec<_>>()
266+
.join(", ");
267+
assert_eq!(nullability, expected, "nullability of {file}");
268+
269+
// Trigger execution to ensure plan validity
270+
DataFrame::new(ctx.state(), plan).show().await?;
271+
}
272+
273+
Ok(())
274+
}
275+
232276
#[tokio::test]
233277
async fn multilayer_aggregate() -> Result<()> {
234278
let proto_plan =
Lines changed: 160 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,160 @@
1+
{
2+
"relations": [
3+
{
4+
"root": {
5+
"input": {
6+
"set": {
7+
"inputs": [
8+
{
9+
"read": {
10+
"common": {
11+
"direct": {}
12+
},
13+
"baseSchema": {
14+
"names": [
15+
"a",
16+
"b",
17+
"c",
18+
"d"
19+
],
20+
"struct": {
21+
"types": [
22+
{
23+
"i64": {
24+
"nullability": "NULLABILITY_NULLABLE"
25+
}
26+
},
27+
{
28+
"i64": {
29+
"nullability": "NULLABILITY_NULLABLE"
30+
}
31+
},
32+
{
33+
"i64": {
34+
"nullability": "NULLABILITY_NULLABLE"
35+
}
36+
},
37+
{
38+
"i64": {
39+
"nullability": "NULLABILITY_NULLABLE"
40+
}
41+
}
42+
],
43+
"nullability": "NULLABILITY_REQUIRED"
44+
}
45+
},
46+
"namedTable": {
47+
"names": [
48+
"data"
49+
]
50+
}
51+
}
52+
},
53+
{
54+
"read": {
55+
"common": {
56+
"direct": {}
57+
},
58+
"baseSchema": {
59+
"names": [
60+
"a",
61+
"b",
62+
"c",
63+
"d"
64+
],
65+
"struct": {
66+
"types": [
67+
{
68+
"i64": {
69+
"nullability": "NULLABILITY_REQUIRED"
70+
}
71+
},
72+
{
73+
"i64": {
74+
"nullability": "NULLABILITY_REQUIRED"
75+
}
76+
},
77+
{
78+
"i64": {
79+
"nullability": "NULLABILITY_NULLABLE"
80+
}
81+
},
82+
{
83+
"i64": {
84+
"nullability": "NULLABILITY_NULLABLE"
85+
}
86+
}
87+
],
88+
"nullability": "NULLABILITY_REQUIRED"
89+
}
90+
},
91+
"namedTable": {
92+
"names": [
93+
"data2"
94+
]
95+
}
96+
}
97+
},
98+
{
99+
"read": {
100+
"common": {
101+
"direct": {}
102+
},
103+
"baseSchema": {
104+
"names": [
105+
"a",
106+
"b",
107+
"c",
108+
"d"
109+
],
110+
"struct": {
111+
"types": [
112+
{
113+
"i64": {
114+
"nullability": "NULLABILITY_REQUIRED"
115+
}
116+
},
117+
{
118+
"i64": {
119+
"nullability": "NULLABILITY_NULLABLE"
120+
}
121+
},
122+
{
123+
"i64": {
124+
"nullability": "NULLABILITY_REQUIRED"
125+
}
126+
},
127+
{
128+
"i64": {
129+
"nullability": "NULLABILITY_NULLABLE"
130+
}
131+
}
132+
],
133+
"nullability": "NULLABILITY_REQUIRED"
134+
}
135+
},
136+
"namedTable": {
137+
"names": [
138+
"data3"
139+
]
140+
}
141+
}
142+
}
143+
],
144+
"op": "SET_OP_INTERSECTION_MULTISET_ALL"
145+
}
146+
},
147+
"names": [
148+
"a",
149+
"b",
150+
"c",
151+
"d"
152+
]
153+
}
154+
}
155+
],
156+
"version": {
157+
"minorNumber": 54,
158+
"producer": "datafusion-test"
159+
}
160+
}

0 commit comments

Comments
 (0)