cynos_query/optimizer/
mod.rs

1//! Query optimizer module.
2
3mod and_predicate;
4mod cross_product;
5mod get_row_count;
6mod implicit_joins;
7mod index_join;
8mod index_selection;
9mod join_reorder;
10mod limit_skip_by_index;
11mod multi_column_or;
12mod not_simplification;
13mod order_by_index;
14mod outer_join_simplification;
15mod pass;
16mod predicate_pushdown;
17mod topn_pushdown;
18
19pub use and_predicate::AndPredicatePass;
20pub use cross_product::CrossProductPass;
21pub use get_row_count::{GetRowCountPass, GetRowCountPlan};
22pub use implicit_joins::ImplicitJoinsPass;
23pub use index_join::IndexJoinPass;
24pub use index_selection::IndexSelection;
25pub use join_reorder::JoinReorder;
26pub use limit_skip_by_index::LimitSkipByIndexPass;
27pub use multi_column_or::{MultiColumnOrConfig, MultiColumnOrPass};
28pub use not_simplification::NotSimplification;
29pub use order_by_index::OrderByIndexPass;
30pub use outer_join_simplification::OuterJoinSimplification;
31pub use pass::OptimizerPass;
32pub use predicate_pushdown::PredicatePushdown;
33pub use topn_pushdown::TopNPushdown;
34
35use crate::planner::{JoinAlgorithm, LogicalPlan, PhysicalPlan};
36use alloc::boxed::Box;
37use alloc::string::{String, ToString};
38use alloc::vec::Vec;
39use cynos_core::Value;
40
41/// Query optimizer that applies optimization passes.
42pub struct Optimizer {
43    passes: Vec<Box<dyn OptimizerPass>>,
44}
45
46impl Default for Optimizer {
47    fn default() -> Self {
48        Self::new()
49    }
50}
51
52impl Optimizer {
53    /// Creates a new optimizer with default passes.
54    ///
55    /// The default passes are applied in this order:
56    /// 1. NotSimplification - Simplify NOT expressions (double negation, De Morgan)
57    /// 2. AndPredicatePass - Break down AND predicates into chained filters
58    /// 3. CrossProductPass - Convert multi-way cross products to binary tree
59    /// 4. ImplicitJoinsPass - Convert CrossProduct + Filter to Join
60    /// 5. OuterJoinSimplification - Convert outer joins to inner when WHERE rejects NULL
61    /// 6. PredicatePushdown - Push filters down the plan tree
62    /// 7. JoinReorder - Reorder joins for better performance
63    ///
64    /// Note: IndexSelection is not included by default because it requires
65    /// ExecutionContext with index information. Use `with_passes()` to add it.
66    pub fn new() -> Self {
67        Self {
68            passes: alloc::vec![
69                Box::new(NotSimplification),
70                Box::new(AndPredicatePass),
71                Box::new(CrossProductPass),
72                Box::new(ImplicitJoinsPass),
73                Box::new(OuterJoinSimplification),
74                Box::new(PredicatePushdown),
75                Box::new(JoinReorder::new()),
76            ],
77        }
78    }
79
80    /// Creates an optimizer with custom passes.
81    pub fn with_passes(passes: Vec<Box<dyn OptimizerPass>>) -> Self {
82        Self { passes }
83    }
84
85    /// Optimizes a logical plan.
86    pub fn optimize(&self, mut plan: LogicalPlan) -> LogicalPlan {
87        for pass in &self.passes {
88            plan = pass.optimize(plan);
89        }
90        plan
91    }
92
93    /// Converts a logical plan to a physical plan.
94    /// Also applies physical plan optimizations (TopNPushdown).
95    pub fn to_physical(&self, plan: LogicalPlan) -> PhysicalPlan {
96        let physical = self.logical_to_physical(plan);
97        // Apply physical plan optimizations
98        TopNPushdown::new().optimize(physical)
99    }
100
101    fn logical_to_physical(&self, plan: LogicalPlan) -> PhysicalPlan {
102        match plan {
103            LogicalPlan::Scan { table } => PhysicalPlan::table_scan(table),
104
105            LogicalPlan::IndexScan {
106                table,
107                index,
108                range_start,
109                range_end,
110                include_start,
111                include_end,
112            } => PhysicalPlan::IndexScan {
113                table,
114                index,
115                range_start,
116                range_end,
117                include_start,
118                include_end,
119                limit: None,
120                offset: None,
121                reverse: false,
122            },
123
124            LogicalPlan::IndexGet { table, index, key } => {
125                PhysicalPlan::index_get(table, index, key)
126            }
127
128            LogicalPlan::IndexInGet { table, index, keys } => {
129                PhysicalPlan::index_in_get(table, index, keys)
130            }
131
132            LogicalPlan::GinIndexScan {
133                table,
134                index,
135                column: _,
136                column_index: _,
137                path,
138                value,
139                query_type,
140            } => {
141                // Extract the key from the JSON path (e.g., "$.category" -> "category")
142                let key = path.trim_start_matches("$.").to_string();
143
144                // Convert value to string for GIN index lookup
145                let value_str = value.map(|v| match v {
146                    Value::String(s) => s,
147                    Value::Int32(i) => alloc::format!("{}", i),
148                    Value::Int64(i) => alloc::format!("{}", i),
149                    Value::Float64(f) => alloc::format!("{}", f),
150                    Value::Boolean(b) => alloc::format!("{}", b),
151                    _ => alloc::format!("{:?}", v),
152                });
153
154                PhysicalPlan::gin_index_scan(table, index, key, value_str, query_type)
155            }
156
157            LogicalPlan::GinIndexScanMulti {
158                table,
159                index,
160                column: _,
161                pairs,
162            } => {
163                // Convert (path, value) pairs to (key, value_str) pairs
164                let string_pairs: Vec<(String, String)> = pairs
165                    .into_iter()
166                    .map(|(path, value)| {
167                        let key = path.trim_start_matches("$.").to_string();
168                        let value_str = match value {
169                            Value::String(s) => s,
170                            Value::Int32(i) => alloc::format!("{}", i),
171                            Value::Int64(i) => alloc::format!("{}", i),
172                            Value::Float64(f) => alloc::format!("{}", f),
173                            Value::Boolean(b) => alloc::format!("{}", b),
174                            _ => alloc::format!("{:?}", value),
175                        };
176                        (key, value_str)
177                    })
178                    .collect();
179
180                PhysicalPlan::gin_index_scan_multi(table, index, string_pairs)
181            }
182
183            LogicalPlan::Filter { input, predicate } => {
184                let input_physical = self.logical_to_physical(*input);
185                PhysicalPlan::filter(input_physical, predicate)
186            }
187
188            LogicalPlan::Project { input, columns } => {
189                let input_physical = self.logical_to_physical(*input);
190                PhysicalPlan::project(input_physical, columns)
191            }
192
193            LogicalPlan::Join {
194                left,
195                right,
196                condition,
197                join_type,
198            } => {
199                let left_physical = self.logical_to_physical(*left);
200                let right_physical = self.logical_to_physical(*right);
201
202                // Choose join algorithm based on condition
203                let algorithm = self.choose_join_algorithm(&condition);
204
205                match algorithm {
206                    JoinAlgorithm::Hash => {
207                        PhysicalPlan::hash_join(left_physical, right_physical, condition, join_type)
208                    }
209                    JoinAlgorithm::SortMerge => PhysicalPlan::sort_merge_join(
210                        left_physical,
211                        right_physical,
212                        condition,
213                        join_type,
214                    ),
215                    JoinAlgorithm::NestedLoop | JoinAlgorithm::IndexNestedLoop => {
216                        PhysicalPlan::nested_loop_join(
217                            left_physical,
218                            right_physical,
219                            condition,
220                            join_type,
221                        )
222                    }
223                }
224            }
225
226            LogicalPlan::Aggregate {
227                input,
228                group_by,
229                aggregates,
230            } => {
231                let input_physical = self.logical_to_physical(*input);
232                PhysicalPlan::hash_aggregate(input_physical, group_by, aggregates)
233            }
234
235            LogicalPlan::Sort { input, order_by } => {
236                let input_physical = self.logical_to_physical(*input);
237                PhysicalPlan::sort(input_physical, order_by)
238            }
239
240            LogicalPlan::Limit {
241                input,
242                limit,
243                offset,
244            } => {
245                let input_physical = self.logical_to_physical(*input);
246                PhysicalPlan::limit(input_physical, limit, offset)
247            }
248
249            LogicalPlan::CrossProduct { left, right } => {
250                let left_physical = self.logical_to_physical(*left);
251                let right_physical = self.logical_to_physical(*right);
252                PhysicalPlan::CrossProduct {
253                    left: Box::new(left_physical),
254                    right: Box::new(right_physical),
255                }
256            }
257
258            LogicalPlan::Union { .. } => {
259                // Union not yet implemented in physical plan
260                PhysicalPlan::Empty
261            }
262
263            LogicalPlan::Empty => PhysicalPlan::Empty,
264        }
265    }
266
267    fn choose_join_algorithm(&self, condition: &crate::ast::Expr) -> JoinAlgorithm {
268        // For equi-joins, prefer hash join
269        if condition.is_equi_join() {
270            return JoinAlgorithm::Hash;
271        }
272
273        // For range joins, use nested loop (could use sort-merge if sorted)
274        if condition.is_range_join() {
275            return JoinAlgorithm::NestedLoop;
276        }
277
278        // Default to nested loop for complex conditions
279        JoinAlgorithm::NestedLoop
280    }
281}
282
283#[cfg(test)]
284mod tests {
285    use super::*;
286    use crate::ast::Expr;
287
288    #[test]
289    fn test_optimizer_default() {
290        let optimizer = Optimizer::new();
291        assert_eq!(optimizer.passes.len(), 7);
292    }
293
294    #[test]
295    fn test_logical_to_physical_scan() {
296        let optimizer = Optimizer::new();
297        let logical = LogicalPlan::scan("users");
298        let physical = optimizer.to_physical(logical);
299
300        assert!(matches!(physical, PhysicalPlan::TableScan { table } if table == "users"));
301    }
302
303    #[test]
304    fn test_logical_to_physical_filter() {
305        let optimizer = Optimizer::new();
306        let logical = LogicalPlan::filter(
307            LogicalPlan::scan("users"),
308            Expr::eq(Expr::column("users", "id", 0), Expr::literal(1i64)),
309        );
310        let physical = optimizer.to_physical(logical);
311
312        assert!(matches!(physical, PhysicalPlan::Filter { .. }));
313    }
314
315    #[test]
316    fn test_logical_to_physical_join() {
317        let optimizer = Optimizer::new();
318        let logical = LogicalPlan::inner_join(
319            LogicalPlan::scan("a"),
320            LogicalPlan::scan("b"),
321            Expr::eq(Expr::column("a", "id", 0), Expr::column("b", "a_id", 0)),
322        );
323        let physical = optimizer.to_physical(logical);
324
325        // Should choose hash join for equi-join
326        assert!(matches!(physical, PhysicalPlan::HashJoin { .. }));
327    }
328}
cynos_query/optimizer/mod.rs

cynos_query/optimizer/
mod.rs
