[FEA] Precompute lookup tables for IVF-PQ search about raft HOT 3 OPEN

Hi there, thanks for a good question! It's been on our radars for a while, but it hasn't been clear so far whether pre-computing lookup tables per-query may get in the way of other raft optimizations.

In raft, the lookup table fully encodes distance components from the query to all possible vectors in a list (cluster). In particular, it depends on the distance from the query to the cluster center. Hence, it's unique for every (query, probe) pair.

As far as I know, some other implementations only encode the residual distances in the lookup table; in that case the lookup table needs only be constructed once per query. Both approaches have their pros and cons. Couple reasons to back up our choice:

1. Encoding the full distance for every (query, probe) pair means we save a little bit of compute during the second phase - scanning through the encoded list. This tends to give better performance with larger datasets (100M or 1B records and up), where the construction of the lookup table takes only a small fraction of overall runtime.
2. We support an alternative codebook mode, where the codebooks are trained per-cluster rather than per-subspace in the feature space. This mode allows even faster lookup table creation due to better data locality, but it naturally depends on the probed cluster id.

from raft.

I'd suggest we keep it open as a feature request, so that we can prioritize and try this as an optional optimization at some point.

from raft.

Thanks @QDXG-CXK and @achirkin. I've gone ahead and converted this to a feature request so we can keep it on our radar.

from raft.