Skip to main content

uqa_execution/distinct/
mod.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Byte-bounded streaming physical `DISTINCT` operator.
8//!
9//! The operator keeps exact encoded keys in memory until their combined byte
10//! size reaches `work_mem`. It then migrates every key to a temporary,
11//! bucketed on-disk set. Disk probes compare the complete encoded key, so a
12//! hash collision can never turn a new row into a duplicate. Output remains
13
14use crate::RowSchemaExecution;
15mod encoding;
16mod memory;
17pub(crate) mod ordered;
18mod spill;
19
20use std::path::{Path, PathBuf};
21
22use crate::{
23    Batch, ExecError, ExecResult, PhysicalOperator, RowSchema, ScalarExpr,
24    SharedExpressionEvaluator,
25};
26
27pub(crate) use encoding::canonical_row_lock_keys_with_catalog;
28pub use encoding::{
29    btree_input_binary_key_with_catalog_and_control, canonical_row_key, canonical_row_key_budgeted,
30    canonical_row_key_with_catalog_and_control, canonical_typed_row_key_with_catalog_and_control,
31    hash_canonical_row, hash_canonical_row_with_enum_catalog,
32    record_image_key_with_catalog_and_control, try_pack_compact_text_pair,
33};
34pub(crate) use encoding::{encode_key, EncodedKey};
35pub(crate) use encoding::{
36    encode_sql_key_with_types_and_catalog, encode_typed_non_null_key, hash_typed_row_with_catalog,
37};
38pub use memory::{CanonicalRowHashSet, ExactRowSet};
39pub(crate) use spill::SeenKeySet;
40#[cfg(test)]
41use spill::{stable_hash, DISK_BUCKETS};
42
43/// Default used by compatibility constructors. Engine callers should pass the
44/// current session's `work_mem` through [`Distinct::all_with_work_mem`] or
45/// [`Distinct::on_with_work_mem`].
46pub const DEFAULT_DISTINCT_WORK_MEM_BYTES: usize = 64 * 1024 * 1024;
47
48/// Stable SQL duplicate elimination.
49///
50/// With no key expressions, the complete positional output row is the key.
51/// With expressions, the operator implements `DISTINCT ON`: it preserves the
52/// first row for each evaluated key in child order.
53pub struct Distinct<'a> {
54    child: Box<dyn PhysicalOperator + 'a>,
55    keys: Option<crate::scalar::PreparedExpressions<Vec<ScalarExpr>>>,
56    key_types: Vec<Option<uqa_sql::ColumnType>>,
57    evaluator: Option<SharedExpressionEvaluator<'a>>,
58    schema: RowSchema,
59    work_mem_bytes: usize,
60    spill_directory: Option<PathBuf>,
61    seen: SeenKeySet,
62}
63
64impl<'a> Distinct<'a> {
65    /// Construct a bounded full-row `DISTINCT` with the compatibility default
66    /// work-memory budget.
67    pub fn all(child: Box<dyn PhysicalOperator + 'a>) -> Self {
68        Self::all_with_work_mem(child, DEFAULT_DISTINCT_WORK_MEM_BYTES)
69    }
70
71    /// Construct a bounded full-row `DISTINCT` with an explicit byte budget.
72    pub fn all_with_work_mem(child: Box<dyn PhysicalOperator + 'a>, work_mem_bytes: usize) -> Self {
73        let schema = child.row_schema().clone();
74        Self {
75            child,
76            keys: None,
77            key_types: Vec::new(),
78            evaluator: None,
79            schema,
80            work_mem_bytes,
81            spill_directory: None,
82            seen: SeenKeySet::new(work_mem_bytes, None),
83        }
84    }
85
86    /// Retain expression/catalog services for full-row equality as well as explicit keys.
87    pub fn with_evaluator(mut self, evaluator: SharedExpressionEvaluator<'a>) -> Self {
88        self.evaluator = Some(evaluator);
89        self
90    }
91
92    /// Construct a bounded `DISTINCT ON` with the compatibility default
93    /// work-memory budget.
94    pub fn on(
95        child: Box<dyn PhysicalOperator + 'a>,
96        keys: Vec<ScalarExpr>,
97        evaluator: SharedExpressionEvaluator<'a>,
98    ) -> Self {
99        Self::on_with_work_mem(child, keys, evaluator, DEFAULT_DISTINCT_WORK_MEM_BYTES)
100    }
101
102    /// Construct a bounded `DISTINCT ON` with an explicit byte budget.
103    pub fn on_with_work_mem(
104        child: Box<dyn PhysicalOperator + 'a>,
105        keys: Vec<ScalarExpr>,
106        evaluator: SharedExpressionEvaluator<'a>,
107        work_mem_bytes: usize,
108    ) -> Self {
109        let schema = child.row_schema().clone();
110        Self {
111            child,
112            keys: Some(crate::scalar::PreparedExpressions::scalars(keys)),
113            key_types: Vec::new(),
114            evaluator: Some(evaluator),
115            schema,
116            work_mem_bytes,
117            spill_directory: None,
118            seen: SeenKeySet::new(work_mem_bytes, None),
119        }
120    }
121
122    /// Place the exact-set files in a caller-selected temporary-data
123    /// directory. The directory must already exist; a private child directory
124    /// is created lazily on the first spill and removed through RAII.
125    pub fn with_spill_directory(mut self, directory: impl Into<PathBuf>) -> Self {
126        self.spill_directory = Some(directory.into());
127        self.reset_seen();
128        self
129    }
130
131    /// Whether this invocation has migrated its key set to disk.
132    pub fn has_spilled(&self) -> bool {
133        self.seen.has_spilled()
134    }
135
136    /// Exact encoded key bytes retained by the in-memory set.
137    pub fn in_memory_key_bytes(&self) -> usize {
138        self.seen.in_memory_bytes()
139    }
140
141    /// Live private spill directory, for diagnostics and cleanup tests.
142    pub fn spill_path(&self) -> Option<&Path> {
143        self.seen.spill_path()
144    }
145
146    fn reset_seen(&mut self) {
147        self.seen = SeenKeySet::new(self.work_mem_bytes, self.spill_directory.clone());
148    }
149
150    fn key(&self, schema: &RowSchema, row: &crate::PhysicalRow) -> ExecResult<Vec<u8>> {
151        if let Some(keys) = self.keys.as_ref() {
152            let evaluator = self.evaluator.as_ref().ok_or_else(|| {
153                ExecError::Other("DISTINCT ON evaluator is not configured".into())
154            })?;
155            let values = keys
156                .iter()
157                .map(|expression| {
158                    evaluator.evaluate_physical_with_function_states(
159                        expression,
160                        schema,
161                        row,
162                        keys.calls(),
163                    )
164                })
165                .collect::<ExecResult<Vec<_>>>()?;
166            return encode_sql_key_with_types_and_catalog(
167                values
168                    .iter()
169                    .zip(&self.key_types)
170                    .map(|(value, ty)| (Some(value), ty.as_ref())),
171                evaluator.enum_labels(),
172            );
173        }
174        let row = schema.view(row);
175        encode_sql_key_with_types_and_catalog(
176            (0..self.schema.len())
177                .map(|index| (row.value_at(index), self.schema.column_type(index))),
178            self.evaluator
179                .as_ref()
180                .and_then(|evaluator| evaluator.enum_labels()),
181        )
182    }
183}
184
185impl PhysicalOperator for Distinct<'_> {
186    fn row_schema(&self) -> &RowSchema {
187        &self.schema
188    }
189
190    fn open(&mut self) -> ExecResult<()> {
191        self.reset_seen();
192        if let Some(keys) = &self.keys {
193            let evaluator = self.evaluator.as_ref().ok_or_else(|| {
194                ExecError::Other("DISTINCT ON evaluator is not configured".into())
195            })?;
196            self.key_types = keys
197                .iter()
198                .map(|key| evaluator.expression_type(key, &self.schema))
199                .collect::<Result<_, _>>()?;
200        }
201        self.child.open()
202    }
203
204    fn next(&mut self) -> ExecResult<Option<Batch>> {
205        loop {
206            let Some(batch) = self.child.next()? else {
207                return Ok(None);
208            };
209            if batch.schema != self.schema {
210                return Err(ExecError::Other(format!(
211                    "DISTINCT input schema mismatch: expected {:?}, got {:?}",
212                    self.schema, batch.schema
213                )));
214            }
215            let mut rows = Vec::with_capacity(batch.rows.len());
216            for row in batch.rows {
217                let key = self.key(&batch.schema, &row)?;
218                if self.seen.insert(key)? {
219                    rows.push(row.without_lock_origins());
220                }
221            }
222            if !rows.is_empty() {
223                return Ok(Some(Batch::from_physical_rows(self.schema.clone(), rows)));
224            }
225        }
226    }
227
228    fn close(&mut self) -> ExecResult<()> {
229        self.reset_seen();
230        self.child.close()
231    }
232}
233
234#[cfg(test)]
235mod tests;