Skip to content

Commit 7fd1b0d

Browse files
[branch-54] fix: Correctly compute nullability in recursive CTE schemas (backport #22552) (#23579)
## Which issue does this PR close? - Backport of #22552 to `branch-54` (for 54.1.0, tracked in #22547). - Fixes execution failure #22034 (regression introduced in 54.0.0 by #21912, which made nullability checking strict without fixing schema derivation). ## Rationale for this change Recursive CTE queries with certain nullability patterns fail at execution in 54.0.0. This restores correct schema derivation for recursive queries. Reviewer note: this has a larger blast radius than the other 54.1.0 backports. It touches 12 files, adds a field to `LogicalPlan::RecursiveQuery`, and includes proto changes (`proto/src/logical_plan/mod.rs`). Worth a deliberate call on whether it clears the patch-release stability bar. ## What changes are included in this PR? Clean cherry-pick of #22552. No adaptation required. ## Are these changes tested? Yes. Carries the original regression coverage (`cte.slt`, `explain_tree.slt`, `explain_analyze.rs`), all tests pass. ## Are there any user-facing changes? Recursive CTEs with these nullability patterns execute again. Adds a field to `LogicalPlan::RecursiveQuery` and the corresponding proto messages (internal, but on public-facing structs). Co-authored-by: Neil Conway <[email protected]>
1 parent 9d41b02 commit 7fd1b0d

12 files changed

Lines changed: 426 additions & 69 deletions

File tree

‎datafusion/catalog/src/cte_worktable.rs‎

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -36,14 +36,16 @@ use crate::{ScanArgs, ScanResult, Session, TableProvider};
3636
pub struct CteWorkTable {
3737
/// The name of the CTE work table
3838
name: String,
39-
/// This schema must be shared across both the static and recursive terms of a recursive query
39+
/// Schema exposed by recursive self-references while planning the recursive term.
40+
///
41+
/// This is a conservative work-table schema, not the final recursive query output
42+
/// schema. For example, the SQL planner may mark fields nullable here so recursive
43+
/// references do not inherit unsound anchor-term nullability assumptions.
4044
table_schema: SchemaRef,
4145
}
4246

4347
impl CteWorkTable {
44-
/// construct a new CteWorkTable with the given name and schema
45-
/// This schema must match the schema of the recursive term of the query
46-
/// Since the scan method will contain an physical plan that assumes this schema
48+
/// Construct a new CteWorkTable with the given name and self-reference schema.
4749
pub fn new(name: &str, table_schema: SchemaRef) -> Self {
4850
Self {
4951
name: name.to_owned(),
@@ -56,7 +58,7 @@ impl CteWorkTable {
5658
&self.name
5759
}
5860

59-
/// The schema of the recursive term of the query
61+
/// The schema exposed by scans of the recursive self-reference.
6062
pub fn schema(&self) -> SchemaRef {
6163
Arc::clone(&self.table_schema)
6264
}

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1794,11 +1794,15 @@ impl DefaultPhysicalPlanner {
17941794
}
17951795
}
17961796
LogicalPlan::RecursiveQuery(RecursiveQuery {
1797-
name, is_distinct, ..
1797+
name,
1798+
is_distinct,
1799+
schema,
1800+
..
17981801
}) => {
17991802
let [static_term, recursive_term] = children.two()?;
18001803
Arc::new(RecursiveQueryExec::try_new(
18011804
name.clone(),
1805+
Arc::clone(schema.inner()),
18021806
static_term,
18031807
recursive_term,
18041808
*is_distinct,

‎datafusion/core/tests/sql/explain_analyze.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1014,7 +1014,7 @@ async fn parquet_recursive_projection_pushdown() -> Result<()> {
10141014
SortExec: expr=[id@0 ASC NULLS LAST], preserve_partitioning=[false]
10151015
RecursiveQueryExec: name=number_series, is_distinct=false
10161016
CoalescePartitionsExec
1017-
ProjectionExec: expr=[id@0 as id, 1 as level]
1017+
ProjectionExec: expr=[CAST(id@0 AS Int64) as id, CAST(1 AS Int64) as level]
10181018
FilterExec: id@0 = 1
10191019
RepartitionExec: partitioning=RoundRobinBatch(NUM_CORES), input_partitions=1
10201020
DataSourceExec: file_groups={1 group: [[TMP_DIR/hierarchy.parquet]]}, projection=[id], file_type=parquet, predicate=id@0 = 1, pruning_predicate=id_null_count@2 != row_count@3 AND id_min@0 <= 1 AND 1 <= id_max@1, required_guarantees=[id in (1)]

‎datafusion/expr/src/logical_plan/builder.rs‎

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -192,12 +192,13 @@ impl LogicalPlanBuilder {
192192
// Ensure that the recursive term has the same field types as the static term
193193
let coerced_recursive_term =
194194
coerce_plan_expr_for_schema(recursive_term, self.plan.schema())?;
195-
Ok(Self::from(LogicalPlan::RecursiveQuery(RecursiveQuery {
195+
let recursive_query = RecursiveQuery::try_new(
196196
name,
197-
static_term: self.plan,
198-
recursive_term: Arc::new(coerced_recursive_term),
197+
self.plan,
198+
Arc::new(coerced_recursive_term),
199199
is_distinct,
200-
})))
200+
)?;
201+
Ok(Self::from(LogicalPlan::RecursiveQuery(recursive_query)))
201202
}
202203

203204
/// Create a values list based relation, and the schema is inferred from data, consuming

‎datafusion/expr/src/logical_plan/plan.rs‎

Lines changed: 169 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -353,10 +353,7 @@ impl LogicalPlan {
353353
LogicalPlan::Copy(CopyTo { output_schema, .. }) => output_schema,
354354
LogicalPlan::Ddl(ddl) => ddl.schema(),
355355
LogicalPlan::Unnest(Unnest { schema, .. }) => schema,
356-
LogicalPlan::RecursiveQuery(RecursiveQuery { static_term, .. }) => {
357-
// we take the schema of the static term as the schema of the entire recursive query
358-
static_term.schema()
359-
}
356+
LogicalPlan::RecursiveQuery(RecursiveQuery { schema, .. }) => schema,
360357
}
361358
}
362359

@@ -740,7 +737,14 @@ impl LogicalPlan {
740737
};
741738
Ok(LogicalPlan::Distinct(distinct))
742739
}
743-
LogicalPlan::RecursiveQuery(_) => Ok(self),
740+
LogicalPlan::RecursiveQuery(RecursiveQuery {
741+
name,
742+
static_term,
743+
recursive_term,
744+
is_distinct,
745+
schema: _,
746+
}) => RecursiveQuery::try_new(name, static_term, recursive_term, is_distinct)
747+
.map(LogicalPlan::RecursiveQuery),
744748
LogicalPlan::Analyze(_) => Ok(self),
745749
LogicalPlan::Explain(_) => Ok(self),
746750
LogicalPlan::TableScan(_) => Ok(self),
@@ -1080,12 +1084,13 @@ impl LogicalPlan {
10801084
}) => {
10811085
self.assert_no_expressions(expr)?;
10821086
let (static_term, recursive_term) = self.only_two_inputs(inputs)?;
1083-
Ok(LogicalPlan::RecursiveQuery(RecursiveQuery {
1084-
name: name.clone(),
1085-
static_term: Arc::new(static_term),
1086-
recursive_term: Arc::new(recursive_term),
1087-
is_distinct: *is_distinct,
1088-
}))
1087+
RecursiveQuery::try_new(
1088+
name.clone(),
1089+
Arc::new(static_term),
1090+
Arc::new(recursive_term),
1091+
*is_distinct,
1092+
)
1093+
.map(LogicalPlan::RecursiveQuery)
10891094
}
10901095
LogicalPlan::Analyze(a) => {
10911096
self.assert_no_expressions(expr)?;
@@ -2257,7 +2262,7 @@ impl PartialOrd for EmptyRelation {
22572262
/// intermediate table, then empty the intermediate table.
22582263
///
22592264
/// [Postgres Docs]: https://www.postgresql.org/docs/current/queries-with.html#QUERIES-WITH-RECURSIVE
2260-
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Hash)]
2265+
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
22612266
pub struct RecursiveQuery {
22622267
/// Name of the query
22632268
pub name: String,
@@ -2269,6 +2274,90 @@ pub struct RecursiveQuery {
22692274
/// Should the output of the recursive term be deduplicated (`UNION`) or
22702275
/// not (`UNION ALL`).
22712276
pub is_distinct: bool,
2277+
/// Schema exposed to parent plans after reconciling the static and recursive terms.
2278+
pub schema: DFSchemaRef,
2279+
}
2280+
2281+
impl PartialOrd for RecursiveQuery {
2282+
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
2283+
match self.name.partial_cmp(&other.name) {
2284+
Some(Ordering::Equal) => {
2285+
match self.static_term.partial_cmp(&other.static_term) {
2286+
Some(Ordering::Equal) => {
2287+
match self.recursive_term.partial_cmp(&other.recursive_term) {
2288+
Some(Ordering::Equal) => {
2289+
self.is_distinct.partial_cmp(&other.is_distinct)
2290+
}
2291+
cmp => cmp,
2292+
}
2293+
}
2294+
cmp => cmp,
2295+
}
2296+
}
2297+
cmp => cmp,
2298+
}
2299+
// If the query definition compares equal but the derived schema differs,
2300+
// return `None` instead of contradicting `PartialEq` with `Some(Equal)`.
2301+
// TODO (https://github.com/apache/datafusion/issues/17477) avoid recomparing all fields
2302+
.filter(|cmp| *cmp != Ordering::Equal || self == other)
2303+
}
2304+
}
2305+
2306+
impl RecursiveQuery {
2307+
pub fn try_new(
2308+
name: String,
2309+
static_term: Arc<LogicalPlan>,
2310+
recursive_term: Arc<LogicalPlan>,
2311+
is_distinct: bool,
2312+
) -> Result<Self> {
2313+
let schema =
2314+
recursive_query_output_schema(static_term.schema(), recursive_term.schema())?;
2315+
Ok(Self {
2316+
name,
2317+
static_term,
2318+
recursive_term,
2319+
is_distinct,
2320+
schema,
2321+
})
2322+
}
2323+
}
2324+
2325+
/// Compute a recursive query's output schema by considering both its static and
2326+
/// recursive terms.
2327+
///
2328+
/// Field names, types, and metadata come from the static term. A field is
2329+
/// nullable if either the static or the recursive term produces a nullable
2330+
/// value in that position, matching how `UNION` reconciles branch nullability.
2331+
///
2332+
/// Functional dependencies are intentionally dropped: the recursive term
2333+
/// appends rows that can duplicate values the static term guarantees unique, so
2334+
/// any FDs carried by the static term may not hold over the combined output.
2335+
fn recursive_query_output_schema(
2336+
static_schema: &DFSchemaRef,
2337+
recursive_schema: &DFSchemaRef,
2338+
) -> Result<DFSchemaRef> {
2339+
if static_schema.fields().len() != recursive_schema.fields().len() {
2340+
return Err(DataFusionError::Plan(format!(
2341+
"Non-recursive term and recursive term must have the same number of columns ({} != {})",
2342+
static_schema.fields().len(),
2343+
recursive_schema.fields().len()
2344+
)));
2345+
}
2346+
2347+
let fields = static_schema
2348+
.iter()
2349+
.zip(recursive_schema.fields())
2350+
.map(|((qualifier, static_field), recursive_field)| {
2351+
let nullable = static_field.is_nullable() || recursive_field.is_nullable();
2352+
(
2353+
qualifier.cloned(),
2354+
static_field.as_ref().clone().with_nullable(nullable).into(),
2355+
)
2356+
})
2357+
.collect::<Vec<_>>();
2358+
2359+
DFSchema::new_with_metadata(fields, static_schema.metadata().clone())
2360+
.map(DFSchemaRef::new)
22722361
}
22732362

22742363
/// Values expression. See
@@ -4500,6 +4589,74 @@ mod tests {
45004589
.build()
45014590
}
45024591

4592+
fn recursive_term_scan(name: &str, fields: Vec<Field>) -> Result<Arc<LogicalPlan>> {
4593+
Ok(Arc::new(
4594+
table_scan(Some(name), &Schema::new(fields), None)?.build()?,
4595+
))
4596+
}
4597+
4598+
#[test]
4599+
fn recursive_query_widens_nullability_per_column() -> Result<()> {
4600+
// Column `a` is non-nullable in both terms and must stay non-nullable;
4601+
// column `b` is non-nullable in the static term but nullable in the
4602+
// recursive term, so the output must widen it to nullable.
4603+
let static_term = recursive_term_scan(
4604+
"static",
4605+
vec![
4606+
Field::new("a", DataType::Int32, false),
4607+
Field::new("b", DataType::Int32, false),
4608+
],
4609+
)?;
4610+
let recursive_term = recursive_term_scan(
4611+
"rec",
4612+
vec![
4613+
Field::new("a", DataType::Int32, false),
4614+
Field::new("b", DataType::Int32, true),
4615+
],
4616+
)?;
4617+
4618+
let query =
4619+
RecursiveQuery::try_new("t".to_string(), static_term, recursive_term, false)?;
4620+
4621+
// Names and types are taken from the static term.
4622+
assert_eq!(query.schema.field(0).name(), "a");
4623+
assert_eq!(query.schema.field(1).name(), "b");
4624+
assert_eq!(query.schema.field(0).data_type(), &DataType::Int32);
4625+
assert_eq!(query.schema.field(1).data_type(), &DataType::Int32);
4626+
// Nullability is widened independently per column.
4627+
assert!(!query.schema.field(0).is_nullable());
4628+
assert!(query.schema.field(1).is_nullable());
4629+
// `schema()` returns the widened recursive-query schema.
4630+
assert_eq!(
4631+
LogicalPlan::RecursiveQuery(query.clone()).schema(),
4632+
&query.schema
4633+
);
4634+
Ok(())
4635+
}
4636+
4637+
#[test]
4638+
fn recursive_query_rejects_column_count_mismatch() -> Result<()> {
4639+
let static_term =
4640+
recursive_term_scan("static", vec![Field::new("a", DataType::Int32, false)])?;
4641+
let recursive_term = recursive_term_scan(
4642+
"rec",
4643+
vec![
4644+
Field::new("a", DataType::Int32, false),
4645+
Field::new("b", DataType::Int32, false),
4646+
],
4647+
)?;
4648+
4649+
let err =
4650+
RecursiveQuery::try_new("t".to_string(), static_term, recursive_term, false)
4651+
.unwrap_err();
4652+
assert!(
4653+
err.strip_backtrace()
4654+
.contains("must have the same number of columns"),
4655+
"unexpected error: {err}"
4656+
);
4657+
Ok(())
4658+
}
4659+
45034660
#[test]
45044661
fn test_display_indent() -> Result<()> {
45054662
let plan = display_plan()?;

‎datafusion/expr/src/logical_plan/tree_node.rs‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -329,13 +329,18 @@ impl TreeNode for LogicalPlan {
329329
static_term,
330330
recursive_term,
331331
is_distinct,
332+
schema,
332333
}) => (static_term, recursive_term).map_elements(f)?.update_data(
333334
|(static_term, recursive_term)| {
335+
// Ordinary child rewrites preserve derived schemas. Call
336+
// `LogicalPlan::recompute_schema` when child schemas should
337+
// be reconciled again.
334338
LogicalPlan::RecursiveQuery(RecursiveQuery {
335339
name,
336340
static_term,
337341
recursive_term,
338342
is_distinct,
343+
schema,
339344
})
340345
},
341346
),

‎datafusion/expr/src/planner.rs‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,8 @@ pub trait ContextProvider {
6161
not_impl_err!("Table Functions are not supported")
6262
}
6363

64-
/// Provides an intermediate table that is used to store the results of a CTE during execution
64+
/// Provides an intermediate table that is used to expose a recursive CTE
65+
/// self-reference during planning and execution.
6566
///
6667
/// CTE stands for "Common Table Expression"
6768
///
@@ -72,6 +73,9 @@ pub trait ContextProvider {
7273
/// of the sql crate (for example [`CteWorkTable`]).
7374
///
7475
/// The [`ContextProvider`] provides a way to "hide" this dependency.
76+
/// The schema argument is the schema to expose for scans of the recursive
77+
/// self-reference, which may be more conservative than the final recursive
78+
/// query output schema.
7579
///
7680
/// [`SqlToRel`]: https://docs.rs/datafusion/latest/datafusion/sql/planner/struct.SqlToRel.html
7781
/// [`CteWorkTable`]: https://docs.rs/datafusion/latest/datafusion/datasource/cte_worktable/struct.CteWorkTable.html

0 commit comments

Comments
 (0)