Skip to main content

uqa_execution/batch/
physical_row.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Allocation-light physical row fragments and projections.
8
9use super::{
10    concat_lock_origins, Arc, ResultRow, RowLockOrigin, RowSchema, SmallVec, Value,
11    INLINE_ROW_FRAGMENTS, NULL_SLOT, NULL_VALUE,
12};
13
14#[derive(Debug, Clone)]
15pub(super) enum RowFragment {
16    Stored {
17        values: Arc<Vec<Value>>,
18        /// Fragment-local output slot -> stored value slot; absent for contiguous values.
19        projection: Option<Arc<[usize]>>,
20    },
21    /// NULL extension and Boolean presence have no width-sized value storage.
22    Constant { value: &'static Value, width: usize },
23}
24
25impl PartialEq for RowFragment {
26    fn eq(&self, other: &Self) -> bool {
27        match (self, other) {
28            (
29                Self::Stored {
30                    values: left,
31                    projection: lp,
32                },
33                Self::Stored {
34                    values: right,
35                    projection: rp,
36                },
37            ) => left == right && lp == rp,
38            (
39                Self::Constant {
40                    value: left,
41                    width: lw,
42                },
43                Self::Constant {
44                    value: right,
45                    width: rw,
46                },
47            ) => left == right && lw == rw,
48            (Self::Constant { value, width }, Self::Stored { values, projection })
49            | (Self::Stored { values, projection }, Self::Constant { value, width }) => {
50                projection.is_none()
51                    && values.len() == *width
52                    && values.iter().all(|stored| stored == *value)
53            }
54        }
55    }
56}
57
58impl RowFragment {
59    fn contiguous(values: Arc<Vec<Value>>) -> Self {
60        Self::Stored {
61            values,
62            projection: None,
63        }
64    }
65
66    fn projected(values: Arc<Vec<Value>>, projection: Arc<[usize]>) -> Self {
67        debug_assert!(projection
68            .iter()
69            .all(|slot| *slot == NULL_SLOT || *slot < values.len()));
70        let identity = projection.len() == values.len()
71            && projection
72                .iter()
73                .enumerate()
74                .all(|(index, slot)| index == *slot);
75        if identity {
76            Self::contiguous(values)
77        } else {
78            Self::Stored {
79                values,
80                projection: Some(projection),
81            }
82        }
83    }
84
85    pub(super) fn len(&self) -> usize {
86        #[cfg(test)]
87        FRAGMENT_WIDTH_READS.with(|reads| reads.set(reads.get() + 1));
88        match self {
89            Self::Stored { values, projection } => projection
90                .as_ref()
91                .map_or(values.len(), |projection| projection.len()),
92            Self::Constant { width, .. } => *width,
93        }
94    }
95
96    pub(super) fn get(&self, slot: usize) -> Option<&Value> {
97        match self {
98            Self::Constant { value, width } => (slot < *width).then_some(*value),
99            Self::Stored { values, projection } => match projection.as_ref() {
100                Some(projection) => match projection.get(slot).copied()? {
101                    NULL_SLOT => Some(&NULL_VALUE),
102                    stored => values.get(stored),
103                },
104                None => values.get(slot),
105            },
106        }
107    }
108
109    pub(super) fn has_shared_values(&self) -> bool {
110        matches!(self, Self::Stored { values, .. } if Arc::strong_count(values) > 1)
111    }
112
113    pub(super) fn can_copy_directly(&self) -> bool {
114        matches!(self, Self::Constant { .. }) || self.has_shared_values()
115    }
116
117    fn stored_slot(&self, slot: usize) -> Option<usize> {
118        match self {
119            Self::Constant { width, .. } => (slot < *width).then_some(slot),
120            Self::Stored { values, projection } => match projection.as_ref() {
121                Some(projection) => projection.get(slot).copied(),
122                None => (slot < values.len()).then_some(slot),
123            },
124        }
125    }
126
127    fn into_prefix(mut self, width: usize) -> Self {
128        debug_assert!(width <= self.len());
129        if width == self.len() {
130            return self;
131        }
132        match &mut self {
133            Self::Constant { width: old, .. } => *old = width,
134            Self::Stored { values, projection } => {
135                if let Some(slots) = projection.as_ref() {
136                    *projection = Some(Arc::from(&slots[..width]));
137                } else if let Some(values) = Arc::get_mut(values) {
138                    values.truncate(width);
139                } else {
140                    *projection = Some((0..width).collect::<Arc<[usize]>>());
141                }
142            }
143        }
144        self
145    }
146
147    #[cfg(test)]
148    pub(super) fn stored_values(&self) -> &Arc<Vec<Value>> {
149        let Self::Stored { values, .. } = self else {
150            panic!("expected stored fragment")
151        };
152        values
153    }
154
155    #[cfg(test)]
156    pub(super) fn projection(&self) -> Option<&Arc<[usize]>> {
157        match self {
158            Self::Stored { projection, .. } => projection.as_ref(),
159            Self::Constant { .. } => None,
160        }
161    }
162}
163
164pub(super) type RowFragments = SmallVec<[RowFragment; INLINE_ROW_FRAGMENTS]>;
165
166/// A physical row owns no column names. Each fragment is created by a scan or
167/// projection and shared thereafter; joining rows copies only `Arc` handles.
168#[derive(Debug, Clone, Default, PartialEq)]
169pub struct PhysicalRow {
170    pub(super) fragments: RowFragments,
171    pub(super) lock_origins: Option<Arc<Vec<RowLockOrigin>>>,
172}
173
174/// One output position in a mixed physical projection.
175#[derive(Debug, Clone, PartialEq)]
176pub enum RowProjectionValue {
177    /// Reuse one flattened slot from the input row.
178    InputSlot(usize),
179    /// Append a newly computed value.
180    Owned(Value),
181}
182
183impl PhysicalRow {
184    #[cfg(test)]
185    pub(crate) fn count_fragment_width_reads<T>(visit: impl FnOnce() -> T) -> (T, usize) {
186        FRAGMENT_WIDTH_READS.with(|reads| reads.set(0));
187        let output = visit();
188        (output, FRAGMENT_WIDTH_READS.with(std::cell::Cell::get))
189    }
190
191    pub fn from_values(values: Vec<Value>) -> Self {
192        let mut fragments = RowFragments::new();
193        if !values.is_empty() {
194            fragments.push(RowFragment::contiguous(Arc::new(values)));
195        }
196        Self {
197            fragments,
198            lock_origins: None,
199        }
200    }
201
202    /// Build a row by sharing a stored positional value vector and applying a
203    /// fragment-local slot projection. Neither the values nor contained
204    /// strings are cloned.
205    pub fn from_shared_values(values: Arc<Vec<Value>>, projection: Arc<[usize]>) -> Self {
206        let mut fragments = RowFragments::new();
207        if !projection.is_empty() {
208            fragments.push(RowFragment::projected(values, projection));
209        }
210        Self {
211            fragments,
212            lock_origins: None,
213        }
214    }
215
216    pub fn from_result_row(schema: &RowSchema, mut row: ResultRow) -> Self {
217        let values = schema
218            .columns()
219            .iter()
220            .map(|column| row.remove(column).unwrap_or(Value::Null))
221            .collect();
222        Self::from_values(values)
223    }
224
225    pub fn nulls(width: usize) -> Self {
226        Self::constant(&NULL_VALUE, width)
227    }
228
229    pub(crate) fn present() -> Self {
230        Self::constant(&Value::Bool(true), 1)
231    }
232
233    fn constant(value: &'static Value, width: usize) -> Self {
234        let mut fragments = RowFragments::new();
235        if width != 0 {
236            fragments.push(RowFragment::Constant { value, width });
237        }
238        Self {
239            fragments,
240            lock_origins: None,
241        }
242    }
243
244    pub fn append_values(mut self, values: Vec<Value>) -> Self {
245        if !values.is_empty() {
246            self.fragments
247                .push(RowFragment::contiguous(Arc::new(values)));
248        }
249        self
250    }
251
252    pub fn concat(left: &Self, right: &Self) -> Self {
253        let mut fragments =
254            RowFragments::with_capacity(left.fragments.len() + right.fragments.len());
255        fragments.extend(left.fragments.iter().cloned());
256        fragments.extend(right.fragments.iter().cloned());
257        let lock_origins =
258            concat_lock_origins(left.lock_origins.as_ref(), right.lock_origins.as_ref());
259        Self {
260            fragments,
261            lock_origins,
262        }
263    }
264
265    pub fn concat_left_owned(mut left: Self, right: &Self) -> Self {
266        left.fragments.extend(right.fragments.iter().cloned());
267        left.lock_origins =
268            concat_lock_origins(left.lock_origins.as_ref(), right.lock_origins.as_ref());
269        left
270    }
271
272    pub fn concat_right_owned(left: &Self, mut right: Self) -> Self {
273        let mut fragments =
274            RowFragments::with_capacity(left.fragments.len() + right.fragments.len());
275        fragments.extend(left.fragments.iter().cloned());
276        fragments.append(&mut right.fragments);
277        let lock_origins =
278            concat_lock_origins(left.lock_origins.as_ref(), right.lock_origins.as_ref());
279        Self {
280            fragments,
281            lock_origins,
282        }
283    }
284
285    pub(crate) fn value(&self, mut slot: usize) -> Option<&Value> {
286        for fragment in &self.fragments {
287            if slot < fragment.len() {
288                return fragment.get(slot);
289            }
290            slot -= fragment.len();
291        }
292        None
293    }
294
295    /// Visit physical slots once in order, including absent values in malformed projections so the caller can preserve its slot diagnostic.
296    pub(crate) fn values(&self) -> impl Iterator<Item = Option<&Value>> {
297        self.fragments
298            .iter()
299            .flat_map(|fragment| (0..fragment.len()).map(move |slot| fragment.get(slot)))
300    }
301
302    /// Re-express selected flattened slots as a compact positional row while
303    /// sharing the underlying value vectors. Consecutive slots backed by the
304    /// same source fragment share one projection fragment; no `Value` (and in
305    /// particular no string payload) is cloned.
306    pub(crate) fn project_slots(&self, slots: &[usize]) -> Self {
307        let mut output = RowFragments::new();
308        let null = RowFragment::Constant {
309            value: &NULL_VALUE,
310            width: 1,
311        };
312        let null_source = self.fragments.len();
313        let mut current_source = None;
314        let mut current = None;
315        let mut current_width = 0;
316        let mut current_projection = Vec::new();
317        let flush = |output: &mut RowFragments,
318                     fragment: &mut Option<&RowFragment>,
319                     width: usize,
320                     projection: &mut Vec<usize>| {
321            if let Some(fragment) = fragment.take() {
322                output.push(match fragment {
323                    RowFragment::Constant { value, .. } => RowFragment::Constant { value, width },
324                    RowFragment::Stored { values, .. } => RowFragment::projected(
325                        Arc::clone(values),
326                        Arc::from(std::mem::take(projection)),
327                    ),
328                });
329            }
330        };
331        for requested in slots {
332            let mut remaining = *requested;
333            let mut resolved = None;
334            if remaining != NULL_SLOT {
335                for (index, fragment) in self.fragments.iter().enumerate() {
336                    if remaining < fragment.len() {
337                        resolved = fragment
338                            .stored_slot(remaining)
339                            .filter(|slot| *slot != NULL_SLOT)
340                            .map(|slot| (index, fragment, slot));
341                        break;
342                    }
343                    remaining -= fragment.len();
344                }
345            }
346            let (source, fragment, stored) = resolved.unwrap_or((null_source, &null, NULL_SLOT));
347            if current_source != Some(source) {
348                flush(
349                    &mut output,
350                    &mut current,
351                    current_width,
352                    &mut current_projection,
353                );
354                current_source = Some(source);
355                current = Some(fragment);
356                current_width = 0;
357            }
358            current_width += 1;
359            if matches!(fragment, RowFragment::Stored { .. }) {
360                current_projection.push(stored);
361            }
362        }
363        flush(
364            &mut output,
365            &mut current,
366            current_width,
367            &mut current_projection,
368        );
369        Self {
370            fragments: output,
371            lock_origins: self.lock_origins.clone(),
372        }
373    }
374
375    /// Build an output row from shared input slots and newly computed values while preserving their requested order and sharing row metadata.
376    pub fn project_with_values(
377        &self,
378        values: impl IntoIterator<Item = RowProjectionValue>,
379    ) -> Self {
380        fn flush_slots(source: &PhysicalRow, output: &mut RowFragments, slots: &mut Vec<usize>) {
381            if slots.is_empty() {
382                return;
383            }
384            let mut projected = source.project_slots(slots);
385            output.append(&mut projected.fragments);
386            slots.clear();
387        }
388
389        fn flush_owned(output: &mut RowFragments, owned: &mut Vec<Value>) {
390            if owned.is_empty() {
391                return;
392            }
393            output.push(RowFragment::contiguous(Arc::new(std::mem::take(owned))));
394        }
395
396        let mut fragments = RowFragments::new();
397        let mut slots = Vec::new();
398        let mut owned = Vec::new();
399        for value in values {
400            match value {
401                RowProjectionValue::InputSlot(slot) => {
402                    flush_owned(&mut fragments, &mut owned);
403                    slots.push(slot);
404                }
405                RowProjectionValue::Owned(value) => {
406                    flush_slots(self, &mut fragments, &mut slots);
407                    owned.push(value);
408                }
409            }
410        }
411        flush_slots(self, &mut fragments, &mut slots);
412        flush_owned(&mut fragments, &mut owned);
413        Self {
414            fragments,
415            lock_origins: self.lock_origins.clone(),
416        }
417    }
418
419    pub fn fragment_count(&self) -> usize {
420        self.fragments.len()
421    }
422
423    pub(crate) fn into_prefix(self, width: usize) -> Self {
424        let mut remaining = width;
425        let mut fragments = RowFragments::new();
426        for fragment in self.fragments {
427            if remaining == 0 {
428                break;
429            }
430            let fragment_width = fragment.len();
431            if fragment_width <= remaining {
432                fragments.push(fragment);
433                remaining -= fragment_width;
434            } else {
435                fragments.push(fragment.into_prefix(remaining));
436                remaining = 0;
437            }
438        }
439        debug_assert_eq!(remaining, 0, "physical row prefix exceeds row width");
440        Self {
441            fragments,
442            lock_origins: self.lock_origins,
443        }
444    }
445}
446
447#[cfg(test)]
448thread_local! {
449    static FRAGMENT_WIDTH_READS: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
450}