wasm_dbms_memory/table_registry/
index_ledger.rs

1// Rust guideline compliant 2026-03-27
2
3//! The index ledger is responsible for keeping track of all the indexes in the database.
4//! It allows for efficient lookup of indexes by name and provides a way to add and remove indexes from the ledger.
5//!
6//! The memory structure consists in having at root level a ledger which associates a name to an index,
7//! and the index itself is a structure that contains the information about the index,
8//! such as the columns it indexes and the type of index (e.g. B-tree, hash, etc.).
9
10mod index_tree;
11
12use std::collections::HashMap;
13
14use wasm_dbms_api::memory::{DEFAULT_ALIGNMENT, MSize, Page};
15use wasm_dbms_api::prelude::{Encode, IndexDef, MemoryError, MemoryResult, PageOffset};
16
17use self::index_tree::IndexTree;
18pub use self::index_tree::IndexTreeWalker;
19use super::RecordAddress;
20use crate::MemoryAccess;
21
22/// The [`IndexLedger`] struct is responsible for managing and providing access to the indexes in the database.
23pub struct IndexLedger {
24    /// Page where the index ledger is stored.
25    ledger_page: Page,
26    /// Table mapping index names to their corresponding **root** page in memory.
27    /// Since indexes are stored as B-trees, the page associated with each index name is the root page of the B-tree structure representing the index.
28    tables: IndexLedgerTables,
29}
30
31/// The [`IndexLedgerTables`] struct is a wrapper around a `HashMap` that maps index names (as `Vec<String>`) to their corresponding root page in memory.
32#[derive(Debug, Clone)]
33struct IndexLedgerTables(HashMap<Vec<String>, Page>);
34
35impl IndexLedger {
36    /// Initializes the index ledger by creating an empty ledger page in memory and setting up the initial structure.
37    pub fn init(
38        ledger_page: Page,
39        indexes: &[IndexDef],
40        mm: &mut impl MemoryAccess,
41    ) -> MemoryResult<()> {
42        let mut tables = HashMap::with_capacity(indexes.len());
43        for index in indexes {
44            let root_page = IndexTree::<wasm_dbms_api::prelude::Uint32>::init(mm)?.root_page();
45            tables.insert(
46                index.0.iter().map(ToString::to_string).collect::<Vec<_>>(),
47                root_page,
48            );
49        }
50
51        let ledger = IndexLedger {
52            ledger_page,
53            tables: IndexLedgerTables(tables),
54        };
55
56        mm.write_at(ledger_page, 0, &ledger.tables)
57    }
58
59    /// Load the page ledger from memory at the given [`Page`].
60    pub fn load(page: Page, mm: &mut impl MemoryAccess) -> MemoryResult<Self> {
61        Ok(Self {
62            tables: mm.read_at(page, 0)?,
63            ledger_page: page,
64        })
65    }
66
67    /// Inserts a key-pointer pair into the index identified by `columns`.
68    pub fn insert<K>(
69        &mut self,
70        columns: &[&str],
71        key: K,
72        pointer: RecordAddress,
73        mm: &mut impl MemoryAccess,
74    ) -> MemoryResult<()>
75    where
76        K: Encode + Ord,
77    {
78        let root_page = self.lookup_root_page(columns)?;
79        let mut tree = IndexTree::<K>::load(root_page);
80        tree.insert(key, pointer, mm)?;
81        self.persist_root_if_changed(columns, root_page, tree.root_page(), mm)
82    }
83
84    /// Looks up all pointers matching `key` in the index identified by `columns`.
85    pub fn search<K>(
86        &self,
87        columns: &[&str],
88        key: &K,
89        mm: &mut impl MemoryAccess,
90    ) -> MemoryResult<Vec<RecordAddress>>
91    where
92        K: Encode + Ord,
93    {
94        let root_page = self.lookup_root_page(columns)?;
95        IndexTree::<K>::load(root_page).search(key, mm)
96    }
97
98    /// Deletes a specific key-pointer pair from the index identified by `columns`.
99    pub fn delete<K>(
100        &mut self,
101        columns: &[&str],
102        key: &K,
103        pointer: RecordAddress,
104        mm: &mut impl MemoryAccess,
105    ) -> MemoryResult<()>
106    where
107        K: Encode + Ord,
108    {
109        let root_page = self.lookup_root_page(columns)?;
110        IndexTree::<K>::load(root_page).delete(key, pointer, mm)
111    }
112
113    /// Updates a specific key-pointer pair in the index identified by `columns`.
114    pub fn update<K>(
115        &mut self,
116        columns: &[&str],
117        key: &K,
118        old_pointer: RecordAddress,
119        new_pointer: RecordAddress,
120        mm: &mut impl MemoryAccess,
121    ) -> MemoryResult<()>
122    where
123        K: Encode + Ord,
124    {
125        let root_page = self.lookup_root_page(columns)?;
126        let mut tree = IndexTree::<K>::load(root_page);
127        tree.update(key, old_pointer, new_pointer, mm)?;
128        self.persist_root_if_changed(columns, root_page, tree.root_page(), mm)
129    }
130
131    /// Opens a forward range scan on the index identified by `columns`.
132    pub fn range_scan<K>(
133        &self,
134        columns: &[&str],
135        start_key: &K,
136        end_key: Option<&K>,
137        mm: &mut impl MemoryAccess,
138    ) -> MemoryResult<IndexTreeWalker<K>>
139    where
140        K: Encode + Ord,
141    {
142        let root_page = self.lookup_root_page(columns)?;
143        IndexTree::<K>::load(root_page).range_scan(start_key, end_key, mm)
144    }
145
146    fn lookup_root_page(&self, columns: &[&str]) -> MemoryResult<Page> {
147        let key = columns.iter().map(ToString::to_string).collect::<Vec<_>>();
148        self.tables
149            .0
150            .get(&key)
151            .copied()
152            .ok_or(MemoryError::IndexNotFound(key))
153    }
154
155    fn persist_root_if_changed(
156        &mut self,
157        columns: &[&str],
158        old_root_page: Page,
159        new_root_page: Page,
160        mm: &mut impl MemoryAccess,
161    ) -> MemoryResult<()> {
162        if old_root_page == new_root_page {
163            return Ok(());
164        }
165
166        let key = columns.iter().map(ToString::to_string).collect::<Vec<_>>();
167        self.tables.0.insert(key, new_root_page);
168        mm.write_at(self.ledger_page, 0, &self.tables)
169    }
170}
171
172impl Encode for IndexLedgerTables {
173    const ALIGNMENT: PageOffset = DEFAULT_ALIGNMENT;
174
175    const SIZE: wasm_dbms_api::prelude::DataSize = wasm_dbms_api::prelude::DataSize::Dynamic;
176
177    fn size(&self) -> wasm_dbms_api::prelude::MSize {
178        // - 8: len of the ledger (number of entries)
179        // - for each entry:
180        //   - 8: len of the number of columns in the index (the key is a Vec<String>)
181        //   - for each column name:
182        //     - 1: len of the column name
183        //     - (name.len() as MSize): the column name itself
184        //   - 4: root page number (Page = u32)
185        8 + self
186            .0
187            .keys()
188            .map(|columns| {
189                8 + columns
190                    .iter()
191                    .map(|col_name| 1 + (col_name.len() as MSize))
192                    .sum::<MSize>()
193                    + 4
194            })
195            .sum::<MSize>()
196    }
197
198    fn encode(&'_ self) -> std::borrow::Cow<'_, [u8]> {
199        let mut bytes = Vec::with_capacity(self.size() as usize);
200        // Encode the number of entries in the ledger
201        bytes.extend_from_slice(&(self.0.len() as u64).to_le_bytes());
202        for (columns, root_page) in &self.0 {
203            // Encode the number of columns in the index
204            bytes.extend_from_slice(&(columns.len() as u64).to_le_bytes());
205            for col_name in columns {
206                // Encode the length of the column name and the column name itself
207                bytes.push(col_name.len() as u8);
208                bytes.extend_from_slice(col_name.as_bytes());
209            }
210            // Encode the root page number (4 bytes, Page = u32)
211            bytes.extend_from_slice(&root_page.to_le_bytes());
212        }
213        bytes.into()
214    }
215
216    fn decode(data: std::borrow::Cow<[u8]>) -> MemoryResult<Self>
217    where
218        Self: Sized,
219    {
220        let mut offset = 0;
221        // Decode the number of entries in the ledger
222        let num_entries = u64::from_le_bytes(data[offset..offset + 8].try_into()?) as usize;
223        offset += 8;
224        let mut tables = HashMap::with_capacity(num_entries);
225        for _ in 0..num_entries {
226            // Decode the number of columns in the index
227            let num_columns = u64::from_le_bytes(data[offset..offset + 8].try_into()?) as usize;
228            offset += 8;
229            let mut columns = Vec::with_capacity(num_columns);
230            for _ in 0..num_columns {
231                // Decode the length of the column name and the column name itself
232                let col_name_len = data[offset] as usize;
233                offset += 1;
234                let col_name = String::from_utf8(data[offset..offset + col_name_len].to_vec())?;
235                offset += col_name_len;
236                columns.push(col_name);
237            }
238            // Decode the root page number (4 bytes, Page = u32)
239            let root_page = Page::from_le_bytes(data[offset..offset + 4].try_into()?);
240            offset += 4;
241            tables.insert(columns, root_page);
242        }
243        Ok(Self(tables))
244    }
245}
246
247#[cfg(test)]
248mod tests {
249    use wasm_dbms_api::prelude::Uint32;
250
251    use super::*;
252    use crate::{HeapMemoryProvider, MemoryManager};
253
254    #[test]
255    fn test_encode_decode_empty_ledger() {
256        let tables = IndexLedgerTables(HashMap::new());
257        let encoded = tables.encode();
258        let decoded = IndexLedgerTables::decode(encoded).expect("decode failed");
259
260        assert!(decoded.0.is_empty());
261    }
262
263    #[test]
264    fn test_encode_decode_single_column_index() {
265        let mut map = HashMap::new();
266        map.insert(vec!["name".to_string()], 42u32);
267        let tables = IndexLedgerTables(map);
268
269        let encoded = tables.encode();
270        let decoded = IndexLedgerTables::decode(encoded).expect("decode failed");
271
272        assert_eq!(decoded.0.len(), 1);
273        assert_eq!(decoded.0[&vec!["name".to_string()]], 42);
274    }
275
276    #[test]
277    fn test_encode_decode_composite_index() {
278        let mut map = HashMap::new();
279        map.insert(
280            vec!["first_name".to_string(), "last_name".to_string()],
281            99u32,
282        );
283        let tables = IndexLedgerTables(map);
284
285        let encoded = tables.encode();
286        let decoded = IndexLedgerTables::decode(encoded).expect("decode failed");
287
288        assert_eq!(decoded.0.len(), 1);
289        assert_eq!(
290            decoded.0[&vec!["first_name".to_string(), "last_name".to_string()]],
291            99
292        );
293    }
294
295    #[test]
296    fn test_encode_decode_multiple_indexes() {
297        let mut map = HashMap::new();
298        map.insert(vec!["id".to_string()], 10u32);
299        map.insert(vec!["email".to_string()], 20u32);
300        map.insert(vec!["city".to_string(), "zip".to_string()], 30u32);
301        let tables = IndexLedgerTables(map.clone());
302
303        let encoded = tables.encode();
304        let decoded = IndexLedgerTables::decode(encoded).expect("decode failed");
305
306        assert_eq!(decoded.0.len(), 3);
307        assert_eq!(decoded.0[&vec!["id".to_string()]], 10);
308        assert_eq!(decoded.0[&vec!["email".to_string()]], 20);
309        assert_eq!(decoded.0[&vec!["city".to_string(), "zip".to_string()]], 30);
310    }
311
312    #[test]
313    fn test_size_matches_encoded_length() {
314        let mut map = HashMap::new();
315        map.insert(vec!["id".to_string()], 10u32);
316        map.insert(vec!["first".to_string(), "last".to_string()], 20u32);
317        let tables = IndexLedgerTables(map);
318
319        let size = tables.size() as usize;
320        let encoded = tables.encode();
321
322        assert_eq!(
323            encoded.len(),
324            size,
325            "size() returned {size} but encode() produced {} bytes",
326            encoded.len()
327        );
328    }
329
330    #[test]
331    fn test_size_empty_ledger() {
332        let tables = IndexLedgerTables(HashMap::new());
333        // Only the 8-byte entry count
334        assert_eq!(tables.size(), 8);
335    }
336
337    #[test]
338    fn test_encode_decode_large_page_number() {
339        let mut map = HashMap::new();
340        // Use a page number > u16::MAX to verify 4-byte encoding
341        map.insert(vec!["col".to_string()], 70_000u32);
342        let tables = IndexLedgerTables(map);
343
344        let encoded = tables.encode();
345        let decoded = IndexLedgerTables::decode(encoded).expect("decode failed");
346
347        assert_eq!(decoded.0[&vec!["col".to_string()]], 70_000);
348    }
349
350    #[test]
351    fn test_init_no_indexes() {
352        let mut mm = MemoryManager::init(HeapMemoryProvider::default());
353        let ledger_page = mm.allocate_page().expect("failed to allocate page");
354
355        IndexLedger::init(ledger_page, &[], &mut mm).expect("init failed");
356
357        let loaded = IndexLedger::load(ledger_page, &mut mm).expect("load failed");
358        assert!(loaded.tables.0.is_empty());
359    }
360
361    #[test]
362    fn test_init_and_load_single_index() {
363        let mut mm = MemoryManager::init(HeapMemoryProvider::default());
364        let ledger_page = mm.allocate_page().expect("failed to allocate page");
365
366        let indexes = [IndexDef(&["email"])];
367        IndexLedger::init(ledger_page, &indexes, &mut mm).expect("init failed");
368
369        let loaded = IndexLedger::load(ledger_page, &mut mm).expect("load failed");
370        assert_eq!(loaded.tables.0.len(), 1);
371        assert!(loaded.tables.0.contains_key(&vec!["email".to_string()]));
372    }
373
374    #[test]
375    fn test_init_and_load_multiple_indexes() {
376        let mut mm = MemoryManager::init(HeapMemoryProvider::default());
377        let ledger_page = mm.allocate_page().expect("failed to allocate page");
378
379        let indexes = [IndexDef(&["id"]), IndexDef(&["first_name", "last_name"])];
380        IndexLedger::init(ledger_page, &indexes, &mut mm).expect("init failed");
381
382        let loaded = IndexLedger::load(ledger_page, &mut mm).expect("load failed");
383        assert_eq!(loaded.tables.0.len(), 2);
384        assert!(loaded.tables.0.contains_key(&vec!["id".to_string()]));
385        assert!(
386            loaded
387                .tables
388                .0
389                .contains_key(&vec!["first_name".to_string(), "last_name".to_string()])
390        );
391    }
392
393    #[test]
394    fn test_init_allocates_distinct_root_pages() {
395        let mut mm = MemoryManager::init(HeapMemoryProvider::default());
396        let ledger_page = mm.allocate_page().expect("failed to allocate page");
397
398        let indexes = [IndexDef(&["a"]), IndexDef(&["b"]), IndexDef(&["c"])];
399        IndexLedger::init(ledger_page, &indexes, &mut mm).expect("init failed");
400
401        let loaded = IndexLedger::load(ledger_page, &mut mm).expect("load failed");
402        let pages: Vec<Page> = loaded.tables.0.values().copied().collect();
403        // All root pages should be distinct
404        let mut unique_pages = pages.clone();
405        unique_pages.sort();
406        unique_pages.dedup();
407        assert_eq!(pages.len(), unique_pages.len());
408    }
409
410    #[test]
411    fn test_ledger_insert_search_delete_update_and_range_scan() {
412        let mut mm = MemoryManager::init(HeapMemoryProvider::default());
413        let ledger_page = mm.allocate_page().expect("failed to allocate page");
414        let indexes = [IndexDef(&["email"])];
415        IndexLedger::init(ledger_page, &indexes, &mut mm).expect("init failed");
416        let mut ledger = IndexLedger::load(ledger_page, &mut mm).expect("load failed");
417
418        let first = RecordAddress { page: 1, offset: 0 };
419        let second = RecordAddress { page: 2, offset: 0 };
420        ledger
421            .insert(&["email"], Uint32(10), first.clone(), &mut mm)
422            .expect("first insert failed");
423        ledger
424            .insert(&["email"], Uint32(10), second.clone(), &mut mm)
425            .expect("second insert failed");
426        ledger
427            .insert(
428                &["email"],
429                Uint32(11),
430                RecordAddress { page: 3, offset: 0 },
431                &mut mm,
432            )
433            .expect("third insert failed");
434
435        let hits = ledger
436            .search(&["email"], &Uint32(10), &mut mm)
437            .expect("search failed");
438        assert_eq!(hits, vec![first.clone(), second.clone()]);
439
440        ledger
441            .delete(&["email"], &Uint32(10), first, &mut mm)
442            .expect("delete failed");
443        let hits = ledger
444            .search(&["email"], &Uint32(10), &mut mm)
445            .expect("search after delete failed");
446        assert_eq!(hits, vec![second.clone()]);
447
448        let replacement = RecordAddress { page: 4, offset: 0 };
449        ledger
450            .update(
451                &["email"],
452                &Uint32(10),
453                second,
454                replacement.clone(),
455                &mut mm,
456            )
457            .expect("update failed");
458        let hits = ledger
459            .search(&["email"], &Uint32(10), &mut mm)
460            .expect("search after update failed");
461        assert_eq!(hits, vec![replacement]);
462
463        let mut walker = ledger
464            .range_scan(&["email"], &Uint32(10), Some(&Uint32(12)), &mut mm)
465            .expect("range scan failed");
466        assert_eq!(
467            walker.next(&mut mm).expect("walker next failed"),
468            Some(RecordAddress { page: 4, offset: 0 })
469        );
470        assert_eq!(
471            walker.next(&mut mm).expect("walker next failed"),
472            Some(RecordAddress { page: 3, offset: 0 })
473        );
474        assert_eq!(walker.next(&mut mm).expect("walker end failed"), None);
475    }
476
477    #[test]
478    fn test_ledger_missing_index_returns_error() {
479        let mut mm = MemoryManager::init(HeapMemoryProvider::default());
480        let ledger_page = mm.allocate_page().expect("failed to allocate page");
481        IndexLedger::init(ledger_page, &[], &mut mm).expect("init failed");
482        let mut ledger = IndexLedger::load(ledger_page, &mut mm).expect("load failed");
483
484        let error = ledger
485            .insert(
486                &["missing"],
487                Uint32(1),
488                RecordAddress { page: 1, offset: 0 },
489                &mut mm,
490            )
491            .expect_err("missing index insert must fail");
492        assert!(
493            matches!(error, MemoryError::IndexNotFound(columns) if columns == vec!["missing".to_string()])
494        );
495    }
496}
wasm_dbms_memory/table_registry/index_ledger.rs

wasm_dbms_memory/table_registry/
index_ledger.rs
