Skip to content

Optimize filtered search for small candidate sets #241

Description

@shaleenji

Problem Statement

Filtered dense search can be inefficient when the filter bitmap identifies a
small candidate set. The previous path materialized vector byte batches and then
searched the subset, which adds memory copies and extra allocation overhead.

Users running selective filters are affected because the query already knows the
small set of candidate ids, but the search path still pays unnecessary vector
batch materialization cost. Metadata fetches can also happen before filter
rejection in some result assembly paths.

Proposed Solution

Use a cheaper prefilter path for small candidate sets:

  • compute the active filter bitmap once and share it across dense/sparse search;
  • convert small filter bitmaps to ids;
  • visit matching vectors directly from MDBX storage;
  • score visited vectors and maintain top-k results without building a vector
    batch copy;
  • keep filtered HNSW as the fallback for larger filtered sets;
  • run defensive postfilter checks before metadata fetches where applicable;
  • add optional timing counters around key filtered-search phases.

Alternatives Considered

Always use filtered HNSW. That keeps one search strategy, but can be excessive
for highly selective filters where direct scoring over a small candidate set is
cheaper.

Always use brute-force over the filtered bitmap. That is good for small filters,
but poor for larger candidate sets. The adaptive threshold keeps both paths.

Additional Context

Implemented in this branch:

  • src/core/ndd.hpp
  • src/storage/vector_storage.hpp
  • src/utils/search_timing.hpp

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions