Skip to main content

uqa_execution/query/
exact_lookup.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Exact-key probes over the caller's selected document, index and private row views.
8
9use super::table_read::TableRead;
10use crate::{serializable::SerializableRelationRead, storage_errors::storage_error};
11use std::collections::BTreeMap;
12use uqa_core::{DocId, PostingList, Predicate, Value};
13use uqa_sql::{ast::ColumnDef, expr::SQLValueCatalog, SQLError};
14use uqa_storage::{document_store::Document, DocumentStore, StoredDocument};
15
16#[derive(Clone, Copy)]
17pub enum FieldPresence {
18    Required,
19    MissingIsNull,
20}
21
22/// Command adapters may retain cached exact keys; snapshot overlays expose their selected rows.
23pub trait ExactLookupOverlay {
24    fn is_empty(&self) -> Result<bool, SQLError>;
25    fn masks(&self, doc_id: DocId) -> Result<bool, SQLError>;
26    fn find_match(
27        &self,
28        columns: &[String],
29        values: &[Value],
30        presence: FieldPresence,
31    ) -> Result<Option<DocId>, SQLError>;
32    fn find_match_with_catalog(
33        &self,
34        columns: &[String],
35        values: &[Value],
36        presence: FieldPresence,
37        _catalog: Option<&dyn SQLValueCatalog>,
38    ) -> Result<Option<DocId>, SQLError> {
39        self.find_match(columns, values, presence)
40    }
41}
42
43pub fn matches_fields(
44    document: &Document,
45    columns: &[String],
46    values: &[Value],
47    presence: FieldPresence,
48) -> Result<bool, SQLError> {
49    matches_fields_with_control(
50        document,
51        columns,
52        values,
53        presence,
54        &uqa_core::memory::ProductionControl::uncontrolled(),
55        None,
56    )
57}
58
59pub(crate) fn matches_fields_with_control(
60    document: &Document,
61    columns: &[String],
62    values: &[Value],
63    presence: FieldPresence,
64    control: &uqa_core::memory::ProductionControl<'_>,
65    catalog: Option<&dyn SQLValueCatalog>,
66) -> Result<bool, SQLError> {
67    for (column, expected) in columns.iter().zip(values) {
68        let actual = document.get(column);
69        if matches!(presence, FieldPresence::Required) && actual.is_none() {
70            return Ok(false);
71        }
72        if !uqa_sql::expr::equal_typed_values_with_enum_catalog(
73            actual.unwrap_or(&Value::Null),
74            expected,
75            control,
76            catalog,
77        )? {
78            return Ok(false);
79        }
80    }
81    Ok(true)
82}
83
84fn matches_value(
85    actual: Option<&Value>,
86    expected: &Value,
87    presence: FieldPresence,
88    catalog: Option<&dyn SQLValueCatalog>,
89) -> Result<bool, SQLError> {
90    if matches!(presence, FieldPresence::Required) && actual.is_none() {
91        return Ok(false);
92    }
93    uqa_sql::expr::equal_typed_values_with_enum_catalog(
94        actual.unwrap_or(&Value::Null),
95        expected,
96        &uqa_core::memory::ProductionControl::uncontrolled(),
97        catalog,
98    )
99}
100
101impl ExactLookupOverlay for BTreeMap<DocId, Option<StoredDocument>> {
102    fn is_empty(&self) -> Result<bool, SQLError> {
103        Ok(self.is_empty())
104    }
105    fn masks(&self, doc_id: DocId) -> Result<bool, SQLError> {
106        Ok(self.contains_key(&doc_id))
107    }
108    fn find_match(
109        &self,
110        columns: &[String],
111        values: &[Value],
112        presence: FieldPresence,
113    ) -> Result<Option<DocId>, SQLError> {
114        self.find_match_with_catalog(columns, values, presence, None)
115    }
116    fn find_match_with_catalog(
117        &self,
118        columns: &[String],
119        values: &[Value],
120        presence: FieldPresence,
121        catalog: Option<&dyn SQLValueCatalog>,
122    ) -> Result<Option<DocId>, SQLError> {
123        for (id, document) in self {
124            if let Some(document) = document {
125                if matches_fields_with_control(
126                    document.fields(),
127                    columns,
128                    values,
129                    presence,
130                    &uqa_core::memory::ProductionControl::uncontrolled(),
131                    catalog,
132                )? {
133                    return Ok(Some(*id));
134                }
135            }
136        }
137        Ok(None)
138    }
139}
140
141impl super::document_changes::DocumentChanges {
142    /// Whether the changed row of `id` holds `values` in `columns`.
143    pub fn row_matches(
144        &self,
145        id: DocId,
146        columns: &[String],
147        values: &[Value],
148        presence: FieldPresence,
149    ) -> Result<bool, SQLError> {
150        self.row_matches_with_catalog(id, columns, values, presence, None)
151    }
152
153    pub fn row_matches_with_catalog(
154        &self,
155        id: DocId,
156        columns: &[String],
157        values: &[Value],
158        presence: FieldPresence,
159        catalog: Option<&dyn SQLValueCatalog>,
160    ) -> Result<bool, SQLError> {
161        for (column, expected) in columns.iter().zip(values) {
162            let actual = self
163                .get_field(id, column)
164                .map_err(|error| storage_error("read private exact key", &error))?;
165            if !matches_value(actual.as_ref(), expected, presence, catalog)? {
166                return Ok(false);
167            }
168        }
169        Ok(true)
170    }
171}
172
173impl ExactLookupOverlay for super::document_changes::DocumentChanges {
174    fn is_empty(&self) -> Result<bool, SQLError> {
175        Ok(!self.has_changes())
176    }
177
178    fn masks(&self, id: DocId) -> Result<bool, SQLError> {
179        self.contains_change(id)
180            .map_err(|error| storage_error("read private exact key", &error))
181    }
182
183    fn find_match(
184        &self,
185        columns: &[String],
186        values: &[Value],
187        presence: FieldPresence,
188    ) -> Result<Option<DocId>, SQLError> {
189        self.find_match_with_catalog(columns, values, presence, None)
190    }
191    fn find_match_with_catalog(
192        &self,
193        columns: &[String],
194        values: &[Value],
195        presence: FieldPresence,
196        catalog: Option<&dyn SQLValueCatalog>,
197    ) -> Result<Option<DocId>, SQLError> {
198        for change in self.changes() {
199            let (id, present) =
200                change.map_err(|error| storage_error("read private exact key", &error))?;
201            if present && self.row_matches_with_catalog(id, columns, values, presence, catalog)? {
202                return Ok(Some(id));
203            }
204        }
205        Ok(None)
206    }
207}
208
209#[derive(Clone, Copy, Debug, PartialEq, Eq)]
210enum IndexConflictProbe {
211    Unanswerable,
212    NoConflict,
213    Conflict(DocId),
214}
215
216/// The identity a key value names in a table that maps its single integer primary key, which holds the key's row or no row at all. `None` leaves the key to its index: a value that names no identity, or a table that does not map its keys.
217fn primary_key_doc_id(
218    maps_keys: bool,
219    columns: &[ColumnDef],
220    column: &str,
221    value: &Value,
222) -> Option<DocId> {
223    if !maps_keys
224        || !columns.iter().any(|candidate| {
225            candidate.name == column && candidate.primary_key && candidate.ty.is_integer()
226        })
227    {
228        return None;
229    }
230    uqa_sql::semantics::key_identity::key_document_id(value)
231}
232
233pub struct ExactLookup<'a> {
234    pub catalog: Option<&'a dyn SQLValueCatalog>,
235    pub table: &'a dyn TableRead,
236    pub overlay: &'a dyn ExactLookupOverlay,
237    pub read: Option<&'a SerializableRelationRead>,
238}
239
240impl ExactLookup<'_> {
241    /// A field lookup preserves the document-store distinction between absent and explicitly NULL fields.
242    pub fn find_field(&self, field: &str, value: &Value) -> Result<Option<DocId>, SQLError> {
243        self.find_field_with_index(field, value, |_, _| Ok(None))
244    }
245
246    /// The index reader must return exact candidates without evaluating stored
247    /// values, or decline the probe. Private rows mask stored identities before
248    /// field reads or comparisons. Field probes retain their relation observation.
249    pub fn find_field_with_index(
250        &self,
251        field: &str,
252        value: &Value,
253        scan: impl FnOnce(&str, &Value) -> Result<Option<PostingList>, SQLError>,
254    ) -> Result<Option<DocId>, SQLError> {
255        if let Some(read) = self.read {
256            read.observe_scan()?;
257        }
258        let columns = [field.to_string()];
259        let values = std::slice::from_ref(value);
260        if let Some(id) = self.overlay.find_match_with_catalog(
261            &columns,
262            values,
263            FieldPresence::Required,
264            self.catalog,
265        )? {
266            return Ok(Some(id));
267        }
268        if self.overlay.is_empty()?
269            || !crate::catalog::index::value::field_is_index_safe(value)
270            || self.comparison_can_fail(&columns, values)
271        {
272            return self.scan_documents(&columns, values, FieldPresence::Required);
273        }
274        // Hydration may acquire the document guard, so select candidates first.
275        let Some(candidates) = scan(field, value)? else {
276            return self.scan_documents(&columns, values, FieldPresence::Required);
277        };
278        let documents = matches!(value, Value::Null).then(|| self.table.read_documents());
279        for entry in candidates.entries() {
280            if self.overlay.masks(entry.doc_id)? {
281                continue;
282            }
283            if let Some(documents) = &documents {
284                let actual = documents
285                    .get_field(entry.doc_id, field)
286                    .map_err(|error| storage_error("verify matching field", &error))?;
287                if actual != Some(Value::Null) {
288                    continue;
289                }
290            }
291            return Ok(Some(entry.doc_id));
292        }
293        Ok(None)
294    }
295
296    pub fn find_conflict(
297        &self,
298        schema_columns: &[ColumnDef],
299        columns: &[String],
300        values: &[Value],
301        scan: impl FnMut(&str, &Predicate) -> Result<Option<PostingList>, SQLError>,
302    ) -> Result<Option<DocId>, SQLError> {
303        if columns.is_empty() || columns.len() != values.len() {
304            return Ok(None);
305        }
306        if columns.len() == 1 {
307            if let Some(id) = primary_key_doc_id(
308                self.table.maps_integer_keys(),
309                schema_columns,
310                &columns[0],
311                &values[0],
312            ) {
313                if let Some(read) = self.read {
314                    read.observe_row(id)?;
315                }
316                if let Some(id) = self.overlay.find_match_with_catalog(
317                    columns,
318                    values,
319                    FieldPresence::MissingIsNull,
320                    self.catalog,
321                )? {
322                    return Ok(Some(id));
323                }
324                if self.overlay.masks(id)? {
325                    return Ok(None);
326                }
327                return self
328                    .table
329                    .read_documents()
330                    .contains_doc_id(id)
331                    .map(|exists| exists.then_some(id))
332                    .map_err(|error| storage_error("check conflicting document", &error));
333            }
334        }
335        match self.indexed_conflict(columns, values, scan)? {
336            IndexConflictProbe::Conflict(id) => Ok(Some(id)),
337            IndexConflictProbe::NoConflict => Ok(None),
338            IndexConflictProbe::Unanswerable => {
339                self.scan(columns, values, FieldPresence::MissingIsNull)
340            }
341        }
342    }
343
344    /// The first answerable index is authoritative, including an empty result. The supplied index reader records its precise predicate before returning candidates.
345    fn indexed_conflict(
346        &self,
347        columns: &[String],
348        values: &[Value],
349        mut scan: impl FnMut(&str, &Predicate) -> Result<Option<PostingList>, SQLError>,
350    ) -> Result<IndexConflictProbe, SQLError> {
351        for (pivot, (column, value)) in columns.iter().zip(values).enumerate() {
352            let predicate = if matches!(value, Value::Null) {
353                Predicate::IsNull
354            } else {
355                Predicate::Equals(value.clone())
356            };
357            let Some(candidates) = scan(column, &predicate)? else {
358                continue;
359            };
360            if let Some(id) = self.overlay.find_match_with_catalog(
361                columns,
362                values,
363                FieldPresence::MissingIsNull,
364                self.catalog,
365            )? {
366                return Ok(IndexConflictProbe::Conflict(id));
367            }
368            let documents = self.table.read_documents();
369            for entry in candidates.entries() {
370                if self.overlay.masks(entry.doc_id)? {
371                    continue;
372                }
373                if columns.len() > 1 {
374                    if let Some(read) = self.read {
375                        read.observe_row(entry.doc_id)?;
376                    }
377                }
378                let mut matches = true;
379                for (index, (column, expected)) in columns.iter().zip(values).enumerate() {
380                    if index == pivot {
381                        continue;
382                    }
383                    let actual = documents
384                        .get_field(entry.doc_id, column)
385                        .map_err(|error| storage_error("verify conflicting document", &error))?;
386                    if !matches_value(
387                        actual.as_ref(),
388                        expected,
389                        FieldPresence::MissingIsNull,
390                        self.catalog,
391                    )? {
392                        matches = false;
393                        break;
394                    }
395                }
396                if matches {
397                    return Ok(IndexConflictProbe::Conflict(entry.doc_id));
398                }
399            }
400            return Ok(IndexConflictProbe::NoConflict);
401        }
402        Ok(IndexConflictProbe::Unanswerable)
403    }
404
405    fn scan(
406        &self,
407        columns: &[String],
408        values: &[Value],
409        presence: FieldPresence,
410    ) -> Result<Option<DocId>, SQLError> {
411        if let Some(read) = self.read {
412            read.observe_scan()?;
413        }
414        if let Some(id) =
415            self.overlay
416                .find_match_with_catalog(columns, values, presence, self.catalog)?
417        {
418            return Ok(Some(id));
419        }
420        self.scan_documents(columns, values, presence)
421    }
422
423    fn scan_documents(
424        &self,
425        columns: &[String],
426        values: &[Value],
427        presence: FieldPresence,
428    ) -> Result<Option<DocId>, SQLError> {
429        let documents = self.table.read_documents();
430        if self.overlay.is_empty()? && !self.comparison_can_fail(columns, values) {
431            return match presence {
432                FieldPresence::Required => documents.find_doc_id_by_field(&columns[0], &values[0]),
433                FieldPresence::MissingIsNull => documents.find_doc_id_by_fields(columns, values),
434            }
435            .map_err(|error| storage_error("find matching document", &error));
436        }
437        let mut after = None;
438        loop {
439            let ids = documents
440                .next_doc_ids(after, crate::DEFAULT_BATCH_SIZE)
441                .map_err(|error| storage_error("scan command-visible document fields", &error))?;
442            let Some(last) = ids.last().copied() else {
443                return Ok(None);
444            };
445            after = Some(last);
446            for id in ids {
447                if self.overlay.masks(id)? {
448                    continue;
449                }
450                let mut matches = true;
451                for (column, expected) in columns.iter().zip(values) {
452                    let actual = documents.get_field(id, column).map_err(|error| {
453                        storage_error("read command-visible document field", &error)
454                    })?;
455                    if !matches_value(actual.as_ref(), expected, presence, self.catalog)? {
456                        matches = false;
457                        break;
458                    }
459                }
460                if matches {
461                    return Ok(Some(id));
462                }
463            }
464        }
465    }
466
467    fn comparison_can_fail(&self, columns: &[String], values: &[Value]) -> bool {
468        values.iter().any(uqa_sql::expr::value_comparison_can_fail)
469            || self.table.column_definitions().iter().any(|column| {
470                columns.contains(&column.name)
471                    && uqa_sql::expr::type_comparison_can_fail(&column.ty)
472            })
473    }
474}
475
476#[cfg(test)]
477mod tests;