The Missing ”WHERE” Clause for Vector Search(pinecone.io)
pinecone.io
The Missing ”WHERE” Clause for Vector Search
https://www.pinecone.io/learn/vector-search-filtering/
25 comments
Amazon's Opensearch (fork of Elasticsearch) natively supports vector-based approximate KNN (using https://github.com/nmslib/nmslib/) which is integrated with Opensearch's native filtering functionality. Elasticsearch also has similar functionality, but I don't know if their KNN code scales quite as well.
Opensearch only supports "pre-filtering" or "post-filtering," which leads to either high latency or incomplete results, as explained in the article.
This is why single-stage filtering was the most-requested feature for us.
From the Opensearch docs:
> You should not use approximate k-NN if you want to apply a filter on the index before the k-NN search, which greatly reduces the number of vectors to be searched.
> Because the graphs are constructed during indexing, it is not possible to apply a filter on an index and then use this search method. All filters are applied on the results produced by the approximate nearest neighbor search.
> If you use the knn query alongside filters or other clauses (e.g. bool, must, match), you might receive fewer than k results.
(https://opensearch.org/docs/search-plugins/knn/approximate-k...)
I know Elasticsearch is working on introducing vector search but it is not yet available. I don't know how they will support filtering.
This is why single-stage filtering was the most-requested feature for us.
From the Opensearch docs:
> You should not use approximate k-NN if you want to apply a filter on the index before the k-NN search, which greatly reduces the number of vectors to be searched.
> Because the graphs are constructed during indexing, it is not possible to apply a filter on an index and then use this search method. All filters are applied on the results produced by the approximate nearest neighbor search.
> If you use the knn query alongside filters or other clauses (e.g. bool, must, match), you might receive fewer than k results.
(https://opensearch.org/docs/search-plugins/knn/approximate-k...)
I know Elasticsearch is working on introducing vector search but it is not yet available. I don't know how they will support filtering.
The approximate kNN is quite nice for many use cases, and scales to billions of documents. However, you're correct that filtering happens on the results. This is only an issue in certain use cases where filtering is very narrow, as you can often just request much higher k than the number of results you really need without much slowdown.
If the filtering is very narrow, as you commented they also provide functionality to perform pre-filtering and then exact kNN on the results. This is of course higher latency, but still quite acceptable for many use cases (this is how I use it).
I believe there are use cases that Pinecone addresses better than Opensearch, but I want to let people know that there is a free, open-source solution which _may_ also work for their use case.
Elasticsearch does currently support vector search through script score using dense vector fields, however I suspect they are still working on improving it and I prefer the Opensearch implementation for the time being https://www.elastic.co/guide/en/elasticsearch/reference/curr...
If the filtering is very narrow, as you commented they also provide functionality to perform pre-filtering and then exact kNN on the results. This is of course higher latency, but still quite acceptable for many use cases (this is how I use it).
I believe there are use cases that Pinecone addresses better than Opensearch, but I want to let people know that there is a free, open-source solution which _may_ also work for their use case.
Elasticsearch does currently support vector search through script score using dense vector fields, however I suspect they are still working on improving it and I prefer the Opensearch implementation for the time being https://www.elastic.co/guide/en/elasticsearch/reference/curr...
I've already subscribed to pinecone newsletter. but accidentally i clicked on this post when i opened HN , what a coincidence .
Hi all, I'm the author - I'll be here to answer any questions you have!
Hi! Yes! Nice article (articles actually).
I realize you are hinting at it as the subject of a later article, but could you share with us a little bit more about single-stage-filtering :D ? how does it work? How can metadata and vector data "coexist" in a same index?
I realize you are hinting at it as the subject of a later article, but could you share with us a little bit more about single-stage-filtering :D ? how does it work? How can metadata and vector data "coexist" in a same index?
Yes as gk1 said, we're figuring out what can be said! I can't fully answer your questions beyond, having both indexes together helps us speed up the search (thanks to a lack of network/serialization/parsing overhead), and because of the structure we store metadata tags in, we also don't need to check the metadata for every sample (hence the cool speedup you get when filtering) - sorry that we can't say anything more yet!
There are different approaches for turning vectors into terms which you can then simply index with something like Elasticsearch. There are papers by the Walmart and Jet.com teams that describe different approaches, starting with both binarised vectors as well as full float vectors. Not saying that this is what Pinecone is using, so it will be interesting to read their follow-up.
I'm from Pinecone and can tell you we are figuring out now exactly how much to say about this.
We know you want to know, and we also know other vector databases want to know -- because this is a highly requested feature and it's far from trivial to implement in a low-latency way. That's why we have to give the admittedly non-satisfying answer of "stay tuned!"
We know you want to know, and we also know other vector databases want to know -- because this is a highly requested feature and it's far from trivial to implement in a low-latency way. That's why we have to give the admittedly non-satisfying answer of "stay tuned!"
Neural networks.
Your damn animated gif has sucked up >4.7GB in my browser and crashed it. Not impressed.
Did animation actually add anything significant anyway.
Did animation actually add anything significant anyway.
I'm not disputing that the image may not add anything to the article but if a 10MiB GIF image can crash your browser maybe you should look at other vendors. I'm on Firefox Developer Edition with approximately 100 tabs open and didn't notice that image as a resource hog.
It's animated (and there are 3 on that page totalling 35MB). Some systems unfold each frame into its own image and store that.
Please open firefox to that page, leave it open for a few minutes and observe the memory. I suspect FX will bloat too.
Please open firefox to that page, leave it open for a few minutes and observe the memory. I suspect FX will bloat too.
may i know what tool was used to create the gifs in this blog post ? . Thanks in advance .
Excalidraw.com for the style/graphs, then Adobe animate for the animation!
I believe it’s Excalidraw and some animation software like Adobe Animate.
Not quite what you're after, but there's a matplotlib style made to look like xkcd
https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot....
https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot....
This works by streaming results from the similarity search to the filter, in descending order of similarity. As soon as enough matches are found, the similarity search is terminated.
Postgres does the same thing for many queries if you look at the query plan.
Not really worthy of a blog post - especially one that says "wait till the next blog post to find out how it works!!".
Postgres does the same thing for many queries if you look at the query plan.
Not really worthy of a blog post - especially one that says "wait till the next blog post to find out how it works!!".
How is what you describe _not_ just an efficiently implemented post filter with early out?
If it turns out that’s all pinecone have, then yeah, I’m gonna be disappointed. My mind is working overtime imagining prefixing vectors with their filter terms to root everything and other naive things…
If it turns out that’s all pinecone have, then yeah, I’m gonna be disappointed. My mind is working overtime imagining prefixing vectors with their filter terms to root everything and other naive things…
I'd be surprised if it was anything else, given that they started with a working vector search database and then added filtering in after the fact.
You have high standards about what should be in a blog post.
And how do construct a search that can stream results in descending order of similarity, that's faster than O(N) for N values in the database?
That's a fairly standard nearest neighbour search[0], usually made fast by using a kd-tree[1] or an R-tree[2].
[0] https://en.wikipedia.org/wiki/Nearest_neighbor_search
[1] https://en.wikipedia.org/wiki/K-d_tree
[2] https://en.wikipedia.org/wiki/R-treeNo, this isn’t at all how it works.
This is not a trivial problem when dealing with vector similarity search, which Postgres does not have.
This is not a trivial problem when dealing with vector similarity search, which Postgres does not have.
Very nice writeup. I have an idea how this might be implemented. Since you rightfully want to keep the details private, let me just ask:
How do you handle the case where the probed clusters contain no elements satisfying the filter criteria? Is the probe extended to additional clusters, or terminated with no results?
How do you handle the case where the probed clusters contain no elements satisfying the filter criteria? Is the probe extended to additional clusters, or terminated with no results?