Post-fitering performance
hlinnaka opened this issue · 4 comments
How does the post-filtering perform compared to pgvector/pgvector#282 and pgvector/pgvector#524? Recall? Speed?
Unlike the current HNSW implementation, StreamingDiskANN has no recall degradation with post-filtering (actually that's the "Streaming" part of the algorithm. You can read more here: https://www.timescale.com/blog/how-we-made-postgresql-as-fast-as-pinecone-for-vector-data/ (Section "
Support for streaming retrieval for accurate metadata filtering").
The same Streaming method is used with and without filters so there is no performance degradation per se. Although obviously for more selective queries more of the graph needs to be traversed.
Honestly, not sure how translatable the streaming approach is to hnsw, but am skeptical it's easy because of complications introduced by the multi-level stuff.
(edited the link in the original question to point to correct PR)
@hlinnaka I did benchmarks for pgvector/pgvector#282 and pgvector/pgvector#524 . I could include scalevector, but found, that scalevector supports only angular distance in stream mode, but I have just now only euclidian datasets with WHERE support. I include it when l2 distance will be available in scalevector.
Even if charts show slightly different performance, both proposed search algorithms are very similar in both case. Recall remains good with filters, speed decreased as soon as more spread filter values distribution. Standard HNSW implementation shows the decrease of recall as expected.
Benchmark done on ARM M1 processor, 16GB shared_memory, fashion_mnist dataset.
- Chart for filter with 10 values (pgvector_hnsw_std has line with less recall outside of this chart) :
- Chart for filter with 100 values (pgvector_hnsw_std has line outside of this chart) - speed decreased due to more vectors processed, recall even increased:
@cevian Streaming search method looks like "PostgreSQL" way to return tuples from index. It is only another "search in graph" option. HNSW authors in their article provided the search example to demonstrate how to deal with levels, but it is not necessary to copy it , when we looks for vectors in level 0. We can use any graph search algorithm.