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_with_control, resolve_join_using_with_control};
10use crate::{
11    binding::{
12        context::BindingContext,
13        production::{bind_source_plan_schema_in_scope_with_control, ControlledBindingContext},
14        SourceScope,
15    },
16    plan::SourcePlan,
17    routines::RoutineResolution,
18    RowSchema, SQLError, SQLParam, ScalarExpr,
19};
20use uqa_core::{
21    memory::{ProductionControl, ProductionVec},
22    Value,
23};
24
25pub fn reduce_null_rejected_outer_joins_to_fixpoint(
26    routines: &dyn RoutineResolution,
27    source: &mut SourcePlan,
28    predicate: Option<&ScalarExpr>,
29    params: &[SQLParam],
30    context: &BindingContext<'_>,
31) -> Result<(), SQLError> {
32    let control = ProductionControl::uncontrolled();
33    reduce_null_rejected_outer_joins_with_control(
34        routines,
35        source,
36        predicate,
37        params,
38        &context.copy_with_control(&control)?,
39        &control,
40    )
41}
42
43pub(crate) fn reduce_null_rejected_outer_joins_with_control(
44    routines: &dyn RoutineResolution,
45    source: &mut SourcePlan,
46    predicate: Option<&ScalarExpr>,
47    params: &[SQLParam],
48    context: &ControlledBindingContext<'_>,
49    control: &ProductionControl<'_>,
50) -> Result<(), SQLError> {
51    loop {
52        control.check()?;
53        let mut qualifications = ProductionVec::new(*control);
54        if let Some(predicate) = predicate {
55            qualifications.push_produced(predicate.clone_with_control(control)?)?;
56        }
57        collect_inner_join_qualifications(source, &mut qualifications, control)?;
58        let mut changed = false;
59        for qualification in qualifications.iter() {
60            changed |= reduce_null_rejected_outer_joins(
61                routines,
62                source,
63                qualification,
64                params,
65                context,
66                SourceScope::new(None),
67                control,
68            )?;
69        }
70        if !changed {
71            return Ok(());
72        }
73    }
74}
75
76fn collect_inner_join_qualifications(
77    source: &SourcePlan,
78    output: &mut ProductionVec<'_, ScalarExpr>,
79    control: &ProductionControl<'_>,
80) -> Result<(), SQLError> {
81    control.check()?;
82    let SourcePlan::Join {
83        left,
84        right,
85        kind,
86        on,
87        ..
88    } = source
89    else {
90        return Ok(());
91    };
92    if !matches!(
93        kind,
94        crate::ast::JoinKind::Inner | crate::ast::JoinKind::Cross
95    ) {
96        return Ok(());
97    }
98    if let Some(on) = on {
99        output.push_produced(on.clone_with_control(control)?)?;
100    }
101    collect_inner_join_qualifications(left, output, control)?;
102    collect_inner_join_qualifications(right, output, control)
103}
104
105fn reduce_null_rejected_outer_joins(
106    routines: &dyn RoutineResolution,
107    source: &mut SourcePlan,
108    predicate: &ScalarExpr,
109    params: &[SQLParam],
110    context: &ControlledBindingContext<'_>,
111    scope: SourceScope<'_>,
112    control: &ProductionControl<'_>,
113) -> Result<bool, SQLError> {
114    control.check()?;
115    let SourcePlan::Join {
116        left,
117        right,
118        kind,
119        using,
120        natural,
121        alias,
122        column_aliases,
123        lateral,
124        ..
125    } = source
126    else {
127        return Ok(false);
128    };
129    let left_schema = bind_source_plan_schema_in_scope_with_control(
130        routines,
131        left,
132        params,
133        context.copy_with_control(control)?,
134        scope.with_names(),
135        control,
136    )?;
137    let preceding = scope.right_namespace_with_control(left, &left_schema, *kind, control)?;
138    let right_scope = SourceScope {
139        outer: scope.outer,
140        preceding: Some(&preceding),
141        inherited_lateral: *lateral,
142        retain_names: true,
143    };
144    let right_schema = bind_source_plan_schema_in_scope_with_control(
145        routines,
146        right,
147        params,
148        context.copy_with_control(control)?,
149        right_scope,
150        control,
151    )?;
152    let resolved_using = resolve_join_using_with_control(
153        using.as_ref(),
154        *natural,
155        &left_schema,
156        &right_schema,
157        control,
158    )?;
159    let (left_predicate_schema, right_predicate_schema) = match alias.as_deref() {
160        Some(alias) => join_alias_input_schemas_with_control(
161            *kind,
162            &left_schema,
163            &right_schema,
164            resolved_using.as_deref(),
165            alias,
166            column_aliases,
167            control,
168        )?,
169        None => (left_schema.clone(), right_schema.clone()),
170    };
171    let rejects_left = predicate_rejects_null_extended_side(
172        routines,
173        predicate,
174        &left_predicate_schema,
175        &right_predicate_schema,
176        params,
177        control,
178    )?;
179    let rejects_right = predicate_rejects_null_extended_side(
180        routines,
181        predicate,
182        &right_predicate_schema,
183        &left_predicate_schema,
184        params,
185        control,
186    )?;
187    let reduced = match (*kind, rejects_left, rejects_right) {
188        (crate::ast::JoinKind::Left, _, true) | (crate::ast::JoinKind::Right, true, _) => {
189            crate::ast::JoinKind::Inner
190        }
191        (crate::ast::JoinKind::Full, true, true) => crate::ast::JoinKind::Inner,
192        (crate::ast::JoinKind::Full, true, false) => crate::ast::JoinKind::Left,
193        (crate::ast::JoinKind::Full, false, true) => crate::ast::JoinKind::Right,
194        (kind, _, _) => kind,
195    };
196    let mut changed = reduced != *kind;
197    *kind = reduced;
198    changed |= reduce_null_rejected_outer_joins(
199        routines, left, predicate, params, context, scope, control,
200    )?;
201    changed |= reduce_null_rejected_outer_joins(
202        routines,
203        right,
204        predicate,
205        params,
206        context,
207        right_scope,
208        control,
209    )?;
210    Ok(changed)
211}
212
213const TRUTH_FALSE: u8 = 1;
214const TRUTH_TRUE: u8 = 2;
215const TRUTH_NULL: u8 = 4;
216const TRUTH_ANY: u8 = TRUTH_FALSE | TRUTH_TRUE | TRUTH_NULL;
217
218fn predicate_rejects_null_extended_side(
219    routines: &dyn RoutineResolution,
220    expression: &ScalarExpr,
221    side: &RowSchema,
222    other: &RowSchema,
223    params: &[SQLParam],
224    control: &ProductionControl<'_>,
225) -> Result<bool, SQLError> {
226    Ok(
227        truth_values_with_null_side(routines, expression, side, other, params, control)?
228            & TRUTH_TRUE
229            == 0,
230    )
231}
232
233fn truth_values_with_null_side(
234    routines: &dyn RoutineResolution,
235    expression: &ScalarExpr,
236    side: &RowSchema,
237    other: &RowSchema,
238    params: &[SQLParam],
239    control: &ProductionControl<'_>,
240) -> Result<u8, SQLError> {
241    control.check()?;
242    match expression {
243        ScalarExpr::Literal(Value::Bool(value)) => {
244            if *value {
245                Ok(TRUTH_TRUE)
246            } else {
247                Ok(TRUTH_FALSE)
248            }
249        }
250        ScalarExpr::Literal(Value::Null) => Ok(TRUTH_NULL),
251        ScalarExpr::IsNull { expr, negated }
252            if expression_is_null_with_side(routines, expr, side, other, params, control)? =>
253        {
254            if *negated {
255                Ok(TRUTH_FALSE)
256            } else {
257                Ok(TRUTH_TRUE)
258            }
259        }
260        ScalarExpr::Between { expr, low, high } => {
261            let value_is_null =
262                expression_is_null_with_side(routines, expr, side, other, params, control)?;
263            let low_is_null =
264                expression_is_null_with_side(routines, low, side, other, params, control)?;
265            let high_is_null =
266                expression_is_null_with_side(routines, high, side, other, params, control)?;
267            if value_is_null || (low_is_null && high_is_null) {
268                Ok(TRUTH_NULL)
269            } else if low_is_null || high_is_null {
270                Ok(TRUTH_FALSE | TRUTH_NULL)
271            } else {
272                Ok(TRUTH_ANY)
273            }
274        }
275        expression
276            if expression_is_null_with_side(
277                routines, expression, side, other, params, control,
278            )? =>
279        {
280            Ok(TRUTH_NULL)
281        }
282        ScalarExpr::Not(inner) => Ok(negate_truth_values(truth_values_with_null_side(
283            routines, inner, side, other, params, control,
284        )?)),
285        ScalarExpr::And(items) => items.iter().try_fold(TRUTH_TRUE, |left, right| {
286            Ok(combine_truth_values(
287                left,
288                truth_values_with_null_side(routines, right, side, other, params, control)?,
289                true,
290            ))
291        }),
292        ScalarExpr::Or(items) => items.iter().try_fold(TRUTH_FALSE, |left, right| {
293            Ok(combine_truth_values(
294                left,
295                truth_values_with_null_side(routines, right, side, other, params, control)?,
296                false,
297            ))
298        }),
299        _ => Ok(TRUTH_ANY),
300    }
301}
302
303fn expression_is_null_with_side(
304    routines: &dyn RoutineResolution,
305    expression: &ScalarExpr,
306    side: &RowSchema,
307    other: &RowSchema,
308    params: &[SQLParam],
309    control: &ProductionControl<'_>,
310) -> Result<bool, SQLError> {
311    control.check()?;
312    match expression {
313        ScalarExpr::Literal(Value::Null) => Ok(true),
314        ScalarExpr::Column(column) => Ok(side.unqualified_position(column).is_some()
315            && other.unqualified_position(column).is_none()),
316        ScalarExpr::QualifiedColumn { qualifier, column } => Ok(side
317            .has_qualified_column(qualifier, column)
318            && !other.has_qualified_column(qualifier, column)),
319        ScalarExpr::Binary { lhs, rhs, .. } => Ok(expression_is_null_with_side(
320            routines, lhs, side, other, params, control,
321        )? || expression_is_null_with_side(
322            routines, rhs, side, other, params, control,
323        )?),
324        ScalarExpr::UnaryMinus(inner)
325        | ScalarExpr::Cast { expr: inner, .. }
326        | ScalarExpr::Collated { expr: inner, .. } => {
327            expression_is_null_with_side(routines, inner, side, other, params, control)
328        }
329        ScalarExpr::Between { expr, low, high } => Ok(expression_is_null_with_side(
330            routines, expr, side, other, params, control,
331        )? || (expression_is_null_with_side(
332            routines, low, side, other, params, control,
333        )? && expression_is_null_with_side(
334            routines, high, side, other, params, control,
335        )?)),
336        ScalarExpr::InList { expr, .. } => {
337            expression_is_null_with_side(routines, expr, side, other, params, control)
338        }
339        ScalarExpr::Func {
340            name,
341            binding,
342            args,
343            ..
344        } => {
345            if !scalar_function_is_strict(
346                routines,
347                name,
348                binding.as_ref(),
349                args,
350                (side, other),
351                params,
352                control,
353            )? {
354                return Ok(false);
355            }
356            for argument in crate::ir::scalar_call_arguments_with_control(args, control)?.iter() {
357                if expression_is_null_with_side(
358                    routines,
359                    argument.value,
360                    side,
361                    other,
362                    params,
363                    control,
364                )? {
365                    return Ok(true);
366                }
367            }
368            Ok(false)
369        }
370        _ => Ok(false),
371    }
372}
373
374fn scalar_function_is_strict(
375    routines: &dyn RoutineResolution,
376    name: &str,
377    binding: Option<&crate::ast::FunctionBinding>,
378    args: &[ScalarExpr],
379    sides: (&RowSchema, &RowSchema),
380    params: &[SQLParam],
381    control: &ProductionControl<'_>,
382) -> Result<bool, SQLError> {
383    let (side, other) = sides;
384    let runtime_name = control.copy_text(name.strip_prefix("pg_catalog.").unwrap_or(name))?;
385    let (mut runtime_name, memory) = runtime_name.into_parts();
386    runtime_name.make_ascii_lowercase();
387    let runtime_name = control.finish(runtime_name, memory)?;
388    if routines.has_registered_scalar_function_with_control(&runtime_name, control)? {
389        return Ok(false);
390    }
391    if let Some(strict) = crate::expr::bound_scalar_function_strictness(name, binding, args.len()) {
392        return Ok(strict);
393    }
394    let schema = RowSchema::join_with_control(side, other, std::iter::empty(), control)?;
395    let signature = crate::function_call_argument_signature_with_control(
396        args,
397        &schema,
398        params,
399        Some(routines),
400        control,
401    )?;
402    if binding.is_none() && !routines.has_visible_sql_functions_with_control(name, control)? {
403        return Ok(false);
404    }
405    Ok(routines
406        .resolve_static_sql_function_strictness_with_control(
407            name,
408            binding,
409            crate::type_resolution::RoutineCallDescriptor {
410                argument_names: &signature.0,
411                argument_types: &signature.1,
412                explicit_variadic: signature.2,
413            },
414            control,
415        )?
416        .unwrap_or(false))
417}
418
419fn negate_truth_values(values: u8) -> u8 {
420    (u8::from(values & TRUTH_FALSE != 0) * TRUTH_TRUE)
421        | (u8::from(values & TRUTH_TRUE != 0) * TRUTH_FALSE)
422        | (values & TRUTH_NULL)
423}
424
425fn combine_truth_values(left: u8, right: u8, and: bool) -> u8 {
426    let mut output = 0;
427    for lhs in [TRUTH_FALSE, TRUTH_TRUE, TRUTH_NULL] {
428        if left & lhs == 0 {
429            continue;
430        }
431        for rhs in [TRUTH_FALSE, TRUTH_TRUE, TRUTH_NULL] {
432            if right & rhs == 0 {
433                continue;
434            }
435            output |= if and {
436                match (lhs, rhs) {
437                    (TRUTH_FALSE, _) | (_, TRUTH_FALSE) => TRUTH_FALSE,
438                    (TRUTH_TRUE, TRUTH_TRUE) => TRUTH_TRUE,
439                    _ => TRUTH_NULL,
440                }
441            } else {
442                match (lhs, rhs) {
443                    (TRUTH_TRUE, _) | (_, TRUTH_TRUE) => TRUTH_TRUE,
444                    (TRUTH_FALSE, TRUTH_FALSE) => TRUTH_FALSE,
445                    _ => TRUTH_NULL,
446                }
447            };
448        }
449    }
450    output
451}