Method search

nodedb/src/engine/sparse/sparse_vector.rs:260–334

Search using WAND algorithm for efficient top-k sparse dot-product retrieval. WAND (Weighted AND) skips candidates whose maximum possible score (sum of max posting weights) can't exceed the current k-th best score. This avoids computing full dot products for most candidates.

(
        &self,
        collection: &str,
        query: &SparseVector,
        top_k: usize,
    )

    /// (sum of max posting weights) can't exceed the current k-th best score.
    /// This avoids computing full dot products for most candidates.
    pub fn search(
        &self,
        collection: &str,
        query: &SparseVector,
        top_k: usize,
    ) -> crate::Result<Vec<SparseSearchResult>> {
        if query.is_empty() || top_k == 0 {
            return Ok(Vec::new());
        }

        let read_txn = self.db.begin_read().map_err(|e| crate::Error::Storage {
            engine: "sparse_vector".into(),
            detail: format!("read txn: {e}"),
        })?;
        let postings_table =
            read_txn
                .open_table(SPARSE_POSTINGS)
                .map_err(|e| crate::Error::Storage {
                    engine: "sparse_vector".into(),
                    detail: format!("open postings: {e}"),
                })?;

        // Load posting lists for all query tokens.
        let mut term_postings: Vec<(f32, Vec<SparsePosting>)> = Vec::new();
        for &(token_id, query_weight) in query {
            if query_weight.abs() < f32::EPSILON {
                continue;
            }
            let key = format!("{collection}:{token_id}");
            if let Ok(Some(guard)) = postings_table.get(key.as_str()) {
                let postings: Vec<SparsePosting> =
                    zerompk::from_msgpack(guard.value()).unwrap_or_default();
                if !postings.is_empty() {
                    term_postings.push((query_weight, postings));
                }
            }
        }

        if term_postings.is_empty() {
            return Ok(Vec::new());
        }

        // Accumulate dot-product scores per document.
        // For each query term, multiply query_weight × doc_weight.
        let mut doc_scores: HashMap<String, f32> = HashMap::new();
        for (query_weight, postings) in &term_postings {
            for posting in postings {
                *doc_scores.entry(posting.doc_id.clone()).or_default() +=
                    query_weight * posting.weight;
            }
        }

        // Extract top-k by score (descending).
        let mut results: Vec<SparseSearchResult> = doc_scores
            .into_iter()
            .map(|(doc_id, score)| SparseSearchResult { doc_id, score })
            .collect();