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

IVF-Flat sample filter is not applied in all required places #1620

Closed
achirkin opened this issue Jun 29, 2023 · 2 comments · Fixed by #1831
Closed

IVF-Flat sample filter is not applied in all required places #1620

achirkin opened this issue Jun 29, 2023 · 2 comments · Fixed by #1831

Comments

@achirkin
Copy link
Contributor

It seems like the filtering in ivf-flat is not entirely correct, it's only applied to one if case out of the few.
Perhaps, it makes sense to shift the condition further below to the place where the found value is added to the queue.

const bool valid = vec_id < list_length;
// Process first shm_assisted_dim dimensions (always using shared memory)
if (valid && sample_filter(queries_offset + blockIdx.y, probe_id, vec_id)) {
loadAndComputeDist<kUnroll, decltype(compute_dist), Veclen, T, AccT> lc(dist,
compute_dist);
for (int pos = 0; pos < shm_assisted_dim;
pos += WarpSize, data += kIndexGroupSize * WarpSize) {
lc.runLoadShmemCompute(data, query_shared, lane_id, pos);
}
}
if (dim > query_smem_elems) {
// The default path - using shfl ops - for dimensions beyond query_smem_elems
loadAndComputeDist<kUnroll, decltype(compute_dist), Veclen, T, AccT> lc(dist,
compute_dist);
for (int pos = shm_assisted_dim; pos < full_warps_along_dim; pos += WarpSize) {
lc.runLoadShflAndCompute(data, query, pos, lane_id);
}
lc.runLoadShflAndComputeRemainder(data, query, lane_id, dim, full_warps_along_dim);
} else {
// when shm_assisted_dim == full_warps_along_dim < dim
if (valid) {
loadAndComputeDist<1, decltype(compute_dist), Veclen, T, AccT> lc(dist, compute_dist);
for (int pos = full_warps_along_dim; pos < dim;
pos += Veclen, data += kIndexGroupSize * Veclen) {
lc.runLoadShmemCompute(data, query_shared, lane_id, pos);
}
}

@lowener
Copy link
Contributor

lowener commented Oct 4, 2023

The call to sample_filter is not right.
It should be sample_filter(queries_offset + blockIdx.y, list_id, vec_id).

@lowener
Copy link
Contributor

lowener commented Oct 17, 2023

True, the filtering was still adding neighbors that didn't pass the test to the queue. I am fixing this in PR #1831

@rapids-bot rapids-bot bot closed this as completed in #1831 Nov 6, 2023
rapids-bot bot pushed a commit that referenced this issue Nov 6, 2023
PR based on the new Bitset feature (#1803) to support vector deletion in ANN.
Closes #1177. 
Closes #1620.
This PR adds `ivf_to_sample_filter` that acts as an intermediate filter to use an IVF index with a bitset filter.

Authors:
  - Micka (https://github.com/lowener)
  - Corey J. Nolet (https://github.com/cjnolet)

Approvers:
  - William Hicks (https://github.com/wphicks)

URL: #1831
benfred pushed a commit to benfred/raft that referenced this issue Nov 8, 2023
PR based on the new Bitset feature (rapidsai#1803) to support vector deletion in ANN.
Closes rapidsai#1177. 
Closes rapidsai#1620.
This PR adds `ivf_to_sample_filter` that acts as an intermediate filter to use an IVF index with a bitset filter.

Authors:
  - Micka (https://github.com/lowener)
  - Corey J. Nolet (https://github.com/cjnolet)

Approvers:
  - William Hicks (https://github.com/wphicks)

URL: rapidsai#1831
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Development

Successfully merging a pull request may close this issue.

3 participants