linkrs_storage/edge/csr_with_properties.rs
1//! CSR with Properties — ladybug-style columnar storage.
2//!
3//! Properties are stored in parallel column arrays keyed by `EdgeId` through
4//! the edge-to-row map. The topology CSR owns the only adjacency index; this
5//! store keeps no per-vertex offsets, lengths, or append heads.
6//!
7//! This implementation uses `Column` (continuous arrays) instead of
8//! `HashMap<u32, Value>` for cache-friendly scans and lower memory overhead.
9//!
10//! Visibility authority lives in `MVCCManager` (`edge_timestamps`): these CSR
11//! row stamps are only a physical projection kept in sync on the write path
12//! for garbage collection. They must never decide query visibility alone.
13
14use std::collections::{HashMap, HashSet};
15use std::sync::Arc;
16
17use linkrs_core::types::{EdgeId, Timestamp};
18use linkrs_core::Value;
19
20use crate::edge::property_schema::PropertySchema;
21use crate::vertex::column::Column;
22
23/// Row visibility for MVCC.
24///
25/// Physical projection of the version authority for collection only.
26/// Every visibility decision delegates to the single
27/// [`crate::mvcc_visibility::Visibility`] predicate so this copy can never
28/// drift into a second time comparison.
29#[derive(Debug, Clone, Copy)]
30struct RowVisibility {
31 create_ts: Timestamp,
32 delete_ts: Option<Timestamp>,
33}
34
35/// Explicit row lifecycle replacing the bare zero-timestamp sentinel check.
36#[derive(Debug, Clone, Copy, PartialEq, Eq)]
37enum RowState {
38 Virgin,
39 Live,
40 Deleted,
41}
42
43impl RowVisibility {
44 fn state(&self) -> RowState {
45 if self.create_ts == linkrs_core::types::RESERVED_ZERO_TIMESTAMP && self.delete_ts.is_none()
46 {
47 RowState::Virgin
48 } else if self.delete_ts.is_some() {
49 RowState::Deleted
50 } else {
51 RowState::Live
52 }
53 }
54
55 fn is_virgin(&self) -> bool {
56 self.state() == RowState::Virgin
57 }
58
59 fn is_live(&self) -> bool {
60 self.state() == RowState::Live
61 }
62}
63
64/// Columnar property storage keyed by edge id.
65///
66/// Every edge owns exactly one row, including edges without properties.
67/// Row identity is the edge-to-row map; there is no per-vertex addressing.
68///
69/// Memory and persistence semantics: property before-images (row version
70/// chains) stay memory-only; `dump` serializes current values plus row
71/// visibility, per-column stable identifiers, encoding choices and refreshed
72/// statistics. A reload restores plain values first, then re-applies the
73/// recorded encodings and statistics, so encoded scans survive checkpoints.
74/// Attribute time travel is therefore valid within a checkpoint epoch.
75/// Row slot holding no edge mapping inside the dense edge map.
76const UNMAPPED_ROW: u32 = u32::MAX;
77
78/// FSST symbol-table ceiling applied whenever a column is encoded. One
79/// value for every encode site, so a column encoded by maintenance and the
80/// same column encoded by a checkpoint share identical parameters.
81pub(crate) const FSST_MAX_SYMBOLS: usize = 255;
82
83/// Exported property row: `(create_ts, delete_ts, per-column values)`.
84pub type ExportedRow = (Timestamp, Option<Timestamp>, Vec<(Arc<str>, Option<Value>)>);
85
86#[derive(Debug, Clone)]
87pub struct CsrWithProperties {
88 property_schema: Vec<PropertySchema>,
89 property_columns: Vec<Column>,
90 /// Column position by name, rebuilt on every schema mutation so hot
91 /// paths never scan the schema linearly.
92 column_index: HashMap<Arc<str>, usize>,
93 /// Column position by stable identifier, rebuilt with the name index.
94 /// Undo parameters keyed by id resolve through this instead of scanning.
95 prop_id_index: HashMap<i32, usize>,
96 visibility: Vec<RowVisibility>,
97 /// Segmented sparse edge-to-row map indexed by the table-allocated edge id.
98 /// One segment covers `EDGE_MAP_SEGMENT_ROWS` ids; untouched segments stay
99 /// unallocated. Live entries hold row indexes, gaps hold `UNMAPPED_ROW`.
100 /// Slot order is preserved by ascending segment iteration.
101 edge_map_segments: Vec<Option<Box<[u32; 1024]>>>,
102 /// Live mapping count, maintained alongside the dense map.
103 edge_map_len: usize,
104 /// Reverse index for O(1) row-to-edge lookup. Authoritative with
105 /// `edge_to_row`; rebuilt on load, never persisted separately.
106 row_to_edge: Vec<Option<EdgeId>>,
107 free_list: Vec<u32>,
108 row_count: usize,
109 /// Column positions mutated since the last stats refresh or checkpoint.
110 /// Drives per-column stats refresh so clean columns never pay recompute.
111 /// Positions shift on schema mutation; the schema-mutating methods remap
112 /// this set together with the schema.
113 dirty_columns: HashSet<usize>,
114 /// Stable column identifier allocator. Never reused or reassigned so
115 /// stored undo parameters keyed by id stay valid across column drops.
116 next_prop_id: i32,
117 /// Checkpoint-epoch floor for attribute time travel.
118 ///
119 /// Row version chains stay memory-only, so a load drops every
120 /// before-image. Strict reads below this floor for rows created at or
121 /// below the query timestamp fail instead of returning the current
122 /// value. Recomputed on every load as the maximum creation stamp;
123 /// zero on fresh tables, disabling the fence.
124 history_floor: Timestamp,
125 /// Inline-form marker: the owning table stores its single scalar in the
126 /// CSR value column, so this store keeps only the schema and the
127 /// name/id indexes. Every row operation fails instead of forking a
128 /// second property truth.
129 inline: bool,
130}
131
132pub(crate) mod encoding;
133pub(crate) mod maintenance;
134pub(crate) mod mapping;
135pub(crate) mod persistence;
136pub(crate) mod read;
137pub(crate) mod schema;
138pub(crate) mod transfer;
139pub(crate) mod visibility;
140pub(crate) mod write;
141
142#[cfg(test)]
143mod tests;