uqa_execution/relational/
limit.rs1use 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 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}