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