uqa_execution/query/
indexed_filter.rs1use 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
16pub trait QueryIndexRead: Sync {
18 fn value_index_scan(
20 &self,
21 table: &str,
22 field: &str,
23 predicate: &Predicate,
24 ) -> Result<Option<PostingList>, SQLError>;
25 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 fn exact_command_matches(
36 &self,
37 table: &str,
38 field: &str,
39 value: &Value,
40 ) -> Result<CommandIndexProbe, SQLError>;
41 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 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;