Skip to main content

uqa_execution/query/document_changes/
identities.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! The rows a transaction changed, indexed by relation generation and identity, for reads at a fixed snapshot. Each entry records whether its row is present now and whether it was present before the transaction first changed it, so that a read knows its visible rows and its row count without reading the rows. The entries are private records that spill to encrypted temporary files as a transaction's own changes do, and savepoints restore them without copying.
8
9use std::collections::BTreeMap;
10use std::sync::Arc;
11
12use uqa_core::{memory::BudgetedVec, DocId};
13use uqa_storage::mvcc::{PrivateRecordChanges, PrivateRecordSnapshot, RecordWrite, VersionError};
14use uqa_storage::read_control::StorageReadControl;
15use uqa_storage::{StorageBackendError, StorageBackendResult, StorageSavepointId};
16
17/// The storage generation of a relation.
18pub type RelationGeneration = [u8; 16];
19
20const KEY_BYTES: usize = 16 + size_of::<u64>();
21/// The entries a page of a scan keeps.
22const PAGE_ENTRIES: usize = 1024;
23
24/// The changed rows of one relation generation, counted.
25#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
26pub struct ChangedRowCounts {
27    /// The rows the transaction changed.
28    pub changed: u64,
29    /// The changed rows that were present before the transaction first changed them.
30    pub before: u64,
31    /// The changed rows that are present now.
32    pub present: u64,
33}
34
35impl ChangedRowCounts {
36    /// The rows a read of the relation sees, given the rows its snapshot holds.
37    pub fn visible_rows(self, snapshot_rows: u64) -> Option<u64> {
38        snapshot_rows
39            .checked_sub(self.before)?
40            .checked_add(self.present)
41    }
42}
43
44fn key(generation: &RelationGeneration, id: DocId) -> [u8; KEY_BYTES] {
45    let mut key = [0; KEY_BYTES];
46    key[..16].copy_from_slice(generation);
47    key[16..].copy_from_slice(&id.to_be_bytes());
48    key
49}
50
51fn invalid(message: &str) -> StorageBackendError {
52    StorageBackendError::Other(message.into())
53}
54
55/// The presence an entry records: now, and before the transaction first changed the row.
56fn decode_entry(value: Option<&[u8]>) -> StorageBackendResult<(bool, bool)> {
57    match value {
58        Some([present, before]) => Ok((*present == 1, *before == 1)),
59        _ => Err(invalid("a changed row entry is malformed")),
60    }
61}
62
63/// The rows a transaction changed, which reads at a fixed snapshot take as views.
64pub struct ChangedIdentities {
65    records: PrivateRecordChanges,
66    counts: BTreeMap<RelationGeneration, ChangedRowCounts>,
67    /// The counts at each savepoint, innermost last.
68    savepoints: Vec<(
69        StorageSavepointId,
70        BTreeMap<RelationGeneration, ChangedRowCounts>,
71    )>,
72    view: Arc<PrivateRecordSnapshot>,
73    current: bool,
74}
75
76impl ChangedIdentities {
77    pub fn new(control: &StorageReadControl) -> StorageBackendResult<Self> {
78        let records = PrivateRecordChanges::new(control.memory());
79        let view = Arc::new(
80            records
81                .snapshot()
82                .map_err(VersionError::into_storage_error)?,
83        );
84        Ok(Self {
85            records,
86            counts: BTreeMap::new(),
87            savepoints: Vec::new(),
88            view,
89            current: true,
90        })
91    }
92
93    /// Record that the row `id` of relation generation `generation` is present now or not. `before` is whether the row was present before this change, which only a first change of the row records.
94    pub fn note(
95        &mut self,
96        generation: &RelationGeneration,
97        id: DocId,
98        before: bool,
99        present: bool,
100        control: &StorageReadControl,
101    ) -> StorageBackendResult<()> {
102        let key = key(generation, id);
103        let previous = self
104            .records
105            .get(&key, control)
106            .map_err(VersionError::into_storage_error)?
107            .map(|write| decode_entry(write.value()))
108            .transpose()?;
109        let before = previous.map_or(before, |(_, before)| before);
110        let value = [u8::from(present), u8::from(before)];
111        self.records
112            .apply(
113                &[RecordWrite {
114                    key: &key,
115                    expected: None,
116                    value: Some(&value),
117                }],
118                control,
119            )
120            .map_err(VersionError::into_storage_error)?;
121        self.current = false;
122        let counts = self.counts.entry(*generation).or_default();
123        match previous {
124            None => {
125                counts.changed += 1;
126                counts.before += u64::from(before);
127                counts.present += u64::from(present);
128            }
129            Some((was_present, _)) => {
130                counts.present = counts.present + u64::from(present) - u64::from(was_present);
131            }
132        }
133        Ok(())
134    }
135
136    /// The view of the records written so far, refreshed after writes.
137    fn snapshot(&mut self) -> StorageBackendResult<&Arc<PrivateRecordSnapshot>> {
138        if !self.current {
139            self.view = Arc::new(
140                self.records
141                    .snapshot()
142                    .map_err(VersionError::into_storage_error)?,
143            );
144            self.current = true;
145        }
146        Ok(&self.view)
147    }
148
149    pub fn savepoint(&mut self, id: StorageSavepointId) -> StorageBackendResult<()> {
150        self.records
151            .savepoint(id)
152            .map_err(VersionError::into_storage_error)?;
153        self.savepoints.push((id, self.counts.clone()));
154        Ok(())
155    }
156
157    /// Release the savepoint `id` and those after it, keeping every change. Returns false when this index does not hold the savepoint.
158    pub fn release(&mut self, id: StorageSavepointId) -> StorageBackendResult<bool> {
159        let Some(position) = self.savepoints.iter().rposition(|(saved, _)| *saved == id) else {
160            return Ok(false);
161        };
162        self.records
163            .release_savepoint(id)
164            .map_err(VersionError::into_storage_error)?;
165        self.savepoints.truncate(position);
166        Ok(true)
167    }
168
169    /// Return to the savepoint `id`, keeping it for another rollback. Returns false when this index does not hold the savepoint.
170    pub fn rollback_to(&mut self, id: StorageSavepointId) -> StorageBackendResult<bool> {
171        let Some(position) = self.savepoints.iter().rposition(|(saved, _)| *saved == id) else {
172            return Ok(false);
173        };
174        self.records
175            .rollback_to_savepoint(id)
176            .map_err(VersionError::into_storage_error)?;
177        self.counts.clone_from(&self.savepoints[position].1);
178        self.savepoints.truncate(position + 1);
179        self.current = false;
180        Ok(true)
181    }
182
183    /// The counted changes of relation generation `generation`.
184    pub fn counts(&self, generation: &RelationGeneration) -> ChangedRowCounts {
185        self.counts.get(generation).copied().unwrap_or_default()
186    }
187
188    /// An immutable view of the changes of relation generation `generation`, which later changes do not alter; `None` when the transaction changed no row of it.
189    pub fn view(
190        &mut self,
191        generation: &RelationGeneration,
192    ) -> StorageBackendResult<Option<ChangedIdentitiesView>> {
193        let counts = self.counts(generation);
194        if counts.changed == 0 {
195            return Ok(None);
196        }
197        Ok(Some(ChangedIdentitiesView {
198            snapshot: Arc::clone(self.snapshot()?),
199            generation: *generation,
200            counts,
201        }))
202    }
203}
204
205/// An immutable view of the rows a transaction changed in one relation generation.
206#[derive(Clone)]
207pub struct ChangedIdentitiesView {
208    snapshot: Arc<PrivateRecordSnapshot>,
209    generation: RelationGeneration,
210    counts: ChangedRowCounts,
211}
212
213impl ChangedIdentitiesView {
214    pub(super) fn read_scope(
215        &self,
216        control: &StorageReadControl,
217    ) -> StorageBackendResult<uqa_storage::mvcc::PrivateRecordReadScope> {
218        self.snapshot
219            .read_scope(control)
220            .map_err(VersionError::into_storage_error)
221    }
222
223    pub fn counts(&self) -> ChangedRowCounts {
224        self.counts
225    }
226
227    /// Whether the transaction changed the row `id`, and whether it is present now.
228    pub(crate) fn presence(
229        &self,
230        id: DocId,
231        control: &StorageReadControl,
232    ) -> StorageBackendResult<Option<bool>> {
233        self.snapshot
234            .get(&key(&self.generation, id), control)
235            .map_err(VersionError::into_storage_error)?
236            .map(|write| decode_entry(write.value()).map(|(present, _)| present))
237            .transpose()
238    }
239
240    /// The changed rows after identity `after`, in identity order.
241    pub(crate) fn cursor(&self, after: Option<DocId>) -> IdentityCursor {
242        IdentityCursor {
243            view: self.clone(),
244            page: None,
245            position: 0,
246            resume: after,
247            done: false,
248        }
249    }
250
251    /// A page of the changed rows after `after`, and whether rows may follow it.
252    fn page(
253        &self,
254        after: Option<DocId>,
255        control: &StorageReadControl,
256    ) -> StorageBackendResult<(BudgetedVec<(DocId, bool)>, bool)> {
257        let after = after.map(|id| key(&self.generation, id));
258        let mut rows = BudgetedVec::new(control.memory());
259        let mut full = false;
260        self.snapshot
261            .visit(
262                &self.generation,
263                after.as_ref().map(<[u8; KEY_BYTES]>::as_slice),
264                control,
265                &mut |write| {
266                    let id = write.key()[16..]
267                        .try_into()
268                        .map(DocId::from_be_bytes)
269                        .map_err(|_| {
270                            VersionError::from(invalid("a changed row key is malformed"))
271                        })?;
272                    let (present, _) = decode_entry(write.value()).map_err(VersionError::from)?;
273                    rows.push((id, present))?;
274                    full = rows.len() == PAGE_ENTRIES;
275                    Ok(!full)
276                },
277            )
278            .map_err(VersionError::into_storage_error)?;
279        Ok((rows, full))
280    }
281}
282
283/// The changed rows of a view in identity order, each with whether it is present now. The cursor owns its view.
284pub(crate) struct IdentityCursor {
285    view: ChangedIdentitiesView,
286    page: Option<BudgetedVec<(DocId, bool)>>,
287    position: usize,
288    resume: Option<DocId>,
289    done: bool,
290}
291
292impl IdentityCursor {
293    pub(crate) fn next(
294        &mut self,
295        control: &StorageReadControl,
296    ) -> StorageBackendResult<Option<(DocId, bool)>> {
297        loop {
298            control.check()?;
299            if let Some(entry) = self.page.as_ref().and_then(|page| page.get(self.position)) {
300                self.position += 1;
301                self.resume = Some(entry.0);
302                return Ok(Some(*entry));
303            }
304            if self.done {
305                return Ok(None);
306            }
307            self.page = None;
308            let (page, full) = self.view.page(self.resume, control)?;
309            self.done = !full;
310            self.page = Some(page);
311            self.position = 0;
312        }
313    }
314}
315
316#[cfg(test)]
317mod tests;