1use 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 index_values: Option<RetainedDocumentFields>,
40 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#[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: BudgetedMap<FieldSet, CommandExactIndex>,
76 expression_indexes: BudgetedMap<FieldSet, CommandExactIndex>,
77 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 pub fn holds(&self, table: &str) -> bool {
90 self.table(table)
91 .is_some_and(|table| !table.rows.is_empty())
92 }
93
94 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 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 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 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 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 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 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 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 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 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 });
367 }
368 self.has_publication = checkpoint.has_publication;
369 }
370
371 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 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 pub fn published_rows(self) -> Option<Self> {
408 self.has_publication.then_some(self)
409 }
410
411 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 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
540fn 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;