oxisql_parse/optimizer/
limit.rs

1//! Pass 4: Limit push-through.
2//!
3//! Push a `Limit` node down into a single-table `Scan` when there are no
4//! aggregations or joins between the limit and the scan.  This allows
5//! the execution engine to stop reading rows early at the storage level.
6//!
7//! The pushed limit is stored in `Scan.limit`.  If a `Scan` already carries a
8//! limit (from a previous pass or a nested query), the more restrictive value
9//! is kept.
10
11use crate::LogicalPlan;
12
13use super::OptPass;
14
15// ── Public struct ─────────────────────────────────────────────────────────────
16
17/// Push a `Limit` node down into a single-table `Scan`.
18pub struct LimitPushThrough;
19
20impl OptPass for LimitPushThrough {
21    fn name(&self) -> &'static str {
22        "LimitPushThrough"
23    }
24
25    fn apply(&self, plan: LogicalPlan) -> LogicalPlan {
26        push_limit(plan)
27    }
28}
29
30// ── Implementation ────────────────────────────────────────────────────────────
31
32pub(super) fn push_limit(plan: LogicalPlan) -> LogicalPlan {
33    match plan {
34        LogicalPlan::Limit {
35            input,
36            count,
37            offset,
38        } => {
39            let inner = push_limit(*input);
40            // Only push when: count is specified, no offset, and the sub-tree
41            // leads to a single scan with no aggregation or join.
42            if let Some(n) = count {
43                if offset.is_none() && can_push_limit_into(&inner) {
44                    return inject_limit(inner, n);
45                }
46            }
47            LogicalPlan::Limit {
48                input: Box::new(inner),
49                count,
50                offset,
51            }
52        }
53        LogicalPlan::Project { input, columns } => LogicalPlan::Project {
54            input: Box::new(push_limit(*input)),
55            columns,
56        },
57        LogicalPlan::Filter { input, predicate } => LogicalPlan::Filter {
58            input: Box::new(push_limit(*input)),
59            predicate,
60        },
61        LogicalPlan::Sort { input, order_by } => LogicalPlan::Sort {
62            input: Box::new(push_limit(*input)),
63            order_by,
64        },
65        // Do not push through aggregations or joins — semantics differ.
66        other => other,
67    }
68}
69
70/// Returns `true` when the plan is a simple path to a single scan with no
71/// aggregations or joins.
72fn can_push_limit_into(plan: &LogicalPlan) -> bool {
73    match plan {
74        LogicalPlan::Scan { .. } => true,
75        LogicalPlan::Filter { input, .. }
76        | LogicalPlan::Project { input, .. }
77        | LogicalPlan::Sort { input, .. }
78        | LogicalPlan::Limit { input, .. } => can_push_limit_into(input),
79        LogicalPlan::Aggregate { .. }
80        | LogicalPlan::Join { .. }
81        | LogicalPlan::Values { .. }
82        | LogicalPlan::Empty
83        | LogicalPlan::SetOp { .. }
84        | LogicalPlan::Cte { .. }
85        | LogicalPlan::CteRef { .. }
86        | LogicalPlan::Window { .. }
87        | LogicalPlan::Subquery { .. }
88        | LogicalPlan::Exists { .. }
89        | LogicalPlan::InSubquery { .. }
90        | LogicalPlan::Compute { .. } => false,
91    }
92}
93
94/// Inject `limit` into the deepest `Scan` reachable through filter/project/sort
95/// nodes.
96fn inject_limit(plan: LogicalPlan, limit: u64) -> LogicalPlan {
97    match plan {
98        LogicalPlan::Scan {
99            table,
100            alias,
101            limit: existing,
102        } => {
103            // Take the more restrictive limit.
104            let new_limit = match existing {
105                Some(e) => Some(e.min(limit as usize)),
106                None => Some(limit as usize),
107            };
108            LogicalPlan::Scan {
109                table,
110                alias,
111                limit: new_limit,
112            }
113        }
114        LogicalPlan::Filter { input, predicate } => LogicalPlan::Filter {
115            input: Box::new(inject_limit(*input, limit)),
116            predicate,
117        },
118        LogicalPlan::Project { input, columns } => LogicalPlan::Project {
119            input: Box::new(inject_limit(*input, limit)),
120            columns,
121        },
122        LogicalPlan::Sort { input, order_by } => LogicalPlan::Sort {
123            input: Box::new(inject_limit(*input, limit)),
124            order_by,
125        },
126        other => other,
127    }
128}
oxisql_parse/optimizer/limit.rs

oxisql_parse/optimizer/
limit.rs
