uqa_execution/query/index_candidates/
ids.rs1use crate::{
10 mutation::PhysicalRowBuffer,
11 physical::physical_exec_error,
12 spill::{SharedSpillReader, SpillBatchWriter, SpillRows},
13 PhysicalRow, RowSchema, SharedSpill, SpillBuffer,
14};
15use std::sync::Arc;
16use uqa_core::{CancellationToken, DocId, Value};
17use uqa_sql::SQLError;
18
19#[derive(Clone)]
20enum IdentityStorage {
21 Memory(Arc<[DocId]>),
22 Spill(SharedSpill),
23}
24
25#[derive(Clone)]
27pub struct SelectedIds {
28 storage: IdentityStorage,
29 cancellation: CancellationToken,
30}
31
32impl SelectedIds {
33 pub(crate) fn partition(
35 &self,
36 bytes: usize,
37 mut select: impl FnMut(DocId) -> Result<Option<bool>, SQLError>,
38 ) -> Result<(Self, Self), SQLError> {
39 let mut first = IdentityBuilder::new(bytes / 2, &self.cancellation);
40 let mut second = IdentityBuilder::new(bytes / 2, &self.cancellation);
41 for id in self.cursor() {
42 let id = id?;
43 match select(id)? {
44 Some(true) => first.push(id)?,
45 Some(false) => second.push(id)?,
46 None => {}
47 }
48 }
49 Ok((first.finish(false)?, second.finish(false)?))
50 }
51
52 pub(crate) fn capture_visit(
54 bytes: usize,
55 cancellation: &CancellationToken,
56 produce: impl FnOnce(&mut dyn FnMut(DocId) -> Result<(), SQLError>) -> Result<(), SQLError>,
57 ) -> Result<Self, SQLError> {
58 let mut builder = IdentityBuilder::new(bytes, cancellation);
59 produce(&mut |id| builder.push(id))?;
60 builder.finish(true)
61 }
62
63 pub fn capture(
65 ids: impl IntoIterator<Item = Result<DocId, SQLError>>,
66 bytes: usize,
67 cancellation: &CancellationToken,
68 ) -> Result<Self, SQLError> {
69 let mut builder = IdentityBuilder::new(bytes, cancellation);
70 for id in ids {
71 builder.push(id?)?;
72 }
73 builder.finish(true)
74 }
75
76 pub(crate) fn from_sorted(
77 ids: Vec<DocId>,
78 bytes: usize,
79 cancellation: &CancellationToken,
80 ) -> Result<Self, SQLError> {
81 cancellation.check()?;
82 if ids.len() <= bytes / size_of::<DocId>() {
83 return Ok(Self {
84 storage: IdentityStorage::Memory(ids.into()),
85 cancellation: cancellation.clone(),
86 });
87 }
88 let mut builder = IdentityBuilder::new(bytes, cancellation);
89 for id in ids {
90 builder.push(id)?;
91 }
92 builder.finish(false)
93 }
94
95 pub fn len(&self) -> usize {
96 match &self.storage {
97 IdentityStorage::Memory(ids) => ids.len(),
98 IdentityStorage::Spill(rows) => rows.rows(),
99 }
100 }
101
102 pub fn is_empty(&self) -> bool {
103 self.len() == 0
104 }
105
106 pub fn cursor(&self) -> SelectedIdCursor {
107 SelectedIdCursor {
108 source: self.clone(),
109 position: 0,
110 rows: None,
111 failed: false,
112 }
113 }
114}
115
116pub struct SelectedIdCursor {
117 source: SelectedIds,
118 position: usize,
119 rows: Option<SpillRows<SharedSpillReader>>,
120 failed: bool,
121}
122
123impl SelectedIdCursor {
124 fn read(&mut self) -> Result<Option<DocId>, SQLError> {
125 self.source.cancellation.check()?;
126 let id = match &self.source.storage {
127 IdentityStorage::Memory(ids) => ids.get(self.position).copied(),
128 IdentityStorage::Spill(source) => {
129 if self.rows.is_none() {
130 self.rows = Some(source.read_rows().map_err(physical_exec_error)?);
131 }
132 self.rows
133 .as_mut()
134 .expect("opened candidate cursor")
135 .next()
136 .map(|row| decode(row.map_err(physical_exec_error)?.row))
137 .transpose()?
138 }
139 };
140 self.position += usize::from(id.is_some());
141 Ok(id)
142 }
143}
144
145impl Iterator for SelectedIdCursor {
146 type Item = Result<DocId, SQLError>;
147
148 fn next(&mut self) -> Option<Self::Item> {
149 if self.failed || self.position == self.source.len() {
150 return None;
151 }
152 match self.read() {
153 Ok(Some(id)) => Some(Ok(id)),
154 Ok(None) => {
155 self.failed = true;
156 Some(Err(SQLError::Internal(
157 "truncated candidate identities".into(),
158 )))
159 }
160 Err(error) => {
161 self.failed = true;
162 Some(Err(error))
163 }
164 }
165 }
166}
167
168struct SpilledIds {
169 rows: SpillBuffer,
170 writer: SpillBatchWriter,
171 schema: RowSchema,
172}
173
174enum CapturedIds {
175 Memory(Vec<DocId>),
176 Spill(Box<SpilledIds>),
177}
178
179pub(super) struct IdentityBuilder {
180 records: CapturedIds,
181 bytes: usize,
182 cancellation: CancellationToken,
183 previous: Option<DocId>,
184 ascending: bool,
185}
186
187impl IdentityBuilder {
188 pub(super) fn new(bytes: usize, cancellation: &CancellationToken) -> Self {
189 Self {
190 records: CapturedIds::Memory(Vec::new()),
191 bytes,
192 cancellation: cancellation.clone(),
193 previous: None,
194 ascending: true,
195 }
196 }
197
198 pub(super) fn push(&mut self, id: DocId) -> Result<(), SQLError> {
199 self.cancellation.check()?;
200 self.ascending &= self.previous.is_none_or(|previous| previous < id);
201 self.previous = Some(id);
202 if let CapturedIds::Memory(ids) = &mut self.records {
203 let limit = self.bytes / 4 / size_of::<DocId>();
204 if ids.len() < limit {
205 if ids.len() == ids.capacity() {
206 let capacity = ids.capacity().saturating_mul(2).max(4).min(limit);
207 ids.reserve_exact(capacity - ids.len());
208 }
209 ids.push(id);
210 return Ok(());
211 }
212 let schema = RowSchema::with_internal_relation_types(
213 uqa_sql::ast::InternalRelationId::allocate(),
214 vec![None],
215 );
216 let mut spilled = SpilledIds {
217 rows: SpillBuffer::new(self.bytes / 4),
218 writer: SpillBatchWriter::new(schema.clone()).map_err(physical_exec_error)?,
219 schema,
220 };
221 for &id in ids.iter() {
222 self.cancellation.check()?;
223 spilled.push(id)?;
224 }
225 self.records = CapturedIds::Spill(Box::new(spilled));
226 }
227 let CapturedIds::Spill(records) = &mut self.records else {
228 unreachable!("spilled candidate identities")
229 };
230 records.push(id)
231 }
232
233 pub(super) fn finish(self, sort: bool) -> Result<SelectedIds, SQLError> {
234 self.cancellation.check()?;
235 let SpilledIds {
236 mut rows,
237 writer,
238 schema,
239 } = match self.records {
240 CapturedIds::Memory(mut ids) => {
241 if sort && !self.ascending {
242 ids.sort_unstable();
243 ids.dedup();
244 }
245 return Ok(SelectedIds {
246 storage: IdentityStorage::Memory(ids.into()),
247 cancellation: self.cancellation,
248 });
249 }
250 CapturedIds::Spill(records) => *records,
251 };
252 writer.finish(&mut rows).map_err(physical_exec_error)?;
253 if !sort || self.ascending {
254 return Ok(SelectedIds {
255 storage: IdentityStorage::Spill(
256 rows.into_shared(schema).map_err(physical_exec_error)?,
257 ),
258 cancellation: self.cancellation,
259 });
260 }
261 let mut ordered = PhysicalRowBuffer::new(
263 self.bytes / 4,
264 self.cancellation.clone(),
265 "sort indexed candidates",
266 );
267 for row in rows.drain_rows().map_err(physical_exec_error)? {
268 ordered.insert("", decode(row.map_err(physical_exec_error)?.row)?)?;
269 }
270 let ordered = ordered.finish()?;
271 let mut output = Self::new(self.bytes, &self.cancellation);
272 ordered.visit(&mut |_, id| {
273 output.push(id)?;
274 Ok(true)
275 })?;
276 output.finish(false)
277 }
278}
279
280impl SpilledIds {
281 fn push(&mut self, id: DocId) -> Result<(), SQLError> {
282 self.writer
283 .push(
284 &mut self.rows,
285 PhysicalRow::from_values(vec![Value::Bytes(id.to_be_bytes().to_vec())]),
286 )
287 .map_err(physical_exec_error)
288 }
289}
290
291fn decode(row: PhysicalRow) -> Result<DocId, SQLError> {
292 let Some(Value::Bytes(bytes)) = row.value(0) else {
293 return Err(SQLError::Internal("invalid candidate identity".into()));
294 };
295 Ok(u64::from_be_bytes(bytes.as_slice().try_into().map_err(
296 |_| SQLError::Internal("invalid candidate identity width".into()),
297 )?))
298}