Skip to main content

uqa_execution/aggregation/
value_buffer.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Spillable ordered aggregate-value buffering.
8
9use super::ordering::{
10    compare_sort_keys, compare_sort_keys_with_catalog, minimum_by, sort_records,
11};
12use uqa_sql::expr::enums::{EnumComparisonState, EnumLabelCatalog};
13
14use super::{
15    BufRead, BufReader, BufWriter, File, Ordering, SQLError, Seek, SeekFrom, Value, Write,
16    AGGREGATE_MERGE_FAN_IN,
17};
18
19#[derive(Clone, serde::Deserialize, serde::Serialize)]
20pub struct AggregateValueRecord {
21    pub(super) value: Value,
22    pub(super) sort_keys: Vec<super::ordering::AggregateSortKey>,
23    pub(super) sequence: u64,
24}
25
26pub struct JsonSpillRun {
27    pub(super) file: uqa_storage::temporary_file::TemporaryFile,
28    pub(super) max_record_bytes: usize,
29}
30
31pub fn write_json_spill_record(
32    writer: &mut impl Write,
33    value: &impl serde::Serialize,
34    description: &str,
35) -> Result<usize, SQLError> {
36    let payload = serde_json::to_vec(value).map_err(|error| {
37        SQLError::Internal(format!("failed to serialize {description}: {error}"))
38    })?;
39    let record_bytes = payload
40        .len()
41        .checked_add(1)
42        .ok_or_else(|| SQLError::Internal(format!("{description} size overflow")))?;
43    writer
44        .write_all(&payload)
45        .map_err(|error| SQLError::Internal(format!("failed to write {description}: {error}")))?;
46    writer
47        .write_all(b"\n")
48        .map_err(|error| SQLError::Internal(format!("failed to write {description}: {error}")))?;
49    Ok(record_bytes)
50}
51
52pub fn read_bounded_json_spill_record<R: BufRead>(
53    reader: &mut R,
54    max_record_bytes: usize,
55    description: &str,
56) -> Result<Option<Vec<u8>>, SQLError> {
57    let mut record = Vec::new();
58    loop {
59        let (chunk_len, terminated) = {
60            let available = reader.fill_buf().map_err(|error| {
61                SQLError::Internal(format!("failed to read {description}: {error}"))
62            })?;
63            if available.is_empty() {
64                if record.is_empty() {
65                    return Ok(None);
66                }
67                return Err(SQLError::Internal(format!(
68                    "truncated {description}: missing record delimiter"
69                )));
70            }
71            match available.iter().position(|byte| *byte == b'\n') {
72                Some(index) => (index + 1, true),
73                None => (available.len(), false),
74            }
75        };
76        let next_len = record
77            .len()
78            .checked_add(chunk_len)
79            .ok_or_else(|| SQLError::Internal(format!("{description} length overflow")))?;
80        if next_len > max_record_bytes {
81            return Err(SQLError::Internal(format!(
82                "{description} exceeds recorded maximum of {max_record_bytes} bytes"
83            )));
84        }
85        record.try_reserve(chunk_len).map_err(|error| {
86            SQLError::Internal(format!(
87                "unable to allocate {chunk_len} more bytes for {description}: {error}"
88            ))
89        })?;
90        let available = reader.fill_buf().map_err(|error| {
91            SQLError::Internal(format!("failed to read {description}: {error}"))
92        })?;
93        record.extend_from_slice(&available[..chunk_len]);
94        reader.consume(chunk_len);
95        if terminated {
96            let delimiter = record.pop();
97            debug_assert_eq!(delimiter, Some(b'\n'));
98            return Ok(Some(record));
99        }
100    }
101}
102
103pub struct AggregateValueBuffer {
104    pub(super) rows: Vec<AggregateValueRecord>,
105    pub(super) runs: Vec<JsonSpillRun>,
106    pub(super) next_sequence: u64,
107    pub(super) budget_bytes: usize,
108    pub(super) memory_bytes: usize,
109    pub(super) comparison_states: Option<std::sync::Arc<[EnumComparisonState]>>,
110    pub(super) key_types: Option<std::sync::Arc<[Option<uqa_sql::ColumnType>]>>,
111}
112
113impl Default for AggregateValueBuffer {
114    fn default() -> Self {
115        Self::new(64 * 1024 * 1024)
116    }
117}
118
119impl AggregateValueBuffer {
120    pub(super) fn new(budget_bytes: usize) -> Self {
121        Self {
122            rows: Vec::new(),
123            runs: Vec::new(),
124            next_sequence: 0,
125            budget_bytes: budget_bytes.max(1),
126            memory_bytes: 0,
127            comparison_states: None,
128            key_types: None,
129        }
130    }
131
132    pub(super) fn push(
133        &mut self,
134        value: Value,
135        sort_keys: Vec<super::ordering::AggregateSortKey>,
136        enums: Option<&dyn EnumLabelCatalog>,
137    ) -> Result<(), SQLError> {
138        if !sort_keys.is_empty()
139            && self.comparison_states.is_none()
140            && enums.is_some_and(EnumLabelCatalog::has_enum_types)
141        {
142            self.comparison_states = Some(
143                (0..sort_keys.len())
144                    .map(|_| EnumComparisonState::default())
145                    .collect(),
146            );
147        }
148        let next_sequence = self
149            .next_sequence
150            .checked_add(1)
151            .ok_or_else(|| SQLError::Internal("aggregate value sequence overflow".into()))?;
152        let record = AggregateValueRecord {
153            value,
154            sort_keys,
155            sequence: self.next_sequence,
156        };
157        let bytes = serde_json::to_vec(&record)
158            .map_err(|error| {
159                SQLError::Internal(format!("failed to size aggregate value: {error}"))
160            })?
161            .len()
162            .checked_add(1)
163            .ok_or_else(|| SQLError::Internal("aggregate value size overflow".into()))?;
164        if !self.rows.is_empty()
165            && self
166                .memory_bytes
167                .checked_add(bytes)
168                .is_none_or(|total| total > self.budget_bytes)
169        {
170            self.flush_run(enums)?;
171        }
172        let next_memory_bytes = self
173            .memory_bytes
174            .checked_add(bytes)
175            .ok_or_else(|| SQLError::Internal("aggregate value size overflow".into()))?;
176        self.rows.push(record);
177        self.memory_bytes = next_memory_bytes;
178        self.next_sequence = next_sequence;
179        // One value is indivisible. It passes through memory once and is
180        // immediately written when its encoding alone exceeds the budget.
181        if self.memory_bytes > self.budget_bytes {
182            self.flush_run(enums)?;
183        }
184        Ok(())
185    }
186
187    pub(super) fn ordered_values(
188        &self,
189        enums: Option<&dyn EnumLabelCatalog>,
190    ) -> Result<Vec<Value>, SQLError> {
191        let capacity = usize::try_from(self.next_sequence).map_err(|_| {
192            SQLError::Internal("aggregate value count exceeds address space".into())
193        })?;
194        let mut values = Vec::new();
195        values.try_reserve_exact(capacity).map_err(|error| {
196            SQLError::Internal(format!(
197                "unable to allocate aggregate result for {capacity} values: {error}"
198            ))
199        })?;
200        self.for_each_ordered(enums, |record| {
201            values.push(record.value);
202            Ok(())
203        })?;
204        Ok(values)
205    }
206
207    pub(super) fn for_each_ordered(
208        &self,
209        enums: Option<&dyn EnumLabelCatalog>,
210        mut visit: impl FnMut(AggregateValueRecord) -> Result<(), SQLError>,
211    ) -> Result<(), SQLError> {
212        let mut memory = self.rows.clone();
213        sort_records(&mut memory, |left, right| {
214            compare_aggregate_value_records_with_catalog(
215                left,
216                right,
217                enums,
218                self.comparison_states.as_deref().unwrap_or_default(),
219                self.key_types.as_deref().unwrap_or_default(),
220            )
221        })?;
222        let mut readers = Vec::with_capacity(self.runs.len() + usize::from(!memory.is_empty()));
223        if !memory.is_empty() {
224            readers.push(AggregateValueRunReader::memory(memory));
225        }
226        for run in &self.runs {
227            readers.push(AggregateValueRunReader::file(run)?);
228        }
229        while let Some((index, _)) = minimum_by(
230            readers
231                .iter()
232                .enumerate()
233                .filter_map(|(index, reader)| reader.current().map(|record| (index, record))),
234            |(_, left), (_, right)| {
235                compare_aggregate_value_records_with_catalog(
236                    left,
237                    right,
238                    enums,
239                    self.comparison_states.as_deref().unwrap_or_default(),
240                    self.key_types.as_deref().unwrap_or_default(),
241                )
242            },
243        )? {
244            visit(readers[index].take_current()?)?;
245        }
246        Ok(())
247    }
248
249    pub(super) fn flush_run(
250        &mut self,
251        enums: Option<&dyn EnumLabelCatalog>,
252    ) -> Result<(), SQLError> {
253        if self.rows.is_empty() {
254            return Ok(());
255        }
256        sort_records(&mut self.rows, |left, right| {
257            compare_aggregate_value_records_with_catalog(
258                left,
259                right,
260                enums,
261                self.comparison_states.as_deref().unwrap_or_default(),
262                self.key_types.as_deref().unwrap_or_default(),
263            )
264        })?;
265        let mut run = uqa_storage::temporary_file::TemporaryFile::new().map_err(|err| {
266            SQLError::Internal(format!("failed to create aggregate spill file: {err}"))
267        })?;
268        let mut max_record_bytes = 0;
269        {
270            let mut writer = BufWriter::new(run.as_file_mut());
271            for row in self.rows.drain(..) {
272                let record_bytes =
273                    write_json_spill_record(&mut writer, &row, "aggregate spill row")?;
274                max_record_bytes = max_record_bytes.max(record_bytes);
275            }
276            writer.flush().map_err(|err| {
277                SQLError::Internal(format!("failed to flush aggregate spill file: {err}"))
278            })?;
279        }
280        run.as_file_mut().seek(SeekFrom::Start(0)).map_err(|err| {
281            SQLError::Internal(format!("failed to rewind aggregate spill file: {err}"))
282        })?;
283        self.runs.push(JsonSpillRun {
284            file: run,
285            max_record_bytes,
286        });
287        self.memory_bytes = 0;
288        if self.runs.len() >= AGGREGATE_MERGE_FAN_IN {
289            let inputs = self
290                .runs
291                .drain(..AGGREGATE_MERGE_FAN_IN)
292                .collect::<Vec<_>>();
293            self.runs.push(merge_aggregate_value_runs_with_catalog(
294                inputs,
295                enums,
296                self.comparison_states.as_deref().unwrap_or_default(),
297                self.key_types.as_deref().unwrap_or_default(),
298            )?);
299        }
300        Ok(())
301    }
302}
303
304pub enum AggregateValueRunReader {
305    Memory {
306        rows: std::vec::IntoIter<AggregateValueRecord>,
307        current: Option<AggregateValueRecord>,
308    },
309    File {
310        reader: BufReader<File>,
311        current: Option<AggregateValueRecord>,
312        max_record_bytes: usize,
313    },
314}
315
316impl AggregateValueRunReader {
317    pub(super) fn memory(rows: Vec<AggregateValueRecord>) -> Self {
318        let mut rows = rows.into_iter();
319        let current = rows.next();
320        Self::Memory { rows, current }
321    }
322
323    pub(super) fn file(run: &JsonSpillRun) -> Result<Self, SQLError> {
324        let file = run.file.reopen().map_err(|error| {
325            SQLError::Internal(format!("failed to reopen aggregate spill file: {error}"))
326        })?;
327        let mut reader = BufReader::new(file);
328        let current = read_aggregate_value_record(&mut reader, run.max_record_bytes)?;
329        Ok(Self::File {
330            reader,
331            current,
332            max_record_bytes: run.max_record_bytes,
333        })
334    }
335
336    pub(super) fn current(&self) -> Option<&AggregateValueRecord> {
337        match self {
338            Self::Memory { current, .. } | Self::File { current, .. } => current.as_ref(),
339        }
340    }
341
342    pub(super) fn take_current(&mut self) -> Result<AggregateValueRecord, SQLError> {
343        match self {
344            Self::Memory { rows, current } => {
345                let record = current
346                    .take()
347                    .ok_or_else(|| SQLError::Internal("aggregate memory run exhausted".into()))?;
348                *current = rows.next();
349                Ok(record)
350            }
351            Self::File {
352                reader,
353                current,
354                max_record_bytes,
355            } => {
356                let record = current
357                    .take()
358                    .ok_or_else(|| SQLError::Internal("aggregate spill run exhausted".into()))?;
359                *current = read_aggregate_value_record(reader, *max_record_bytes)?;
360                Ok(record)
361            }
362        }
363    }
364}
365
366pub fn read_aggregate_value_record(
367    reader: &mut impl std::io::BufRead,
368    max_record_bytes: usize,
369) -> Result<Option<AggregateValueRecord>, SQLError> {
370    let Some(record) =
371        read_bounded_json_spill_record(reader, max_record_bytes, "aggregate spill row")?
372    else {
373        return Ok(None);
374    };
375    serde_json::from_slice(&record).map(Some).map_err(|error| {
376        SQLError::Internal(format!(
377            "failed to deserialize aggregate spill row: {error}"
378        ))
379    })
380}
381
382pub fn merge_aggregate_value_runs(runs: Vec<JsonSpillRun>) -> Result<JsonSpillRun, SQLError> {
383    merge_aggregate_value_runs_with_catalog(runs, None, &[], &[])
384}
385
386fn merge_aggregate_value_runs_with_catalog(
387    runs: Vec<JsonSpillRun>,
388    enums: Option<&dyn EnumLabelCatalog>,
389    states: &[EnumComparisonState],
390    types: &[Option<uqa_sql::ColumnType>],
391) -> Result<JsonSpillRun, SQLError> {
392    let mut readers = runs
393        .iter()
394        .map(AggregateValueRunReader::file)
395        .collect::<Result<Vec<_>, _>>()?;
396    let mut output = uqa_storage::temporary_file::TemporaryFile::new().map_err(|error| {
397        SQLError::Internal(format!("failed to create aggregate merge run: {error}"))
398    })?;
399    let mut max_record_bytes = 0;
400    {
401        let mut writer = BufWriter::new(output.as_file_mut());
402        while let Some((index, _)) = minimum_by(
403            readers
404                .iter()
405                .enumerate()
406                .filter_map(|(index, reader)| reader.current().map(|record| (index, record))),
407            |(_, left), (_, right)| {
408                compare_aggregate_value_records_with_catalog(left, right, enums, states, types)
409            },
410        )? {
411            let record = readers[index].take_current()?;
412            let record_bytes =
413                write_json_spill_record(&mut writer, &record, "aggregate merge row")?;
414            max_record_bytes = max_record_bytes.max(record_bytes);
415        }
416        writer.flush().map_err(|error| {
417            SQLError::Internal(format!("failed to flush aggregate merge run: {error}"))
418        })?;
419    }
420    output
421        .as_file_mut()
422        .seek(SeekFrom::Start(0))
423        .map_err(|error| {
424            SQLError::Internal(format!("failed to rewind aggregate merge run: {error}"))
425        })?;
426    Ok(JsonSpillRun {
427        file: output,
428        max_record_bytes,
429    })
430}
431
432pub fn compare_aggregate_value_records(
433    a: &AggregateValueRecord,
434    b: &AggregateValueRecord,
435) -> Result<Ordering, SQLError> {
436    let ordering = compare_sort_keys(&a.sort_keys, &b.sort_keys)?;
437    Ok(ordering.then_with(|| a.sequence.cmp(&b.sequence)))
438}
439
440fn compare_aggregate_value_records_with_catalog(
441    a: &AggregateValueRecord,
442    b: &AggregateValueRecord,
443    enums: Option<&dyn EnumLabelCatalog>,
444    states: &[EnumComparisonState],
445    types: &[Option<uqa_sql::ColumnType>],
446) -> Result<Ordering, SQLError> {
447    let ordering =
448        compare_sort_keys_with_catalog(&a.sort_keys, &b.sort_keys, enums, states, types)?;
449    Ok(ordering.then_with(|| a.sequence.cmp(&b.sequence)))
450}