plugmem_core/index/
mod.rs

1//! The recall indexes: shared posting storage, the BM25
2//! lexical index, and plain id-list indexes (tag → facts,
3//! entity → facts) with sorted-list intersection.
4//!
5//! The temporal index needs no module of its own — it is an Ordered
6//! [`Arena`](plugmem_arena::Arena) of
7//! [`TemporalSlot`](crate::model::TemporalSlot)s queried with `range`,
8//! and lives directly in the engine.
9
10pub mod bm25;
11pub mod hnsw;
12pub mod postings;
13pub mod varint;
14pub mod vecpool;
15
16use alloc::vec::Vec;
17
18use crate::id::FactId;
19use postings::PostingStore;
20
21/// Key → sorted fact-id lists without term frequencies: the tag and
22/// entity indexes.
23pub type IdListIndex<'a> = PostingStore<'a, false>;
24
25/// Reusable scratch for [`intersect`] (two ping-pong buffers; after
26/// warm-up an intersection allocates nothing).
27#[derive(Debug, Default)]
28pub struct IntersectScratch {
29    a: Vec<u32>,
30    b: Vec<u32>,
31}
32
33impl IntersectScratch {
34    /// Empty scratch buffers.
35    pub fn new() -> Self {
36        Self::default()
37    }
38}
39
40/// Intersects the sorted lists of `keys` into `out` (ascending ids).
41///
42/// Starts from the shortest list (fewest candidates) and filters it
43/// against the others by merge — cost is O(shortest + Σ walked prefixes).
44/// An absent key means an empty list, so the intersection is empty; an
45/// empty `keys` slice yields an empty result (the caller treats "no tag
46/// filter" as "no allow-set", not as "allow everything").
47pub fn intersect(
48    index: &IdListIndex<'_>,
49    keys: &[u32],
50    scratch: &mut IntersectScratch,
51    out: &mut Vec<FactId>,
52) {
53    out.clear();
54    let Some((first, rest)) = keys
55        .iter()
56        .min_by_key(|&&k| index.count(k))
57        .map(|&smallest| {
58            (
59                smallest,
60                keys.iter().copied().filter(move |&k| k != smallest),
61            )
62        })
63    else {
64        return;
65    };
66    scratch.a.clear();
67    scratch.a.extend(index.entries(first).map(|(id, _)| id.0));
68    for key in rest {
69        if scratch.a.is_empty() {
70            break;
71        }
72        scratch.b.clear();
73        let mut other = index.entries(key).map(|(id, _)| id.0).peekable();
74        for &id in &scratch.a {
75            while other.peek().is_some_and(|&o| o < id) {
76                other.next();
77            }
78            if other.peek() == Some(&id) {
79                scratch.b.push(id);
80            }
81        }
82        core::mem::swap(&mut scratch.a, &mut scratch.b);
83    }
84    out.extend(scratch.a.iter().map(|&id| FactId(id)));
85}
plugmem_core/index/mod.rs

plugmem_core/index/
mod.rs
