Module wand 

WAND search over sparse-vector posting lists.

This module is a self-contained implementation of the inverted-index side of sparse-vector retrieval: sorted posting lists carrying weight ceilings, cursors over them, a query frontier that knows how good any not-yet-scored record could still be, and a batch search loop that scores windows of record ids and prunes the ranges that can no longer reach the top-k.

Layout:

• Posting — one element of a list: id, weight, tail_max.
• cursor — the PostingCursor trait (peek / advance / seek / remaining / last_id / upper_bound) and SliceCursor over a slice of postings.
• postings — Postings, the in-RAM list with upsert / delete and ceiling maintenance, plus PostingsBuilder.
• mmap — MmapCursor, a cursor over mmap_index posting entries.
• frontier — Frontier, the set of active cursors for a query.
• sink — the ScoreSink trait, TopKSink and CollectAll.
• [search] — search and search_with.

Ceiling invariant

Every posting stores tail_max, the maximum weight over itself and every element after it in the list (an inclusive suffix maximum). Hence for every position i, tail_max[i] >= weight[j] for all j >= i, and the sequence tail_max is non-increasing. A cursor positioned at i exposes tail_max[i] as its upper_bound(): no element it has not consumed yet has a larger weight.

Pruning

Records are scored in increasing id order, so the k-th best score seen so far is a threshold that a later record must strictly exceed to enter (ties are resolved in favour of the lower id, and the lower id was scored first). The frontier bounds the score of any unscored record by the sum, over lanes, of max(0, query_weight * upper_bound); a record absent from a lane contributes nothing, hence the clamp at zero. Sorting lanes by their current id and accumulating those bounds gives a pivot: every id below the pivot lane’s current id lives only in lanes whose accumulated bound is below the threshold, so those lanes can be seeked forward to the pivot in one move. When even the full sum cannot beat the threshold, the search ends.

Negative query weights need a lower bound on the weights of a list to be bounded; cursors report f32::NEG_INFINITY by default, which makes such a lane’s contribution unbounded and disables pruning for it while keeping the result exact.

Ordering

Results are sorted by score descending, then by record id ascending.

Queries

A query is a list of (dimension, weight). A dimension repeated in the query is merged by summing its weights before the lanes are built, and zero weights are dropped. Weights stored in posting lists are expected to be non-zero (the index strips zeros at insert time); a stored zero is still a presence and would be returned with a zero score.

Re-exports

pub use cursor::PostingCursor;

pub use cursor::SliceCursor;

pub use frontier::Frontier;

pub use frontier::Lane;

pub use mmap::MmapCursor;

pub use postings::Postings;

pub use postings::PostingsBuilder;

pub use search::search;

pub use search::search_with;

pub use search::Scratch;

pub use search::SearchOptions;

pub use sink::CollectAll;

pub use sink::ScoreSink;

pub use sink::TopKSink;

pub use search::search_ids;

Modules

cursor

Cursors: forward-only readers over a sorted posting list.

frontier

The frontier: the set of active cursors of a query, and what it knows about the records nobody has scored yet.

mmap

Cursor over the posting entries of an mmap’d index.

postings

In-RAM posting list with mutation and ceiling maintenance.

search

The search loop: window-batched scoring with WAND pruning.

sink

Where scored records go: a top-k tracker or a plain collector.

Structs

Posting

One element of a posting list.

Type Aliases

DimId

Identifier of a dimension of the sparse space (token id, feature id).

RecordId

Identifier of an indexed record (document, node, row).

Weight

A weight stored in a posting or carried by a query dimension.