uqa_execution/query/document_changes/
identities.rs1use 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
17pub type RelationGeneration = [u8; 16];
19
20const KEY_BYTES: usize = 16 + size_of::<u64>();
21const PAGE_ENTRIES: usize = 1024;
23
24#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
26pub struct ChangedRowCounts {
27 pub changed: u64,
29 pub before: u64,
31 pub present: u64,
33}
34
35impl ChangedRowCounts {
36 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
55fn 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
63pub struct ChangedIdentities {
65 records: PrivateRecordChanges,
66 counts: BTreeMap<RelationGeneration, ChangedRowCounts>,
67 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 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 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 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 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 pub fn counts(&self, generation: &RelationGeneration) -> ChangedRowCounts {
185 self.counts.get(generation).copied().unwrap_or_default()
186 }
187
188 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#[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 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 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 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
283pub(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;