use serde::{Deserialize, Serialize};
use std::collections::HashMap;
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct TableStats {
pub table_name: String,
pub total_rows: usize,
pub page_count: usize,
pub column_distinct: HashMap<String, usize>,
pub column_nulls: HashMap<String, usize>,
pub avg_row_size: usize,
pub last_analyzed_epoch_secs: u64,
}
impl TableStats {
pub fn new(table_name: &str, total_rows: usize, page_count: usize) -> Self {
let avg_size = page_count
.saturating_mul(4096)
.checked_div(total_rows)
.unwrap_or(128);
Self {
table_name: table_name.to_string(),
total_rows,
page_count: page_count.max(1),
column_distinct: HashMap::new(),
column_nulls: HashMap::new(),
avg_row_size: avg_size.max(16),
last_analyzed_epoch_secs: web_time::SystemTime::now()
.duration_since(web_time::UNIX_EPOCH)
.unwrap_or_default()
.as_secs(),
}
}
pub fn estimate_selectivity(&self, column: &str, is_equality: bool) -> f64 {
if self.total_rows == 0 {
return 1.0;
}
if let Some(&distinct) = self.column_distinct.get(column)
&& distinct > 0
{
if is_equality {
return (1.0 / distinct as f64).min(1.0);
} else {
return 0.33;
}
}
if is_equality {
0.1 } else {
0.33
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PlanType {
PkLookup,
IndexScan,
SeqScan,
HnswVectorScan,
BruteForceVectorScan,
HashJoin,
NestedLoopJoin,
}
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct CostEstimate {
pub startup_cost: f64,
pub total_cost: f64,
pub estimated_rows: usize,
pub plan_detail: String,
}
impl std::fmt::Display for CostEstimate {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"(cost={:.2}..{:.2} rows={})",
self.startup_cost, self.total_cost, self.estimated_rows
)
}
}
pub struct CostOptimizer {
pub page_io_cost: f64,
pub seq_page_cost: f64,
pub cpu_eval_cost: f64,
pub index_cpu_cost: f64,
pub vector_chunk_cost: f64,
}
impl Default for CostOptimizer {
fn default() -> Self {
Self {
page_io_cost: 1.0,
seq_page_cost: 0.8,
cpu_eval_cost: 0.01,
index_cpu_cost: 0.005,
vector_chunk_cost: 0.02,
}
}
}
impl CostOptimizer {
pub fn new() -> Self {
Self::default()
}
pub fn estimate_seq_scan(&self, stats: &TableStats, selectivity: f64) -> CostEstimate {
let startup_cost = 0.0;
let io_cost = (stats.page_count as f64) * self.seq_page_cost;
let cpu_cost = (stats.total_rows as f64) * self.cpu_eval_cost;
let total_cost = startup_cost + io_cost + cpu_cost;
let estimated_rows = ((stats.total_rows as f64) * selectivity).round() as usize;
CostEstimate {
startup_cost,
total_cost,
estimated_rows: estimated_rows.max(1),
plan_detail: format!(
"SeqScan on {} {}",
stats.table_name,
CostEstimate {
startup_cost,
total_cost,
estimated_rows: estimated_rows.max(1),
plan_detail: String::new()
}
),
}
}
pub fn estimate_pk_lookup(&self, stats: &TableStats) -> CostEstimate {
let tree_depth = (stats.page_count as f64).log2().clamp(1.0, 4.0);
let startup_cost = tree_depth * self.page_io_cost;
let total_cost = startup_cost + self.cpu_eval_cost;
CostEstimate {
startup_cost,
total_cost,
estimated_rows: 1,
plan_detail: format!(
"PkLookup on {} (cost={:.2}..{:.2} rows=1)",
stats.table_name, startup_cost, total_cost
),
}
}
pub fn estimate_index_scan(
&self,
stats: &TableStats,
index_name: &str,
column: &str,
selectivity: f64,
) -> CostEstimate {
let tree_depth = (stats.page_count as f64).log2().clamp(1.0, 4.0);
let startup_cost = tree_depth * 0.5; let estimated_rows = ((stats.total_rows as f64) * selectivity).round().max(1.0) as usize;
let index_io = (estimated_rows as f64) * self.index_cpu_cost;
let table_fetch_io = (estimated_rows as f64) * self.page_io_cost;
let total_cost = startup_cost + index_io + table_fetch_io;
CostEstimate {
startup_cost,
total_cost,
estimated_rows,
plan_detail: format!(
"IndexScan on {} using {} on col '{}' (cost={:.2}..{:.2} rows={})",
stats.table_name, index_name, column, startup_cost, total_cost, estimated_rows
),
}
}
pub fn estimate_vector_search(
&self,
stats: &TableStats,
top_k: usize,
dimensions: usize,
has_hnsw_index: bool,
) -> CostEstimate {
if has_hnsw_index {
let startup_cost = 0.5;
let log_n = (stats.total_rows as f64).log2().max(1.0);
let distance_evals = log_n * 16.0; let compute_cost = distance_evals * (dimensions as f64 / 8.0) * self.vector_chunk_cost;
let total_cost = startup_cost + compute_cost;
CostEstimate {
startup_cost,
total_cost,
estimated_rows: top_k.min(stats.total_rows.max(1)),
plan_detail: format!(
"HnswVectorScan on {} [k={top_k}, d={dimensions}] (cost={:.2}..{:.2} rows={})",
stats.table_name,
startup_cost,
total_cost,
top_k.min(stats.total_rows.max(1))
),
}
} else {
let startup_cost = 0.0;
let io_cost = (stats.page_count as f64) * self.seq_page_cost;
let compute_cost =
(stats.total_rows as f64) * (dimensions as f64 / 8.0) * self.vector_chunk_cost;
let total_cost = startup_cost + io_cost + compute_cost;
CostEstimate {
startup_cost,
total_cost,
estimated_rows: top_k.min(stats.total_rows.max(1)),
plan_detail: format!(
"BruteForceVectorScan on {} [k={top_k}, d={dimensions}] (cost={:.2}..{:.2} rows={})",
stats.table_name,
startup_cost,
total_cost,
top_k.min(stats.total_rows.max(1))
),
}
}
}
pub fn choose_scan_plan(
&self,
stats: &TableStats,
available_index: Option<(&str, &str)>, is_pk_candidate: bool,
selectivity: f64,
) -> (PlanType, CostEstimate) {
if is_pk_candidate {
let pk_cost = self.estimate_pk_lookup(stats);
return (PlanType::PkLookup, pk_cost);
}
let seq_cost = self.estimate_seq_scan(stats, selectivity);
if let Some((idx_name, col)) = available_index {
let idx_cost = self.estimate_index_scan(stats, idx_name, col, selectivity);
if idx_cost.total_cost < seq_cost.total_cost {
return (PlanType::IndexScan, idx_cost);
}
}
(PlanType::SeqScan, seq_cost)
}
}