Skip to main content

uqa_execution/catalog/index/value/
cache.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Bounded evaluated-key retention preserves the existing SQL eligibility policy.
8
9use super::{comparison, ColumnValueIndex};
10use std::borrow::Cow;
11use uqa_core::{DocId, Predicate, Value};
12use uqa_sql::SQLError;
13use uqa_storage::{
14    btree_index::retained::RetainedValueIndex, read_control::StorageReadControl,
15    StorageBackendError,
16};
17
18mod builder;
19mod probes;
20mod projection;
21mod publication;
22pub use builder::ValueIndexBuilder;
23pub use projection::visit_stored_fields;
24pub use publication::apply_cached_values;
25
26#[derive(Clone)]
27pub struct ValueIndexCache {
28    // With retained storage this holds eligibility flags and no row population.
29    policy: ColumnValueIndex,
30    retained: Option<RetainedValueIndex>,
31    field: String,
32    limit: usize,
33    resident_bytes: usize,
34}
35
36fn storage(error: StorageBackendError) -> SQLError {
37    crate::storage_errors::storage_error("retained value index", &error)
38}
39
40fn value_bytes(value: &Value, control: &StorageReadControl) -> Result<usize, SQLError> {
41    let payload = value
42        .retained_payload_bytes(control.memory(), control.cancellation())
43        .map_err(|error| storage(StorageBackendError::backend("retained key", error)))?;
44    // Both the identity map and the search tree may own the value. The allowance also covers their nodes, NULL identities and key headers.
45    payload
46        .checked_add(std::mem::size_of::<Value>())
47        .and_then(|bytes| bytes.checked_mul(2))
48        .and_then(|bytes| bytes.checked_add(128))
49        .ok_or_else(|| storage(uqa_core::memory::MemoryError::SizeOverflow.into()))
50}
51
52fn observe(policy: &mut ColumnValueIndex, value: &Value) {
53    policy.has_temporal |= super::value_is_temporal(value);
54    policy.has_row_values |= super::value_is_row(value);
55    policy.comparison.include(value);
56}
57
58impl ValueIndexCache {
59    pub fn is_carried(&self) -> bool {
60        self.policy.is_carried()
61    }
62
63    pub fn is_spilled(&self) -> bool {
64        self.retained.is_some()
65    }
66
67    pub fn stored_value(
68        &self,
69        id: DocId,
70        control: &StorageReadControl,
71    ) -> Result<Option<Cow<'_, Value>>, SQLError> {
72        match &self.retained {
73            Some(values) => values
74                .get(id, control)
75                .map(|value| value.map(Cow::Owned))
76                .map_err(storage),
77            None => Ok(self.policy.stored_value(id).map(Cow::Borrowed)),
78        }
79    }
80
81    pub fn contains(&self, id: DocId, control: &StorageReadControl) -> Result<bool, SQLError> {
82        self.retained.as_ref().map_or_else(
83            || Ok(self.policy.contains(id)),
84            |values| values.contains(id, control).map_err(storage),
85        )
86    }
87
88    /// Stored expression keys remain the old source of truth when removing a row. A failed migration or replacement publishes neither a partial tree nor new eligibility flags.
89    pub fn replace(
90        &mut self,
91        id: DocId,
92        value: Option<&Value>,
93        control: &StorageReadControl,
94    ) -> Result<(), SQLError> {
95        let prepared = self.prepare_replace(id, value, control)?;
96        self.apply_prepared(prepared);
97        Ok(())
98    }
99
100    fn prepare_replace<'a>(
101        &self,
102        id: DocId,
103        value: Option<&'a Value>,
104        control: &StorageReadControl,
105    ) -> Result<publication::PreparedChange<'a>, SQLError> {
106        control.check().map_err(storage)?;
107        if self.retained.is_some() {
108            let mut replacement = self.clone();
109            let values = replacement.retained.as_mut().expect("retained index");
110            values.replace(id, value, control).map_err(storage)?;
111            if let Some(value) = value {
112                observe(&mut replacement.policy, value);
113            }
114            return Ok(publication::PreparedChange::Replacement(replacement));
115        }
116        let previous = self
117            .policy
118            .stored_value(id)
119            .map(|value| value_bytes(value, control))
120            .transpose()?
121            .unwrap_or(0);
122        let new_bytes = value
123            .map(|value| value_bytes(value, control))
124            .transpose()?
125            .unwrap_or(0);
126        let bytes = self
127            .resident_bytes
128            .checked_sub(previous)
129            .and_then(|bytes| bytes.checked_add(new_bytes))
130            .ok_or_else(|| storage(uqa_core::memory::MemoryError::SizeOverflow.into()))?;
131        if bytes > self.limit {
132            let mut builder = ValueIndexBuilder::new(&self.field, self.is_carried(), self.limit)?;
133            for (&old_id, old) in &self.policy.values {
134                if old_id != id {
135                    builder.push(old_id, old.clone(), control)?;
136                }
137            }
138            if let Some(value) = value {
139                builder.push(id, value.clone(), control)?;
140            }
141            let mut replacement = builder.finish(control)?;
142            // Removal never made the old accelerator less conservative; changing its backing must not do so either.
143            replacement.policy.has_temporal |= self.policy.has_temporal;
144            replacement.policy.has_row_values |= self.policy.has_row_values;
145            if self.policy.comparison.can_fail() {
146                replacement.policy.comparison = comparison::StoredComparison::Fallible;
147            } else if self.policy.comparison.field_needs_evaluation()
148                && !replacement.policy.comparison.can_fail()
149            {
150                replacement.policy.comparison = comparison::StoredComparison::TypedField;
151            }
152            return Ok(publication::PreparedChange::Replacement(replacement));
153        }
154        Ok(publication::PreparedChange::Resident { id, value, bytes })
155    }
156
157    #[must_use]
158    pub fn with_use(mut self, field: &str, carried: bool) -> Self {
159        self.set_use(field, carried);
160        self
161    }
162
163    pub fn set_use(&mut self, field: &str, carried: bool) {
164        if self.retained.is_some() {
165            self.policy.index = (!carried).then(|| uqa_storage::BTreeIndex::new(field));
166        } else {
167            let previous = std::mem::replace(
168                &mut self.policy,
169                ColumnValueIndex::build_carried(std::iter::empty()),
170            );
171            self.policy = previous.with_use(field, carried);
172        }
173        self.field = field.to_string();
174    }
175
176    pub fn clear(&mut self) {
177        self.policy.clear();
178        if let Some(values) = &mut self.retained {
179            values.clear();
180        }
181        self.resident_bytes = 0;
182    }
183
184    pub fn supports(&self, predicate: &Predicate) -> bool {
185        self.policy.supports(predicate)
186    }
187}
188
189#[cfg(test)]
190mod tests;