1use 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}
25pub 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
37pub 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 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 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 if let Expr::Cast { implicit, .. } = node {
170 *implicit = false;
171 }
172 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
191pub 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
260fn 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}