mongreldb_core/index/
maintain.rs

1//! Secondary-index **delta** maintenance for row replace / update.
2//!
3//! When a row is rewritten (product `update_many` normalizes to delete+put with
4//! a new `RowId`, or a same-PK put replaces an older version), only **Bitmap**
5//! secondary keys that actually change need remove+insert work. Unchanged
6//! equality keys only re-point membership from the old row id to the new one
7//! (or no-op when the row id is unchanged).
8//!
9//! Pure planning lives here so tests can lock the delta policy without driving
10//! the full write path. Application against live maps is
11//! [`crate::engine::Table`]'s responsibility via
12//! [`apply_bitmap_secondary_delta`].
13
14use crate::index::BitmapIndex;
15use crate::memtable::{Row, Value};
16use crate::rowid::RowId;
17use crate::schema::{IndexKind, Schema};
18use std::collections::HashMap;
19
20/// One planned change against a single Bitmap secondary index column.
21#[derive(Debug, Clone, PartialEq, Eq)]
22pub enum BitmapIndexDelta {
23    /// Indexed key unchanged: re-point `old_row_id` → `new_row_id` under `key`
24    /// when the ids differ; pure no-op when they are equal.
25    Repoint { column_id: u16, key: Vec<u8> },
26    /// Indexed key changed (or appeared/disappeared): drop old membership and
27    /// insert new when present.
28    Move {
29        column_id: u16,
30        old_key: Option<Vec<u8>>,
31        new_key: Option<Vec<u8>>,
32    },
33}
34
35/// Encode the Bitmap key for a column value if the column is present on the row.
36///
37/// Matches `index_into`: missing columns are not indexed; present `Null` uses
38/// `Value::encode_key()` (empty bytes).
39pub fn bitmap_key_for_column(row: &Row, column_id: u16) -> Option<Vec<u8>> {
40    row.columns.get(&column_id).map(Value::encode_key)
41}
42
43/// Plan Bitmap secondary-index deltas between two row images.
44///
45/// Only `IndexKind::Bitmap` entries in `schema.indexes` are planned. ANN / FM /
46/// Sparse / MinHash / LearnedRange keep their existing full reindex paths for
47/// now (different remove semantics).
48pub fn plan_bitmap_secondary_deltas(
49    schema: &Schema,
50    old: &Row,
51    new: &Row,
52) -> Vec<BitmapIndexDelta> {
53    let mut out = Vec::new();
54    for idef in &schema.indexes {
55        if idef.kind != IndexKind::Bitmap {
56            continue;
57        }
58        let old_key = bitmap_key_for_column(old, idef.column_id);
59        let new_key = bitmap_key_for_column(new, idef.column_id);
60        match (old_key, new_key) {
61            (Some(o), Some(n)) if o == n => {
62                out.push(BitmapIndexDelta::Repoint {
63                    column_id: idef.column_id,
64                    key: o,
65                });
66            }
67            (old_key, new_key) => {
68                out.push(BitmapIndexDelta::Move {
69                    column_id: idef.column_id,
70                    old_key,
71                    new_key,
72                });
73            }
74        }
75    }
76    out
77}
78
79/// Apply planned Bitmap deltas to live index maps.
80///
81/// `old_row_id` / `new_row_id` are taken from the row images so callers can
82/// pass pre-tombstone and post-put identities.
83pub fn apply_bitmap_secondary_delta(
84    bitmap: &mut HashMap<u16, BitmapIndex>,
85    deltas: &[BitmapIndexDelta],
86    old_row_id: RowId,
87    new_row_id: RowId,
88) {
89    for delta in deltas {
90        match delta {
91            BitmapIndexDelta::Repoint { column_id, key } => {
92                let Some(b) = bitmap.get_mut(column_id) else {
93                    continue;
94                };
95                if old_row_id != new_row_id {
96                    b.remove(key, old_row_id);
97                    b.insert(key.clone(), new_row_id);
98                }
99                // same row id + same key: no secondary work
100            }
101            BitmapIndexDelta::Move {
102                column_id,
103                old_key,
104                new_key,
105            } => {
106                let Some(b) = bitmap.get_mut(column_id) else {
107                    continue;
108                };
109                if let Some(k) = old_key {
110                    b.remove(k, old_row_id);
111                }
112                if let Some(k) = new_key {
113                    b.insert(k.clone(), new_row_id);
114                }
115            }
116        }
117    }
118}
119
120/// Convenience: plan + apply Bitmap secondary maintenance for a replace.
121pub fn maintain_bitmap_secondary_on_replace(
122    schema: &Schema,
123    bitmap: &mut HashMap<u16, BitmapIndex>,
124    old: &Row,
125    new: &Row,
126) {
127    let deltas = plan_bitmap_secondary_deltas(schema, old, new);
128    apply_bitmap_secondary_delta(bitmap, &deltas, old.row_id, new.row_id);
129}
130
131#[cfg(test)]
132mod tests {
133    use super::*;
134    use crate::schema::{ColumnDef, ColumnFlags, IndexDef, TypeId};
135
136    fn schema_trip_bitmap() -> Schema {
137        Schema {
138            schema_id: 1,
139            columns: vec![
140                ColumnDef {
141                    id: 1,
142                    name: "id".into(),
143                    ty: TypeId::Int64,
144                    flags: ColumnFlags::empty().with(ColumnFlags::PRIMARY_KEY),
145                    default_value: None,
146                    embedding_source: None,
147                },
148                ColumnDef {
149                    id: 2,
150                    name: "trip_id".into(),
151                    ty: TypeId::Int64,
152                    flags: ColumnFlags::empty(),
153                    default_value: None,
154                    embedding_source: None,
155                },
156                ColumnDef {
157                    id: 3,
158                    name: "title".into(),
159                    ty: TypeId::Bytes,
160                    flags: ColumnFlags::empty(),
161                    default_value: None,
162                    embedding_source: None,
163                },
164            ],
165            indexes: vec![IndexDef {
166                name: "segments_trip_idx".into(),
167                column_id: 2,
168                kind: IndexKind::Bitmap,
169                predicate: None,
170                options: Default::default(),
171            }],
172            colocation: vec![],
173            constraints: Default::default(),
174            clustered: false,
175        }
176    }
177
178    fn row(rid: u64, id: i64, trip: i64, title: &[u8]) -> Row {
179        let mut r = Row::new(RowId(rid), crate::epoch::Epoch(1));
180        r.columns.insert(1, Value::Int64(id));
181        r.columns.insert(2, Value::Int64(trip));
182        r.columns.insert(3, Value::Bytes(title.to_vec()));
183        r
184    }
185
186    #[test]
187    fn plan_title_only_change_is_repoint_not_move() {
188        let schema = schema_trip_bitmap();
189        let old = row(0, 10, 42, b"before");
190        let new = row(1, 10, 42, b"after");
191        let deltas = plan_bitmap_secondary_deltas(&schema, &old, &new);
192        assert_eq!(
193            deltas,
194            vec![BitmapIndexDelta::Repoint {
195                column_id: 2,
196                key: Value::Int64(42).encode_key(),
197            }]
198        );
199    }
200
201    #[test]
202    fn plan_trip_id_change_is_move() {
203        let schema = schema_trip_bitmap();
204        let old = row(0, 10, 42, b"x");
205        let new = row(1, 10, 99, b"x");
206        let deltas = plan_bitmap_secondary_deltas(&schema, &old, &new);
207        assert_eq!(
208            deltas,
209            vec![BitmapIndexDelta::Move {
210                column_id: 2,
211                old_key: Some(Value::Int64(42).encode_key()),
212                new_key: Some(Value::Int64(99).encode_key()),
213            }]
214        );
215    }
216
217    #[test]
218    fn apply_repoint_removes_old_rid_under_same_key() {
219        let schema = schema_trip_bitmap();
220        let mut bitmap = HashMap::new();
221        bitmap.insert(2, BitmapIndex::new());
222        let old = row(0, 10, 42, b"before");
223        let new = row(1, 10, 42, b"after");
224        bitmap
225            .get_mut(&2)
226            .unwrap()
227            .insert(Value::Int64(42).encode_key(), old.row_id);
228        maintain_bitmap_secondary_on_replace(&schema, &mut bitmap, &old, &new);
229        let b = bitmap.get(&2).unwrap();
230        assert!(!b.contains(&Value::Int64(42).encode_key(), old.row_id));
231        assert!(b.contains(&Value::Int64(42).encode_key(), new.row_id));
232    }
233
234    #[test]
235    fn apply_move_switches_keys() {
236        let schema = schema_trip_bitmap();
237        let mut bitmap = HashMap::new();
238        bitmap.insert(2, BitmapIndex::new());
239        let old = row(0, 10, 42, b"x");
240        let new = row(1, 10, 99, b"x");
241        bitmap
242            .get_mut(&2)
243            .unwrap()
244            .insert(Value::Int64(42).encode_key(), old.row_id);
245        maintain_bitmap_secondary_on_replace(&schema, &mut bitmap, &old, &new);
246        let b = bitmap.get(&2).unwrap();
247        assert!(!b.contains(&Value::Int64(42).encode_key(), old.row_id));
248        assert!(b.contains(&Value::Int64(99).encode_key(), new.row_id));
249    }
250}
mongreldb_core/index/maintain.rs

mongreldb_core/index/
maintain.rs
