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;
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 index_values: Option<RetainedDocumentFields>,
41 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#[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: BudgetedMap<FieldSet, CommandExactIndex>,
77 expression_indexes: BudgetedMap<FieldSet, CommandExactIndex>,
78 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 pub fn holds(&self, table: &str) -> bool {
91 self.table(table)
92 .is_some_and(|table| !table.rows.is_empty())
93 }
94
95 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 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 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 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 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 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 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 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 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 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 });
368 }
369 self.has_publication = checkpoint.has_publication;
370 }
371
372 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 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 pub fn published_rows(self) -> Option<Self> {
409 self.has_publication.then_some(self)
410 }
411
412 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 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
510fn 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;