Skip to main content

uqa_execution/mutation/rules/
columns.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Completed required-column metadata retains compact equal runs or bounded spill.
8
9use std::collections::BTreeSet;
10
11use uqa_core::{CancellationToken, Value};
12use uqa_sql::SQLError;
13
14use crate::mutation::prepared::{decode_prepared_doc_id, encode_prepared_doc_id};
15use crate::physical::physical_exec_error;
16use crate::spill::{SharedSpill, SharedSpillReader, SpillBatchWriter, SpillBuffer, SpillRows};
17use crate::{PhysicalRow, RowSchema};
18
19mod selection;
20
21type Columns<const N: usize> = [BTreeSet<String>; N];
22
23/// Complete projection requirements, computed before supplemental SQL evaluation starts.
24pub struct RuleColumnSets<const N: usize> {
25    storage: Storage<N>,
26    count: usize,
27    any: bool,
28    cancellation: CancellationToken,
29}
30
31enum Storage<const N: usize> {
32    Uniform(Columns<N>),
33    Spill(SharedSpill),
34}
35
36impl<const N: usize> RuleColumnSets<N> {
37    pub(super) fn from_rows(
38        input: impl IntoIterator<Item = Result<Columns<N>, SQLError>>,
39        bytes: usize,
40        cancellation: CancellationToken,
41    ) -> Result<Self, SQLError> {
42        let mut rows = SpillBuffer::new(bytes);
43        let mut writer = SpillBatchWriter::new(schema::<N>()).map_err(physical_exec_error)?;
44        let mut pending = None::<(usize, Columns<N>)>;
45        let mut count = 0_usize;
46        let mut any = false;
47        let mut flushed = false;
48        for columns in input {
49            cancellation.check()?;
50            let columns = columns?;
51            count = count
52                .checked_add(1)
53                .ok_or_else(|| invalid("row count overflow"))?;
54            any |= columns.iter().any(|columns| !columns.is_empty());
55            if let Some((length, previous)) = &mut pending {
56                if *previous == columns {
57                    *length += 1;
58                    continue;
59                }
60            }
61            if let Some(run) = pending.take() {
62                writer
63                    .push(&mut rows, encode(run))
64                    .map_err(physical_exec_error)?;
65                flushed = true;
66            }
67            pending = Some((1, columns));
68        }
69        cancellation.check()?;
70        let storage = if flushed {
71            if let Some(run) = pending {
72                writer
73                    .push(&mut rows, encode(run))
74                    .map_err(physical_exec_error)?;
75            }
76            writer.finish(&mut rows).map_err(physical_exec_error)?;
77            Storage::Spill(
78                rows.into_shared(schema::<N>())
79                    .map_err(physical_exec_error)?,
80            )
81        } else {
82            Storage::Uniform(pending.map_or_else(empty, |(_, columns)| columns))
83        };
84        Ok(Self {
85            storage,
86            count,
87            any,
88            cancellation,
89        })
90    }
91
92    pub fn has_required_columns(&self) -> bool {
93        self.any
94    }
95
96    pub fn reader(&self) -> Result<RuleColumnIter<N>, SQLError> {
97        self.cancellation.check()?;
98        let (pending, rows) = match &self.storage {
99            Storage::Uniform(columns) => ((self.count, columns.clone()), None),
100            Storage::Spill(rows) => (
101                (0, empty()),
102                Some(Box::new(rows.read_rows().map_err(physical_exec_error)?)),
103            ),
104        };
105        Ok(RuleColumnIter {
106            pending,
107            rows,
108            remaining: self.count,
109            cancellation: self.cancellation.clone(),
110            finished: false,
111        })
112    }
113}
114
115/// Owned replay remains valid when a batch replaces its original event images.
116pub struct RuleColumnIter<const N: usize> {
117    pending: (usize, Columns<N>),
118    rows: Option<Box<SpillRows<SharedSpillReader>>>,
119    remaining: usize,
120    cancellation: CancellationToken,
121    finished: bool,
122}
123
124impl<const N: usize> RuleColumnIter<N> {
125    fn read_next(&mut self) -> Result<Option<Columns<N>>, SQLError> {
126        self.cancellation.check()?;
127        if self.pending.0 == 0 {
128            if let Some(row) = self.rows.as_mut().and_then(Iterator::next) {
129                self.pending = decode(row.map_err(physical_exec_error)?.row)?;
130                if self.pending.0 > self.remaining {
131                    return Err(invalid("run exceeds the declared row count"));
132                }
133            }
134        }
135        if self.pending.0 == 0 {
136            return if self.remaining == 0 {
137                Ok(None)
138            } else {
139                Err(invalid("missing required-column rows"))
140            };
141        }
142        self.remaining = self
143            .remaining
144            .checked_sub(1)
145            .ok_or_else(|| invalid("more rows than declared"))?;
146        self.pending.0 -= 1;
147        Ok(Some(self.pending.1.clone()))
148    }
149}
150
151impl<const N: usize> Iterator for RuleColumnIter<N> {
152    type Item = Result<Columns<N>, SQLError>;
153
154    fn next(&mut self) -> Option<Self::Item> {
155        if self.finished {
156            return None;
157        }
158        match self.read_next() {
159            Ok(Some(columns)) => Some(Ok(columns)),
160            Ok(None) => {
161                self.finished = true;
162                None
163            }
164            Err(error) => {
165                self.finished = true;
166                Some(Err(error))
167            }
168        }
169    }
170}
171
172fn empty<const N: usize>() -> Columns<N> {
173    std::array::from_fn(|_| BTreeSet::new())
174}
175
176fn schema<const N: usize>() -> RowSchema {
177    RowSchema::new(
178        std::iter::once("count".into())
179            .chain((0..N).map(|side| format!("columns_{side}")))
180            .collect(),
181    )
182}
183
184fn encode<const N: usize>((count, columns): (usize, Columns<N>)) -> PhysicalRow {
185    PhysicalRow::from_values(
186        std::iter::once(encode_prepared_doc_id(count as u64))
187            .chain(
188                columns
189                    .into_iter()
190                    .map(|columns| Value::List(columns.into_iter().map(Value::Str).collect())),
191            )
192            .collect(),
193    )
194}
195
196fn decode<const N: usize>(row: PhysicalRow) -> Result<(usize, Columns<N>), SQLError> {
197    let mut values = row.into_physical_values().into_iter();
198    let count = usize::try_from(decode_prepared_doc_id(
199        values.next().ok_or_else(|| invalid("missing run length"))?,
200        "rewrite-rule required columns",
201    )?)
202    .map_err(|_| invalid("run exceeds the addressable row count"))?;
203    if count == 0 {
204        return Err(invalid("empty run"));
205    }
206    let mut output = empty();
207    for columns in &mut output {
208        let Some(Value::List(names)) = values.next() else {
209            return Err(invalid("invalid column set"));
210        };
211        for name in names {
212            let Value::Str(name) = name else {
213                return Err(invalid("column name is not text"));
214            };
215            if !columns.insert(name) {
216                return Err(invalid("duplicate column name"));
217            }
218        }
219    }
220    if values.next().is_some() {
221        return Err(invalid("invalid record width"));
222    }
223    Ok((count, output))
224}
225
226fn invalid(message: &str) -> SQLError {
227    SQLError::Internal(format!("rewrite-rule required columns: {message}"))
228}
229
230#[cfg(test)]
231mod tests;