ddb_core/engine/
index.rs

1// Index structures for fast lookups in JOINs and WHERE clauses
2use crate::engine::row::Row;
3use crate::functions::Value;
4use std::collections::HashMap;
5
6/// Hash-based index for equality lookups
7/// Maps column value -> list of row indices with that value
8#[derive(Debug, Clone)]
9pub struct HashIndex {
10    /// Column name being indexed
11    column: String,
12    /// Map from column value (as string) to row indices
13    index: HashMap<String, Vec<usize>>,
14}
15
16impl HashIndex {
17    /// Create a new hash index on a specific column
18    pub fn new(column: String) -> Self {
19        HashIndex {
20            column,
21            index: HashMap::new(),
22        }
23    }
24
25    /// Build index from a vector of rows
26    pub fn build(column: &str, rows: &[Row]) -> Self {
27        let mut index = HashMap::new();
28
29        for (row_idx, row) in rows.iter().enumerate() {
30            if let Some(value) = row.get(column) {
31                let key = value_to_index_key(value);
32                index.entry(key).or_insert_with(Vec::new).push(row_idx);
33            }
34        }
35
36        HashIndex {
37            column: column.to_string(),
38            index,
39        }
40    }
41
42    /// Lookup rows by value - returns row indices
43    pub fn lookup(&self, value: &Value) -> Option<&Vec<usize>> {
44        let key = value_to_index_key(value);
45        self.index.get(&key)
46    }
47
48    /// Get the column name this index is built on
49    pub fn column(&self) -> &str {
50        &self.column
51    }
52
53    /// Get number of unique values in index
54    pub fn cardinality(&self) -> usize {
55        self.index.len()
56    }
57
58    /// Get total number of rows indexed
59    pub fn row_count(&self) -> usize {
60        self.index.values().map(|v| v.len()).sum()
61    }
62}
63
64/// Convert a value to an index key (string representation)
65fn value_to_index_key(value: &Value) -> String {
66    match value {
67        Value::Null => "NULL".to_string(),
68        Value::Integer(i) => format!("I:{}", i),
69        Value::Float(f) => format!("F:{}", f),
70        Value::String(s) => format!("S:{}", s),
71        Value::Boolean(b) => format!("B:{}", b),
72        Value::Date(d) => format!("D:{}", d.format("%Y-%m-%d")),
73        Value::DateTime(dt) => format!("DT:{}", dt.format("%Y-%m-%d %H:%M:%S")),
74        Value::Time(t) => format!("T:{}", t.format("%H:%M:%S")),
75    }
76}
77
78/// Index manager - holds multiple indexes for a table
79#[derive(Debug, Clone)]
80pub struct IndexManager {
81    /// Map from column name to hash index
82    indexes: HashMap<String, HashIndex>,
83}
84
85impl IndexManager {
86    /// Create a new index manager
87    pub fn new() -> Self {
88        IndexManager {
89            indexes: HashMap::new(),
90        }
91    }
92
93    /// Add an index for a column
94    pub fn add_index(&mut self, column: String, index: HashIndex) {
95        self.indexes.insert(column, index);
96    }
97
98    /// Get an index for a column if it exists
99    pub fn get_index(&self, column: &str) -> Option<&HashIndex> {
100        self.indexes.get(column)
101    }
102
103    /// Check if an index exists for a column
104    pub fn has_index(&self, column: &str) -> bool {
105        self.indexes.contains_key(column)
106    }
107
108    /// Build index for a column from rows
109    pub fn build_index(&mut self, column: &str, rows: &[Row]) {
110        let index = HashIndex::build(column, rows);
111        self.indexes.insert(column.to_string(), index);
112    }
113
114    /// Get statistics about all indexes
115    pub fn stats(&self) -> Vec<(String, usize, usize)> {
116        self.indexes
117            .iter()
118            .map(|(col, idx)| (col.clone(), idx.cardinality(), idx.row_count()))
119            .collect()
120    }
121}
122
123impl Default for IndexManager {
124    fn default() -> Self {
125        Self::new()
126    }
127}
128
129#[cfg(test)]
130mod tests {
131    use super::*;
132
133    fn create_test_rows() -> Vec<Row> {
134        let mut rows = Vec::new();
135        for i in 1..=100 {
136            let mut row = Row::new();
137            row.set("id", Value::Integer(i));
138            row.set("dept", Value::String(format!("dept{}", i % 10)));
139            row.set("salary", Value::Integer(30000 + i * 1000));
140            rows.push(row);
141        }
142        rows
143    }
144
145    #[test]
146    fn test_hash_index_build() {
147        let rows = create_test_rows();
148        let index = HashIndex::build("dept", &rows);
149
150        assert_eq!(index.cardinality(), 10); // 10 unique departments
151        assert_eq!(index.row_count(), 100); // 100 total rows
152    }
153
154    #[test]
155    fn test_hash_index_lookup() {
156        let rows = create_test_rows();
157        let index = HashIndex::build("dept", &rows);
158
159        let dept5 = Value::String("dept5".to_string());
160        let matches = index.lookup(&dept5).unwrap();
161        assert_eq!(matches.len(), 10); // 10 rows with dept5
162    }
163
164    #[test]
165    fn test_index_manager() {
166        let rows = create_test_rows();
167        let mut manager = IndexManager::new();
168
169        manager.build_index("id", &rows);
170        manager.build_index("dept", &rows);
171
172        assert!(manager.has_index("id"));
173        assert!(manager.has_index("dept"));
174        assert!(!manager.has_index("salary"));
175
176        let stats = manager.stats();
177        assert_eq!(stats.len(), 2);
178    }
179}
ddb_core/engine/index.rs

ddb_core/engine/
index.rs
