Skip to main content

uqa_execution/query/
indexed_filter.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Reconcile selected storage indexes with cached command keys and retained private versions.
8
9use super::document_changes::DocumentChanges;
10use crate::mutation::overlay::CommandIndexProbe;
11use crate::storage_errors::storage_error;
12use uqa_core::{CancellationToken, Payload, PostingEntry, PostingList, Predicate, Value};
13use uqa_sql::SQLError;
14use uqa_storage::DocumentStore;
15
16/// All inputs refer to the query's selected relation generation and original read allowance.
17pub trait QueryIndexRead: Sync {
18    /// Probe stored values and record the original serializable predicate observation.
19    fn value_index_scan(
20        &self,
21        table: &str,
22        field: &str,
23        predicate: &Predicate,
24    ) -> Result<Option<PostingList>, SQLError>;
25    /// Visit support without collecting a posting list, retaining the same selected snapshot and predicate observation. False means unsupported and must not follow any callback.
26    fn visit_value_index(
27        &self,
28        table: &str,
29        field: &str,
30        predicate: &Predicate,
31        visit: &mut dyn FnMut(uqa_core::DocId) -> Result<(), SQLError>,
32    ) -> Result<bool, SQLError>;
33    fn command_overlay_changes(&self, table: &str) -> Result<Option<DocumentChanges>, SQLError>;
34    /// Capture command-only masks together with cached matches from the same frame stack.
35    fn exact_command_matches(
36        &self,
37        table: &str,
38        field: &str,
39        value: &Value,
40    ) -> Result<CommandIndexProbe, SQLError>;
41    /// Capture every cached command match before returning its exact frame mask. The callback captures identities and must not reenter the engine.
42    fn visit_exact_command_matches(
43        &self,
44        table: &str,
45        field: &str,
46        value: &Value,
47        visit: &mut dyn FnMut(uqa_core::DocId) -> Result<(), SQLError>,
48    ) -> Result<DocumentChanges, SQLError>;
49}
50
51pub fn scan(
52    reads: &dyn QueryIndexRead,
53    table: &str,
54    field: &str,
55    predicate: &Predicate,
56    cancellation: &CancellationToken,
57) -> Result<Option<PostingList>, SQLError> {
58    let Some(indexed) = reads.value_index_scan(table, field, predicate)? else {
59        return Ok(None);
60    };
61    let changes = reads.command_overlay_changes(table)?;
62    if changes.as_ref().is_some_and(DocumentChanges::has_changes) {
63        if let Predicate::Equals(value) = predicate {
64            if crate::catalog::index::value::field_is_index_safe(value) {
65                if matches!(value, Value::Null) {
66                    return Ok(Some(PostingList::from_sorted_unchecked(Vec::new())));
67                }
68                let command = reads.exact_command_matches(table, field, value)?;
69                return merge_exact(
70                    indexed,
71                    &changes.expect("changed rows").without_staged(),
72                    command,
73                    field,
74                    predicate,
75                    cancellation,
76                )
77                .map(Some);
78            }
79        }
80    }
81    merge_changes(indexed, changes, field, predicate, cancellation).map(Some)
82}
83
84fn merge_exact(
85    indexed: PostingList,
86    fixed: &DocumentChanges,
87    command: CommandIndexProbe,
88    field: &str,
89    predicate: &Predicate,
90    cancellation: &CancellationToken,
91) -> Result<PostingList, SQLError> {
92    let error = |error| storage_error("read indexed query changes", &error);
93    let mut entries = Vec::with_capacity(indexed.len());
94    for entry in indexed.entries() {
95        cancellation.check()?;
96        if !command
97            .changes
98            .contains_change(entry.doc_id)
99            .map_err(error)?
100            && !fixed.contains_change(entry.doc_id).map_err(error)?
101        {
102            entries.push(entry.clone());
103        }
104    }
105    // Fixed portal/transaction versions retain their original source. Command keys above them are never obtained by traversing these changes.
106    for change in fixed.changes() {
107        cancellation.check()?;
108        let (id, present) = change.map_err(error)?;
109        if present
110            && !command.changes.contains_change(id).map_err(error)?
111            && predicate.evaluate(fixed.get_field(id, field).map_err(error)?.as_ref())
112        {
113            entries.push(PostingEntry::new(id, Payload::default()));
114        }
115    }
116    for &id in command.matches.iter() {
117        cancellation.check()?;
118        entries.push(PostingEntry::new(id, Payload::default()));
119    }
120    entries.sort_unstable_by_key(|entry| entry.doc_id);
121    Ok(PostingList::from_sorted_unchecked(entries))
122}
123
124fn merge_changes(
125    indexed: PostingList,
126    changes: Option<DocumentChanges>,
127    field: &str,
128    predicate: &Predicate,
129    cancellation: &CancellationToken,
130) -> Result<PostingList, SQLError> {
131    let Some(changes) = changes.filter(DocumentChanges::has_changes) else {
132        return Ok(indexed);
133    };
134    let error = |error| storage_error("read indexed command changes", &error);
135    let mut candidates = indexed.entries().iter().peekable();
136    let mut entries = Vec::with_capacity(indexed.len());
137    for change in changes.changes() {
138        cancellation.check()?;
139        let (id, present) = change.map_err(error)?;
140        while candidates.peek().is_some_and(|entry| entry.doc_id < id) {
141            entries.push(candidates.next().expect("a peeked candidate").clone());
142        }
143        if candidates.peek().is_some_and(|entry| entry.doc_id == id) {
144            candidates.next();
145        }
146        if present && predicate.evaluate(changes.get_field(id, field).map_err(error)?.as_ref()) {
147            entries.push(PostingEntry::new(id, Payload::default()));
148        }
149    }
150    entries.extend(candidates.cloned());
151    Ok(PostingList::from_sorted_unchecked(entries))
152}
153
154#[cfg(test)]
155mod tests;