Skip to main content

uqa_execution/mutation/
overlay.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Statement-local row overlays and exact index state. The rows a command stages for a table spill to encrypted temporary files once its allowance is under pressure, as a transaction's own changes do, so that one statement is bounded by disk rather than by its allowance.
8
9use std::sync::Arc;
10use uqa_core::{
11    memory::{BudgetedMap, BudgetedString, BudgetedVec, MemoryReservation},
12    DocId, Value,
13};
14use uqa_sql::SQLError;
15use uqa_storage::document_store::{Document, DocumentMetadata, RetainedDocumentFields};
16use uqa_storage::{read_control::StorageReadControl, StorageBackendResult};
17
18use crate::query::document_changes::DocumentChanges;
19use crate::query::exact_lookup::FieldPresence;
20
21mod comparison;
22mod exact;
23mod expressions;
24mod matching;
25pub use expressions::CommandIndexProbe;
26mod keys;
27mod spilled;
28mod staged;
29use exact::CommandExactIndex;
30use keys::{FieldSet, KeyFields, KeyKind};
31pub(crate) use spilled::StagedRow;
32use staged::StagedRows;
33pub(crate) use staged::{StagedCursor, StagedRowsView};
34
35#[derive(Clone)]
36pub struct CommandStoredDocument {
37    pub fields: RetainedDocumentFields,
38    pub metadata: DocumentMetadata,
39    /// Evaluated UNIQUE expression keys, separate from user-visible fields.
40    index_values: Option<RetainedDocumentFields>,
41    /// A nested command already published this version to transaction storage.
42    published: bool,
43}
44
45impl CommandStoredDocument {
46    pub fn new(
47        fields: Arc<Document>,
48        metadata: DocumentMetadata,
49        control: &StorageReadControl,
50    ) -> StorageBackendResult<Self> {
51        Ok(Self {
52            fields: RetainedDocumentFields::new(fields, control)?,
53            metadata,
54            index_values: None,
55            published: false,
56        })
57    }
58}
59
60#[derive(Default)]
61pub struct CommandMutationOverlay {
62    tables: Option<BudgetedMap<String, CommandTableOverlay>>,
63    has_publication: bool,
64}
65
66/// Immutable row roots at a transaction or savepoint boundary; cached exact keys are rebuilt after undo.
67#[derive(Clone, Default)]
68pub struct CommandOverlayCheckpoint {
69    tables: Vec<(String, StagedRows)>,
70    has_publication: bool,
71}
72
73struct CommandTableOverlay {
74    rows: StagedRows,
75    /// Exact indexes of the rows in memory; the spilled tier holds the entries of its own rows.
76    exact_indexes: BudgetedMap<FieldSet, CommandExactIndex>,
77    expression_indexes: BudgetedMap<FieldSet, CommandExactIndex>,
78    /// The ordinal the next exact index takes in the spilled tier. Ordinals are never reused, so the entries an index whose construction failed left behind are never read.
79    next_ordinal: u32,
80    has_fallible_comparison: bool,
81    _name_memory: MemoryReservation,
82}
83
84impl CommandMutationOverlay {
85    fn table(&self, table: &str) -> Option<&CommandTableOverlay> {
86        self.tables.as_ref()?.get(table)
87    }
88
89    /// Whether this command staged a row for `table`.
90    pub fn holds(&self, table: &str) -> bool {
91        self.table(table)
92            .is_some_and(|table| !table.rows.is_empty())
93    }
94
95    /// At least the number of rows `overlays` staged for `table`, without reading them; a row staged by several commands or staged again after it spilled counts more than once.
96    pub fn staged_row_bound(overlays: &[Self], table: &str) -> u64 {
97        overlays
98            .iter()
99            .filter_map(|overlay| overlay.table(table))
100            .fold(0, |count, rows| {
101                count.saturating_add(rows.rows.count_bound())
102            })
103    }
104
105    /// The row the newest of `overlays` staged for `id` in `table`: its fields, or `None` for a row the command deleted. `None` when no command staged the row.
106    pub fn row(
107        overlays: &[Self],
108        table: &str,
109        id: DocId,
110        control: &StorageReadControl,
111    ) -> Result<Option<Option<CommandStoredDocument>>, SQLError> {
112        for overlay in overlays.iter().rev() {
113            if let Some(rows) = overlay.table(table) {
114                if let Some(row) = rows.rows.get(id, control).map_err(storage_error)? {
115                    return Ok(Some(row));
116                }
117            }
118        }
119        Ok(None)
120    }
121
122    /// Whether one of `overlays` staged a row for `id` in `table`.
123    pub fn stages(
124        overlays: &[Self],
125        table: &str,
126        id: DocId,
127        control: &StorageReadControl,
128    ) -> Result<bool, SQLError> {
129        for overlay in overlays {
130            if let Some(rows) = overlay.table(table) {
131                if rows.rows.contains(id, control).map_err(storage_error)? {
132                    return Ok(true);
133                }
134            }
135        }
136        Ok(false)
137    }
138
139    /// `base` with the rows `overlays` staged for `table` above it, the newest command's rows above the others. The rows are not copied; later stages do not change the result.
140    pub fn changes(
141        overlays: &[Self],
142        table: &str,
143        base: DocumentChanges,
144        control: &StorageReadControl,
145    ) -> Result<DocumentChanges, SQLError> {
146        let views = overlays
147            .iter()
148            .filter_map(|overlay| overlay.table(table))
149            .filter(|rows| !rows.rows.is_empty())
150            .map(|rows| rows.rows.view());
151        base.with_staged(views, control).map_err(storage_error)
152    }
153
154    fn bind(
155        &mut self,
156        control: &StorageReadControl,
157    ) -> Result<&mut BudgetedMap<String, CommandTableOverlay>, SQLError> {
158        control.check().map_err(resource_error)?;
159        let tables = self
160            .tables
161            .get_or_insert_with(|| BudgetedMap::new(control.memory()));
162        if !tables.budget().shares_allowance(control.memory()) {
163            return Err(SQLError::Internal(
164                "command overlay received a different memory allowance".into(),
165            ));
166        }
167        Ok(tables)
168    }
169
170    /// Retain an evaluated row and prepare every cached-key change before publishing any row or index mutation.
171    pub fn stage(
172        &mut self,
173        table: &str,
174        id: DocId,
175        document: Option<(Arc<Document>, DocumentMetadata)>,
176        control: &StorageReadControl,
177    ) -> Result<(), SQLError> {
178        let document = document
179            .map(|(fields, metadata)| CommandStoredDocument::new(fields, metadata, control))
180            .transpose()
181            .map_err(resource_error)?;
182        self.stage_evaluated(table, id, document, control)
183    }
184
185    /// Publish an already evaluated row and its expression keys together.
186    pub fn stage_evaluated(
187        &mut self,
188        table: &str,
189        id: DocId,
190        document: Option<CommandStoredDocument>,
191        control: &StorageReadControl,
192    ) -> Result<(), SQLError> {
193        let tables = self.bind(control)?;
194        if let Some(table) = tables.get_mut(table) {
195            return table.stage(id, document, control);
196        }
197        let mut name = BudgetedString::new(control.memory());
198        name.push_str(table).map_err(resource_error)?;
199        let (name, names) = name.into_parts();
200        let mut rows = CommandTableOverlay {
201            rows: StagedRows::new(control),
202            exact_indexes: BudgetedMap::new(control.memory()),
203            expression_indexes: BudgetedMap::new(control.memory()),
204            next_ordinal: 0,
205            has_fallible_comparison: false,
206            _name_memory: names,
207        };
208        rows.stage(id, document, control)?;
209        let entry = tables.prepare_entry(name, rows).map_err(resource_error)?;
210        control.check().map_err(resource_error)?;
211        tables.insert_prepared(entry);
212        Ok(())
213    }
214
215    /// Probe exact canonical keys across command frames; newer replacements and tombstones mask older candidates. Candidate merging retains only the smallest visible identity.
216    pub fn find_match(
217        overlays: &mut [Self],
218        table: &str,
219        fields: &[String],
220        values: &[Value],
221        presence: FieldPresence,
222        control: &StorageReadControl,
223    ) -> Result<Option<DocId>, SQLError> {
224        Self::find_match_with_catalog(overlays, table, fields, values, presence, control, None)
225    }
226
227    /// Retain catalog-dependent comparison semantics while newer frames mask older rows.
228    pub fn find_match_with_catalog(
229        overlays: &mut [Self],
230        table: &str,
231        fields: &[String],
232        values: &[Value],
233        presence: FieldPresence,
234        control: &StorageReadControl,
235        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
236    ) -> Result<Option<DocId>, SQLError> {
237        if fields.len() != values.len() {
238            return Err(SQLError::Internal(
239                "command-overlay exact lookup has mismatched fields and values".into(),
240            ));
241        }
242        control.check().map_err(resource_error)?;
243        if overlays.iter().all(|overlay| !overlay.holds(table)) {
244            return Ok(None);
245        }
246        if values.iter().any(uqa_sql::expr::value_comparison_can_fail)
247            || overlays.iter().any(|overlay| {
248                overlay
249                    .table(table)
250                    .is_some_and(|table| table.has_fallible_comparison)
251            })
252        {
253            return comparison::find_match(
254                overlays, table, fields, values, presence, control, catalog,
255            );
256        }
257        let (fields, key) = keys::lookup_parts(fields, values, control)?;
258        for overlay in overlays.iter_mut() {
259            if let Some(rows) = overlay.bind(control)?.get_mut(table) {
260                rows.prepare_index(KeyKind::Columns, &fields, control)?;
261            }
262        }
263        let mut found = None;
264        for (position, overlay) in overlays.iter().enumerate().rev() {
265            let Some(rows) = overlay.table(table) else {
266                continue;
267            };
268            let newer = &overlays[position + 1..];
269            let index = rows
270                .exact_indexes
271                .get(fields.values())
272                .expect("prepared exact index");
273            if let Some(candidates) = index.candidates(key.bytes()) {
274                for (&id, ()) in candidates {
275                    control.check().map_err(resource_error)?;
276                    if found.is_some_and(|found| id >= found) {
277                        break;
278                    }
279                    if Self::stages(newer, table, id, control)? {
280                        continue;
281                    }
282                    // Full canonical bytes already establish value equality. Only field presence is absent from that representation; checking it does not reparse JSONB or allocate numeric comparison scratch.
283                    let document = rows
284                        .rows
285                        .memory
286                        .get(&id)
287                        .and_then(Option::as_ref)
288                        .expect("cached present row");
289                    if matches!(presence, FieldPresence::Required)
290                        && !holds_fields(document, &fields)
291                    {
292                        continue;
293                    }
294                    found = Some(id);
295                    break;
296                }
297            }
298            if let Some(spilled) = &rows.rows.spilled {
299                let mut after = None;
300                'pages: loop {
301                    let page = spilled::index_page(
302                        spilled.view(),
303                        index.ordinal(),
304                        key.bytes(),
305                        after,
306                        control,
307                    )
308                    .map_err(storage_error)?;
309                    for (id, complete) in page.rows.iter().copied() {
310                        control.check().map_err(resource_error)?;
311                        if found.is_some_and(|found| id >= found) {
312                            break 'pages;
313                        }
314                        // A row in memory shadows its spilled version, whose entries the memory tier's index replaces.
315                        if rows.rows.memory.get(&id).is_some()
316                            || Self::stages(newer, table, id, control)?
317                            || (matches!(presence, FieldPresence::Required) && !complete)
318                        {
319                            continue;
320                        }
321                        found = Some(id);
322                        break 'pages;
323                    }
324                    match page.resume {
325                        Some(resume) => after = Some(resume),
326                        None => break,
327                    }
328                }
329            }
330        }
331        Ok(found)
332    }
333}
334
335impl CommandMutationOverlay {
336    pub fn checkpoint(&self) -> CommandOverlayCheckpoint {
337        CommandOverlayCheckpoint {
338            tables: self
339                .tables
340                .iter()
341                .flat_map(|tables| tables.iter())
342                .map(|(name, table)| (name.clone(), table.rows.clone()))
343                .collect(),
344            has_publication: self.has_publication,
345        }
346    }
347
348    pub fn restore(&mut self, checkpoint: &CommandOverlayCheckpoint) {
349        if let Some(tables) = self.tables.as_mut() {
350            tables.for_each_mut(|name, table| {
351                table.rows = checkpoint
352                    .tables
353                    .iter()
354                    .find(|(saved, _)| saved == name)
355                    .map_or_else(
356                        || {
357                            StagedRows::new(&StorageReadControl::new(
358                                table.rows.memory.budget(),
359                                &uqa_core::CancellationToken::new(),
360                            ))
361                        },
362                        |(_, rows)| rows.clone(),
363                    );
364                table.exact_indexes = BudgetedMap::new(table.exact_indexes.budget());
365                table.expression_indexes = BudgetedMap::new(table.expression_indexes.budget());
366                // Index ordinals remain monotone: restored runs can still contain entries of an earlier cached index.
367            });
368        }
369        self.has_publication = checkpoint.has_publication;
370    }
371
372    /// Replace every enclosing command's staged image after a nested command writes it. This keeps later callbacks and exact-key probes on the newest version.
373    pub fn published(
374        overlays: &mut [Self],
375        table: &str,
376        id: DocId,
377        document: Option<(Arc<Document>, DocumentMetadata)>,
378        control: &StorageReadControl,
379    ) -> Result<(), SQLError> {
380        let document = document
381            .map(|(fields, metadata)| CommandStoredDocument::new(fields, metadata, control))
382            .transpose()
383            .map_err(resource_error)?;
384        Self::published_evaluated(overlays, table, id, document, control)
385    }
386
387    /// Refresh enclosing rows with the keys evaluated for their published image.
388    pub fn published_evaluated(
389        overlays: &mut [Self],
390        table: &str,
391        id: DocId,
392        mut document: Option<CommandStoredDocument>,
393        control: &StorageReadControl,
394    ) -> Result<(), SQLError> {
395        if let Some(document) = document.as_mut() {
396            document.published = true;
397        }
398        for overlay in overlays {
399            if Self::stages(std::slice::from_ref(overlay), table, id, control)? {
400                overlay.stage_evaluated(table, id, document.clone(), control)?;
401                overlay.has_publication = true;
402            }
403        }
404        Ok(())
405    }
406
407    /// Retain an ended command only when a nested command changed one of its staged rows.
408    pub fn published_rows(self) -> Option<Self> {
409        self.has_publication.then_some(self)
410    }
411
412    /// Whether writing an identity would overwrite a nested command's published row, including its deletion when `deleted_supersedes` holds.
413    pub fn was_published(
414        &self,
415        table: &str,
416        id: DocId,
417        deleted_supersedes: bool,
418        cancellation: &uqa_core::CancellationToken,
419    ) -> Result<bool, SQLError> {
420        let Some(table) = self.table(table) else {
421            return Ok(false);
422        };
423        let control = StorageReadControl::new(table.rows.memory.budget(), cancellation);
424        Ok(table
425            .rows
426            .get(id, &control)
427            .map_err(storage_error)?
428            .is_some_and(|row| row.map_or(deleted_supersedes, |row| row.published)))
429    }
430
431    /// The visible rows `overlays` staged for `table` whose `fields` hold `values`, the newest command's first; a missing field holds null.
432    pub fn matches(
433        overlays: &mut [Self],
434        table: &str,
435        fields: &[String],
436        values: &[Value],
437        control: &StorageReadControl,
438    ) -> Result<BudgetedVec<DocId>, SQLError> {
439        Self::matches_with_catalog(overlays, table, fields, values, control, None)
440    }
441
442    pub fn matches_with_catalog(
443        overlays: &mut [Self],
444        table: &str,
445        fields: &[String],
446        values: &[Value],
447        control: &StorageReadControl,
448        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
449    ) -> Result<BudgetedVec<DocId>, SQLError> {
450        Self::matches_keys(
451            overlays,
452            table,
453            fields,
454            values,
455            KeyKind::Columns,
456            control,
457            catalog,
458        )
459    }
460
461    fn matches_keys(
462        overlays: &mut [Self],
463        table: &str,
464        fields: &[String],
465        values: &[Value],
466        kind: KeyKind,
467        control: &StorageReadControl,
468        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
469    ) -> Result<BudgetedVec<DocId>, SQLError> {
470        let mut found = BudgetedVec::new(control.memory());
471        matching::visit_matches(
472            overlays,
473            table,
474            matching::MatchKeys {
475                fields,
476                values,
477                kind,
478            },
479            control,
480            catalog,
481            &mut |id| found.push(id).map_err(resource_error),
482        )?;
483        Ok(found)
484    }
485
486    pub fn visit_matches_with_catalog(
487        overlays: &mut [Self],
488        table: &str,
489        fields: &[String],
490        values: &[Value],
491        control: &StorageReadControl,
492        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
493        visit: &mut dyn FnMut(DocId) -> Result<(), SQLError>,
494    ) -> Result<(), SQLError> {
495        matching::visit_matches(
496            overlays,
497            table,
498            matching::MatchKeys {
499                fields,
500                values,
501                kind: KeyKind::Columns,
502            },
503            control,
504            catalog,
505            visit,
506        )
507    }
508}
509
510/// Whether `document` holds every field of `fields`.
511fn holds_fields(document: &CommandStoredDocument, fields: &FieldSet) -> bool {
512    fields
513        .values()
514        .iter()
515        .all(|field| document.fields.contains_key(field))
516}
517
518mod table;
519
520fn resource_error(error: impl std::error::Error + Send + Sync + 'static) -> SQLError {
521    crate::storage_errors::storage_error(
522        "retain command overlay",
523        &uqa_storage::StorageBackendError::backend("command overlay", error),
524    )
525}
526
527fn storage_error(error: uqa_storage::StorageBackendError) -> SQLError {
528    crate::storage_errors::storage_error("retain command overlay", &error)
529}
530
531#[cfg(test)]
532mod tests;