Skip to main content

uqa_execution/distinct/
memory.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Collision-safe in-memory and reusable exact row sets.
8
9use crate::RowSchemaExecution;
10use std::collections::HashMap;
11use std::path::PathBuf;
12
13use smallvec::SmallVec;
14use uqa_core::Value;
15use uqa_sql::ResultRow;
16
17use crate::{ExecResult, PhysicalRow, RowSchema};
18
19use super::encoding::{encode_key, encode_key_borrowed, hash_canonical_row_with_enum_catalog};
20use super::spill::SeenKeySet;
21
22/// Collision-safe in-memory set for positional SQL rows.
23///
24/// Probes consume borrowed values and stream their canonical representation
25/// directly into the hash function. Only the first distinct row is copied
26/// into the contiguous key arena; repeated build rows and every lookup avoid
27/// both a positional `Vec<Value>` allocation and value cloning. Hash matches
28/// always verify the complete SQL [`Value`] equality domain.
29pub struct CanonicalRowHashSet {
30    pub(super) rows: Vec<SmallVec<[Value; 2]>>,
31    index: HashMap<u64, SmallVec<[usize; 1]>, ahash::RandomState>,
32}
33
34impl CanonicalRowHashSet {
35    #[must_use]
36    pub fn new() -> Self {
37        Self {
38            rows: Vec::new(),
39            index: HashMap::with_hasher(ahash::RandomState::new()),
40        }
41    }
42
43    /// Insert a positional key assembled from borrowed values.
44    /// Returns `true` only when this is the first SQL-equal key.
45    pub fn insert_borrowed(&mut self, values: &[&Value]) -> ExecResult<bool> {
46        self.insert_borrowed_with_catalog(values, None)
47    }
48
49    pub fn insert_borrowed_with_catalog(
50        &mut self,
51        values: &[&Value],
52        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
53    ) -> ExecResult<bool> {
54        let hash = hash_canonical_row_with_enum_catalog(
55            self.index.hasher(),
56            values.iter().copied().map(Some),
57            catalog,
58        )?;
59        if self.matching(hash, values.iter().copied(), catalog)? {
60            return Ok(false);
61        }
62
63        let row = values
64            .iter()
65            .map(|value| (*value).clone())
66            .collect::<SmallVec<[Value; 2]>>();
67        let row_index = self.rows.len();
68        self.rows.push(row);
69        self.index.entry(hash).or_default().push(row_index);
70        Ok(true)
71    }
72
73    /// Insert an already positional key without an intermediate borrowed-row
74    /// carrier. Values are copied only for a previously unseen key.
75    pub fn insert_values(&mut self, values: &[Value]) -> ExecResult<bool> {
76        self.insert_values_with_catalog(values, None)
77    }
78
79    pub fn insert_values_with_catalog(
80        &mut self,
81        values: &[Value],
82        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
83    ) -> ExecResult<bool> {
84        let hash = hash_canonical_row_with_enum_catalog(
85            self.index.hasher(),
86            values.iter().map(Some),
87            catalog,
88        )?;
89        if self.matching(hash, values.iter(), catalog)? {
90            return Ok(false);
91        }
92
93        let row_index = self.rows.len();
94        self.rows.push(values.iter().cloned().collect());
95        self.index.entry(hash).or_default().push(row_index);
96        Ok(true)
97    }
98
99    /// Probe with a composite row of borrowed values without allocating or
100    /// copying the key.
101    pub fn contains_borrowed(&self, values: &[&Value]) -> ExecResult<bool> {
102        self.contains_borrowed_with_catalog(values, None)
103    }
104
105    pub fn contains_borrowed_with_catalog(
106        &self,
107        values: &[&Value],
108        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
109    ) -> ExecResult<bool> {
110        let hash = hash_canonical_row_with_enum_catalog(
111            self.index.hasher(),
112            values.iter().copied().map(Some),
113            catalog,
114        )?;
115        self.matching(hash, values.iter().copied(), catalog)
116    }
117
118    /// Probe with an already positional value slice.
119    pub fn contains_values(&self, values: &[Value]) -> ExecResult<bool> {
120        self.contains_values_with_catalog(values, None)
121    }
122
123    pub fn contains_values_with_catalog(
124        &self,
125        values: &[Value],
126        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
127    ) -> ExecResult<bool> {
128        let hash = hash_canonical_row_with_enum_catalog(
129            self.index.hasher(),
130            values.iter().map(Some),
131            catalog,
132        )?;
133        self.matching(hash, values.iter(), catalog)
134    }
135
136    fn matching<'a>(
137        &self,
138        hash: u64,
139        values: impl ExactSizeIterator<Item = &'a Value> + Clone,
140        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
141    ) -> ExecResult<bool> {
142        let Some(bucket) = self.index.get(&hash) else {
143            return Ok(false);
144        };
145        for index in bucket {
146            let stored = &self.rows[*index];
147            if stored.len() != values.len() {
148                continue;
149            }
150            let mut equal = true;
151            for (stored, value) in stored.iter().zip(values.clone()) {
152                if !uqa_sql::expr::equal_typed_values_with_enum_catalog(
153                    stored,
154                    value,
155                    &uqa_core::memory::ProductionControl::uncontrolled(),
156                    catalog,
157                )? {
158                    equal = false;
159                    break;
160                }
161            }
162            if equal {
163                return Ok(true);
164            }
165        }
166        Ok(false)
167    }
168}
169
170impl Default for CanonicalRowHashSet {
171    fn default() -> Self {
172        Self::new()
173    }
174}
175
176/// Exact, byte-bounded row-key set that can outlive one physical operator.
177///
178/// Recursive fixpoint evaluation needs duplicate state to survive across
179/// multiple executions of its recursive term. [`Distinct`](crate::distinct::Distinct) deliberately
180/// resets its state on every `open`, so this small public carrier exposes the
181/// same collision-safe memory-to-disk migration without coupling the engine to
182/// the on-disk format.
183pub struct ExactRowSet {
184    seen: SeenKeySet,
185}
186
187impl ExactRowSet {
188    pub fn new(work_mem_bytes: usize) -> Self {
189        Self {
190            seen: SeenKeySet::new(work_mem_bytes, None),
191        }
192    }
193
194    pub fn with_spill_directory(work_mem_bytes: usize, directory: impl Into<PathBuf>) -> Self {
195        Self {
196            seen: SeenKeySet::new(work_mem_bytes, Some(directory.into())),
197        }
198    }
199
200    /// Insert the positional values from `row` in `schema` order.
201    /// Returns `true` only for the first exact occurrence.
202    pub fn insert_row(&mut self, row: &ResultRow, schema: &[String]) -> ExecResult<bool> {
203        self.seen.insert(row_key(row, schema)?)
204    }
205
206    pub fn contains_row(&mut self, row: &ResultRow, schema: &[String]) -> ExecResult<bool> {
207        self.seen.contains(&row_key(row, schema)?)
208    }
209
210    /// Insert an already-positional SQL value key without constructing a
211    /// named row. The binary encoding is the same collision-safe,
212    /// cross-numeric representation used by physical DISTINCT.
213    pub fn insert_values(&mut self, values: &[Value]) -> ExecResult<bool> {
214        self.seen.insert(encode_key(values)?)
215    }
216
217    /// Probe an already-positional SQL value key without constructing a named
218    /// row. Disk-backed sets perform an exact full-key comparison.
219    pub fn contains_values(&mut self, values: &[Value]) -> ExecResult<bool> {
220        self.seen.contains(&encode_key(values)?)
221    }
222
223    /// Insert a physical row directly in logical schema order without constructing a named row or cloning its values.
224    pub fn insert_physical(&mut self, row: &PhysicalRow, schema: &RowSchema) -> ExecResult<bool> {
225        let view = schema.view(row);
226        self.seen.insert(encode_key_borrowed(
227            (0..schema.len()).map(|position| view.value_at(position)),
228        )?)
229    }
230
231    /// Probe a physical row directly in logical schema order without constructing a named row or cloning its values.
232    pub fn contains_physical(&mut self, row: &PhysicalRow, schema: &RowSchema) -> ExecResult<bool> {
233        let view = schema.view(row);
234        self.seen.contains(&encode_key_borrowed(
235            (0..schema.len()).map(|position| view.value_at(position)),
236        )?)
237    }
238
239    pub fn has_spilled(&self) -> bool {
240        self.seen.has_spilled()
241    }
242
243    pub fn in_memory_key_bytes(&self) -> usize {
244        self.seen.in_memory_bytes()
245    }
246}
247
248fn row_key(row: &ResultRow, schema: &[String]) -> ExecResult<Vec<u8>> {
249    encode_key_borrowed(schema.iter().map(|column| row.get(column)))
250}