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