Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[BUG] knn_merge_parts not implemented for k>1024 #2171

Open
tfeher opened this issue Feb 9, 2024 · 0 comments
Open

[BUG] knn_merge_parts not implemented for k>1024 #2171

tfeher opened this issue Feb 9, 2024 · 0 comments
Assignees
Labels
bug Something isn't working Vector Search

Comments

@tfeher
Copy link
Contributor

tfeher commented Feb 9, 2024

Describe the bug

knn_merge_parts is only implemented for k<=1024, and it silently returns without doing any work for k>1024:

{
if (k == 1)
knn_merge_parts_impl<value_idx, value_t, 1, 1>(
inK, inV, outK, outV, n_samples, n_parts, k, stream, translations);
else if (k <= 32)
knn_merge_parts_impl<value_idx, value_t, 32, 2>(
inK, inV, outK, outV, n_samples, n_parts, k, stream, translations);
else if (k <= 64)
knn_merge_parts_impl<value_idx, value_t, 64, 3>(
inK, inV, outK, outV, n_samples, n_parts, k, stream, translations);
else if (k <= 128)
knn_merge_parts_impl<value_idx, value_t, 128, 3>(
inK, inV, outK, outV, n_samples, n_parts, k, stream, translations);
else if (k <= 256)
knn_merge_parts_impl<value_idx, value_t, 256, 4>(
inK, inV, outK, outV, n_samples, n_parts, k, stream, translations);
else if (k <= 512)
knn_merge_parts_impl<value_idx, value_t, 512, 8>(
inK, inV, outK, outV, n_samples, n_parts, k, stream, translations);
else if (k <= 1024)
knn_merge_parts_impl<value_idx, value_t, 1024, 8>(
inK, inV, outK, outV, n_samples, n_parts, k, stream, translations);
}

knn_merge_parts is used during brute force search if:

  • an offset index needs to be added to the indices. This feature is used in raft_ann_bench in the ground_truth generator. There is an easy workaround for this case.
  • When merging results from multi-gpu search (SNMG ANN #1993, tagging @viclafargue for visibility)

Expected behavior

  • Throw an error if input parameters are out of range
  • Ideally improve knn_merge_parts, so that it handles larger k.

Additional context
The limitation comes from the fact that we are using faiss::blockselect. We have radix top-k that does not have a limit on k, so we just need to map the input to a format that radix-topk can consume.

@tfeher tfeher added bug Something isn't working Vector Search labels Feb 9, 2024
rapids-bot bot pushed a commit that referenced this issue Mar 19, 2024
Generating ANN bench ground truth is affected by bug #2171, when k>1024. This PR fixes the issue for the ground truth generation.

Authors:
  - Tamas Bela Feher (https://github.com/tfeher)

Approvers:
  - Corey J. Nolet (https://github.com/cjnolet)

URL: #2180
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working Vector Search
Projects
None yet
Development

No branches or pull requests

2 participants