Skip to main content

uqa_sql/semantics/locking/
null_rejection.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Determine nullable join sides from SQL predicates and strict function metadata.
8
9use crate::semantics::{join_alias_input_schemas, resolve_join_using};
10use crate::{
11    binding::{bind_source_plan_schema_in_scope, context::BindingContext, SourceScope},
12    plan::SourcePlan,
13    routines::RoutineResolution,
14    RowSchema, SQLError, SQLParam, ScalarExpr,
15};
16use uqa_core::Value;
17
18pub fn reduce_null_rejected_outer_joins_to_fixpoint(
19    routines: &dyn RoutineResolution,
20    source: &mut SourcePlan,
21    predicate: Option<&ScalarExpr>,
22    params: &[SQLParam],
23    context: &BindingContext<'_>,
24) -> Result<(), SQLError> {
25    loop {
26        let mut qualifications = predicate.iter().map(|expr| (*expr).clone()).collect();
27        collect_inner_join_qualifications(source, &mut qualifications);
28        let mut changed = false;
29        for qualification in &qualifications {
30            changed |= reduce_null_rejected_outer_joins(
31                routines,
32                source,
33                qualification,
34                params,
35                context,
36                SourceScope::new(None),
37            )?;
38        }
39        if !changed {
40            return Ok(());
41        }
42    }
43}
44
45fn collect_inner_join_qualifications(source: &SourcePlan, output: &mut Vec<ScalarExpr>) {
46    let SourcePlan::Join {
47        left,
48        right,
49        kind,
50        on,
51        ..
52    } = source
53    else {
54        return;
55    };
56    if !matches!(
57        kind,
58        crate::ast::JoinKind::Inner | crate::ast::JoinKind::Cross
59    ) {
60        return;
61    }
62    if let Some(on) = on {
63        output.push(on.clone());
64    }
65    collect_inner_join_qualifications(left, output);
66    collect_inner_join_qualifications(right, output);
67}
68
69fn reduce_null_rejected_outer_joins(
70    routines: &dyn RoutineResolution,
71    source: &mut SourcePlan,
72    predicate: &ScalarExpr,
73    params: &[SQLParam],
74    context: &BindingContext<'_>,
75    scope: SourceScope<'_>,
76) -> Result<bool, SQLError> {
77    let SourcePlan::Join {
78        left,
79        right,
80        kind,
81        using,
82        natural,
83        alias,
84        column_aliases,
85        lateral,
86        ..
87    } = source
88    else {
89        return Ok(false);
90    };
91    let left_schema =
92        bind_source_plan_schema_in_scope(routines, left, params, context, scope.with_names())?;
93    let preceding = scope.right_namespace(left, &left_schema, *kind);
94    let right_scope = SourceScope {
95        outer: scope.outer,
96        preceding: Some(&preceding),
97        inherited_lateral: *lateral,
98        retain_names: true,
99    };
100    let right_schema =
101        bind_source_plan_schema_in_scope(routines, right, params, context, right_scope)?;
102    let resolved_using = resolve_join_using(using.as_ref(), *natural, &left_schema, &right_schema)?;
103    let (left_predicate_schema, right_predicate_schema) = match alias.as_deref() {
104        Some(alias) => join_alias_input_schemas(
105            *kind,
106            &left_schema,
107            &right_schema,
108            resolved_using.as_ref(),
109            alias,
110            column_aliases,
111        )?,
112        None => (left_schema.clone(), right_schema.clone()),
113    };
114    let rejects_left = predicate_rejects_null_extended_side(
115        routines,
116        predicate,
117        &left_predicate_schema,
118        &right_predicate_schema,
119        params,
120    )?;
121    let rejects_right = predicate_rejects_null_extended_side(
122        routines,
123        predicate,
124        &right_predicate_schema,
125        &left_predicate_schema,
126        params,
127    )?;
128    let reduced = match (*kind, rejects_left, rejects_right) {
129        (crate::ast::JoinKind::Left, _, true) | (crate::ast::JoinKind::Right, true, _) => {
130            crate::ast::JoinKind::Inner
131        }
132        (crate::ast::JoinKind::Full, true, true) => crate::ast::JoinKind::Inner,
133        (crate::ast::JoinKind::Full, true, false) => crate::ast::JoinKind::Left,
134        (crate::ast::JoinKind::Full, false, true) => crate::ast::JoinKind::Right,
135        (kind, _, _) => kind,
136    };
137    let mut changed = reduced != *kind;
138    *kind = reduced;
139    changed |= reduce_null_rejected_outer_joins(routines, left, predicate, params, context, scope)?;
140    changed |=
141        reduce_null_rejected_outer_joins(routines, right, predicate, params, context, right_scope)?;
142    Ok(changed)
143}
144
145const TRUTH_FALSE: u8 = 1;
146const TRUTH_TRUE: u8 = 2;
147const TRUTH_NULL: u8 = 4;
148const TRUTH_ANY: u8 = TRUTH_FALSE | TRUTH_TRUE | TRUTH_NULL;
149
150fn predicate_rejects_null_extended_side(
151    routines: &dyn RoutineResolution,
152    expression: &ScalarExpr,
153    side: &RowSchema,
154    other: &RowSchema,
155    params: &[SQLParam],
156) -> Result<bool, SQLError> {
157    Ok(truth_values_with_null_side(routines, expression, side, other, params)? & TRUTH_TRUE == 0)
158}
159
160fn truth_values_with_null_side(
161    routines: &dyn RoutineResolution,
162    expression: &ScalarExpr,
163    side: &RowSchema,
164    other: &RowSchema,
165    params: &[SQLParam],
166) -> Result<u8, SQLError> {
167    match expression {
168        ScalarExpr::Literal(Value::Bool(value)) => {
169            if *value {
170                Ok(TRUTH_TRUE)
171            } else {
172                Ok(TRUTH_FALSE)
173            }
174        }
175        ScalarExpr::Literal(Value::Null) => Ok(TRUTH_NULL),
176        ScalarExpr::IsNull { expr, negated }
177            if expression_is_null_with_side(routines, expr, side, other, params)? =>
178        {
179            if *negated {
180                Ok(TRUTH_FALSE)
181            } else {
182                Ok(TRUTH_TRUE)
183            }
184        }
185        ScalarExpr::Between { expr, low, high } => {
186            let value_is_null = expression_is_null_with_side(routines, expr, side, other, params)?;
187            let low_is_null = expression_is_null_with_side(routines, low, side, other, params)?;
188            let high_is_null = expression_is_null_with_side(routines, high, side, other, params)?;
189            if value_is_null || (low_is_null && high_is_null) {
190                Ok(TRUTH_NULL)
191            } else if low_is_null || high_is_null {
192                Ok(TRUTH_FALSE | TRUTH_NULL)
193            } else {
194                Ok(TRUTH_ANY)
195            }
196        }
197        expression if expression_is_null_with_side(routines, expression, side, other, params)? => {
198            Ok(TRUTH_NULL)
199        }
200        ScalarExpr::Not(inner) => Ok(negate_truth_values(truth_values_with_null_side(
201            routines, inner, side, other, params,
202        )?)),
203        ScalarExpr::And(items) => items.iter().try_fold(TRUTH_TRUE, |left, right| {
204            Ok(combine_truth_values(
205                left,
206                truth_values_with_null_side(routines, right, side, other, params)?,
207                true,
208            ))
209        }),
210        ScalarExpr::Or(items) => items.iter().try_fold(TRUTH_FALSE, |left, right| {
211            Ok(combine_truth_values(
212                left,
213                truth_values_with_null_side(routines, right, side, other, params)?,
214                false,
215            ))
216        }),
217        _ => Ok(TRUTH_ANY),
218    }
219}
220
221fn expression_is_null_with_side(
222    routines: &dyn RoutineResolution,
223    expression: &ScalarExpr,
224    side: &RowSchema,
225    other: &RowSchema,
226    params: &[SQLParam],
227) -> Result<bool, SQLError> {
228    match expression {
229        ScalarExpr::Literal(Value::Null) => Ok(true),
230        ScalarExpr::Column(column) => Ok(side.unqualified_position(column).is_some()
231            && other.unqualified_position(column).is_none()),
232        ScalarExpr::QualifiedColumn { qualifier, column } => Ok(side
233            .has_qualified_column(qualifier, column)
234            && !other.has_qualified_column(qualifier, column)),
235        ScalarExpr::Binary { lhs, rhs, .. } => Ok(expression_is_null_with_side(
236            routines, lhs, side, other, params,
237        )? || expression_is_null_with_side(
238            routines, rhs, side, other, params,
239        )?),
240        ScalarExpr::UnaryMinus(inner)
241        | ScalarExpr::Cast { expr: inner, .. }
242        | ScalarExpr::Collated { expr: inner, .. } => {
243            expression_is_null_with_side(routines, inner, side, other, params)
244        }
245        ScalarExpr::Between { expr, low, high } => {
246            Ok(
247                expression_is_null_with_side(routines, expr, side, other, params)?
248                    || (expression_is_null_with_side(routines, low, side, other, params)?
249                        && expression_is_null_with_side(routines, high, side, other, params)?),
250            )
251        }
252        ScalarExpr::InList { expr, .. } => {
253            expression_is_null_with_side(routines, expr, side, other, params)
254        }
255        ScalarExpr::Func {
256            name,
257            binding,
258            args,
259            ..
260        } => {
261            if !scalar_function_is_strict(
262                routines,
263                name,
264                binding.as_ref(),
265                args,
266                side,
267                other,
268                params,
269            )? {
270                return Ok(false);
271            }
272            for argument in crate::scalar_call_arguments(args)? {
273                if expression_is_null_with_side(routines, argument.value, side, other, params)? {
274                    return Ok(true);
275                }
276            }
277            Ok(false)
278        }
279        _ => Ok(false),
280    }
281}
282
283fn scalar_function_is_strict(
284    routines: &dyn RoutineResolution,
285    name: &str,
286    binding: Option<&crate::ast::FunctionBinding>,
287    args: &[ScalarExpr],
288    side: &RowSchema,
289    other: &RowSchema,
290    params: &[SQLParam],
291) -> Result<bool, SQLError> {
292    let runtime_name = name
293        .strip_prefix("pg_catalog.")
294        .unwrap_or(name)
295        .to_ascii_lowercase();
296    if routines.has_registered_scalar_function(&runtime_name) {
297        return Ok(false);
298    }
299    if let Some(strict) = crate::expr::bound_scalar_function_strictness(name, binding, args.len()) {
300        return Ok(strict);
301    }
302    let schema = RowSchema::join(side, other, std::iter::empty::<String>());
303    let (argument_names, argument_types, explicit_variadic) =
304        crate::type_resolution::function_call_argument_signature(
305            args,
306            &schema,
307            params,
308            Some(routines),
309        )?;
310    if binding.is_none() && routines.lookup_visible_sql_functions(name)?.is_none() {
311        return Ok(false);
312    }
313    Ok(routines
314        .resolve_static_sql_function(
315            name,
316            binding,
317            &argument_names,
318            &argument_types,
319            explicit_variadic,
320        )?
321        .is_some_and(|function| function.def.strict))
322}
323
324fn negate_truth_values(values: u8) -> u8 {
325    (u8::from(values & TRUTH_FALSE != 0) * TRUTH_TRUE)
326        | (u8::from(values & TRUTH_TRUE != 0) * TRUTH_FALSE)
327        | (values & TRUTH_NULL)
328}
329
330fn combine_truth_values(left: u8, right: u8, and: bool) -> u8 {
331    let mut output = 0;
332    for lhs in [TRUTH_FALSE, TRUTH_TRUE, TRUTH_NULL] {
333        if left & lhs == 0 {
334            continue;
335        }
336        for rhs in [TRUTH_FALSE, TRUTH_TRUE, TRUTH_NULL] {
337            if right & rhs == 0 {
338                continue;
339            }
340            output |= if and {
341                match (lhs, rhs) {
342                    (TRUTH_FALSE, _) | (_, TRUTH_FALSE) => TRUTH_FALSE,
343                    (TRUTH_TRUE, TRUTH_TRUE) => TRUTH_TRUE,
344                    _ => TRUTH_NULL,
345                }
346            } else {
347                match (lhs, rhs) {
348                    (TRUTH_TRUE, _) | (_, TRUTH_TRUE) => TRUTH_TRUE,
349                    (TRUTH_FALSE, TRUTH_FALSE) => TRUTH_FALSE,
350                    _ => TRUTH_NULL,
351                }
352            };
353        }
354    }
355    output
356}