uqa_execution/distinct/
memory.rs1use 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
22pub 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 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 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 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 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
176pub 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 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 pub fn insert_values(&mut self, values: &[Value]) -> ExecResult<bool> {
214 self.seen.insert(encode_key(values)?)
215 }
216
217 pub fn contains_values(&mut self, values: &[Value]) -> ExecResult<bool> {
220 self.seen.contains(&encode_key(values)?)
221 }
222
223 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 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}