Skip to main content

uqa_sql/semantics/
conflict.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Unique-index inference, target validation, and SQL predicate implication.
8use crate::{
9    ast::{BinaryOp, ColumnDef, TableConstraintSet},
10    binding::snapshot::BindingSnapshot,
11    catalog::index::EnforcedKey,
12    plan::AggregateClassifier,
13    plan::{ConflictPlan, ExpressionPlan, InsertPlan},
14    routines::RoutineResolution,
15    RowSchema, SQLError, SQLParam, ScalarExpr as Expr,
16};
17use std::collections::BTreeSet;
18use uqa_core::Value;
19
20pub trait ConflictCatalog {
21    fn try_describe_table(&self, table: &str) -> Result<Option<Vec<ColumnDef>>, String>;
22    fn enforced_keys(&self, table: &str) -> Result<Vec<EnforcedKey>, String>;
23    fn try_declared_table_constraints(&self, table: &str) -> Result<TableConstraintSet, String>;
24}
25/// Capture the stored-expression catalog scope only when an inference expression requires binding.
26pub trait InferenceBindingScope {
27    fn binding_scope(&self) -> Result<BindingSnapshot, SQLError>;
28}
29#[derive(Clone, Copy)]
30pub struct InferenceContext<'a> {
31    pub catalog: &'a dyn ConflictCatalog,
32    pub aggregates: &'a dyn AggregateClassifier,
33    pub routines: &'a dyn RoutineResolution,
34    pub binding: &'a dyn InferenceBindingScope,
35}
36
37/// Analyze the inference clause in the INSERT target's scope before uniqueness arbitration, including commands that produce no input rows.
38pub fn prepare_inference_predicate<'a>(
39    context: InferenceContext<'_>,
40    statement: &'a InsertPlan,
41    params: &[SQLParam],
42) -> Result<std::borrow::Cow<'a, InsertPlan>, SQLError> {
43    if statement
44        .on_conflict
45        .as_ref()
46        .is_none_or(|conflict| conflict.predicate.is_none() && conflict.expressions.is_empty())
47    {
48        return Ok(std::borrow::Cow::Borrowed(statement));
49    }
50    let columns = context
51        .catalog
52        .try_describe_table(&statement.table)
53        .map_err(SQLError::Internal)?
54        .ok_or_else(|| SQLError::UnknownTable(statement.table.clone()))?;
55    let schema = RowSchema::with_column_definitions(Some(&statement.target_qualifier), &columns);
56    let mut statement = statement.clone();
57    if let Some(conflict) = &mut statement.on_conflict {
58        for expression in conflict
59            .expressions
60            .iter_mut()
61            .chain(conflict.predicate.iter_mut().map(Box::as_mut))
62        {
63            prepare_inference_expression(
64                context,
65                expression,
66                &statement.target_qualifier,
67                &schema,
68                &columns,
69                params,
70            )?;
71        }
72        // A rewritten view expression can resolve to a simple base-table attribute.
73        let expressions = std::mem::take(&mut conflict.expressions);
74        for expression in expressions {
75            if let Expr::Column(column) = expression {
76                conflict.conflict_columns.push(column);
77            } else {
78                conflict.expressions.push(expression);
79            }
80        }
81    }
82    Ok(std::borrow::Cow::Owned(statement))
83}
84
85fn prepare_inference_expression(
86    context: InferenceContext<'_>,
87    expression: &mut Expr,
88    qualifier: &str,
89    schema: &RowSchema,
90    columns: &[crate::ast::ColumnDef],
91    params: &[SQLParam],
92) -> Result<(), SQLError> {
93    let mut has_subquery = false;
94    expression.visit(&mut |part| {
95        has_subquery |= matches!(
96            part,
97            Expr::ScalarSubquery(_) | Expr::Exists { .. } | Expr::InSubquery { .. }
98        );
99    });
100    if has_subquery {
101        return Err(predicate_error(
102            "0A000",
103            "cannot use subquery in index inference",
104        ));
105    }
106    if crate::semantics::aggregates::contains_aggregate(context.aggregates, expression) {
107        return Err(predicate_error(
108            "42803",
109            "aggregate functions are not allowed in index inference",
110        ));
111    }
112    if crate::semantics::windows::expr_has_window(expression) {
113        return Err(predicate_error(
114            "42P20",
115            "window functions are not allowed in index inference",
116        ));
117    }
118    let mut plan = ExpressionPlan {
119        scalar: expression.clone(),
120        subqueries: Vec::new(),
121    };
122    let binding = context.binding.binding_scope()?;
123    crate::binding::bind_expression_plan_routines_for_storage(
124        context.routines,
125        &mut plan,
126        params,
127        &binding.context(),
128        schema,
129    )?;
130    crate::plan::rewrite_scalar_expression(&mut plan.scalar, &mut |expression| {
131        if let Expr::QualifiedColumn {
132            qualifier: source,
133            column,
134        } = expression
135        {
136            if source == qualifier {
137                *expression = Expr::Column(column.clone());
138            }
139        }
140    });
141    crate::plan::rewrite_scalar_expression(&mut plan.scalar, &mut |expression| {
142        if let Expr::Cast { expr, ty, .. } = expression {
143            if let Expr::Column(name) = expr.as_ref() {
144                if columns.iter().any(|column| {
145                    column.name == *name
146                        && crate::ast::ColumnType::from_sql_name(ty).ok().as_ref()
147                            == Some(&column.ty)
148                }) {
149                    *expression = Expr::Column(name.clone());
150                }
151            }
152        }
153    });
154    *expression = inference_identity(plan.scalar);
155    Ok(())
156}
157
158fn inference_identity(mut expression: Expr) -> Expr {
159    // Inference precedes optimization: result envelopes derive from these bound inputs, while stored index syntax retains the explicit COLLATE nodes, typed constants and routine identities themselves.
160    crate::plan::rewrite_scalar_expression(&mut expression, &mut |node| {
161        while matches!(node, Expr::Collated { .. }) {
162            let Expr::Collated { expr, .. } = std::mem::replace(node, Expr::Literal(Value::Null))
163            else {
164                unreachable!("derived result envelope");
165            };
166            *node = *expr;
167        }
168        // Coercion display form is not identity, but the conversion and destination type are.
169        if let Expr::Cast { implicit, .. } = node {
170            *implicit = false;
171        }
172        // An explicit COLLATE remains a node of its own, and the same call over one relation derives the same input collation, so the recorded selection is not identity. A key stored before calls recorded it still matches.
173        if let Expr::Func {
174            binding: Some(binding),
175            ..
176        } = node
177        {
178            binding.input_collation = None;
179        }
180    });
181    expression
182}
183
184fn predicate_error(sqlstate: &str, message: &str) -> SQLError {
185    SQLError::Routine {
186        sqlstate: sqlstate.into(),
187        message: message.into(),
188    }
189}
190
191/// Match the inference expressions analyzed by [`prepare_inference_predicate`] against the stored unique keys.
192pub fn conflict_key_indices(
193    catalog: &dyn ConflictCatalog,
194    table: &str,
195    keys: &[EnforcedKey],
196    conflict: &ConflictPlan,
197) -> Result<Vec<usize>, SQLError> {
198    if let Some(name) = &conflict.constraint {
199        return constraint_target_index(catalog, table, keys, name);
200    }
201    if conflict.conflict_columns.is_empty() && conflict.expressions.is_empty() {
202        return Ok((0..keys.len()).collect());
203    }
204    validate_conflict_columns(catalog, table, &conflict.conflict_columns)?;
205    let target = conflict
206        .conflict_columns
207        .iter()
208        .map(String::as_str)
209        .collect::<BTreeSet<_>>();
210    let indexes = keys
211        .iter()
212        .enumerate()
213        .filter_map(|(index, key)| {
214            (key.columns
215                .iter()
216                .map(String::as_str)
217                .collect::<BTreeSet<_>>()
218                == target
219                && {
220                    let expressions = key
221                        .keys
222                        .iter()
223                        .filter_map(|key| match key {
224                            crate::ast::IndexKey::Expression(expr) => Some(inference_identity(
225                                ExpressionPlan::lower((**expr).clone()).scalar,
226                            )),
227                            crate::ast::IndexKey::Column(_) => None,
228                        })
229                        .collect::<Vec<_>>();
230                    expressions
231                        .iter()
232                        .all(|expr| conflict.expressions.contains(expr))
233                        && conflict
234                            .expressions
235                            .iter()
236                            .all(|expr| expressions.contains(expr))
237                }
238                && key.predicate.as_deref().is_none_or(|required| {
239                    conflict.predicate.as_deref().is_some_and(|given| {
240                        implies(
241                            given,
242                            &inference_identity(ExpressionPlan::lower(required.clone()).scalar),
243                        )
244                    })
245                }))
246            .then_some(index)
247        })
248        .collect::<Vec<_>>();
249    if indexes.is_empty() {
250        return Err(SQLError::Routine {
251            sqlstate: "42P10".into(),
252            message:
253                "there is no unique or exclusion constraint matching the ON CONFLICT specification"
254                    .into(),
255        });
256    }
257    Ok(indexes)
258}
259
260/// Prove that every row for which `given` is true also makes `required` true. SQL NULL is never treated as false in a proof that would admit an invalid arbiter.
261fn implies(given: &Expr, required: &Expr) -> bool {
262    if given == required || matches!(required, Expr::Literal(Value::Bool(true))) {
263        return true;
264    }
265    if matches!(given, Expr::Literal(Value::Bool(false) | Value::Null)) {
266        return true;
267    }
268    if let Expr::And(parts) = required {
269        return parts.iter().all(|part| implies(given, part));
270    }
271    if let Expr::Or(parts) = given {
272        return parts.iter().all(|part| implies(part, required));
273    }
274    if let Expr::And(parts) = given {
275        if parts.iter().any(|part| implies(part, required)) {
276            return true;
277        }
278    }
279    if let Expr::Or(parts) = required {
280        return parts.iter().any(|part| implies(given, part));
281    }
282    if let Some((left, given_op, given_value)) = comparison(given) {
283        if let Some((right, required_op, required_value)) = comparison(required) {
284            return left == right
285                && comparison_implies(given_op, given_value, required_op, required_value);
286        }
287        if let Expr::IsNull {
288            expr,
289            negated: true,
290        } = required
291        {
292            return left == expr.as_ref() && !matches!(given_value, Value::Null);
293        }
294    }
295    false
296}
297
298fn comparison(expr: &Expr) -> Option<(&Expr, BinaryOp, &Value)> {
299    let Expr::Binary { op, lhs, rhs } = expr else {
300        return None;
301    };
302    if !matches!(
303        op,
304        BinaryOp::Equal
305            | BinaryOp::NotEqual
306            | BinaryOp::Less
307            | BinaryOp::LessEqual
308            | BinaryOp::Greater
309            | BinaryOp::GreaterEqual
310    ) {
311        return None;
312    }
313    if let Expr::Literal(value) = rhs.as_ref() {
314        return Some((lhs, *op, value));
315    }
316    if let Expr::Literal(value) = lhs.as_ref() {
317        let reversed = match op {
318            BinaryOp::Less => BinaryOp::Greater,
319            BinaryOp::LessEqual => BinaryOp::GreaterEqual,
320            BinaryOp::Greater => BinaryOp::Less,
321            BinaryOp::GreaterEqual => BinaryOp::LessEqual,
322            other => *other,
323        };
324        return Some((rhs, reversed, value));
325    }
326    None
327}
328
329fn comparison_implies(given: BinaryOp, left: &Value, required: BinaryOp, right: &Value) -> bool {
330    use BinaryOp::{Equal, Greater, GreaterEqual, Less, LessEqual, NotEqual};
331    if matches!(left, Value::Null) || matches!(right, Value::Null) {
332        return false;
333    }
334    if std::mem::discriminant(left) != std::mem::discriminant(right) {
335        return false;
336    }
337    let order = left.cmp(right);
338    match (given, required) {
339        (Equal, Equal) | (NotEqual, NotEqual) => order.is_eq(),
340        (Equal, NotEqual) => !order.is_eq(),
341        (Equal | GreaterEqual, Greater) | (GreaterEqual, NotEqual) => order.is_gt(),
342        (Equal | LessEqual, Less) | (LessEqual, NotEqual) => order.is_lt(),
343        (Equal | Greater | GreaterEqual, GreaterEqual) | (Greater, Greater | NotEqual) => {
344            order.is_ge()
345        }
346        (Equal | Less | LessEqual, LessEqual) | (Less, Less | NotEqual) => order.is_le(),
347        _ => false,
348    }
349}
350
351pub fn validate_conflict_target(
352    catalog: &dyn ConflictCatalog,
353    table: &str,
354    conflict: &ConflictPlan,
355) -> Result<(), SQLError> {
356    let keys = catalog
357        .enforced_keys(table)
358        .map_err(|error| SQLError::Internal(format!("conflict target keys: {error}")))?;
359    conflict_key_indices(catalog, table, &keys, conflict).map(|_| ())
360}
361
362fn constraint_target_index(
363    catalog: &dyn ConflictCatalog,
364    table: &str,
365    keys: &[EnforcedKey],
366    name: &str,
367) -> Result<Vec<usize>, SQLError> {
368    if let Some(index) = keys
369        .iter()
370        .position(|key| key.constraint_owned && key.name.as_deref() == Some(name))
371    {
372        return Ok(vec![index]);
373    }
374    let snapshot = catalog
375        .try_declared_table_constraints(table)
376        .map_err(SQLError::Internal)?;
377    let columns = catalog
378        .try_describe_table(table)
379        .map_err(SQLError::Internal)?
380        .ok_or_else(|| SQLError::UnknownTable(table.into()))?;
381    let exists = snapshot
382        .checks
383        .iter()
384        .any(|check| check.name.as_deref() == Some(name))
385        || snapshot
386            .foreign_keys
387            .iter()
388            .any(|key| key.name.as_deref() == Some(name))
389        || columns.iter().any(|column| {
390            column.not_null_name.as_deref() == Some(name)
391                || column.check_name.as_deref() == Some(name)
392                || column
393                    .references
394                    .as_ref()
395                    .is_some_and(|reference| reference.name.as_deref() == Some(name))
396        });
397    if exists {
398        return Err(SQLError::Routine {
399            sqlstate: "42809".into(),
400            message: "constraint in ON CONFLICT clause has no associated index".into(),
401        });
402    }
403    Err(SQLError::Routine {
404        sqlstate: "42704".into(),
405        message: format!("constraint \"{name}\" for table \"{table}\" does not exist"),
406    })
407}
408
409fn validate_conflict_columns(
410    catalog: &dyn ConflictCatalog,
411    table: &str,
412    names: &[String],
413) -> Result<(), SQLError> {
414    let columns = catalog
415        .try_describe_table(table)
416        .map_err(SQLError::Internal)?
417        .ok_or_else(|| SQLError::UnknownTable(table.into()))?;
418    for name in names {
419        if !columns.iter().any(|column| column.name == *name)
420            && !matches!(
421                name.as_str(),
422                "ctid" | "tableoid" | "xmin" | "xmax" | "cmin" | "cmax"
423            )
424        {
425            return Err(SQLError::UnknownColumn(name.clone()));
426        }
427    }
428    Ok(())
429}
430
431#[cfg(test)]
432mod inference;
433
434#[cfg(test)]
435mod tests {
436    use super::*;
437
438    #[test]
439    fn inference_implication_ignores_cast_origin_but_preserves_cast_types() {
440        let predicate = |implicit, ty: &str, bound| {
441            inference_identity(Expr::Binary {
442                op: BinaryOp::Greater,
443                lhs: Box::new(Expr::Cast {
444                    implicit,
445                    expr: Box::new(Expr::Column("value".into())),
446                    ty: ty.into(),
447                }),
448                rhs: Box::new(Expr::Literal(Value::Int(bound))),
449            })
450        };
451        for implicit in [false, true] {
452            let required = predicate(implicit, "bigint", 0);
453            let equivalent = predicate(!implicit, "bigint", 0);
454            assert_eq!(required, equivalent);
455            assert!(implies(&equivalent, &required));
456            assert!(implies(&predicate(!implicit, "bigint", 1), &required));
457            assert!(!implies(&predicate(!implicit, "bigint", -1), &required));
458            assert!(!implies(&predicate(!implicit, "integer", 0), &required));
459        }
460    }
461}