Feature: Support level-aware prefetch in HNSW search

[yoonseok-kim]

Describe what you are looking for

In the current index_gt HNSW implementation, prefetching, metric evaluation, and predicate evaluation are executed at different stages depending on the search level.

• From upper levels down to (base − 1)
  • prefetch -> metric (search_for_one_)
• Base level
  • prefetch -> metric -> predicate (search_to_find_in_base_)

Prefetching is currently used primarily as an optimization to read vector data for up to max_neighbors(m~2m) in advance. However, the current prefetch_t interface is not flexible enough to support the following use cases.

• A user may want to enable prefetching only at upper levels, while disabling it on the base level.
• When predicates are used, a user(me) may want to prefetch additional data required by the predicate, not only the vector values.
  • Note that predicates are evaluated only at the base level.

Currently, prefetch_t has the following signature.

struct prefetch_t {
    template <typename member_citerator_like_at>
    inline void operator()(member_citerator_like_at, member_citerator_like_at) const noexcept {}
};

To support the scenarios above, I would like to propose extending prefetch_t so that the level information can be passed into the prefetch stage.

struct prefetch_t {
    template <typename member_citerator_like_at>
    inline void operator()(member_citerator_like_at, member_citerator_like_at) const noexcept {}

    // new feature
    template <typename member_citerator_like_at>
    inline void operator()(member_citerator_like_at, member_citerator_like_at, level_t) const noexcept {}
};

I think this change is backward-compatible and can be implemented internally without altering existing behavior.

I’ve submitted a PR(#696) with the corresponding changes. I would appreciate any feedback or suggestions.

Can you contribute to the implementation?

• I can contribute

Is your feature request specific to a certain interface?

C++ implementation

Contact Details

kys910524@gmail.com

Is there an existing issue for this?

• I have searched the existing issues

Code of Conduct

• I agree to follow this project's Code of Conduct