oxirs_core/query/

plan_cache.rs

//! Query plan caching for improved performance
//!
//! This module provides an LRU cache for compiled query plans with persistence support.

use crate::query::plan::ExecutionPlan;
use crate::OxirsError;
use lru::LruCache;
use scirs2_core::metrics::Counter;
use serde::{Deserialize, Serialize};
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
use std::num::NonZeroUsize;
use std::path::Path;
use std::sync::{Arc, RwLock};
use std::time::Instant;

/// Query plan cache with LRU eviction
///
/// Caches compiled execution plans to avoid repeated query compilation
/// and optimization overhead.
///
/// This is the full-featured LRU implementation backed by the `lru` crate and
/// SciRS2 metrics.  For a simpler, self-contained cache see [`QueryPlanCache`] below.
pub struct LruQueryPlanCache {
    /// LRU cache for execution plans
    cache: Arc<RwLock<LruCache<u64, CachedPlan>>>,
    /// Cache statistics
    stats: Arc<RwLock<CacheStatistics>>,
    /// Metrics counters
    hit_counter: Counter,
    miss_counter: Counter,
    eviction_counter: Counter,
    /// Cache configuration
    config: CacheConfig,
}

/// Cached execution plan with metadata
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct CachedPlan {
    /// The compiled execution plan
    pub plan: SerializablePlan,
    /// Query signature (hash)
    pub signature: u64,
    /// When the plan was cached
    pub cached_at_ms: u128,
    /// How many times this plan was accessed
    pub access_count: u64,
    /// Last access time
    pub last_accessed_ms: u128,
    /// Estimated execution cost
    pub estimated_cost: f64,
    /// Average actual execution time (milliseconds)
    pub avg_execution_time_ms: f64,
}

/// Serializable representation of execution plan
#[derive(Debug, Clone, Serialize, Deserialize)]
pub enum SerializablePlan {
    /// Triple scan operation
    TripleScan { pattern_desc: String },
    /// Hash join operation
    HashJoin {
        left: Box<SerializablePlan>,
        right: Box<SerializablePlan>,
        join_vars: Vec<String>,
    },
    /// Filter operation
    Filter {
        input: Box<SerializablePlan>,
        expr_desc: String,
    },
    /// Projection operation
    Project {
        input: Box<SerializablePlan>,
        variables: Vec<String>,
    },
    /// Union operation
    Union {
        left: Box<SerializablePlan>,
        right: Box<SerializablePlan>,
    },
    /// Empty plan
    Empty,
}

/// Cache configuration
#[derive(Debug, Clone)]
pub struct CacheConfig {
    /// Maximum number of cached plans
    pub max_size: usize,
    /// Enable persistence to disk
    pub enable_persistence: bool,
    /// Path for persisted cache
    pub persistence_path: Option<String>,
    /// Time-to-live for cached plans (milliseconds)
    pub ttl_ms: Option<u128>,
}

impl Default for CacheConfig {
    fn default() -> Self {
        Self {
            max_size: 1000,
            enable_persistence: false,
            persistence_path: None,
            ttl_ms: Some(3_600_000), // 1 hour
        }
    }
}

/// Cache statistics
#[derive(Debug, Clone, Default, Serialize, Deserialize)]
pub struct CacheStatistics {
    /// Total cache hits
    pub hits: u64,
    /// Total cache misses
    pub misses: u64,
    /// Total evictions
    pub evictions: u64,
    /// Current cache size
    pub current_size: usize,
    /// Total plans cached
    pub total_cached: u64,
}

impl LruQueryPlanCache {
    /// Create a new query plan cache
    pub fn new(config: CacheConfig) -> Self {
        let capacity = NonZeroUsize::new(config.max_size)
            .unwrap_or(NonZeroUsize::new(1000).expect("1000 is non-zero"));

        Self {
            cache: Arc::new(RwLock::new(LruCache::new(capacity))),
            stats: Arc::new(RwLock::new(CacheStatistics::default())),
            hit_counter: Counter::new("plan_cache.hits".to_string()),
            miss_counter: Counter::new("plan_cache.misses".to_string()),
            eviction_counter: Counter::new("plan_cache.evictions".to_string()),
            config,
        }
    }

    /// Get a cached plan for a query string
    pub fn get(&self, query: &str) -> Option<CachedPlan> {
        let signature = Self::compute_signature(query);

        let start = Instant::now();

        let result = {
            let mut cache = self.cache.write().ok()?;
            cache.get_mut(&signature).cloned()
        };

        let _elapsed = start.elapsed(); // Track elapsed time for future use

        if let Some(mut plan) = result {
            // Update access metrics
            plan.access_count += 1;
            plan.last_accessed_ms = Instant::now().elapsed().as_millis();

            // Check TTL
            if let Some(ttl) = self.config.ttl_ms {
                let age = plan.last_accessed_ms - plan.cached_at_ms;
                if age > ttl {
                    // Expired, remove from cache
                    self.remove(query);
                    self.record_miss();
                    return None;
                }
            }

            // Update cache with new access info
            if let Ok(mut cache) = self.cache.write() {
                cache.put(signature, plan.clone());
            }

            self.record_hit();
            Some(plan)
        } else {
            self.record_miss();
            None
        }
    }

    /// Put a compiled plan into the cache
    pub fn put(
        &self,
        query: &str,
        plan: ExecutionPlan,
        estimated_cost: f64,
    ) -> Result<(), OxirsError> {
        let signature = Self::compute_signature(query);
        let serializable = Self::convert_to_serializable(&plan);

        let cached_plan = CachedPlan {
            plan: serializable,
            signature,
            cached_at_ms: Instant::now().elapsed().as_millis(),
            access_count: 0,
            last_accessed_ms: Instant::now().elapsed().as_millis(),
            estimated_cost,
            avg_execution_time_ms: 0.0,
        };

        let mut cache = self
            .cache
            .write()
            .map_err(|e| OxirsError::Query(format!("Failed to write cache: {}", e)))?;

        // Check if we're evicting an entry
        let will_evict = cache.len() >= cache.cap().get();
        if will_evict {
            self.record_eviction();
        }

        cache.put(signature, cached_plan);

        // Update statistics
        let mut stats = self
            .stats
            .write()
            .map_err(|e| OxirsError::Query(format!("Failed to write stats: {}", e)))?;
        stats.current_size = cache.len();
        stats.total_cached += 1;

        Ok(())
    }

    /// Remove a cached plan
    pub fn remove(&self, query: &str) -> Option<CachedPlan> {
        let signature = Self::compute_signature(query);

        self.cache.write().ok()?.pop(&signature)
    }

    /// Clear all cached plans
    pub fn clear(&self) -> Result<(), OxirsError> {
        let mut cache = self
            .cache
            .write()
            .map_err(|e| OxirsError::Query(format!("Failed to write cache: {}", e)))?;
        cache.clear();

        let mut stats = self
            .stats
            .write()
            .map_err(|e| OxirsError::Query(format!("Failed to write stats: {}", e)))?;
        stats.current_size = 0;

        Ok(())
    }

    /// Get cache statistics
    pub fn statistics(&self) -> CacheStatistics {
        self.stats
            .read()
            .ok()
            .map(|s| s.clone())
            .unwrap_or_default()
    }

    /// Get cache hit rate
    pub fn hit_rate(&self) -> f64 {
        let stats = self.statistics();
        let total = stats.hits + stats.misses;
        if total == 0 {
            return 0.0;
        }
        stats.hits as f64 / total as f64
    }

    /// Persist cache to disk
    pub fn persist(&self) -> Result<(), OxirsError> {
        if !self.config.enable_persistence {
            return Ok(());
        }

        let path = self
            .config
            .persistence_path
            .as_ref()
            .ok_or_else(|| OxirsError::Io("No persistence path configured".to_string()))?;

        let cache = self
            .cache
            .read()
            .map_err(|e| OxirsError::Query(format!("Failed to read cache: {}", e)))?;

        // Convert cache to serializable format
        let entries: Vec<(u64, CachedPlan)> = cache.iter().map(|(k, v)| (*k, v.clone())).collect();

        let json = serde_json::to_string_pretty(&entries)
            .map_err(|e| OxirsError::Serialize(e.to_string()))?;

        std::fs::write(path, json).map_err(|e| OxirsError::Io(e.to_string()))?;

        tracing::info!("Persisted {} cached plans to {}", entries.len(), path);

        Ok(())
    }

    /// Load cache from disk
    pub fn load(&self) -> Result<(), OxirsError> {
        if !self.config.enable_persistence {
            return Ok(());
        }

        let path = self
            .config
            .persistence_path
            .as_ref()
            .ok_or_else(|| OxirsError::Io("No persistence path configured".to_string()))?;

        if !Path::new(path).exists() {
            return Ok(()); // No cached data to load
        }

        let json = std::fs::read_to_string(path).map_err(|e| OxirsError::Io(e.to_string()))?;

        let entries: Vec<(u64, CachedPlan)> =
            serde_json::from_str(&json).map_err(|e| OxirsError::Parse(e.to_string()))?;

        let mut cache = self
            .cache
            .write()
            .map_err(|e| OxirsError::Query(format!("Failed to write cache: {}", e)))?;

        for (sig, plan) in entries {
            cache.put(sig, plan);
        }

        tracing::info!("Loaded {} cached plans from {}", cache.len(), path);

        Ok(())
    }

    /// Update execution time for a cached plan
    pub fn update_execution_time(
        &self,
        query: &str,
        execution_time_ms: f64,
    ) -> Result<(), OxirsError> {
        let signature = Self::compute_signature(query);

        let mut cache = self
            .cache
            .write()
            .map_err(|e| OxirsError::Query(format!("Failed to write cache: {}", e)))?;

        if let Some(plan) = cache.get_mut(&signature) {
            // Update average execution time with exponential moving average
            let alpha = 0.3; // Weight for new measurement
            if plan.avg_execution_time_ms == 0.0 {
                plan.avg_execution_time_ms = execution_time_ms;
            } else {
                plan.avg_execution_time_ms =
                    alpha * execution_time_ms + (1.0 - alpha) * plan.avg_execution_time_ms;
            }
        }

        Ok(())
    }

    // Private helper methods

    fn compute_signature(query: &str) -> u64 {
        let mut hasher = DefaultHasher::new();
        query.hash(&mut hasher);
        hasher.finish()
    }

    fn convert_to_serializable(plan: &ExecutionPlan) -> SerializablePlan {
        match plan {
            ExecutionPlan::TripleScan { pattern } => SerializablePlan::TripleScan {
                pattern_desc: format!("{:?}", pattern),
            },
            ExecutionPlan::HashJoin {
                left,
                right,
                join_vars,
            } => SerializablePlan::HashJoin {
                left: Box::new(Self::convert_to_serializable(left)),
                right: Box::new(Self::convert_to_serializable(right)),
                join_vars: join_vars.iter().map(|v| format!("{:?}", v)).collect(),
            },
            ExecutionPlan::Filter { input, condition } => SerializablePlan::Filter {
                input: Box::new(Self::convert_to_serializable(input)),
                expr_desc: format!("{:?}", condition),
            },
            ExecutionPlan::Project { input, vars } => SerializablePlan::Project {
                input: Box::new(Self::convert_to_serializable(input)),
                variables: vars.iter().map(|v| format!("{:?}", v)).collect(),
            },
            ExecutionPlan::Union { left, right } => SerializablePlan::Union {
                left: Box::new(Self::convert_to_serializable(left)),
                right: Box::new(Self::convert_to_serializable(right)),
            },
            _ => SerializablePlan::Empty,
        }
    }

    fn record_hit(&self) {
        self.hit_counter.add(1);
        if let Ok(mut stats) = self.stats.write() {
            stats.hits += 1;
        }
    }

    fn record_miss(&self) {
        self.miss_counter.add(1);
        if let Ok(mut stats) = self.stats.write() {
            stats.misses += 1;
        }
    }

    fn record_eviction(&self) {
        self.eviction_counter.add(1);
        if let Ok(mut stats) = self.stats.write() {
            stats.evictions += 1;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_cache_creation() {
        let config = CacheConfig::default();
        let cache = LruQueryPlanCache::new(config);

        let stats = cache.statistics();
        assert_eq!(stats.hits, 0);
        assert_eq!(stats.misses, 0);
    }

    #[test]
    fn test_cache_put_get() {
        let config = CacheConfig::default();
        let cache = LruQueryPlanCache::new(config);

        let query = "SELECT ?s ?p ?o WHERE { ?s ?p ?o }";
        let plan = ExecutionPlan::TripleScan {
            pattern: crate::model::pattern::TriplePattern::new(None, None, None),
        };

        cache
            .put(query, plan, 100.0)
            .expect("cache put should succeed");

        let cached = cache.get(query);
        assert!(cached.is_some());
        assert_eq!(
            cached.expect("cached value should exist").estimated_cost,
            100.0
        );
    }

    #[test]
    fn test_cache_miss() {
        let config = CacheConfig::default();
        let cache = LruQueryPlanCache::new(config);

        let result = cache.get("SELECT ?s WHERE { ?s ?p ?o }");
        assert!(result.is_none());

        let stats = cache.statistics();
        assert_eq!(stats.misses, 1);
    }

    #[test]
    fn test_cache_remove() {
        let config = CacheConfig::default();
        let cache = LruQueryPlanCache::new(config);

        let query = "SELECT ?s WHERE { ?s ?p ?o }";
        let plan = ExecutionPlan::TripleScan {
            pattern: crate::model::pattern::TriplePattern::new(None, None, None),
        };

        cache
            .put(query, plan, 50.0)
            .expect("cache put should succeed");
        assert!(cache.get(query).is_some());

        cache.remove(query);
        assert!(cache.get(query).is_none());
    }

    #[test]
    fn test_cache_clear() {
        let config = CacheConfig::default();
        let cache = LruQueryPlanCache::new(config);

        let plan = ExecutionPlan::TripleScan {
            pattern: crate::model::pattern::TriplePattern::new(None, None, None),
        };

        cache
            .put("query1", plan.clone(), 50.0)
            .expect("cache put should succeed");
        cache
            .put("query2", plan, 75.0)
            .expect("cache put should succeed");

        cache.clear().expect("cache clear should succeed");

        let stats = cache.statistics();
        assert_eq!(stats.current_size, 0);
    }

    #[test]
    fn test_hit_rate() {
        let config = CacheConfig::default();
        let cache = LruQueryPlanCache::new(config);

        let plan = ExecutionPlan::TripleScan {
            pattern: crate::model::pattern::TriplePattern::new(None, None, None),
        };

        let query = "SELECT * WHERE { ?s ?p ?o }";
        cache
            .put(query, plan, 100.0)
            .expect("cache put should succeed");

        // One hit
        cache.get(query);
        // One miss
        cache.get("SELECT * WHERE { ?x ?y ?z }");

        let hit_rate = cache.hit_rate();
        assert!((hit_rate - 0.5).abs() < 0.01); // 50% hit rate
    }

    #[test]
    fn test_lru_eviction() {
        let config = CacheConfig {
            max_size: 2, // Small cache for testing
            ..Default::default()
        };

        let cache = LruQueryPlanCache::new(config);

        let plan = ExecutionPlan::TripleScan {
            pattern: crate::model::pattern::TriplePattern::new(None, None, None),
        };

        cache
            .put("query1", plan.clone(), 10.0)
            .expect("cache put should succeed");
        cache
            .put("query2", plan.clone(), 20.0)
            .expect("cache put should succeed");
        cache
            .put("query3", plan, 30.0)
            .expect("cache put should succeed"); // Should evict query1

        assert!(cache.get("query1").is_none()); // Evicted
        assert!(cache.get("query2").is_some());
        assert!(cache.get("query3").is_some());
    }

    #[test]
    fn test_execution_time_update() {
        let config = CacheConfig::default();
        let cache = LruQueryPlanCache::new(config);

        let query = "SELECT ?s WHERE { ?s ?p ?o }";
        let plan = ExecutionPlan::TripleScan {
            pattern: crate::model::pattern::TriplePattern::new(None, None, None),
        };

        cache
            .put(query, plan, 100.0)
            .expect("cache put should succeed");

        cache
            .update_execution_time(query, 50.0)
            .expect("update should succeed");

        let cached = cache.get(query).expect("cache get should succeed");
        assert_eq!(cached.avg_execution_time_ms, 50.0);

        cache
            .update_execution_time(query, 70.0)
            .expect("update should succeed");

        let cached2 = cache.get(query).expect("cache get should succeed");
        // Should be exponential moving average
        assert!(cached2.avg_execution_time_ms > 50.0 && cached2.avg_execution_time_ms < 70.0);
    }
}

// ===========================================================================
// Simpler, self-contained QueryPlanCache
//
// A lightweight alternative to LruQueryPlanCache that does not depend on the
// `lru` crate or SciRS2 metrics and is easier to use in unit tests and in
// parts of the system that only need basic LRU semantics.
// ===========================================================================

use std::collections::HashMap;

/// A compiled SPARQL query plan ready for execution.
#[derive(Debug, Clone)]
pub struct QueryPlan {
    /// FNV / DefaultHasher hash of the original query string.
    pub query_hash: u64,
    /// The raw SPARQL query string.
    pub original_query: String,
    /// Human-readable descriptions of the optimized pattern steps.
    pub optimized_patterns: Vec<String>,
    /// Estimated execution cost (lower is better).
    pub estimated_cost: f64,
    /// Unix timestamp (ms) when this plan was created.
    pub created_at_ms: i64,
}

impl QueryPlan {
    fn now_ms() -> i64 {
        use std::time::{SystemTime, UNIX_EPOCH};
        SystemTime::now()
            .duration_since(UNIX_EPOCH)
            .map(|d| d.as_millis() as i64)
            .unwrap_or(0)
    }

    /// Construct a new plan.  `created_at_ms` is set to the current time.
    pub fn new(
        query_hash: u64,
        original_query: impl Into<String>,
        optimized_patterns: Vec<String>,
        estimated_cost: f64,
    ) -> Self {
        Self {
            query_hash,
            original_query: original_query.into(),
            optimized_patterns,
            estimated_cost,
            created_at_ms: Self::now_ms(),
        }
    }
}

/// Aggregated statistics for a [`QueryPlanCache`] instance.
#[derive(Debug, Clone, Default)]
pub struct PlanCacheStats {
    /// Number of successful cache lookups.
    pub hits: u64,
    /// Number of failed cache lookups.
    pub misses: u64,
    /// Number of plans evicted to make room for new entries.
    pub evictions: u64,
    /// Current number of entries in the cache.
    pub size: usize,
}

/// A simple LRU query-plan cache with O(n) eviction.
///
/// This is deliberately kept dependency-free (no `lru` crate, no SciRS2).
/// The access order vector has the most-recently-used entry at the **front**
/// (index 0) and the least-recently-used at the **back**.
///
/// For the high-throughput LRU cache backed by the `lru` crate, see
/// [`LruQueryPlanCache`].
pub struct QueryPlanCache {
    plans: HashMap<u64, QueryPlan>,
    /// Most-recently-used at index 0; least-recently-used at the back.
    access_order: Vec<u64>,
    max_size: usize,
    stats: PlanCacheStats,
}

impl QueryPlanCache {
    /// Create a new cache that can hold at most `max_size` plans.
    ///
    /// If `max_size` is 0 it is treated as 1 to avoid degenerate behaviour.
    pub fn new(max_size: usize) -> Self {
        let max_size = max_size.max(1);
        Self {
            plans: HashMap::new(),
            access_order: Vec::new(),
            max_size,
            stats: PlanCacheStats::default(),
        }
    }

    /// Retrieve the plan for `query_hash`.
    ///
    /// On a hit the entry is moved to the front of the access-order list and
    /// `stats.hits` is incremented.  On a miss `stats.misses` is incremented.
    pub fn get(&mut self, query_hash: u64) -> Option<&QueryPlan> {
        if self.plans.contains_key(&query_hash) {
            // Move to front of access_order.
            if let Some(pos) = self.access_order.iter().position(|&h| h == query_hash) {
                self.access_order.remove(pos);
            }
            self.access_order.insert(0, query_hash);
            self.stats.hits += 1;
            self.plans.get(&query_hash)
        } else {
            self.stats.misses += 1;
            None
        }
    }

    /// Insert a plan into the cache.
    ///
    /// If the cache is at capacity, [`evict_lru`] is called first.  The new
    /// entry is placed at the front of the access-order list.
    ///
    /// [`evict_lru`]: QueryPlanCache::evict_lru
    pub fn insert(&mut self, plan: QueryPlan) {
        let hash = plan.query_hash;

        // If the hash is already present, remove it from access_order so it
        // can be re-inserted at the front.
        if self.plans.contains_key(&hash) {
            if let Some(pos) = self.access_order.iter().position(|&h| h == hash) {
                self.access_order.remove(pos);
            }
        } else if self.plans.len() >= self.max_size {
            self.evict_lru();
        }

        self.plans.insert(hash, plan);
        self.access_order.insert(0, hash);
        self.stats.size = self.plans.len();
    }

    /// Remove and return the least-recently-used plan (the one at the back of
    /// the access-order list).  Increments `stats.evictions`.
    ///
    /// Returns `None` if the cache is empty.
    pub fn evict_lru(&mut self) -> Option<QueryPlan> {
        let lru_hash = self.access_order.pop()?;
        let plan = self.plans.remove(&lru_hash);
        self.stats.evictions += 1;
        self.stats.size = self.plans.len();
        plan
    }

    /// Remove a specific plan by hash.  Returns `true` if it existed.
    pub fn invalidate(&mut self, query_hash: u64) -> bool {
        let existed = self.plans.remove(&query_hash).is_some();
        if existed {
            if let Some(pos) = self.access_order.iter().position(|&h| h == query_hash) {
                self.access_order.remove(pos);
            }
            self.stats.size = self.plans.len();
        }
        existed
    }

    /// Remove all entries and reset size to zero (other statistics are kept).
    pub fn clear(&mut self) {
        self.plans.clear();
        self.access_order.clear();
        self.stats.size = 0;
    }

    /// Return a snapshot of the current statistics.
    pub fn stats(&self) -> &PlanCacheStats {
        &self.stats
    }

    /// Cache hit rate: `hits / (hits + misses)`, or `0.0` if no operations
    /// have been performed yet.
    pub fn hit_rate(&self) -> f64 {
        let total = self.stats.hits + self.stats.misses;
        if total == 0 {
            0.0
        } else {
            self.stats.hits as f64 / total as f64
        }
    }

    /// Current number of cached plans.
    pub fn len(&self) -> usize {
        self.plans.len()
    }

    /// Return `true` if the cache contains no plans.
    pub fn is_empty(&self) -> bool {
        self.plans.is_empty()
    }
}

// ---------------------------------------------------------------------------
// Tests for the simple QueryPlanCache
// ---------------------------------------------------------------------------

#[cfg(test)]
mod simple_cache_tests {
    use super::*;

    fn make_plan(hash: u64, query: &str, cost: f64) -> QueryPlan {
        QueryPlan::new(hash, query, vec!["scan".to_string()], cost)
    }

    #[test]
    fn test_simple_cache_new_is_empty() {
        let cache = QueryPlanCache::new(10);
        assert!(cache.is_empty());
        assert_eq!(cache.len(), 0);
    }

    #[test]
    fn test_simple_cache_insert_and_get_hit() {
        let mut cache = QueryPlanCache::new(10);
        cache.insert(make_plan(1, "SELECT ?s ?p ?o WHERE {?s ?p ?o}", 100.0));
        let plan = cache.get(1);
        assert!(plan.is_some());
        assert_eq!(plan.expect("plan should exist").query_hash, 1);
    }

    #[test]
    fn test_simple_cache_miss_increments_stat() {
        let mut cache = QueryPlanCache::new(10);
        assert!(cache.get(42).is_none());
        assert_eq!(cache.stats().misses, 1);
        assert_eq!(cache.stats().hits, 0);
    }

    #[test]
    fn test_simple_cache_hit_increments_stat() {
        let mut cache = QueryPlanCache::new(10);
        cache.insert(make_plan(7, "SELECT * WHERE {?s ?p ?o}", 50.0));
        cache.get(7);
        assert_eq!(cache.stats().hits, 1);
        assert_eq!(cache.stats().misses, 0);
    }

    #[test]
    fn test_simple_cache_hit_rate_zero_initially() {
        let cache = QueryPlanCache::new(5);
        assert_eq!(cache.hit_rate(), 0.0);
    }

    #[test]
    fn test_simple_cache_hit_rate_after_ops() {
        let mut cache = QueryPlanCache::new(5);
        cache.insert(make_plan(1, "q1", 10.0));
        cache.get(1); // hit
        cache.get(2); // miss
        let rate = cache.hit_rate();
        assert!((rate - 0.5).abs() < 1e-9);
    }

    #[test]
    fn test_simple_cache_evict_lru_on_full() {
        let mut cache = QueryPlanCache::new(2);
        cache.insert(make_plan(1, "q1", 1.0)); // LRU = q1
        cache.insert(make_plan(2, "q2", 2.0)); // LRU = q1, MRU = q2
                                               // Insert q3 — q1 should be evicted.
        cache.insert(make_plan(3, "q3", 3.0));
        assert_eq!(cache.len(), 2);
        assert!(cache.get(1).is_none(), "q1 should have been evicted");
        assert!(cache.get(2).is_some());
        assert!(cache.get(3).is_some());
    }

    #[test]
    fn test_simple_cache_evict_lru_access_order() {
        let mut cache = QueryPlanCache::new(2);
        cache.insert(make_plan(1, "q1", 1.0));
        cache.insert(make_plan(2, "q2", 2.0));
        // Access q1 to make it MRU; q2 becomes LRU.
        cache.get(1);
        // Insert q3 — q2 should be evicted.
        cache.insert(make_plan(3, "q3", 3.0));
        assert!(cache.get(2).is_none(), "q2 should have been evicted");
        assert!(cache.get(1).is_some());
        assert!(cache.get(3).is_some());
    }

    #[test]
    fn test_simple_cache_evict_lru_explicit() {
        let mut cache = QueryPlanCache::new(5);
        cache.insert(make_plan(1, "q1", 1.0));
        cache.insert(make_plan(2, "q2", 2.0));
        let evicted = cache.evict_lru();
        assert!(evicted.is_some());
        assert_eq!(cache.stats().evictions, 1);
        assert_eq!(cache.len(), 1);
    }

    #[test]
    fn test_simple_cache_evict_lru_empty_returns_none() {
        let mut cache = QueryPlanCache::new(5);
        assert!(cache.evict_lru().is_none());
    }

    #[test]
    fn test_simple_cache_invalidate_existing() {
        let mut cache = QueryPlanCache::new(5);
        cache.insert(make_plan(99, "q99", 9.0));
        let removed = cache.invalidate(99);
        assert!(removed);
        assert!(cache.is_empty());
    }

    #[test]
    fn test_simple_cache_invalidate_missing_returns_false() {
        let mut cache = QueryPlanCache::new(5);
        assert!(!cache.invalidate(404));
    }

    #[test]
    fn test_simple_cache_clear() {
        let mut cache = QueryPlanCache::new(5);
        cache.insert(make_plan(1, "q1", 1.0));
        cache.insert(make_plan(2, "q2", 2.0));
        cache.clear();
        assert!(cache.is_empty());
        assert_eq!(cache.stats().size, 0);
    }

    #[test]
    fn test_simple_cache_plan_fields() {
        let plan = QueryPlan::new(
            42,
            "SELECT * WHERE {?s ?p ?o}",
            vec!["index_scan".to_string()],
            2.5,
        );
        assert_eq!(plan.query_hash, 42);
        assert_eq!(plan.optimized_patterns, vec!["index_scan".to_string()]);
        assert!((plan.estimated_cost - 2.5).abs() < 1e-9);
        assert!(plan.created_at_ms >= 0);
    }

    #[test]
    fn test_simple_cache_stats_size_tracks_inserts() {
        let mut cache = QueryPlanCache::new(10);
        cache.insert(make_plan(1, "q1", 1.0));
        cache.insert(make_plan(2, "q2", 2.0));
        assert_eq!(cache.stats().size, 2);
    }

    #[test]
    fn test_simple_cache_reinsertion_updates_access_order() {
        let mut cache = QueryPlanCache::new(3);
        cache.insert(make_plan(1, "q1", 1.0));
        cache.insert(make_plan(2, "q2", 2.0));
        // Re-insert q1; it should become MRU.  Then insert q3: q2 (LRU) is evicted.
        cache.insert(make_plan(1, "q1", 1.5)); // update q1, now MRU
                                               // Cache at capacity (2 distinct hashes since max_size=3 and we have 2).
                                               // Insert q3 now — cache has room, no eviction.
        cache.insert(make_plan(3, "q3", 3.0));
        assert_eq!(cache.len(), 3); // 1, 2, 3 all present
    }
}