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}
111
112impl Default for AggregateValueBuffer {
113    fn default() -> Self {
114        Self::new(64 * 1024 * 1024)
115    }
116}
117
118impl AggregateValueBuffer {
119    pub(super) fn new(budget_bytes: usize) -> Self {
120        Self {
121            rows: Vec::new(),
122            runs: Vec::new(),
123            next_sequence: 0,
124            budget_bytes: budget_bytes.max(1),
125            memory_bytes: 0,
126            comparison_states: None,
127        }
128    }
129
130    pub(super) fn push(
131        &mut self,
132        value: Value,
133        sort_keys: Vec<super::ordering::AggregateSortKey>,
134        enums: Option<&dyn EnumLabelCatalog>,
135    ) -> Result<(), SQLError> {
136        if !sort_keys.is_empty()
137            && self.comparison_states.is_none()
138            && enums.is_some_and(EnumLabelCatalog::has_enum_types)
139        {
140            self.comparison_states = Some(
141                (0..sort_keys.len())
142                    .map(|_| EnumComparisonState::default())
143                    .collect(),
144            );
145        }
146        let next_sequence = self
147            .next_sequence
148            .checked_add(1)
149            .ok_or_else(|| SQLError::Internal("aggregate value sequence overflow".into()))?;
150        let record = AggregateValueRecord {
151            value,
152            sort_keys,
153            sequence: self.next_sequence,
154        };
155        let bytes = serde_json::to_vec(&record)
156            .map_err(|error| {
157                SQLError::Internal(format!("failed to size aggregate value: {error}"))
158            })?
159            .len()
160            .checked_add(1)
161            .ok_or_else(|| SQLError::Internal("aggregate value size overflow".into()))?;
162        if !self.rows.is_empty()
163            && self
164                .memory_bytes
165                .checked_add(bytes)
166                .is_none_or(|total| total > self.budget_bytes)
167        {
168            self.flush_run(enums)?;
169        }
170        let next_memory_bytes = self
171            .memory_bytes
172            .checked_add(bytes)
173            .ok_or_else(|| SQLError::Internal("aggregate value size overflow".into()))?;
174        self.rows.push(record);
175        self.memory_bytes = next_memory_bytes;
176        self.next_sequence = next_sequence;
177        // One value is indivisible. It passes through memory once and is
178        // immediately written when its encoding alone exceeds the budget.
179        if self.memory_bytes > self.budget_bytes {
180            self.flush_run(enums)?;
181        }
182        Ok(())
183    }
184
185    pub(super) fn ordered_values(
186        &self,
187        enums: Option<&dyn EnumLabelCatalog>,
188    ) -> Result<Vec<Value>, SQLError> {
189        let capacity = usize::try_from(self.next_sequence).map_err(|_| {
190            SQLError::Internal("aggregate value count exceeds address space".into())
191        })?;
192        let mut values = Vec::new();
193        values.try_reserve_exact(capacity).map_err(|error| {
194            SQLError::Internal(format!(
195                "unable to allocate aggregate result for {capacity} values: {error}"
196            ))
197        })?;
198        self.for_each_ordered(enums, |record| {
199            values.push(record.value);
200            Ok(())
201        })?;
202        Ok(values)
203    }
204
205    pub(super) fn for_each_ordered(
206        &self,
207        enums: Option<&dyn EnumLabelCatalog>,
208        mut visit: impl FnMut(AggregateValueRecord) -> Result<(), SQLError>,
209    ) -> Result<(), SQLError> {
210        let mut memory = self.rows.clone();
211        sort_records(&mut memory, |left, right| {
212            compare_aggregate_value_records_with_catalog(
213                left,
214                right,
215                enums,
216                self.comparison_states.as_deref().unwrap_or_default(),
217            )
218        })?;
219        let mut readers = Vec::with_capacity(self.runs.len() + usize::from(!memory.is_empty()));
220        if !memory.is_empty() {
221            readers.push(AggregateValueRunReader::memory(memory));
222        }
223        for run in &self.runs {
224            readers.push(AggregateValueRunReader::file(run)?);
225        }
226        while let Some((index, _)) = minimum_by(
227            readers
228                .iter()
229                .enumerate()
230                .filter_map(|(index, reader)| reader.current().map(|record| (index, record))),
231            |(_, left), (_, right)| {
232                compare_aggregate_value_records_with_catalog(
233                    left,
234                    right,
235                    enums,
236                    self.comparison_states.as_deref().unwrap_or_default(),
237                )
238            },
239        )? {
240            visit(readers[index].take_current()?)?;
241        }
242        Ok(())
243    }
244
245    pub(super) fn flush_run(
246        &mut self,
247        enums: Option<&dyn EnumLabelCatalog>,
248    ) -> Result<(), SQLError> {
249        if self.rows.is_empty() {
250            return Ok(());
251        }
252        sort_records(&mut self.rows, |left, right| {
253            compare_aggregate_value_records_with_catalog(
254                left,
255                right,
256                enums,
257                self.comparison_states.as_deref().unwrap_or_default(),
258            )
259        })?;
260        let mut run = uqa_storage::temporary_file::TemporaryFile::new().map_err(|err| {
261            SQLError::Internal(format!("failed to create aggregate spill file: {err}"))
262        })?;
263        let mut max_record_bytes = 0;
264        {
265            let mut writer = BufWriter::new(run.as_file_mut());
266            for row in self.rows.drain(..) {
267                let record_bytes =
268                    write_json_spill_record(&mut writer, &row, "aggregate spill row")?;
269                max_record_bytes = max_record_bytes.max(record_bytes);
270            }
271            writer.flush().map_err(|err| {
272                SQLError::Internal(format!("failed to flush aggregate spill file: {err}"))
273            })?;
274        }
275        run.as_file_mut().seek(SeekFrom::Start(0)).map_err(|err| {
276            SQLError::Internal(format!("failed to rewind aggregate spill file: {err}"))
277        })?;
278        self.runs.push(JsonSpillRun {
279            file: run,
280            max_record_bytes,
281        });
282        self.memory_bytes = 0;
283        if self.runs.len() >= AGGREGATE_MERGE_FAN_IN {
284            let inputs = self
285                .runs
286                .drain(..AGGREGATE_MERGE_FAN_IN)
287                .collect::<Vec<_>>();
288            self.runs.push(merge_aggregate_value_runs_with_catalog(
289                inputs,
290                enums,
291                self.comparison_states.as_deref().unwrap_or_default(),
292            )?);
293        }
294        Ok(())
295    }
296}
297
298pub enum AggregateValueRunReader {
299    Memory {
300        rows: std::vec::IntoIter<AggregateValueRecord>,
301        current: Option<AggregateValueRecord>,
302    },
303    File {
304        reader: BufReader<File>,
305        current: Option<AggregateValueRecord>,
306        max_record_bytes: usize,
307    },
308}
309
310impl AggregateValueRunReader {
311    pub(super) fn memory(rows: Vec<AggregateValueRecord>) -> Self {
312        let mut rows = rows.into_iter();
313        let current = rows.next();
314        Self::Memory { rows, current }
315    }
316
317    pub(super) fn file(run: &JsonSpillRun) -> Result<Self, SQLError> {
318        let file = run.file.reopen().map_err(|error| {
319            SQLError::Internal(format!("failed to reopen aggregate spill file: {error}"))
320        })?;
321        let mut reader = BufReader::new(file);
322        let current = read_aggregate_value_record(&mut reader, run.max_record_bytes)?;
323        Ok(Self::File {
324            reader,
325            current,
326            max_record_bytes: run.max_record_bytes,
327        })
328    }
329
330    pub(super) fn current(&self) -> Option<&AggregateValueRecord> {
331        match self {
332            Self::Memory { current, .. } | Self::File { current, .. } => current.as_ref(),
333        }
334    }
335
336    pub(super) fn take_current(&mut self) -> Result<AggregateValueRecord, SQLError> {
337        match self {
338            Self::Memory { rows, current } => {
339                let record = current
340                    .take()
341                    .ok_or_else(|| SQLError::Internal("aggregate memory run exhausted".into()))?;
342                *current = rows.next();
343                Ok(record)
344            }
345            Self::File {
346                reader,
347                current,
348                max_record_bytes,
349            } => {
350                let record = current
351                    .take()
352                    .ok_or_else(|| SQLError::Internal("aggregate spill run exhausted".into()))?;
353                *current = read_aggregate_value_record(reader, *max_record_bytes)?;
354                Ok(record)
355            }
356        }
357    }
358}
359
360pub fn read_aggregate_value_record(
361    reader: &mut impl std::io::BufRead,
362    max_record_bytes: usize,
363) -> Result<Option<AggregateValueRecord>, SQLError> {
364    let Some(record) =
365        read_bounded_json_spill_record(reader, max_record_bytes, "aggregate spill row")?
366    else {
367        return Ok(None);
368    };
369    serde_json::from_slice(&record).map(Some).map_err(|error| {
370        SQLError::Internal(format!(
371            "failed to deserialize aggregate spill row: {error}"
372        ))
373    })
374}
375
376pub fn merge_aggregate_value_runs(runs: Vec<JsonSpillRun>) -> Result<JsonSpillRun, SQLError> {
377    merge_aggregate_value_runs_with_catalog(runs, None, &[])
378}
379
380fn merge_aggregate_value_runs_with_catalog(
381    runs: Vec<JsonSpillRun>,
382    enums: Option<&dyn EnumLabelCatalog>,
383    states: &[EnumComparisonState],
384) -> Result<JsonSpillRun, SQLError> {
385    let mut readers = runs
386        .iter()
387        .map(AggregateValueRunReader::file)
388        .collect::<Result<Vec<_>, _>>()?;
389    let mut output = uqa_storage::temporary_file::TemporaryFile::new().map_err(|error| {
390        SQLError::Internal(format!("failed to create aggregate merge run: {error}"))
391    })?;
392    let mut max_record_bytes = 0;
393    {
394        let mut writer = BufWriter::new(output.as_file_mut());
395        while let Some((index, _)) = minimum_by(
396            readers
397                .iter()
398                .enumerate()
399                .filter_map(|(index, reader)| reader.current().map(|record| (index, record))),
400            |(_, left), (_, right)| {
401                compare_aggregate_value_records_with_catalog(left, right, enums, states)
402            },
403        )? {
404            let record = readers[index].take_current()?;
405            let record_bytes =
406                write_json_spill_record(&mut writer, &record, "aggregate merge row")?;
407            max_record_bytes = max_record_bytes.max(record_bytes);
408        }
409        writer.flush().map_err(|error| {
410            SQLError::Internal(format!("failed to flush aggregate merge run: {error}"))
411        })?;
412    }
413    output
414        .as_file_mut()
415        .seek(SeekFrom::Start(0))
416        .map_err(|error| {
417            SQLError::Internal(format!("failed to rewind aggregate merge run: {error}"))
418        })?;
419    Ok(JsonSpillRun {
420        file: output,
421        max_record_bytes,
422    })
423}
424
425pub fn compare_aggregate_value_records(
426    a: &AggregateValueRecord,
427    b: &AggregateValueRecord,
428) -> Result<Ordering, SQLError> {
429    let ordering = compare_sort_keys(&a.sort_keys, &b.sort_keys)?;
430    Ok(ordering.then_with(|| a.sequence.cmp(&b.sequence)))
431}
432
433fn compare_aggregate_value_records_with_catalog(
434    a: &AggregateValueRecord,
435    b: &AggregateValueRecord,
436    enums: Option<&dyn EnumLabelCatalog>,
437    states: &[EnumComparisonState],
438) -> Result<Ordering, SQLError> {
439    let ordering = compare_sort_keys_with_catalog(&a.sort_keys, &b.sort_keys, enums, states)?;
440    Ok(ordering.then_with(|| a.sequence.cmp(&b.sequence)))
441}