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::{ColumnType, ResultRow};
16
17use crate::{ExecResult, PhysicalRow, RowSchema};
18
19use super::encoding::{
20    encode_key, encode_key_borrowed, encode_sql_key_with_types_and_catalog,
21    hash_typed_row_with_catalog,
22};
23use super::spill::SeenKeySet;
24
25/// Collision-safe in-memory set for positional SQL rows.
26///
27/// Probes consume borrowed values and stream their canonical representation
28/// directly into the hash function. Only the first distinct row is copied
29/// into the contiguous key arena; repeated build rows and every lookup avoid
30/// both a positional `Vec<Value>` allocation and value cloning. Hash matches
31/// always verify the complete SQL [`Value`] equality domain.
32pub struct CanonicalRowHashSet {
33    pub(super) rows: Vec<SmallVec<[Value; 2]>>,
34    index: HashMap<u64, SmallVec<[usize; 1]>, ahash::RandomState>,
35    types: Vec<Option<ColumnType>>,
36}
37
38impl CanonicalRowHashSet {
39    #[must_use]
40    pub fn new() -> Self {
41        Self::with_sql_types(Vec::new())
42    }
43
44    /// Retain the selected key types for every insertion, hash probe and collision comparison.
45    #[must_use]
46    pub fn with_sql_types(types: Vec<Option<ColumnType>>) -> Self {
47        Self {
48            rows: Vec::new(),
49            index: HashMap::with_hasher(ahash::RandomState::new()),
50            types,
51        }
52    }
53
54    /// Insert a positional key assembled from borrowed values.
55    /// Returns `true` only when this is the first SQL-equal key.
56    pub fn insert_borrowed(&mut self, values: &[&Value]) -> ExecResult<bool> {
57        self.insert_borrowed_with_catalog(values, None)
58    }
59
60    pub fn insert_borrowed_with_catalog(
61        &mut self,
62        values: &[&Value],
63        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
64    ) -> ExecResult<bool> {
65        let hash = self.hash_values(values.iter().copied(), catalog)?;
66        if self.matching(hash, values.iter().copied(), catalog)? {
67            return Ok(false);
68        }
69
70        let row = values
71            .iter()
72            .map(|value| (*value).clone())
73            .collect::<SmallVec<[Value; 2]>>();
74        let row_index = self.rows.len();
75        self.rows.push(row);
76        self.index.entry(hash).or_default().push(row_index);
77        Ok(true)
78    }
79
80    /// Insert an already positional key without an intermediate borrowed-row
81    /// carrier. Values are copied only for a previously unseen key.
82    pub fn insert_values(&mut self, values: &[Value]) -> ExecResult<bool> {
83        self.insert_values_with_catalog(values, None)
84    }
85
86    pub fn insert_values_with_catalog(
87        &mut self,
88        values: &[Value],
89        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
90    ) -> ExecResult<bool> {
91        let hash = self.hash_values(values.iter(), catalog)?;
92        if self.matching(hash, values.iter(), catalog)? {
93            return Ok(false);
94        }
95
96        let row_index = self.rows.len();
97        self.rows.push(values.iter().cloned().collect());
98        self.index.entry(hash).or_default().push(row_index);
99        Ok(true)
100    }
101
102    /// Probe with a composite row of borrowed values without allocating or
103    /// copying the key.
104    pub fn contains_borrowed(&self, values: &[&Value]) -> ExecResult<bool> {
105        self.contains_borrowed_with_catalog(values, None)
106    }
107
108    pub fn contains_borrowed_with_catalog(
109        &self,
110        values: &[&Value],
111        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
112    ) -> ExecResult<bool> {
113        let hash = self.hash_values(values.iter().copied(), catalog)?;
114        self.matching(hash, values.iter().copied(), catalog)
115    }
116
117    /// Probe with an already positional value slice.
118    pub fn contains_values(&self, values: &[Value]) -> ExecResult<bool> {
119        self.contains_values_with_catalog(values, None)
120    }
121
122    pub fn contains_values_with_catalog(
123        &self,
124        values: &[Value],
125        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
126    ) -> ExecResult<bool> {
127        let hash = self.hash_values(values.iter(), catalog)?;
128        self.matching(hash, values.iter(), catalog)
129    }
130
131    fn hash_values<'a>(
132        &'a self,
133        values: impl ExactSizeIterator<Item = &'a Value>,
134        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
135    ) -> ExecResult<u64> {
136        hash_typed_row_with_catalog(
137            self.index.hasher(),
138            values.enumerate().map(|(index, value)| {
139                (Some(value), self.types.get(index).and_then(Option::as_ref))
140            }),
141            catalog,
142        )
143    }
144
145    fn matching<'a>(
146        &self,
147        hash: u64,
148        values: impl ExactSizeIterator<Item = &'a Value> + Clone,
149        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
150    ) -> ExecResult<bool> {
151        let Some(bucket) = self.index.get(&hash) else {
152            return Ok(false);
153        };
154        for index in bucket {
155            let stored = &self.rows[*index];
156            if stored.len() != values.len() {
157                continue;
158            }
159            let mut equal = true;
160            for (position, (stored, value)) in stored.iter().zip(values.clone()).enumerate() {
161                if !uqa_sql::expr::equal_selected_values_with_catalog(
162                    stored,
163                    value,
164                    self.types.get(position).and_then(Option::as_ref),
165                    &uqa_core::memory::ProductionControl::uncontrolled(),
166                    catalog,
167                )? {
168                    equal = false;
169                    break;
170                }
171            }
172            if equal {
173                return Ok(true);
174            }
175        }
176        Ok(false)
177    }
178}
179
180impl Default for CanonicalRowHashSet {
181    fn default() -> Self {
182        Self::new()
183    }
184}
185
186/// Exact, byte-bounded row-key set that can outlive one physical operator.
187///
188/// Recursive fixpoint evaluation needs duplicate state to survive across
189/// multiple executions of its recursive term. [`Distinct`](crate::distinct::Distinct) deliberately
190/// resets its state on every `open`, so this small public carrier exposes the
191/// same collision-safe memory-to-disk migration without coupling the engine to
192/// the on-disk format.
193pub struct ExactRowSet {
194    seen: SeenKeySet,
195    types: Option<Vec<Option<ColumnType>>>,
196}
197
198impl ExactRowSet {
199    /// The first SQL insertion selects the key types; probes do not bind an empty set. Explicit selected types can instead be supplied by `with_sql_types`.
200    pub fn new(work_mem_bytes: usize) -> Self {
201        Self {
202            seen: SeenKeySet::new(work_mem_bytes, None),
203            types: None,
204        }
205    }
206
207    /// Keep the selected SQL value-key types across memory-to-disk migration and later probes. Raw-key methods retain their existing representation domain.
208    pub fn with_sql_types(work_mem_bytes: usize, types: Vec<Option<ColumnType>>) -> Self {
209        Self {
210            seen: SeenKeySet::new(work_mem_bytes, None),
211            types: Some(types),
212        }
213    }
214
215    pub fn with_spill_directory(work_mem_bytes: usize, directory: impl Into<PathBuf>) -> Self {
216        Self {
217            seen: SeenKeySet::new(work_mem_bytes, Some(directory.into())),
218            types: None,
219        }
220    }
221
222    /// Insert the positional values from `row` in `schema` order.
223    /// Returns `true` only for the first exact occurrence.
224    pub fn insert_row(&mut self, row: &ResultRow, schema: &[String]) -> ExecResult<bool> {
225        self.seen.insert(row_key(row, schema)?)
226    }
227
228    pub fn contains_row(&mut self, row: &ResultRow, schema: &[String]) -> ExecResult<bool> {
229        self.seen.contains(&row_key(row, schema)?)
230    }
231
232    /// Insert an already-positional SQL value key without constructing a
233    /// named row. The binary encoding is the same collision-safe,
234    /// cross-numeric representation used by physical DISTINCT.
235    pub fn insert_values(&mut self, values: &[Value]) -> ExecResult<bool> {
236        self.seen.insert(encode_key(values)?)
237    }
238
239    /// Probe an already-positional SQL value key without constructing a named
240    /// row. Disk-backed sets perform an exact full-key comparison.
241    pub fn contains_values(&mut self, values: &[Value]) -> ExecResult<bool> {
242        self.seen.contains(&encode_key(values)?)
243    }
244
245    /// Insert selected SQL keys with the statement's retained type catalog.
246    pub fn insert_sql_values(
247        &mut self,
248        values: &[Value],
249        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
250    ) -> ExecResult<bool> {
251        self.types.get_or_insert_with(Vec::new);
252        self.seen.insert(self.sql_key(values, catalog)?)
253    }
254
255    /// Probe the same SQL equality domain used during insertion, including after spill.
256    pub fn contains_sql_values(
257        &mut self,
258        values: &[Value],
259        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
260    ) -> ExecResult<bool> {
261        self.seen.contains(&self.sql_key(values, catalog)?)
262    }
263
264    fn sql_key(
265        &self,
266        values: &[Value],
267        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
268    ) -> ExecResult<Vec<u8>> {
269        let types = self.types.as_deref().unwrap_or_default();
270        encode_sql_key_with_types_and_catalog(
271            values
272                .iter()
273                .enumerate()
274                .map(|(index, value)| (Some(value), types.get(index).and_then(Option::as_ref))),
275            catalog,
276        )
277    }
278
279    /// Insert SQL fields in logical schema order without cloning their payloads. An unbound set captures this schema's selected types once; every later insertion and probe uses the captured or explicitly selected types.
280    pub fn insert_sql_physical(
281        &mut self,
282        row: &PhysicalRow,
283        schema: &RowSchema,
284        catalog: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
285    ) -> ExecResult<bool> {
286        let types = self.types.get_or_insert_with(|| {
287            (0..schema.len())
288                .map(|position| schema.column_type(position).cloned())
289                .collect()
290        });
291        let view = schema.view(row);
292        self.seen.insert(encode_sql_key_with_types_and_catalog(
293            (0..schema.len()).map(|position| {
294                (
295                    view.value_at(position),
296                    types.get(position).and_then(Option::as_ref),
297                )
298            }),
299            catalog,
300        )?)
301    }
302
303    /// Insert a physical row directly in logical schema order without constructing a named row or cloning its values.
304    pub fn insert_physical(&mut self, row: &PhysicalRow, schema: &RowSchema) -> ExecResult<bool> {
305        let view = schema.view(row);
306        self.seen.insert(encode_key_borrowed(
307            (0..schema.len()).map(|position| view.value_at(position)),
308        )?)
309    }
310
311    /// Probe a physical row directly in logical schema order without constructing a named row or cloning its values.
312    pub fn contains_physical(&mut self, row: &PhysicalRow, schema: &RowSchema) -> ExecResult<bool> {
313        let view = schema.view(row);
314        self.seen.contains(&encode_key_borrowed(
315            (0..schema.len()).map(|position| view.value_at(position)),
316        )?)
317    }
318
319    pub fn has_spilled(&self) -> bool {
320        self.seen.has_spilled()
321    }
322
323    pub fn in_memory_key_bytes(&self) -> usize {
324        self.seen.in_memory_bytes()
325    }
326}
327
328fn row_key(row: &ResultRow, schema: &[String]) -> ExecResult<Vec<u8>> {
329    encode_key_borrowed(schema.iter().map(|column| row.get(column)))
330}