nodedb_sql/planner/subquery/
exists.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! `EXISTS` / `NOT EXISTS` lowered to a semi / anti join.
4//!
5//! The inner query becomes the build side. Each AND-ed equality that links an
6//! outer relation to an inner one becomes a probe key; every other conjunct
7//! stays a local predicate on the inner scan.
8
9use std::ops::ControlFlow;
10
11use sqlparser::ast::{self, SetExpr};
12
13use crate::error::{Result, SqlError};
14use crate::functions::registry::FunctionRegistry;
15use crate::parser::normalize::normalize_ident;
16use crate::planner::ast_helpers::{flatten_and_expr, rebuild_and_expr};
17use crate::planner::select::{convert_projection, plan_query};
18use crate::resolver::ColumnScope;
19use crate::resolver::columns::TableScope;
20use crate::resolver::expr::convert_expr;
21use crate::types::*;
22
23use super::extract::SubqueryJoin;
24
25const SET_OPERATION: &str = "EXISTS over a set operation (UNION / INTERSECT / EXCEPT) \
26     is not supported; wrap the set operation in a derived table and select from that";
27
28const OUTER_ONLY_EQUALITY: &str = "an equality naming only outer relations inside EXISTS \
29     is not supported; move it to the enclosing WHERE clause";
30
31const CORRELATION_UNDER_OR: &str = "a correlated reference under OR inside EXISTS \
32     is not supported; each correlation must be an AND-ed equality";
33
34/// Plan `EXISTS (SELECT ... )` as a semi join, `NOT EXISTS` as an anti join.
35///
36/// `outer` is the enclosing query's scope. The inner FROM clause resolves
37/// nested inside it, so a qualifier naming no inner relation reaches the outer
38/// query instead of erroring as an unknown relation.
39pub(super) fn plan_exists_subquery(
40    subquery: &ast::Query,
41    negated: bool,
42    outer: &TableScope,
43    catalog: &dyn SqlCatalog,
44    functions: &FunctionRegistry,
45    temporal: crate::TemporalScope,
46) -> Result<SubqueryJoin> {
47    let SetExpr::Select(select) = &*subquery.body else {
48        return Err(SqlError::Unsupported {
49            detail: SET_OPERATION.into(),
50        });
51    };
52
53    let local = TableScope::resolve_from(catalog, functions, temporal, &select.from)?;
54    let nested = local.clone().nested_in(outer.clone());
55
56    // EXISTS discards the projected values. The conversion still runs so a
57    // column the inner SELECT list names but no relation declares is rejected.
58    convert_projection(&select.projection, &nested)?;
59
60    let mut on = Vec::new();
61    let mut local_conjuncts = Vec::new();
62    if let Some(where_expr) = &select.selection {
63        let mut conjuncts = Vec::new();
64        flatten_and_expr(where_expr, &mut conjuncts);
65        for conjunct in conjuncts {
66            // Converting against the nested scope gates both inner and outer
67            // column names before the conjunct is classified.
68            convert_expr(&conjunct, &ColumnScope::Relations(&nested))?;
69            match correlation_pair(&conjunct, &local, outer)? {
70                Some(pair) => on.push(pair),
71                None => local_conjuncts.push(conjunct),
72            }
73        }
74    }
75
76    let inner_plan = plan_local_query(
77        subquery,
78        select,
79        local_conjuncts,
80        catalog,
81        functions,
82        temporal,
83    )?;
84
85    Ok(SubqueryJoin {
86        on,
87        inner_plan,
88        join_type: if negated {
89            JoinType::Anti
90        } else {
91            JoinType::Semi
92        },
93    })
94}
95
96/// Plan the inner query carrying only its local predicates.
97///
98/// The projection widens to `*`: EXISTS ignores the values, but the scan must
99/// still carry the correlation key columns for the join probe.
100fn plan_local_query(
101    subquery: &ast::Query,
102    select: &ast::Select,
103    local_conjuncts: Vec<ast::Expr>,
104    catalog: &dyn SqlCatalog,
105    functions: &FunctionRegistry,
106    temporal: crate::TemporalScope,
107) -> Result<SqlPlan> {
108    let mut inner_select = select.clone();
109    inner_select.projection = vec![ast::SelectItem::Wildcard(
110        ast::WildcardAdditionalOptions::default(),
111    )];
112    inner_select.selection = if local_conjuncts.is_empty() {
113        None
114    } else {
115        Some(rebuild_and_expr(local_conjuncts))
116    };
117
118    let mut inner_query = subquery.clone();
119    *inner_query.body = SetExpr::Select(Box::new(inner_select));
120    plan_query(&inner_query, catalog, functions, temporal)
121}
122
123/// Which query a column reference belongs to.
124enum Side {
125    /// A column of a relation in the subquery's own FROM clause.
126    Inner(String),
127    /// A column of a relation in the enclosing query.
128    Outer(String),
129    /// Anything else: a literal, a function call, a computed expression.
130    Other,
131}
132
133/// Classify one conjunct of the inner WHERE clause.
134///
135/// Returns the `(outer column, inner column)` probe key for a correlation, or
136/// `None` for a predicate local to the inner query. A conjunct that reads an
137/// outer relation in any other shape raises a typed error naming that shape.
138fn correlation_pair(
139    expr: &ast::Expr,
140    inner: &TableScope,
141    outer: &TableScope,
142) -> Result<Option<(String, String)>> {
143    let bare = unnest(expr);
144    if let ast::Expr::BinaryOp { left, op, right } = bare {
145        let l = classify(left, inner, outer);
146        let r = classify(right, inner, outer);
147        match (op, &l, &r) {
148            (ast::BinaryOperator::Eq, Side::Inner(ic), Side::Outer(oc))
149            | (ast::BinaryOperator::Eq, Side::Outer(oc), Side::Inner(ic)) => {
150                return Ok(Some((oc.clone(), ic.clone())));
151            }
152            (ast::BinaryOperator::Eq, Side::Outer(_), Side::Outer(_)) => {
153                return Err(SqlError::Unsupported {
154                    detail: OUTER_ONLY_EQUALITY.into(),
155                });
156            }
157            (ast::BinaryOperator::Or, _, _)
158                if references_outer(left, inner, outer)
159                    || references_outer(right, inner, outer) =>
160            {
161                return Err(SqlError::Unsupported {
162                    detail: CORRELATION_UNDER_OR.into(),
163                });
164            }
165            (op, Side::Inner(_), Side::Outer(_)) | (op, Side::Outer(_), Side::Inner(_))
166                if is_inequality(op) =>
167            {
168                return Err(SqlError::Unsupported {
169                    detail: format!(
170                        "a correlated inequality ('{op}') inside EXISTS is not supported; \
171                         a semi join probes on equality keys only"
172                    ),
173                });
174            }
175            _ => {}
176        }
177    }
178
179    if references_outer(bare, inner, outer) {
180        return Err(SqlError::Unsupported {
181            detail: format!(
182                "the correlated predicate '{expr}' inside EXISTS is not supported; \
183                 a correlation must be an AND-ed equality between one outer column \
184                 and one inner column"
185            ),
186        });
187    }
188    Ok(None)
189}
190
191/// Decide which query a column reference belongs to by relation membership.
192///
193/// A qualifier names the relation directly. A bare name goes to whichever
194/// scope resolves it, inner first, matching the resolution order the
195/// expression converter already applied.
196fn classify(expr: &ast::Expr, inner: &TableScope, outer: &TableScope) -> Side {
197    match expr {
198        ast::Expr::CompoundIdentifier(parts) if parts.len() == 2 => {
199            let qualifier = normalize_ident(&parts[0]);
200            let column = normalize_ident(&parts[1]);
201            if inner.table_by_ref(&qualifier).is_some() {
202                Side::Inner(column)
203            } else if outer.table_by_ref(&qualifier).is_some() {
204                Side::Outer(column)
205            } else {
206                Side::Other
207            }
208        }
209        ast::Expr::Identifier(ident) => {
210            let column = normalize_ident(ident);
211            if inner.check_name(None, &column).is_ok() {
212                Side::Inner(column)
213            } else if outer.check_name(None, &column).is_ok() {
214                Side::Outer(column)
215            } else {
216                Side::Other
217            }
218        }
219        ast::Expr::Nested(nested) => classify(nested, inner, outer),
220        _ => Side::Other,
221    }
222}
223
224/// Whether any column reference anywhere in `expr` names an outer relation.
225fn references_outer(expr: &ast::Expr, inner: &TableScope, outer: &TableScope) -> bool {
226    let walk = ast::visit_expressions(expr, |node| {
227        if matches!(classify(node, inner, outer), Side::Outer(_)) {
228            ControlFlow::Break(())
229        } else {
230            ControlFlow::Continue(())
231        }
232    });
233    walk.is_break()
234}
235
236fn unnest(expr: &ast::Expr) -> &ast::Expr {
237    match expr {
238        ast::Expr::Nested(inner) => unnest(inner),
239        other => other,
240    }
241}
242
243fn is_inequality(op: &ast::BinaryOperator) -> bool {
244    matches!(
245        op,
246        ast::BinaryOperator::Gt
247            | ast::BinaryOperator::GtEq
248            | ast::BinaryOperator::Lt
249            | ast::BinaryOperator::LtEq
250            | ast::BinaryOperator::NotEq
251    )
252}
nodedb_sql/planner/subquery/exists.rs

nodedb_sql/planner/subquery/
exists.rs
