1use super::*;
2
3pub struct DataIndexingEngine {
5 indexes: HashMap<String, DataIndex>,
6 indexing_strategy: IndexingStrategy,
7 query_optimizer: QueryOptimizer,
8}
9
10#[derive(Debug, Clone)]
12pub struct DataIndex {
13 pub index_id: String,
14 pub index_type: IndexType,
15 pub indexed_columns: Vec<String>,
16 pub statistics: IndexStatistics,
17}
18
19#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
21pub enum IndexType {
22 BTree,
23 Hash,
24 Bitmap,
25 FullText,
26 Spatial,
27 TimeSeries,
28}
29
30#[derive(Debug, Clone)]
32pub struct IndexStatistics {
33 pub entries: u64,
34 pub size: u64,
35 pub selectivity: f64,
36 pub usage_count: u64,
37}
38
39pub struct QueryOptimizer {
41 optimization_rules: Vec<OptimizationRule>,
42 cost_model: CostModel,
43 execution_plan: ExecutionPlan,
44}
45
46#[derive(Debug, Clone, PartialEq)]
48pub enum OptimizationRule {
49 PredicatePushdown,
50 IndexSelection,
51 JoinOrder,
52 AggregationPushdown,
53 Materialization,
54}
55
56pub struct CostModel {
58 pub cpu_cost: f64,
59 pub io_cost: f64,
60 pub memory_cost: f64,
61 pub network_cost: f64,
62}
63
64#[derive(Debug, Clone)]
66pub struct ExecutionPlan {
67 pub plan_id: String,
68 pub operations: Vec<QueryOperation>,
69 pub estimated_cost: f64,
70 pub execution_time: u64,
71}
72
73#[derive(Debug, Clone, Copy, PartialEq, Eq)]
75pub enum JoinType {
76 NestedLoop,
77 HashJoin,
78}
79
80#[derive(Debug, Clone, PartialEq)]
83pub enum QueryOperation {
84 Scan {
86 table: String,
87 estimated_rows: usize,
88 },
89 Filter { predicate: String, selectivity: f64 },
91 Join {
94 left_cost: f64,
95 right_cost: f64,
96 join_type: JoinType,
97 },
98 Aggregate { group_by: Vec<String> },
100 Sort { columns: Vec<String> },
102 Limit { count: usize },
104 Project { columns: Vec<String> },
106}
107
108#[derive(Debug, Clone)]
111pub struct QueryStep {
112 pub operation: QueryOperation,
113 pub estimated_cost: f64,
114 pub estimated_rows: usize,
115}
116
117#[derive(Debug, Clone)]
119pub struct QueryPlan {
120 pub operations: Vec<QueryStep>,
121 pub estimated_cost: f64,
122 pub estimated_rows: usize,
123}
124
125impl QueryOperation {
126 fn data_size_hint(&self) -> f64 {
130 match self {
131 QueryOperation::Scan { estimated_rows, .. } => *estimated_rows as f64,
132 QueryOperation::Filter { selectivity, .. } => 100.0 / selectivity.max(0.01),
133 QueryOperation::Join {
134 left_cost,
135 right_cost,
136 ..
137 } => left_cost * right_cost,
138 QueryOperation::Aggregate { group_by } => group_by.len().max(1) as f64 * 100.0,
139 QueryOperation::Sort { columns } => columns.len().max(1) as f64 * 100.0,
140 QueryOperation::Limit { count } => *count as f64,
141 QueryOperation::Project { columns } => columns.len().max(1) as f64 * 100.0,
142 }
143 }
144
145 fn plan_priority(&self) -> u8 {
149 match self {
150 QueryOperation::Scan { .. } => 0,
151 QueryOperation::Project { .. } => 0,
152 QueryOperation::Filter { .. } => 1,
153 QueryOperation::Join { .. } => 2,
154 QueryOperation::Aggregate { .. } => 3,
155 QueryOperation::Sort { .. } => 4,
156 QueryOperation::Limit { .. } => 5,
157 }
158 }
159}
160
161impl DataIndexingEngine {
162 pub fn new() -> Self {
164 Self {
165 indexes: HashMap::new(),
166 indexing_strategy: IndexingStrategy::BTree,
167 query_optimizer: QueryOptimizer::new(),
168 }
169 }
170
171 pub fn initialize(&mut self) -> Result<(), StatisticalError> {
173 self.query_optimizer.initialize()?;
174 Ok(())
175 }
176
177 pub fn indexing_strategy(&self) -> &IndexingStrategy {
179 &self.indexing_strategy
180 }
181
182 pub fn set_indexing_strategy(&mut self, strategy: IndexingStrategy) {
184 self.indexing_strategy = strategy;
185 }
186
187 pub fn add_index(&mut self, index: DataIndex) {
189 self.indexes.insert(index.index_id.clone(), index);
190 }
191
192 pub fn get_index(&self, index_id: &str) -> Option<&DataIndex> {
194 self.indexes.get(index_id)
195 }
196
197 pub fn remove_index(&mut self, index_id: &str) -> Option<DataIndex> {
199 self.indexes.remove(index_id)
200 }
201
202 pub fn list_index_ids(&self) -> Vec<String> {
204 self.indexes.keys().cloned().collect()
205 }
206
207 pub fn index_count(&self) -> usize {
209 self.indexes.len()
210 }
211
212 pub fn query_optimizer(&self) -> &QueryOptimizer {
214 &self.query_optimizer
215 }
216
217 pub fn query_optimizer_mut(&mut self) -> &mut QueryOptimizer {
219 &mut self.query_optimizer
220 }
221}
222
223impl QueryOptimizer {
224 pub fn new() -> Self {
226 Self {
227 optimization_rules: vec![
228 OptimizationRule::PredicatePushdown,
229 OptimizationRule::IndexSelection,
230 ],
231 cost_model: CostModel {
232 cpu_cost: 0.0,
233 io_cost: 0.0,
234 memory_cost: 0.0,
235 network_cost: 0.0,
236 },
237 execution_plan: ExecutionPlan {
238 plan_id: "default".to_string(),
239 operations: Vec::new(),
240 estimated_cost: 0.0,
241 execution_time: 0,
242 },
243 }
244 }
245
246 pub fn initialize(&mut self) -> Result<(), StatisticalError> {
248 Ok(())
249 }
250
251 pub fn optimization_rules(&self) -> &[OptimizationRule] {
253 &self.optimization_rules
254 }
255
256 pub fn add_optimization_rule(&mut self, rule: OptimizationRule) {
258 if !self.optimization_rules.contains(&rule) {
259 self.optimization_rules.push(rule);
260 }
261 }
262
263 pub fn has_rule(&self, rule: &OptimizationRule) -> bool {
265 self.optimization_rules.contains(rule)
266 }
267
268 pub fn estimate_cost(&self, operation: &QueryOperation) -> CostModel {
273 let n = operation.data_size_hint();
274 match operation {
275 QueryOperation::Scan { .. } => CostModel {
277 cpu_cost: 0.1 * n,
278 io_cost: 1.0 * n,
279 memory_cost: 0.05 * n,
280 network_cost: 0.0,
281 },
282 QueryOperation::Filter { .. } => CostModel {
284 cpu_cost: 0.2 * n,
285 io_cost: 0.0,
286 memory_cost: 0.02 * n,
287 network_cost: 0.0,
288 },
289 QueryOperation::Project { .. } => CostModel {
291 cpu_cost: 0.1 * n,
292 io_cost: 0.0,
293 memory_cost: 0.02 * n,
294 network_cost: 0.0,
295 },
296 QueryOperation::Aggregate { .. } => CostModel {
298 cpu_cost: 0.5 * n,
299 io_cost: 0.1 * n,
300 memory_cost: 0.3 * n,
301 network_cost: 0.0,
302 },
303 QueryOperation::Join { .. } => CostModel {
305 cpu_cost: 1.0 * n,
306 io_cost: 0.5 * n,
307 memory_cost: 1.0 * n,
308 network_cost: 0.5 * n,
309 },
310 QueryOperation::Sort { .. } => CostModel {
312 cpu_cost: 0.6 * n,
313 io_cost: 0.2 * n,
314 memory_cost: 0.5 * n,
315 network_cost: 0.0,
316 },
317 QueryOperation::Limit { .. } => CostModel {
319 cpu_cost: 0.05 * n,
320 io_cost: 0.0,
321 memory_cost: 0.01 * n,
322 network_cost: 0.0,
323 },
324 }
325 }
326
327 pub fn optimize_with_cost(
332 &mut self,
333 operations: &[QueryOperation],
334 ) -> Result<ExecutionPlan, StatisticalError> {
335 let mut indexed: Vec<(usize, QueryOperation)> = operations
336 .iter()
337 .cloned()
338 .map(|op| op)
339 .enumerate()
340 .collect();
341 indexed.sort_by(|a, b| {
344 let ca = self.estimate_cost(&a.1).total_cost();
345 let cb = self.estimate_cost(&b.1).total_cost();
346 ca.partial_cmp(&cb).unwrap_or(std::cmp::Ordering::Equal)
347 });
348
349 let mut ordered: Vec<QueryOperation> = indexed.into_iter().map(|(_, op)| op).collect();
350 let total: f64 = ordered
351 .iter()
352 .map(|op| self.estimate_cost(op).total_cost())
353 .sum();
354
355 self.cost_model = ordered.iter().map(|op| self.estimate_cost(op)).fold(
358 CostModel {
359 cpu_cost: 0.0,
360 io_cost: 0.0,
361 memory_cost: 0.0,
362 network_cost: 0.0,
363 },
364 |acc, c| CostModel {
365 cpu_cost: acc.cpu_cost + c.cpu_cost,
366 io_cost: acc.io_cost + c.io_cost,
367 memory_cost: acc.memory_cost + c.memory_cost,
368 network_cost: acc.network_cost + c.network_cost,
369 },
370 );
371
372 let plan = ExecutionPlan {
373 plan_id: format!("plan_{}", self.next_plan_id()),
374 operations: std::mem::take(&mut ordered),
375 estimated_cost: total,
376 execution_time: 0,
377 };
378 self.execution_plan = plan.clone();
379 Ok(plan)
380 }
381
382 pub fn get_execution_plan(&self) -> Option<&ExecutionPlan> {
384 if self.execution_plan.operations.is_empty() {
385 None
386 } else {
387 Some(&self.execution_plan)
388 }
389 }
390
391 fn next_plan_id(&self) -> u64 {
393 self.execution_plan.operations.len() as u64 + 1
395 }
396
397 pub fn optimize(&self, operations: Vec<QueryOperation>) -> Result<QueryPlan, StatisticalError> {
411 if operations.is_empty() {
412 return Ok(QueryPlan {
413 operations: Vec::new(),
414 estimated_cost: 0.0,
415 estimated_rows: 0,
416 });
417 }
418
419 let mut reordered: Vec<QueryOperation> = operations;
423 reordered.sort_by_key(|op| op.plan_priority());
424
425 for op in reordered.iter_mut() {
427 if let QueryOperation::Join {
428 left_cost,
429 right_cost,
430 join_type,
431 } = op
432 {
433 if *left_cost >= 1000.0 && *right_cost >= 1000.0 {
434 *join_type = JoinType::HashJoin;
435 } else if *left_cost < 100.0 && *right_cost < 100.0 {
436 *join_type = JoinType::NestedLoop;
437 }
438 }
439 }
440
441 let mut steps: Vec<QueryStep> = Vec::with_capacity(reordered.len());
443 let mut current_rows: usize = 0;
444 let mut total_cost: f64 = 0.0;
445
446 for op in reordered {
447 let (cost, output_rows) = Self::estimate_step(&op, current_rows);
448 steps.push(QueryStep {
449 operation: op,
450 estimated_cost: cost,
451 estimated_rows: output_rows,
452 });
453 current_rows = output_rows;
454 total_cost += cost;
455 }
456
457 Ok(QueryPlan {
458 operations: steps,
459 estimated_cost: total_cost,
460 estimated_rows: current_rows,
461 })
462 }
463
464 fn estimate_step(op: &QueryOperation, input_rows: usize) -> (f64, usize) {
467 match op {
468 QueryOperation::Scan { estimated_rows, .. } => {
469 let cost = *estimated_rows as f64 * 0.01;
470 (cost, *estimated_rows)
471 }
472 QueryOperation::Filter { selectivity, .. } => {
473 let n = input_rows.max(1) as f64;
474 let cost = n * selectivity * 0.005;
475 let output = (n * selectivity).round() as usize;
476 (cost, output)
477 }
478 QueryOperation::Join {
479 left_cost,
480 right_cost,
481 ..
482 } => {
483 let n = left_cost * right_cost;
484 let cost = n * 0.001;
485 let output = n.round() as usize;
486 (cost, output)
487 }
488 QueryOperation::Aggregate { .. } => {
489 let n = input_rows.max(1) as f64;
490 let cost = n * 0.01;
491 (cost, input_rows)
492 }
493 QueryOperation::Sort { .. } => {
494 let n = input_rows.max(1) as f64;
495 let cost = n * 0.01;
496 (cost, input_rows)
497 }
498 QueryOperation::Limit { count } => {
499 let cost = *count as f64 * 0.001;
500 let output = (*count).min(input_rows.max(1));
501 (cost, output)
502 }
503 QueryOperation::Project { .. } => {
504 let n = input_rows.max(1) as f64;
505 let cost = n * 0.001;
506 (cost, input_rows)
507 }
508 }
509 }
510}
511
512impl CostModel {
513 pub fn total_cost(&self) -> f64 {
515 self.cpu_cost + self.io_cost + self.memory_cost + self.network_cost
516 }
517
518 pub fn is_better_than(&self, other: &CostModel) -> bool {
520 self.total_cost() < other.total_cost()
521 }
522}