Skip to main content

uqa_sql/semantics/
partition.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Declarative partition validation, value comparison, and routing semantics.
8
9use crate::{
10    assignment::AssignmentContext,
11    ast::{ColumnDef, Expr, TableHierarchy},
12    schema::SchemaExpressionCatalog,
13    type_resolution::FunctionTypeResolver,
14    ResultRow, RowSchema, SQLError, SQLParam,
15};
16use std::cmp::Ordering;
17use uqa_core::Value;
18
19/// Hierarchy definitions needed to validate and route a row; no storage writes are exposed.
20pub trait PartitionCatalog {
21    fn try_table_hierarchy(&self, table: &str) -> Result<TableHierarchy, String>;
22    fn direct_hierarchy_children(&self, parent: &str) -> Result<Vec<String>, SQLError>;
23    fn try_resolve_table_name(&self, name: &str) -> Result<Option<String>, String>;
24    fn try_describe_table(&self, table: &str) -> Result<Option<Vec<ColumnDef>>, String>;
25    /// The object identity of a table, which survives renames.
26    fn try_table_object_id(&self, table: &str) -> Result<Option<[u8; 16]>, String>;
27}
28
29/// Evaluate declared partition keys and bounds with the caller's expression scope.
30pub trait PartitionExpressions {
31    /// Reconstruct a stored key using its retained type and routine identities and current catalog names.
32    fn expression_text(&self, expression: &Expr) -> Result<String, SQLError>;
33    fn evaluate_bound(&self, expression: &Expr, params: &[SQLParam]) -> Result<Value, SQLError>;
34    fn evaluate_row(
35        &self,
36        expression: &Expr,
37        row: &dyn crate::expr::RowLookup,
38        schema: &RowSchema,
39        params: &[SQLParam],
40    ) -> Result<Value, SQLError>;
41}
42
43#[derive(Clone, Copy)]
44pub struct PartitionContext<'a> {
45    pub catalog: &'a dyn PartitionCatalog,
46    pub expressions: &'a dyn PartitionExpressions,
47    pub types: &'a dyn FunctionTypeResolver,
48    /// Catalog-aware assignment coercion of bound values and output of key values.
49    pub assignment: &'a dyn AssignmentContext,
50    /// Aggregate, window and set-returning classification of bound and key expressions.
51    pub schema: &'a dyn SchemaExpressionCatalog,
52}
53
54fn compare_values(
55    context: &PartitionContext<'_>,
56    left: &Value,
57    right: &Value,
58) -> Result<Ordering, SQLError> {
59    crate::expr::compare_typed_values_with_enum_catalog(
60        left,
61        right,
62        &uqa_core::memory::ProductionControl::uncontrolled(),
63        Some(&crate::expr::EngineValueCatalog(context.assignment)),
64        None,
65    )
66}
67
68mod admission;
69mod bounds;
70mod datum_text;
71mod hash;
72mod key;
73pub use key::key_type as partition_key_type;
74
75pub use admission::validate_new_partition_bound;
76pub use bounds::transform_partition_bound;
77pub use datum_text::{partition_datum_text, range_bound_text, stored_datum};
78
79pub fn validate_hash_partition_spec(
80    context: &PartitionContext<'_>,
81    spec: &crate::ast::PartitionSpec,
82    columns: &[crate::ast::ColumnDef],
83) -> Result<(), SQLError> {
84    hash::validate_partition_spec(context.types, spec, columns)
85}
86
87/// Test one stored row against a prospective direct-child bound before the
88/// hierarchy edge is installed. DEFAULT means no existing non-default sibling
89/// accepts the row, matching the routing decision the new edge will expose.
90pub fn prospective_partition_bound_accepts_document(
91    context: &PartitionContext<'_>,
92    parent: &str,
93    bound: &crate::ast::PartitionBound,
94    document: &ResultRow,
95) -> Result<bool, SQLError> {
96    let hierarchy = context
97        .catalog
98        .try_table_hierarchy(parent)
99        .map_err(|error| SQLError::Internal(format!("read parent partition metadata: {error}")))?;
100    let spec = hierarchy
101        .partition_spec
102        .as_ref()
103        .ok_or_else(|| SQLError::Routine {
104            sqlstate: "42809".into(),
105            message: format!("relation \"{parent}\" is not partitioned"),
106        })?;
107    let key = routing_key(context, parent, spec, document, &[])?;
108    if !matches!(bound, crate::ast::PartitionBound::Default) {
109        return partition_bound_matches(context, bound, &key, &[]);
110    }
111    for sibling in context.catalog.direct_hierarchy_children(parent)? {
112        let sibling_hierarchy = context
113            .catalog
114            .try_table_hierarchy(&sibling)
115            .map_err(|error| SQLError::Internal(format!("read child partition: {error}")))?;
116        let Some(sibling_bound) = sibling_hierarchy.partition_bound.as_ref() else {
117            continue;
118        };
119        if matches!(sibling_bound, crate::ast::PartitionBound::Default) {
120            continue;
121        }
122        if partition_bound_matches(context, sibling_bound, &key, &[])? {
123            return Ok(false);
124        }
125    }
126    Ok(true)
127}
128
129/// Evaluate a retained detached-partition CHECK without requiring a live
130/// parent edge. This is also the exact predicate used for prospective ATTACH
131/// row scans.
132pub fn partition_constraint_accepts_document(
133    context: &PartitionContext<'_>,
134    table: &str,
135    spec: &crate::ast::PartitionSpec,
136    bound: &crate::ast::PartitionBound,
137    document: &ResultRow,
138) -> Result<bool, SQLError> {
139    let key = routing_key(context, table, spec, document, &[])?;
140    partition_bound_matches(context, bound, &key, &[])
141}
142
143/// A row's partition key under one partitioned table, with the row hash of a HASH partition key.
144struct RoutingKey {
145    values: Vec<Value>,
146    hash: Option<u64>,
147}
148
149fn routing_key(
150    context: &PartitionContext<'_>,
151    table: &str,
152    spec: &crate::ast::PartitionSpec,
153    document: &ResultRow,
154    params: &[SQLParam],
155) -> Result<RoutingKey, SQLError> {
156    let (values, definitions) =
157        evaluate_partition_keys(context, table, &spec.keys, document, params)?;
158    let hash = (spec.strategy == crate::ast::PartitionStrategy::Hash)
159        .then(|| hash::row_hash(context, spec, &definitions, &values))
160        .transpose()?;
161    Ok(RoutingKey { values, hash })
162}
163
164/// Why partition routing rejects a row. The executor reports each with a description of the row, which depends on the statement and the role that writes it.
165#[derive(Debug, Clone, PartialEq)]
166pub enum PartitionRejection {
167    /// The row does not satisfy the partition constraint of `relation`, which a statement names and routes from: `new row for relation "x" violates partition constraint`.
168    Constraint { relation: String },
169    /// No partition of `relation` accepts the row, whose partition key has the values `keys`: `no partition of relation "x" found for row`.
170    NoPartition { relation: String, keys: Vec<Value> },
171}
172
173/// Where a row that a statement writes through a relation is stored.
174#[derive(Debug, Clone, PartialEq)]
175pub enum PartitionRoute {
176    /// The relation that stores the row.
177    Target(String),
178    /// Routing rejects the row.
179    Rejected(PartitionRejection),
180}
181
182/// Route a row that an `INSERT` writes through `requested_table`, as `ExecFindPartition` does: a partitioned table that is itself a partition first checks its own partition constraint, and each level then selects the partition whose bound accepts the row. A relation that is not partitioned stores the row itself, without a check: `ExecInsert` checks the partition constraint of a partition that the statement names after its other constraints, which the caller does with [`partition_constraint_accepts_row`].
183pub fn route_partition_insert(
184    context: &PartitionContext<'_>,
185    requested_table: &str,
186    document: &ResultRow,
187    params: &[SQLParam],
188    include_descendants: bool,
189) -> Result<PartitionRoute, SQLError> {
190    let table = context
191        .catalog
192        .try_resolve_table_name(requested_table)
193        .map_err(|error| SQLError::Internal(format!("resolve INSERT table: {error}")))?
194        .ok_or_else(|| SQLError::UnknownTable(requested_table.to_string()))?;
195    let hierarchy = context
196        .catalog
197        .try_table_hierarchy(&table)
198        .map_err(|error| SQLError::Internal(format!("read partition metadata: {error}")))?;
199    let Some(spec) = hierarchy.partition_spec.as_ref() else {
200        return Ok(PartitionRoute::Target(table));
201    };
202    if !include_descendants {
203        return Err(SQLError::Routine {
204            sqlstate: "42809".into(),
205            message: format!("cannot insert into partitioned table \"{requested_table}\""),
206        });
207    }
208    if !partition_constraint_accepts_row(context, &table, document, params)? {
209        return Ok(PartitionRoute::Rejected(PartitionRejection::Constraint {
210            relation: table,
211        }));
212    }
213    route_partition_tree(context, &table, spec, document, params)
214}
215
216/// Whether the row satisfies the partition constraint of `table`, which holds the bounds of the partition and of each of its partition ancestors (`ExecPartitionCheck`). A relation that is not a partition accepts every row.
217pub fn partition_constraint_accepts_row(
218    context: &PartitionContext<'_>,
219    table: &str,
220    document: &ResultRow,
221    params: &[SQLParam],
222) -> Result<bool, SQLError> {
223    let mut child = table.to_string();
224    let mut visited = std::collections::BTreeSet::new();
225    loop {
226        if !visited.insert(child.clone()) {
227            return Err(SQLError::Internal(format!(
228                "partition hierarchy cycle reaches `{child}`"
229            )));
230        }
231        let hierarchy = context
232            .catalog
233            .try_table_hierarchy(&child)
234            .map_err(|error| SQLError::Internal(format!("read partition metadata: {error}")))?;
235        if hierarchy.partition_bound.is_none() {
236            return Ok(true);
237        }
238        let parent = hierarchy.parents.first().ok_or_else(|| {
239            SQLError::Internal(format!("partition `{child}` has no parent relation"))
240        })?;
241        let parent_hierarchy = context
242            .catalog
243            .try_table_hierarchy(parent)
244            .map_err(|error| {
245                SQLError::Internal(format!("read parent partition metadata: {error}"))
246            })?;
247        let spec = parent_hierarchy.partition_spec.as_ref().ok_or_else(|| {
248            SQLError::Internal(format!("partition parent `{parent}` has no partition key"))
249        })?;
250        match select_direct_partition(context, parent, spec, document, params)? {
251            DirectPartition::Child(selected) if selected == child => {}
252            DirectPartition::Child(_) | DirectPartition::None { .. } => return Ok(false),
253        }
254        child.clone_from(parent);
255    }
256}
257
258fn route_partition_tree(
259    context: &PartitionContext<'_>,
260    table: &str,
261    spec: &crate::ast::PartitionSpec,
262    document: &ResultRow,
263    params: &[SQLParam],
264) -> Result<PartitionRoute, SQLError> {
265    let child = match select_direct_partition(context, table, spec, document, params)? {
266        DirectPartition::Child(child) => child,
267        DirectPartition::None { keys } => {
268            return Ok(PartitionRoute::Rejected(PartitionRejection::NoPartition {
269                relation: table.to_string(),
270                keys,
271            }))
272        }
273    };
274    let hierarchy = context
275        .catalog
276        .try_table_hierarchy(&child)
277        .map_err(|error| SQLError::Internal(format!("read partition metadata: {error}")))?;
278    match hierarchy.partition_spec.as_ref() {
279        Some(spec) => route_partition_tree(context, &child, spec, document, params),
280        None => Ok(PartitionRoute::Target(child)),
281    }
282}
283
284/// The direct partition of a partitioned table that accepts a row, or the row's partition key values when none does.
285enum DirectPartition {
286    Child(String),
287    None { keys: Vec<Value> },
288}
289
290fn select_direct_partition(
291    context: &PartitionContext<'_>,
292    parent: &str,
293    spec: &crate::ast::PartitionSpec,
294    document: &ResultRow,
295    params: &[SQLParam],
296) -> Result<DirectPartition, SQLError> {
297    let key = routing_key(context, parent, spec, document, params)?;
298    Ok(match select_partition(context, parent, &key, params)? {
299        Some(child) => DirectPartition::Child(child),
300        None => DirectPartition::None { keys: key.values },
301    })
302}
303
304fn select_partition(
305    context: &PartitionContext<'_>,
306    parent: &str,
307    key: &RoutingKey,
308    params: &[SQLParam],
309) -> Result<Option<String>, SQLError> {
310    let mut default = None;
311    for child in context.catalog.direct_hierarchy_children(parent)? {
312        let child_hierarchy = context
313            .catalog
314            .try_table_hierarchy(&child)
315            .map_err(|error| SQLError::Internal(format!("read child partition: {error}")))?;
316        let Some(bound) = child_hierarchy.partition_bound.as_ref() else {
317            continue;
318        };
319        if matches!(bound, crate::ast::PartitionBound::Default) {
320            if default.replace(child).is_some() {
321                return Err(SQLError::Internal(format!(
322                    "partitioned table `{parent}` has more than one default partition"
323                )));
324            }
325            continue;
326        }
327        if partition_bound_matches(context, bound, key, params)? {
328            return Ok(Some(child));
329        }
330    }
331    Ok(default)
332}
333
334fn evaluate_partition_keys(
335    context: &PartitionContext<'_>,
336    table: &str,
337    expressions: &[crate::ast::Expr],
338    document: &ResultRow,
339    params: &[SQLParam],
340) -> Result<(Vec<Value>, Vec<crate::ast::ColumnDef>), SQLError> {
341    let definitions = context
342        .catalog
343        .try_describe_table(table)
344        .map_err(|error| SQLError::Internal(format!("read partition row type: {error}")))?
345        .ok_or_else(|| SQLError::UnknownTable(table.to_string()))?;
346    let schema = crate::RowSchema::with_types(
347        definitions
348            .iter()
349            .map(|definition| definition.name.clone())
350            .collect(),
351        definitions
352            .iter()
353            .map(|definition| Some(definition.ty.clone()))
354            .collect(),
355    );
356    let values = expressions
357        .iter()
358        .map(|expression| {
359            context
360                .expressions
361                .evaluate_row(expression, document, &schema, params)
362        })
363        .collect::<Result<Vec<_>, _>>()?;
364    Ok((values, definitions))
365}
366
367fn partition_bound_matches(
368    context: &PartitionContext<'_>,
369    bound: &crate::ast::PartitionBound,
370    key: &RoutingKey,
371    params: &[SQLParam],
372) -> Result<bool, SQLError> {
373    use crate::ast::PartitionBound;
374    let keys = key.values.as_slice();
375    match bound {
376        PartitionBound::Default => Ok(true),
377        PartitionBound::List(values) => {
378            let [key] = keys else {
379                return Err(SQLError::Internal(
380                    "LIST partition has more than one partition key".into(),
381                ));
382            };
383            for expression in values {
384                let bound = context.expressions.evaluate_bound(expression, params)?;
385                if compare_values(context, &bound, key)?.is_eq() {
386                    return Ok(true);
387                }
388            }
389            Ok(false)
390        }
391        PartitionBound::Range { lower, upper } => {
392            if keys.iter().any(|value| matches!(value, Value::Null)) {
393                return Ok(false);
394            }
395            Ok(
396                compare_key_to_bound(context, keys, lower, params)? != Ordering::Less
397                    && compare_key_to_bound(context, keys, upper, params)? == Ordering::Less,
398            )
399        }
400        PartitionBound::Hash { modulus, remainder } => hash::bound_matches(
401            key.hash.ok_or_else(|| {
402                SQLError::Internal("HASH partition bound has no computed row hash".into())
403            })?,
404            *modulus,
405            *remainder,
406        ),
407    }
408}
409
410fn compare_key_to_bound(
411    context: &PartitionContext<'_>,
412    keys: &[Value],
413    bound: &[crate::ast::PartitionRangeDatum],
414    params: &[SQLParam],
415) -> Result<Ordering, SQLError> {
416    if keys.len() != bound.len() {
417        return Err(SQLError::Internal(format!(
418            "partition key width {} differs from bound width {}",
419            keys.len(),
420            bound.len()
421        )));
422    }
423    for (key, datum) in keys.iter().zip(bound) {
424        let ordering = match datum {
425            crate::ast::PartitionRangeDatum::MinValue => Ordering::Greater,
426            crate::ast::PartitionRangeDatum::MaxValue => Ordering::Less,
427            crate::ast::PartitionRangeDatum::Value(expression) => compare_values(
428                context,
429                key,
430                &context.expressions.evaluate_bound(expression, params)?,
431            )?,
432        };
433        if ordering != Ordering::Equal {
434            return Ok(ordering);
435        }
436    }
437    Ok(Ordering::Equal)
438}
439
440mod identity;
441mod order;
442pub use order::partition_bound_order;
443mod tree;
444pub use identity::{
445    foreign_key_scan_tables, partition_ancestor_tables, partition_hierarchy_root,
446    partition_identity_owner,
447};
448pub use tree::{partition_tree, PartitionTreeNode};