Skip to main content

uqa_execution/relational/
limit.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Streaming LIMIT/OFFSET, including ordered `FETCH ... WITH TIES`.
8
9use super::{
10    equal_typed_sort_key_values, BackwardScanSupport, Batch, ExecError, ExecResult,
11    PhysicalOperator, PhysicalScanDirection, RowSchema, ScalarExpr, SharedExpressionEvaluator,
12    SortKey, Value,
13};
14use crate::PhysicalRow;
15
16struct WithTies<'a> {
17    keys: crate::scalar::PreparedExpressions<Vec<SortKey>>,
18    types: Vec<Option<uqa_sql::ColumnType>>,
19    evaluator: SharedExpressionEvaluator<'a>,
20    boundary: Option<Vec<Value>>,
21    finished: bool,
22}
23
24#[derive(Clone, Copy)]
25enum DirectionalLimitState {
26    Initial,
27    Rescan,
28    Empty,
29    InWindow,
30    SubplanEof,
31    WindowEnd,
32    WindowEndTies,
33    WindowStart,
34}
35
36pub struct Limit<'a> {
37    child: Box<dyn PhysicalOperator + 'a>,
38    input_pending: crate::physical::demand::PendingRows,
39    offset: u64,
40    limit: Option<u64>,
41    skipped: u64,
42    emitted: u64,
43    schema: RowSchema,
44    with_ties: Option<WithTies<'a>>,
45    directional_state: DirectionalLimitState,
46    directional_position: u64,
47    directional_current: Option<PhysicalRow>,
48}
49
50impl<'a> Limit<'a> {
51    pub fn new(child: Box<dyn PhysicalOperator + 'a>, offset: u64, limit: Option<u64>) -> Self {
52        let schema = child.row_schema().clone();
53        Self {
54            child,
55            input_pending: crate::physical::demand::PendingRows::default(),
56            offset,
57            limit,
58            skipped: 0,
59            emitted: 0,
60            schema,
61            with_ties: None,
62            directional_state: DirectionalLimitState::Initial,
63            directional_position: 0,
64            directional_current: None,
65        }
66    }
67
68    /// Build an ordered `FETCH ... WITH TIES` boundary. The caller must pass the complete effective `ORDER BY` key list and a non-null row count.
69    pub fn with_ties(
70        child: Box<dyn PhysicalOperator + 'a>,
71        offset: u64,
72        limit: u64,
73        mut keys: Vec<SortKey>,
74        evaluator: SharedExpressionEvaluator<'a>,
75    ) -> Self {
76        let schema = child.row_schema().clone();
77        for key in &mut keys {
78            let expression = std::mem::replace(&mut key.expr, ScalarExpr::Literal(Value::Null));
79            key.expr = evaluator.bind_type_introspection(expression, &schema);
80        }
81        Self {
82            child,
83            input_pending: crate::physical::demand::PendingRows::default(),
84            offset,
85            limit: Some(limit),
86            skipped: 0,
87            emitted: 0,
88            schema,
89            with_ties: Some(WithTies {
90                keys: crate::scalar::PreparedExpressions::sort_keys(keys),
91                types: Vec::new(),
92                evaluator,
93                boundary: None,
94                finished: false,
95            }),
96            directional_state: DirectionalLimitState::Initial,
97            directional_position: 0,
98            directional_current: None,
99        }
100    }
101
102    fn reset_directional_state(&mut self) {
103        self.directional_state = DirectionalLimitState::Rescan;
104        self.directional_position = 0;
105        self.directional_current = None;
106        if let Some(with_ties) = self.with_ties.as_mut() {
107            with_ties.boundary = None;
108            with_ties.finished = false;
109        }
110    }
111
112    fn child_row(&mut self, direction: PhysicalScanDirection) -> ExecResult<Option<PhysicalRow>> {
113        let Some(batch) = self.child.next_direction(direction)? else {
114            return Ok(None);
115        };
116        if batch.schema != self.schema {
117            return Err(ExecError::Other(format!(
118                "directional LIMIT input schema mismatch: expected {:?}, got {:?}",
119                self.schema, batch.schema
120            )));
121        }
122        let mut rows = batch.rows.into_iter();
123        let row = rows.next();
124        if rows.next().is_some() {
125            return Err(ExecError::Other(
126                "directional LIMIT input returned more than one row".into(),
127            ));
128        }
129        Ok(row)
130    }
131
132    fn capture_tie_boundary(&mut self, row: &PhysicalRow) -> ExecResult<()> {
133        let Some(with_ties) = self.with_ties.as_mut() else {
134            return Ok(());
135        };
136        with_ties.boundary = Some(
137            with_ties
138                .keys
139                .iter()
140                .map(|key| {
141                    with_ties.evaluator.evaluate_physical_with_function_states(
142                        &key.expr,
143                        &self.schema,
144                        row,
145                        with_ties.keys.calls(),
146                    )
147                })
148                .collect::<ExecResult<Vec<_>>>()?,
149        );
150        Ok(())
151    }
152
153    fn tie_matches(&self, row: &PhysicalRow) -> ExecResult<bool> {
154        let with_ties = self
155            .with_ties
156            .as_ref()
157            .ok_or_else(|| ExecError::Other("LIMIT tie state is absent".into()))?;
158        let values = with_ties
159            .keys
160            .iter()
161            .map(|key| {
162                with_ties.evaluator.evaluate_physical_with_function_states(
163                    &key.expr,
164                    &self.schema,
165                    row,
166                    with_ties.keys.calls(),
167                )
168            })
169            .collect::<ExecResult<Vec<_>>>()?;
170        let boundary = with_ties
171            .boundary
172            .as_ref()
173            .ok_or_else(|| ExecError::Other("LIMIT tie boundary is absent".into()))?;
174        equal_typed_sort_key_values(
175            boundary,
176            &values,
177            &with_ties.types,
178            with_ties.evaluator.enum_labels(),
179        )
180    }
181
182    fn directional_batch(&self, row: PhysicalRow) -> Batch {
183        Batch::from_physical_rows(self.schema.clone(), vec![row])
184    }
185
186    #[expect(
187        clippy::too_many_lines,
188        reason = "mirrors PostgreSQL's directional LIMIT state machine"
189    )]
190    fn next_directional(&mut self, direction: PhysicalScanDirection) -> ExecResult<Option<Batch>> {
191        if matches!(self.directional_state, DirectionalLimitState::Initial) {
192            self.reset_directional_state();
193        }
194        loop {
195            match self.directional_state {
196                DirectionalLimitState::Initial => unreachable!(),
197                DirectionalLimitState::Rescan => {
198                    if direction == PhysicalScanDirection::Backward {
199                        return Ok(None);
200                    }
201                    if self.limit == Some(0) {
202                        self.directional_state = DirectionalLimitState::Empty;
203                        return Ok(None);
204                    }
205                    loop {
206                        let Some(row) = self.child_row(PhysicalScanDirection::Forward)? else {
207                            self.directional_state = DirectionalLimitState::Empty;
208                            return Ok(None);
209                        };
210                        if self.with_ties.is_some()
211                            && self.limit.is_some_and(|limit| {
212                                self.directional_position.saturating_sub(self.offset)
213                                    == limit.saturating_sub(1)
214                            })
215                        {
216                            self.capture_tie_boundary(&row)?;
217                        }
218                        self.directional_current = Some(row.clone());
219                        self.directional_position = self
220                            .directional_position
221                            .checked_add(1)
222                            .ok_or_else(|| ExecError::Other("LIMIT position overflow".into()))?;
223                        if self.directional_position > self.offset {
224                            self.directional_state = DirectionalLimitState::InWindow;
225                            return Ok(Some(self.directional_batch(row)));
226                        }
227                    }
228                }
229                DirectionalLimitState::Empty => return Ok(None),
230                DirectionalLimitState::InWindow => {
231                    if direction == PhysicalScanDirection::Forward {
232                        if self.limit.is_some_and(|limit| {
233                            self.directional_position.saturating_sub(self.offset) >= limit
234                        }) {
235                            if self.with_ties.is_none() {
236                                self.directional_state = DirectionalLimitState::WindowEnd;
237                                return Ok(None);
238                            }
239                            self.directional_state = DirectionalLimitState::WindowEndTies;
240                            continue;
241                        }
242                        let Some(row) = self.child_row(PhysicalScanDirection::Forward)? else {
243                            self.directional_state = DirectionalLimitState::SubplanEof;
244                            return Ok(None);
245                        };
246                        if self.with_ties.is_some()
247                            && self.limit.is_some_and(|limit| {
248                                self.directional_position.saturating_sub(self.offset)
249                                    == limit.saturating_sub(1)
250                            })
251                        {
252                            self.capture_tie_boundary(&row)?;
253                        }
254                        self.directional_current = Some(row.clone());
255                        self.directional_position = self
256                            .directional_position
257                            .checked_add(1)
258                            .ok_or_else(|| ExecError::Other("LIMIT position overflow".into()))?;
259                        return Ok(Some(self.directional_batch(row)));
260                    }
261                    if self.directional_position <= self.offset.saturating_add(1) {
262                        self.directional_state = DirectionalLimitState::WindowStart;
263                        return Ok(None);
264                    }
265                    let row = self
266                        .child_row(PhysicalScanDirection::Backward)?
267                        .ok_or_else(|| {
268                            ExecError::Other("LIMIT input failed to scan backwards".into())
269                        })?;
270                    self.directional_current = Some(row.clone());
271                    self.directional_position -= 1;
272                    return Ok(Some(self.directional_batch(row)));
273                }
274                DirectionalLimitState::WindowEndTies => {
275                    if direction == PhysicalScanDirection::Forward {
276                        let Some(row) = self.child_row(PhysicalScanDirection::Forward)? else {
277                            self.directional_state = DirectionalLimitState::SubplanEof;
278                            return Ok(None);
279                        };
280                        if self.tie_matches(&row)? {
281                            self.directional_current = Some(row.clone());
282                            self.directional_position =
283                                self.directional_position.checked_add(1).ok_or_else(|| {
284                                    ExecError::Other("LIMIT position overflow".into())
285                                })?;
286                            return Ok(Some(self.directional_batch(row)));
287                        }
288                        self.directional_state = DirectionalLimitState::WindowEnd;
289                        return Ok(None);
290                    }
291                    if self.directional_position <= self.offset.saturating_add(1) {
292                        self.directional_state = DirectionalLimitState::WindowStart;
293                        return Ok(None);
294                    }
295                    let row = self
296                        .child_row(PhysicalScanDirection::Backward)?
297                        .ok_or_else(|| {
298                            ExecError::Other("LIMIT input failed to scan backwards".into())
299                        })?;
300                    self.directional_current = Some(row.clone());
301                    self.directional_position -= 1;
302                    self.directional_state = DirectionalLimitState::InWindow;
303                    return Ok(Some(self.directional_batch(row)));
304                }
305                DirectionalLimitState::SubplanEof => {
306                    if direction == PhysicalScanDirection::Forward {
307                        return Ok(None);
308                    }
309                    let row = self
310                        .child_row(PhysicalScanDirection::Backward)?
311                        .ok_or_else(|| {
312                            ExecError::Other("LIMIT input failed to leave end position".into())
313                        })?;
314                    self.directional_current = Some(row.clone());
315                    self.directional_state = DirectionalLimitState::InWindow;
316                    return Ok(Some(self.directional_batch(row)));
317                }
318                DirectionalLimitState::WindowEnd => {
319                    if direction == PhysicalScanDirection::Forward {
320                        return Ok(None);
321                    }
322                    let row = if self.with_ties.is_some() {
323                        self.child_row(PhysicalScanDirection::Backward)?
324                            .ok_or_else(|| {
325                                ExecError::Other("LIMIT input failed to leave tie boundary".into())
326                            })?
327                    } else {
328                        self.directional_current.clone().ok_or_else(|| {
329                            ExecError::Other("LIMIT window has no current row".into())
330                        })?
331                    };
332                    self.directional_current = Some(row.clone());
333                    self.directional_state = DirectionalLimitState::InWindow;
334                    return Ok(Some(self.directional_batch(row)));
335                }
336                DirectionalLimitState::WindowStart => {
337                    if direction == PhysicalScanDirection::Backward {
338                        return Ok(None);
339                    }
340                    let row = self.directional_current.clone().ok_or_else(|| {
341                        ExecError::Other("LIMIT window has no current row".into())
342                    })?;
343                    self.directional_state = DirectionalLimitState::InWindow;
344                    return Ok(Some(self.directional_batch(row)));
345                }
346            }
347        }
348    }
349}
350
351impl PhysicalOperator for Limit<'_> {
352    fn row_schema(&self) -> &RowSchema {
353        &self.schema
354    }
355
356    fn output_ordering(&self) -> &[crate::PhysicalOrder] {
357        self.child.output_ordering()
358    }
359
360    fn backward_scan_support(&self) -> BackwardScanSupport {
361        if self.child.backward_scan_support() == BackwardScanSupport::Native {
362            BackwardScanSupport::Native
363        } else {
364            BackwardScanSupport::Unsupported
365        }
366    }
367
368    fn open(&mut self) -> ExecResult<()> {
369        self.input_pending.clear();
370        self.skipped = 0;
371        self.emitted = 0;
372        if let Some(with_ties) = self.with_ties.as_mut() {
373            with_ties.boundary = None;
374            with_ties.types = Vec::new();
375            with_ties.finished = false;
376        }
377        self.directional_state = DirectionalLimitState::Initial;
378        self.directional_position = 0;
379        self.directional_current = None;
380        if self.limit == Some(0) {
381            return Ok(());
382        }
383        if let Some(with_ties) = self.with_ties.as_mut() {
384            with_ties.types = with_ties
385                .keys
386                .iter()
387                .map(|key| with_ties.evaluator.expression_type(&key.expr, &self.schema))
388                .collect::<Result<_, _>>()?;
389        }
390        self.child.open()
391    }
392
393    fn next(&mut self) -> ExecResult<Option<Batch>> {
394        self.pull(None)
395    }
396    fn next_with_demand(&mut self, rows: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
397        self.pull(Some(rows))
398    }
399
400    fn next_direction(&mut self, direction: PhysicalScanDirection) -> ExecResult<Option<Batch>> {
401        self.next_directional(direction)
402    }
403
404    fn rewind(&mut self) -> ExecResult<()> {
405        self.input_pending.clear();
406        self.reset_directional_state();
407        self.child.rewind()
408    }
409
410    fn close(&mut self) -> ExecResult<()> {
411        self.input_pending.clear();
412        self.directional_current = None;
413        if let Some(with_ties) = self.with_ties.as_mut() {
414            with_ties.boundary = None;
415            with_ties.types = Vec::new();
416        }
417        self.child.close()
418    }
419}
420
421impl Limit<'_> {
422    fn pull(&mut self, demand: Option<std::num::NonZeroUsize>) -> ExecResult<Option<Batch>> {
423        if self.limit == Some(0)
424            || self
425                .with_ties
426                .as_ref()
427                .is_some_and(|with_ties| with_ties.finished)
428            || self.with_ties.is_none() && self.limit.is_some_and(|limit| self.emitted >= limit)
429        {
430            return Ok(None);
431        }
432        loop {
433            let remaining = self.limit.map(|limit| limit.saturating_sub(self.emitted));
434            let requested = demand.map(|rows| rows.get() as u64);
435            let output = match (remaining, requested) {
436                (Some(0), _) if self.with_ties.is_some() => Some(1),
437                (Some(remaining), Some(requested)) => Some(remaining.min(requested)),
438                (remaining, requested) => remaining.or(requested),
439            };
440            let input = output.map(|output| {
441                let count = output
442                    .saturating_add(self.offset.saturating_sub(self.skipped))
443                    .min(crate::batch::DEFAULT_BATCH_SIZE as u64)
444                    .max(1) as usize;
445                std::num::NonZeroUsize::new(count).expect("positive input quota")
446            });
447            let Some(batch) = self.input_pending.pull(self.child.as_mut(), input)? else {
448                return Ok(None);
449            };
450            let mut buf = Vec::new();
451            for row in batch.rows {
452                if self.skipped < self.offset {
453                    self.skipped += 1;
454                    continue;
455                }
456                if let Some(lim) = self.limit {
457                    if self.emitted >= lim {
458                        let Some(with_ties) = self.with_ties.as_mut() else {
459                            return if buf.is_empty() {
460                                Ok(None)
461                            } else {
462                                Ok(Some(Batch::from_physical_rows(self.schema.clone(), buf)))
463                            };
464                        };
465                        let values = with_ties
466                            .keys
467                            .iter()
468                            .map(|key| {
469                                with_ties.evaluator.evaluate_physical_with_function_states(
470                                    &key.expr,
471                                    &self.schema,
472                                    &row,
473                                    with_ties.keys.calls(),
474                                )
475                            })
476                            .collect::<ExecResult<Vec<_>>>()?;
477                        let boundary = with_ties.boundary.as_ref().ok_or_else(|| {
478                            crate::ExecError::Other(
479                                "WITH TIES boundary was not captured".to_string(),
480                            )
481                        })?;
482                        if !equal_typed_sort_key_values(
483                            boundary,
484                            &values,
485                            &with_ties.types,
486                            with_ties.evaluator.enum_labels(),
487                        )? {
488                            with_ties.finished = true;
489                            return if buf.is_empty() {
490                                Ok(None)
491                            } else {
492                                Ok(Some(Batch::from_physical_rows(self.schema.clone(), buf)))
493                            };
494                        }
495                    } else if self.with_ties.is_some() && self.emitted + 1 == lim {
496                        let with_ties = self.with_ties.as_mut().expect("checked above");
497                        with_ties.boundary = Some(
498                            with_ties
499                                .keys
500                                .iter()
501                                .map(|key| {
502                                    with_ties.evaluator.evaluate_physical_with_function_states(
503                                        &key.expr,
504                                        &self.schema,
505                                        &row,
506                                        with_ties.keys.calls(),
507                                    )
508                                })
509                                .collect::<ExecResult<Vec<_>>>()?,
510                        );
511                    }
512                }
513                buf.push(row);
514                self.emitted += 1;
515            }
516            if !buf.is_empty() {
517                return Ok(Some(Batch::from_physical_rows(self.schema.clone(), buf)));
518            }
519        }
520    }
521}