velesdb_core/velesql/

explain.rs

//! Query plan explanation for `VelesQL`.
//!
//! This module provides EXPLAIN functionality to display query execution plans.
//!
//! # Example
//!
//! ```ignore
//! use velesdb_core::velesql::{Parser, QueryPlan};
//!
//! let query = Parser::parse("SELECT * FROM docs WHERE vector NEAR $v LIMIT 10")?;
//! let plan = QueryPlan::from_select(&query.select);
//! println!("{}", plan.to_tree());
//! ```

use serde::{Deserialize, Serialize};
use std::fmt::{self, Write as _};

use super::ast::{Condition, SelectStatement};

/// Query execution plan generated by EXPLAIN.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct QueryPlan {
    /// Root node of the plan tree.
    pub root: PlanNode,
    /// Estimated execution cost in milliseconds.
    pub estimated_cost_ms: f64,
    /// Index type used (if any).
    pub index_used: Option<IndexType>,
    /// Filter strategy.
    pub filter_strategy: FilterStrategy,
}

/// A node in the query execution plan tree.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub enum PlanNode {
    /// Vector similarity search operation.
    VectorSearch(VectorSearchPlan),
    /// Metadata filter operation.
    Filter(FilterPlan),
    /// Limit results.
    Limit(LimitPlan),
    /// Offset skip.
    Offset(OffsetPlan),
    /// Table scan (no index).
    TableScan(TableScanPlan),
    /// Sequential operations.
    Sequence(Vec<PlanNode>),
}

/// Vector search plan details.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct VectorSearchPlan {
    /// Collection name.
    pub collection: String,
    /// `ef_search` parameter (for HNSW).
    pub ef_search: u32,
    /// Number of candidates to retrieve.
    pub candidates: u32,
}

/// Filter plan details.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct FilterPlan {
    /// Filter conditions as string representation.
    pub conditions: String,
    /// Estimated selectivity (0.0 - 1.0).
    pub selectivity: f64,
}

/// Limit plan details.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct LimitPlan {
    /// Maximum number of results.
    pub count: u64,
}

/// Offset plan details.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct OffsetPlan {
    /// Number of results to skip.
    pub count: u64,
}

/// Table scan plan (no index used).
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct TableScanPlan {
    /// Collection name.
    pub collection: String,
}

/// Type of index used in the query.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum IndexType {
    /// HNSW index for vector search.
    Hnsw,
    /// Flat index (brute force).
    Flat,
    /// Binary quantization index.
    BinaryQuantization,
}

/// Strategy for applying filters.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, Default)]
pub enum FilterStrategy {
    /// No filter.
    #[default]
    None,
    /// Pre-filtering: filter before vector search (high selectivity).
    PreFilter,
    /// Post-filtering: filter after vector search (low selectivity).
    PostFilter,
}

impl QueryPlan {
    /// Creates a new query plan from a SELECT statement.
    #[must_use]
    pub fn from_select(stmt: &SelectStatement) -> Self {
        let mut nodes = Vec::new();
        let mut has_vector_search = false;
        let mut filter_conditions = Vec::new();
        let mut filter_strategy = FilterStrategy::None;
        let mut index_used = None;

        // Analyze WHERE clause
        if let Some(ref condition) = stmt.where_clause {
            Self::analyze_condition(condition, &mut has_vector_search, &mut filter_conditions);
        }

        // Build plan nodes
        if has_vector_search {
            index_used = Some(IndexType::Hnsw);
            let candidates = u32::try_from(stmt.limit.unwrap_or(50)).unwrap_or(u32::MAX);
            nodes.push(PlanNode::VectorSearch(VectorSearchPlan {
                collection: stmt.from.clone(),
                ef_search: 100, // Default HNSW parameter
                candidates,
            }));
        } else {
            nodes.push(PlanNode::TableScan(TableScanPlan {
                collection: stmt.from.clone(),
            }));
        }

        // Add filter if needed
        if !filter_conditions.is_empty() {
            let selectivity = Self::estimate_selectivity(&filter_conditions);
            filter_strategy = if selectivity > 0.1 {
                FilterStrategy::PostFilter
            } else {
                FilterStrategy::PreFilter
            };

            nodes.push(PlanNode::Filter(FilterPlan {
                conditions: filter_conditions.join(" AND "),
                selectivity,
            }));
        }

        // Add offset before limit
        if let Some(offset) = stmt.offset {
            nodes.push(PlanNode::Offset(OffsetPlan { count: offset }));
        }

        // Add limit
        if let Some(limit) = stmt.limit {
            nodes.push(PlanNode::Limit(LimitPlan { count: limit }));
        }

        let root = if nodes.len() == 1 {
            nodes.swap_remove(0)
        } else {
            PlanNode::Sequence(nodes)
        };

        let estimated_cost_ms = Self::estimate_cost(&root, has_vector_search);

        Self {
            root,
            estimated_cost_ms,
            index_used,
            filter_strategy,
        }
    }

    /// Analyzes a condition to extract vector search and filter info.
    fn analyze_condition(
        condition: &Condition,
        has_vector_search: &mut bool,
        filter_conditions: &mut Vec<String>,
    ) {
        match condition {
            Condition::VectorSearch(_) | Condition::VectorFusedSearch(_) => {
                *has_vector_search = true;
            }
            Condition::Comparison(cmp) => {
                filter_conditions.push(format!("{} {} ?", cmp.column, cmp.operator.as_str()));
            }
            Condition::In(inc) => {
                filter_conditions.push(format!("{} IN (...)", inc.column));
            }
            Condition::Between(btw) => {
                filter_conditions.push(format!("{} BETWEEN ? AND ?", btw.column));
            }
            Condition::Like(lk) => {
                filter_conditions.push(format!("{} LIKE ?", lk.column));
            }
            Condition::IsNull(isn) => {
                let op = if isn.is_null {
                    "IS NULL"
                } else {
                    "IS NOT NULL"
                };
                filter_conditions.push(format!("{} {op}", isn.column));
            }
            Condition::Match(m) => {
                filter_conditions.push(format!("{} MATCH ?", m.column));
            }
            Condition::And(left, right) | Condition::Or(left, right) => {
                Self::analyze_condition(left, has_vector_search, filter_conditions);
                Self::analyze_condition(right, has_vector_search, filter_conditions);
            }
            Condition::Not(inner) | Condition::Group(inner) => {
                Self::analyze_condition(inner, has_vector_search, filter_conditions);
            }
        }
    }

    /// Estimates selectivity (placeholder - would need statistics in production).
    fn estimate_selectivity(conditions: &[String]) -> f64 {
        // Heuristic: more conditions = lower selectivity
        let base = 0.5_f64;
        base.powi(i32::try_from(conditions.len()).unwrap_or(i32::MAX))
    }

    /// Estimates execution cost in milliseconds.
    fn estimate_cost(root: &PlanNode, has_vector_search: bool) -> f64 {
        let base_cost = if has_vector_search { 0.05 } else { 1.0 };

        match root {
            PlanNode::Sequence(nodes) => nodes
                .iter()
                .fold(base_cost, |acc, node| acc + Self::node_cost(node)),
            _ => base_cost + Self::node_cost(root),
        }
    }

    fn node_cost(node: &PlanNode) -> f64 {
        match node {
            PlanNode::VectorSearch(_) => 0.05,
            PlanNode::Filter(f) => 0.01 * (1.0 - f.selectivity),
            PlanNode::Limit(_) | PlanNode::Offset(_) => 0.001,
            PlanNode::TableScan(_) => 1.0,
            PlanNode::Sequence(nodes) => nodes.iter().map(Self::node_cost).sum(),
        }
    }

    /// Renders the plan as a tree string.
    #[must_use]
    pub fn to_tree(&self) -> String {
        let mut output = String::from("Query Plan:\n");
        Self::render_node(&self.root, &mut output, "", true);

        let _ = write!(
            output,
            "\nEstimated cost: {:.3}ms\n",
            self.estimated_cost_ms
        );

        if let Some(ref idx) = self.index_used {
            let _ = writeln!(output, "Index used: {}", idx.as_str());
        }

        if self.filter_strategy != FilterStrategy::None {
            let _ = writeln!(output, "Filter strategy: {}", self.filter_strategy.as_str());
        }

        output
    }

    fn render_node(node: &PlanNode, output: &mut String, prefix: &str, is_last: bool) {
        let connector = if is_last { "└─ " } else { "├─ " };
        let child_prefix = format!("{}{}", prefix, if is_last { "   " } else { "│  " });

        match node {
            PlanNode::VectorSearch(vs) => {
                let _ = writeln!(output, "{prefix}{connector}VectorSearch");
                let _ = writeln!(output, "{child_prefix}├─ Collection: {}", vs.collection);
                let _ = writeln!(output, "{child_prefix}├─ ef_search: {}", vs.ef_search);
                let _ = writeln!(output, "{child_prefix}└─ Candidates: {}", vs.candidates);
            }
            PlanNode::Filter(f) => {
                let _ = writeln!(output, "{prefix}{connector}Filter");
                let _ = writeln!(output, "{child_prefix}├─ Conditions: {}", f.conditions);
                let _ = writeln!(
                    output,
                    "{child_prefix}└─ Selectivity: {:.1}%",
                    f.selectivity * 100.0
                );
            }
            PlanNode::Limit(l) => {
                let _ = writeln!(output, "{prefix}{connector}Limit: {}", l.count);
            }
            PlanNode::Offset(o) => {
                let _ = writeln!(output, "{prefix}{connector}Offset: {}", o.count);
            }
            PlanNode::TableScan(ts) => {
                let _ = writeln!(output, "{prefix}{connector}TableScan: {}", ts.collection);
            }
            PlanNode::Sequence(nodes) => {
                for (i, child) in nodes.iter().enumerate() {
                    Self::render_node(child, output, prefix, i == nodes.len() - 1);
                }
            }
        }
    }

    /// Renders the plan as JSON.
    ///
    /// # Errors
    ///
    /// Returns an error if serialization fails.
    pub fn to_json(&self) -> Result<String, serde_json::Error> {
        serde_json::to_string_pretty(self)
    }
}

impl IndexType {
    /// Returns the index type as a string.
    #[must_use]
    pub const fn as_str(&self) -> &'static str {
        match self {
            Self::Hnsw => "HNSW",
            Self::Flat => "Flat",
            Self::BinaryQuantization => "BinaryQuantization",
        }
    }
}

impl FilterStrategy {
    /// Returns the filter strategy as a string.
    #[must_use]
    pub const fn as_str(&self) -> &'static str {
        match self {
            Self::None => "none",
            Self::PreFilter => "pre-filtering (high selectivity)",
            Self::PostFilter => "post-filtering (low selectivity)",
        }
    }
}

impl super::ast::CompareOp {
    /// Returns the operator as a string.
    #[must_use]
    pub const fn as_str(&self) -> &'static str {
        match self {
            Self::Eq => "=",
            Self::NotEq => "!=",
            Self::Gt => ">",
            Self::Gte => ">=",
            Self::Lt => "<",
            Self::Lte => "<=",
        }
    }
}

impl fmt::Display for QueryPlan {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.to_tree())
    }
}