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