sparse_vector/wand/
mod.rs

1//! WAND search over sparse-vector posting lists.
2//!
3//! This module is a self-contained implementation of the inverted-index side
4//! of sparse-vector retrieval: sorted posting lists carrying weight ceilings,
5//! cursors over them, a query frontier that knows how good any not-yet-scored
6//! record could still be, and a batch search loop that scores windows of
7//! record ids and prunes the ranges that can no longer reach the top-k.
8//!
9//! Layout:
10//!
11//! - [`Posting`] — one element of a list: `id`, `weight`, `tail_max`.
12//! - [`cursor`] — the [`PostingCursor`] trait (peek / advance / seek /
13//!   remaining / last_id / upper_bound) and [`SliceCursor`] over a slice of
14//!   postings.
15//! - [`postings`] — [`Postings`], the in-RAM list with upsert / delete and
16//!   ceiling maintenance, plus [`PostingsBuilder`].
17//! - [`mmap`] — [`MmapCursor`], a cursor over `mmap_index` posting entries.
18//! - [`frontier`] — [`Frontier`], the set of active cursors for a query.
19//! - [`sink`] — the [`ScoreSink`] trait, [`TopKSink`] and [`CollectAll`].
20//! - [`search`] — [`search`](search::search) and [`search_with`].
21//!
22//! # Ceiling invariant
23//!
24//! Every posting stores `tail_max`, the maximum weight over *itself and every
25//! element after it* in the list (an inclusive suffix maximum). Hence for
26//! every position `i`, `tail_max[i] >= weight[j]` for all `j >= i`, and the
27//! sequence `tail_max` is non-increasing. A cursor positioned at `i` exposes
28//! `tail_max[i]` as its `upper_bound()`: no element it has not consumed yet
29//! has a larger weight.
30//!
31//! # Pruning
32//!
33//! Records are scored in increasing id order, so the k-th best score seen so
34//! far is a threshold that a later record must *strictly* exceed to enter
35//! (ties are resolved in favour of the lower id, and the lower id was scored
36//! first). The frontier bounds the score of any unscored record by the sum,
37//! over lanes, of `max(0, query_weight * upper_bound)`; a record absent from
38//! a lane contributes nothing, hence the clamp at zero. Sorting lanes by their
39//! current id and accumulating those bounds gives a pivot: every id below the
40//! pivot lane's current id lives only in lanes whose accumulated bound is
41//! below the threshold, so those lanes can be seeked forward to the pivot in
42//! one move. When even the full sum cannot beat the threshold, the search
43//! ends.
44//!
45//! Negative query weights need a *lower* bound on the weights of a list to be
46//! bounded; cursors report `f32::NEG_INFINITY` by default, which makes such a
47//! lane's contribution unbounded and disables pruning for it while keeping
48//! the result exact.
49//!
50//! # Ordering
51//!
52//! Results are sorted by score descending, then by record id ascending.
53//!
54//! # Queries
55//!
56//! A query is a list of `(dimension, weight)`. A dimension repeated in the
57//! query is merged by summing its weights before the lanes are built, and
58//! zero weights are dropped. Weights stored in posting lists are expected
59//! to be non-zero (the index strips zeros at insert time); a stored zero is
60//! still a presence and would be returned with a zero score.
61
62pub mod cursor;
63pub mod frontier;
64pub mod mmap;
65pub mod postings;
66pub mod search;
67pub mod sink;
68
69#[cfg(test)]
70mod tests;
71
72pub use cursor::{PostingCursor, SliceCursor};
73pub use frontier::{Frontier, Lane};
74pub use mmap::MmapCursor;
75pub use postings::{Postings, PostingsBuilder};
76pub use search::{search, search_with, Scratch, SearchOptions};
77pub use sink::{CollectAll, ScoreSink, TopKSink};
78
79/// Identifier of an indexed record (document, node, row).
80pub type RecordId = u64;
81
82/// Identifier of a dimension of the sparse space (token id, feature id).
83pub type DimId = u32;
84
85/// A weight stored in a posting or carried by a query dimension.
86pub type Weight = f32;
87
88/// One element of a posting list.
89#[derive(Clone, Copy, Debug, PartialEq)]
90pub struct Posting {
91    /// Record the weight belongs to.
92    pub id: RecordId,
93    /// Weight of the record on the list's dimension.
94    pub weight: Weight,
95    /// Maximum weight over this element and every element after it in the
96    /// list. See the module documentation for the invariant.
97    pub tail_max: Weight,
98}
99
100impl Posting {
101    /// A posting whose ceiling is its own weight (a list of one element).
102    pub fn solo(id: RecordId, weight: Weight) -> Self {
103        Self {
104            id,
105            weight,
106            tail_max: weight,
107        }
108    }
109}
110
111pub use search::search_ids;
sparse_vector/wand/mod.rs

sparse_vector/wand/
mod.rs
