oxirs_tdb/dictionary/
node_table.rs

1//! NodeTable for Term ↔ NodeId mapping with prefix compression
2
3use super::node_id::NodeId;
4use super::term::Term;
5use crate::btree::BTree;
6use crate::compression::prefix::PrefixCompressor;
7use crate::error::Result;
8use crate::storage::{BufferPool, PageId};
9use parking_lot::RwLock;
10use std::sync::Arc;
11
12/// NodeTable provides bidirectional mapping between Terms and NodeIds
13///
14/// Uses two B+Trees:
15/// - term_to_id: Term → NodeId (for encoding)
16/// - id_to_term: NodeId → Term (for decoding)
17///
18/// # Prefix Compression
19///
20/// For IRI terms, the NodeTable automatically applies prefix compression
21/// to reduce storage overhead. Common IRI prefixes (namespaces) are stored
22/// once and referenced by ID, significantly reducing memory usage for
23/// datasets with many IRIs sharing the same namespace.
24pub struct NodeTable {
25    /// B+Tree mapping Term → NodeId
26    term_to_id: RwLock<BTree<Term, NodeId>>,
27
28    /// B+Tree mapping NodeId → Term
29    id_to_term: RwLock<BTree<NodeId, Term>>,
30
31    /// Next available NodeId
32    next_id: RwLock<NodeId>,
33
34    /// Prefix compressor for IRI optimization
35    prefix_compressor: RwLock<PrefixCompressor>,
36
37    /// Enable prefix compression (can be disabled for testing)
38    compression_enabled: bool,
39}
40
41impl NodeTable {
42    /// Create a new NodeTable with prefix compression enabled
43    pub fn new(buffer_pool: Arc<BufferPool>) -> Self {
44        Self::with_compression(buffer_pool, true)
45    }
46
47    /// Create a new NodeTable with configurable compression
48    pub fn with_compression(buffer_pool: Arc<BufferPool>, compression_enabled: bool) -> Self {
49        NodeTable {
50            term_to_id: RwLock::new(BTree::new(buffer_pool.clone())),
51            id_to_term: RwLock::new(BTree::new(buffer_pool)),
52            next_id: RwLock::new(NodeId::FIRST),
53            prefix_compressor: RwLock::new(PrefixCompressor::new(15)), // Minimum 15 chars for compression
54            compression_enabled,
55        }
56    }
57
58    /// Reconstruct a NodeTable from persisted B+Tree roots and the next id to
59    /// hand out (used when reopening a store from its superblock).
60    pub fn from_roots(
61        buffer_pool: Arc<BufferPool>,
62        term_to_id_root: Option<PageId>,
63        id_to_term_root: Option<PageId>,
64        next_id: NodeId,
65    ) -> Self {
66        let term_to_id = match term_to_id_root {
67            Some(page) => BTree::from_root(buffer_pool.clone(), page),
68            None => BTree::new(buffer_pool.clone()),
69        };
70        let id_to_term = match id_to_term_root {
71            Some(page) => BTree::from_root(buffer_pool.clone(), page),
72            None => BTree::new(buffer_pool),
73        };
74        NodeTable {
75            term_to_id: RwLock::new(term_to_id),
76            id_to_term: RwLock::new(id_to_term),
77            next_id: RwLock::new(next_id),
78            prefix_compressor: RwLock::new(PrefixCompressor::new(15)),
79            compression_enabled: true,
80        }
81    }
82
83    /// Current root page of the `term_to_id` B+Tree (for superblock persistence).
84    pub fn term_to_id_root(&self) -> Option<PageId> {
85        self.term_to_id.read().root_page()
86    }
87
88    /// Current root page of the `id_to_term` B+Tree (for superblock persistence).
89    pub fn id_to_term_root(&self) -> Option<PageId> {
90        self.id_to_term.read().root_page()
91    }
92
93    /// Next dictionary [`NodeId`] to be allocated (for superblock persistence).
94    pub fn next_id_value(&self) -> NodeId {
95        *self.next_id.read()
96    }
97
98    /// Get prefix compression statistics
99    pub fn compression_stats(&self) -> crate::compression::prefix::CompressionStats {
100        let compressor = self.prefix_compressor.read();
101        compressor.stats()
102    }
103
104    /// Get or create a NodeId for a term
105    ///
106    /// If the term already exists, returns its NodeId.
107    /// Otherwise, assigns a new NodeId and stores the mapping.
108    ///
109    /// # Prefix Compression
110    ///
111    /// When prefix compression is enabled and the term is an IRI,
112    /// the compressor tracks the IRI prefix for statistics. Future
113    /// versions will use this for actual storage optimization.
114    pub fn get_or_create(&self, term: &Term) -> Result<NodeId> {
115        // Try to find existing mapping
116        {
117            let term_to_id = self.term_to_id.read();
118            if let Some(id) = term_to_id.search(term)? {
119                return Ok(id);
120            }
121        }
122
123        // Term not found, create new mapping
124        let mut term_to_id = self.term_to_id.write();
125        let mut id_to_term = self.id_to_term.write();
126        let mut next_id = self.next_id.write();
127
128        // Double-check (another thread might have created it)
129        if let Some(id) = term_to_id.search(term)? {
130            return Ok(id);
131        }
132
133        // Track IRI prefix for compression statistics
134        if self.compression_enabled {
135            if let Some(iri) = term.as_iri() {
136                let mut compressor = self.prefix_compressor.write();
137                // Track the IRI to build prefix dictionary
138                // This doesn't change storage format yet, just tracks stats
139                let _ = compressor.compress(iri);
140            }
141        }
142
143        // Assign new NodeId
144        let id = *next_id;
145        *next_id = next_id.next();
146
147        // Store bidirectional mapping
148        term_to_id.insert(term.clone(), id)?;
149        id_to_term.insert(id, term.clone())?;
150
151        Ok(id)
152    }
153
154    /// Get NodeId for a term (returns None if not found)
155    pub fn get_id(&self, term: &Term) -> Result<Option<NodeId>> {
156        let term_to_id = self.term_to_id.read();
157        term_to_id.search(term)
158    }
159
160    /// Get Term for a NodeId (returns None if not found)
161    pub fn get_term(&self, id: NodeId) -> Result<Option<Term>> {
162        let id_to_term = self.id_to_term.read();
163        id_to_term.search(&id)
164    }
165
166    /// Get the total number of terms stored
167    pub fn size(&self) -> u64 {
168        let next_id = self.next_id.read();
169        next_id.as_u64() - NodeId::FIRST.as_u64()
170    }
171
172    /// Check if a term exists in the dictionary
173    pub fn contains(&self, term: &Term) -> Result<bool> {
174        Ok(self.get_id(term)?.is_some())
175    }
176
177    /// Check if a NodeId exists in the dictionary
178    pub fn contains_id(&self, id: NodeId) -> Result<bool> {
179        Ok(self.get_term(id)?.is_some())
180    }
181}
182
183#[cfg(test)]
184mod tests {
185    use super::*;
186    use crate::storage::FileManager;
187    use tempfile::TempDir;
188
189    fn create_test_node_table() -> (TempDir, NodeTable) {
190        let temp_dir = TempDir::new().unwrap();
191        let db_path = temp_dir.path().join("test.db");
192
193        let file_manager = Arc::new(FileManager::open(&db_path, true).unwrap());
194        let buffer_pool = Arc::new(BufferPool::new(100, file_manager));
195
196        let node_table = NodeTable::new(buffer_pool);
197        (temp_dir, node_table)
198    }
199
200    #[test]
201    fn test_node_table_get_or_create() -> Result<()> {
202        let (_temp_dir, table) = create_test_node_table();
203
204        let term1 = Term::iri("http://example.org/resource1");
205        let term2 = Term::iri("http://example.org/resource2");
206
207        let id1 = table.get_or_create(&term1)?;
208        let id2 = table.get_or_create(&term2)?;
209
210        // Different terms get different IDs
211        assert_ne!(id1, id2);
212
213        // Same term gets same ID
214        let id1_again = table.get_or_create(&term1)?;
215        assert_eq!(id1, id1_again);
216
217        Ok(())
218    }
219
220    #[test]
221    fn test_node_table_bidirectional_mapping() -> Result<()> {
222        let (_temp_dir, table) = create_test_node_table();
223
224        let term = Term::literal_with_lang("Hello World", "en");
225        let id = table.get_or_create(&term)?;
226
227        // Verify bidirectional mapping
228        assert_eq!(table.get_id(&term)?, Some(id));
229        assert_eq!(table.get_term(id)?, Some(term));
230
231        Ok(())
232    }
233
234    #[test]
235    fn test_node_table_get_id_not_found() -> Result<()> {
236        let (_temp_dir, table) = create_test_node_table();
237
238        let term = Term::iri("http://not-exists.com");
239        assert_eq!(table.get_id(&term)?, None);
240
241        Ok(())
242    }
243
244    #[test]
245    fn test_node_table_get_term_not_found() -> Result<()> {
246        let (_temp_dir, table) = create_test_node_table();
247
248        let id = NodeId::new(999);
249        assert_eq!(table.get_term(id)?, None);
250
251        Ok(())
252    }
253
254    #[test]
255    fn test_node_table_size() -> Result<()> {
256        let (_temp_dir, table) = create_test_node_table();
257
258        assert_eq!(table.size(), 0);
259
260        table.get_or_create(&Term::iri("http://a.com"))?;
261        assert_eq!(table.size(), 1);
262
263        table.get_or_create(&Term::iri("http://b.com"))?;
264        assert_eq!(table.size(), 2);
265
266        // Creating same term again doesn't increase size
267        table.get_or_create(&Term::iri("http://a.com"))?;
268        assert_eq!(table.size(), 2);
269
270        Ok(())
271    }
272
273    #[test]
274    fn test_node_table_contains() -> Result<()> {
275        let (_temp_dir, table) = create_test_node_table();
276
277        let term1 = Term::iri("http://exists.com");
278        let term2 = Term::iri("http://not-exists.com");
279
280        table.get_or_create(&term1)?;
281
282        assert!(table.contains(&term1)?);
283        assert!(!table.contains(&term2)?);
284
285        Ok(())
286    }
287
288    #[test]
289    fn test_node_table_contains_id() -> Result<()> {
290        let (_temp_dir, table) = create_test_node_table();
291
292        let term = Term::literal("test");
293        let id = table.get_or_create(&term)?;
294
295        assert!(table.contains_id(id)?);
296        assert!(!table.contains_id(NodeId::new(999))?);
297
298        Ok(())
299    }
300
301    #[test]
302    fn test_node_table_multiple_term_types() -> Result<()> {
303        let (_temp_dir, table) = create_test_node_table();
304
305        let iri = Term::iri("http://example.org");
306        let literal = Term::literal("test value");
307        let blank = Term::blank_node("b0");
308
309        let id1 = table.get_or_create(&iri)?;
310        let id2 = table.get_or_create(&literal)?;
311        let id3 = table.get_or_create(&blank)?;
312
313        // All get unique IDs
314        assert_ne!(id1, id2);
315        assert_ne!(id2, id3);
316        assert_ne!(id1, id3);
317
318        // All are retrievable
319        assert_eq!(table.get_term(id1)?, Some(iri));
320        assert_eq!(table.get_term(id2)?, Some(literal));
321        assert_eq!(table.get_term(id3)?, Some(blank));
322
323        Ok(())
324    }
325
326    #[test]
327    fn test_prefix_compression_integration() -> Result<()> {
328        let temp_dir = TempDir::new().unwrap();
329        let db_path = temp_dir.path().join("test.db");
330
331        let file_manager = Arc::new(FileManager::open(&db_path, true).unwrap());
332        let buffer_pool = Arc::new(BufferPool::new(100, file_manager));
333
334        // Create NodeTable with compression enabled
335        let table = NodeTable::with_compression(buffer_pool, true);
336
337        // Add IRIs sharing common namespaces
338        let iri1 = Term::iri("http://www.w3.org/1999/02/22-rdf-syntax-ns#type");
339        let iri2 = Term::iri("http://www.w3.org/1999/02/22-rdf-syntax-ns#Property");
340        let iri3 = Term::iri("http://www.w3.org/2000/01/rdf-schema#label");
341        let iri4 = Term::iri("http://www.w3.org/2000/01/rdf-schema#comment");
342
343        // Encode all IRIs
344        table.get_or_create(&iri1)?;
345        table.get_or_create(&iri2)?;
346        table.get_or_create(&iri3)?;
347        table.get_or_create(&iri4)?;
348
349        // Check compression statistics
350        let stats = table.compression_stats();
351
352        // Should have detected 2 common prefixes
353        assert_eq!(stats.num_prefixes, 2);
354
355        // Prefixes should save space
356        assert!(stats.total_prefix_bytes > 0);
357
358        Ok(())
359    }
360
361    #[test]
362    fn test_prefix_compression_disabled() -> Result<()> {
363        let temp_dir = TempDir::new().unwrap();
364        let db_path = temp_dir.path().join("test.db");
365
366        let file_manager = Arc::new(FileManager::open(&db_path, true).unwrap());
367        let buffer_pool = Arc::new(BufferPool::new(100, file_manager));
368
369        // Create NodeTable with compression disabled
370        let table = NodeTable::with_compression(buffer_pool, false);
371
372        // Add IRIs
373        let iri1 = Term::iri("http://example.org/Person");
374        let iri2 = Term::iri("http://example.org/name");
375
376        table.get_or_create(&iri1)?;
377        table.get_or_create(&iri2)?;
378
379        // Compression disabled - no prefixes should be tracked
380        let stats = table.compression_stats();
381        assert_eq!(stats.num_prefixes, 0);
382
383        Ok(())
384    }
385
386    #[test]
387    fn test_prefix_compression_with_short_iris() -> Result<()> {
388        let temp_dir = TempDir::new().unwrap();
389        let db_path = temp_dir.path().join("test.db");
390
391        let file_manager = Arc::new(FileManager::open(&db_path, true).unwrap());
392        let buffer_pool = Arc::new(BufferPool::new(100, file_manager));
393
394        let table = NodeTable::with_compression(buffer_pool, true);
395
396        // Add short IRI (below minimum compression threshold)
397        let short_iri = Term::iri("http://a.b");
398
399        table.get_or_create(&short_iri)?;
400
401        // Short IRIs should not create prefixes
402        let stats = table.compression_stats();
403        assert_eq!(stats.num_prefixes, 0);
404
405        Ok(())
406    }
407
408    #[test]
409    fn test_prefix_compression_with_literals() -> Result<()> {
410        let temp_dir = TempDir::new().unwrap();
411        let db_path = temp_dir.path().join("test.db");
412
413        let file_manager = Arc::new(FileManager::open(&db_path, true).unwrap());
414        let buffer_pool = Arc::new(BufferPool::new(100, file_manager));
415
416        let table = NodeTable::with_compression(buffer_pool, true);
417
418        // Add literals (should not be compressed)
419        let lit1 = Term::literal("This is a long literal value that could be compressed");
420        let lit2 = Term::literal("Another long literal value");
421
422        table.get_or_create(&lit1)?;
423        table.get_or_create(&lit2)?;
424
425        // Literals should not create prefixes
426        let stats = table.compression_stats();
427        assert_eq!(stats.num_prefixes, 0);
428
429        Ok(())
430    }
431
432    #[test]
433    fn test_prefix_compression_realistic_dataset() -> Result<()> {
434        let temp_dir = TempDir::new().unwrap();
435        let db_path = temp_dir.path().join("test.db");
436
437        let file_manager = Arc::new(FileManager::open(&db_path, true).unwrap());
438        let buffer_pool = Arc::new(BufferPool::new(100, file_manager));
439
440        let table = NodeTable::with_compression(buffer_pool, true);
441
442        // Simulate realistic RDF dataset with common vocabularies
443        let vocab_iris = vec![
444            // RDF vocabulary
445            "http://www.w3.org/1999/02/22-rdf-syntax-ns#type",
446            "http://www.w3.org/1999/02/22-rdf-syntax-ns#Property",
447            "http://www.w3.org/1999/02/22-rdf-syntax-ns#Statement",
448            // RDFS vocabulary
449            "http://www.w3.org/2000/01/rdf-schema#label",
450            "http://www.w3.org/2000/01/rdf-schema#comment",
451            "http://www.w3.org/2000/01/rdf-schema#Class",
452            // FOAF vocabulary
453            "http://xmlns.com/foaf/0.1/Person",
454            "http://xmlns.com/foaf/0.1/name",
455            "http://xmlns.com/foaf/0.1/knows",
456            // Application-specific
457            "http://example.org/vocab/Employee",
458            "http://example.org/vocab/salary",
459            "http://example.org/vocab/department",
460        ];
461
462        for iri in vocab_iris {
463            table.get_or_create(&Term::iri(iri))?;
464        }
465
466        // Should detect common namespace prefixes
467        let stats = table.compression_stats();
468
469        // Expect at least 4 prefixes: rdf, rdfs, foaf, example
470        assert!(stats.num_prefixes >= 4);
471
472        // Prefixes should provide meaningful compression
473        assert!(stats.total_prefix_bytes > 100);
474
475        Ok(())
476    }
477}
oxirs_tdb/dictionary/node_table.rs

oxirs_tdb/dictionary/
node_table.rs
