The Missing WHERE Clause in Vector Search

Vector similarity search makes massive datasets searchable in fractions of a second. Yet despite the brilliance and utility of this technology, often what seem to be the most straightforward problems are the most difficult to solve. Such as filtering.

Filtering takes the top place in being seemingly simple — but actually incredibly complex. Applying fast-but-accurate filters when performing a vector search (ie, nearest-neighbor search) on massive datasets is a surprisingly stubborn problem.

This article explains the two common methods for adding filters to vector search, and their serious limitations. Then we will explore Pinecone’s solution to filtering in vector search.


The Filter Problem

In vector similarity search we build vector representations of some data (images, text, cooking recipes, etc), storing it in an index (a database for vectors), and then searching through that index with another query vector.

If you found this article through Google, what brought you here was a semantic search identifying that the vector representation of your search query aligned with Google’s vector representation of this page.

Netflix, Amazon, Spotify, and many others use vector similarity search to power their recommendation systems, using it to identify similar users and base their new show, product, or music recommendations on what these similar groups of people seem to like.

In search and recommender systems there is almost always a need to apply filters: Google can filter searches by category (like news or shopping) , date, or even language and region; Netflix, Amazon, and Spotify may want to focus on comparing users in similar geographies. Restricting the search scope to relevant vectors is — for many use-cases — an absolute necessity for providing a better customer experience.

Despite the clear need, there has been no good approach for metadata filtering — restricting the scope of a vector search based on a set of metadata conditions — that’s both accurate and fast.

We may want to restrict our search to a category of records or a specific date range.

For example, say we want to build a semantic search application for a large corporation to search through internal documents. Users will often want to filter their search to a specific department. It should be as simple as writing this pseudo-code:

top-k where department == 'engineering'
OR
top-k where department != 'hr'

top-k where {department: {"$eq": "engineering"}}
OR
top-k where {department: {"$ne": "hr"}}

And what if we only want the last few weeks of data? Or need to see how the documents have changed over time — we would want to restrict the search to old records only!

top-k where date >= 14 days ago
OR
top-k where date < 3 years ago

top-k where {date: {"$gte": 14}}
OR
top-k where {date: {"$lt": 1095}}

There are countless variations and combinations of queries just like these.

top-k where date >= 14 days ago AND department == 'finance'

top-k where {"date": {"$gte": 14}, department: {"$eq": "finance"}}

Without filters, we restrict our ability to build powerful tools for search. Imagine Excel without data filters, SQL without a WHERE clause, or Python without if...else statements. The capabilities of these tools become massively diminished, and the same applies to vector search without filters.

But implementing such filters into a semantic/vector search application isn’t easy. Let’s first look at the two most common approaches — along with their advantages and disadvantages. They are pre-filtering and post-filtering.

Post and pre-filtering — note that for post-filtering, we search then apply the metadata filter. For pre-filtering, we apply the metadata filter then search.

These approaches require two indexes: The vector index as per usual, and a metadata index. It is through this metadata index that we identify those vectors which satisfy our filter conditions.

Pre-Filtering

The first approach we could take is to pre-filter our vectors. This consists of taking our metadata index and applying our set of conditions. From here, we return a list of all records in our vector index that satisfies our filter conditions.

Now when we search, we’ve restricted our scope — so our vector similarity search will be faster, and we’ll only return relevant results!

The problem is that our pre-filter disrupts how ANN engines work (ANN requires the full index), leaving us with two options:

Build an ANN index for every possible filter. Perform a brute-force kNN search across remaining vectors.

Option (1) is simply not practical, there are far too many possible filter outputs in a typical index.

That leaves us with option (2), creating the additional overhead of brute-force checking every single vector embedding remaining after the metadata filter.

Pre-filtering is excellent for returning relevant results, but significantly slows-down our search due to the exhaustive, brute-force search that’s required.

While slow for smaller datasets — the problem is exacerbated for larger datasets. This brute-force search is simply not manageable for datasets in the millions or billions.

Maybe post-filtering will work better?

Post-Filtering

We can’t rely on a brute-force search every time we apply a filter, so what if we applied the filter after our vector search?

Working through it, we have our vector index and a query — we perform a similarity search as usual. We return k of the top nearest matches. We’ll set k == 10.

We’ve now got our top 10 best matches, but there’s plenty of vectors in here that would not satisfy our filter conditions.

We go ahead and apply our post-search filter to remove those irrelevant results. That filter has removed six of our results, leaving us with just four results. We wanted ten results, and we’ve returned four. That’s not so great.

Unfortunately, it gets worse… What if we didn’t return any results in the top k that satisfy our filter conditions? That leaves us with no results at all.

By applying our metadata filter post-search, we avoid the speed issues of an initial brute-force search. Still, we risk returning very few or even zero results, even though there may be relevant records in the dataset. So much for improving customer experience…

We can eliminate the risk of returning too few (or zero) results by increasing k to a high number. But now we have slower search times thanks to our excessively high k searches, and so we’re back to the slow search times of pre-filtering.

Slow search with pre-filtering, or unreliable results with post-filtering. Neither of these approaches sounds particularly attractive, so what can we do?

Single-Stage Filtering

Pinecone’s single-stage filtering produces the accurate results of pre-filtering at even faster speeds than post-filtering.

It works by merging the vector and metadata indexes into a single index — resulting in a single-stage filter as opposed to the two-stage filter-and-search method of pre- and post-filtering.

This gives us pre-filtering accuracy benefits without being restricted to small datasets. It can even increase search speeds whether you have a dataset of 1 million or 100 billion.

Exactly how this works will be covered in a later article. For now, let’s explore some of the new single-stage filtering features and test its performance.

Testing the New Filtering

Filtering in Pinecone is effortless to use. All we need are some vectors, metadata, and an API key.

In this example we use the Stanford Question and Answering Dataset (SQuAD) for both English and Italian languages.

The SQuAD datasets are a set of paragraphs, questions, and answers. Each of those paragraphs is sourced from different Wikipedia pages, and the SQuAD data includes the topic title:

{
 'id': '573387acd058e614000b5cb5',
 'title': 'University_of_Notre_Dame',
 'context': 'One of the main driving forces in the growth of the University was its football team, the ... against the New York Giants in New York City.',
 'question': 'In what year did the team lead by Knute Rockne win the Rose Bowl?',
 'answers': {
 'text': '1925',
 'answer_start': 354
 }
}

From this, we have two metadata tags:

  • lang — the source text’s language (either en or it).
  • title — the topic title of the source text.

We pre-process the datasets to create a new format that looks like:

{
 'id': '573387acd058e614000b5cb5en',
 'context': 'One of the main driving forces in the growth of the University was its football team, the ... against the New York Giants in New York City.',
 'metadata': {
 'lang': 'en',
 'title': 'University_of_Notre_Dame'
 }
}

For Pinecone, we need three items: id, vector, and metadata. We have two of those, but we’re missing our vector field.

The vector field will contain the dense vector embedding of the context. We can build these embeddings using models from sentence-transformers.

We will search in either English or Italian in our use case and return the most similar English/Italian paragraphs. For this, we will need to use a multi-lingual vector embedding model. We can use the stsb-xlm-r-multilingual transformer model from sentence-transformers to do this.

Let’s go ahead and encode our context values:

The new format we produce includes our sample id, text, vector, and metadata, which we can go ahead and upsert to Pinecone:

{
 'id': '573387acd058e614000b5cb5en',
 'vector': [0.1, 0.8, 0.2, ..., 0.7],
 'metadata': {
 'lang': 'en',
 'title': 'University_of_Notre_Dame'
 }
}

We can add as many metadata tags as we’d like. They can even contain numerical values.

Creating the Index

Now, all we need to do is build our Pinecone index. We can use the Python client — which we install using pip install pinecone.

Using an API key we can initialize a new index for our SQuAD data with:

And we’re ready to upsert our data! We’ll perform the upload in batches of 100:

That’s it — our vectors and metadata are ready to go!

Searching

Let’s start with an unfiltered search. We’ll search for paragraphs that are similar to "Early engineering courses provided by American Universities in the 1870s". We encode this using the sentence-transformer model, then query our index with index.query.

We’re returning the three top_k (most similar) results — Pinecone returns our IDs and their respective similarity scores. As we have our contexts stored locally, we can map these IDs back to our contexts using a dictionary (get_sample) like so:

The first Italian paragraph reads:

The College of Engineering was established in the 1920s, however, the first courses in civil and mechanical engineering have been a part of the College of Sciences since the 1870s. Today the college, housed in the Fitzpatrick, Cushing and Stinson-Remick Halls of Engineering, comprises five study departments - aerospace and mechanical engineering, chemical and biomolecular engineering, civil engineering and geological sciences, computer science and engineering, electronic engineering - with eight B. S bachelor's offers. In addition, the college offers five years of dual degree programs with the College of Arts and Letters and an additional B.

So we’re getting great results for both English and Italian paragraphs. However, what if we’d prefer to return English results only?

We can do that using Pinecone’s single-stage filtering. Filters can be built using a set of operators that can be applied to strings and/or numbers:

OperatorFunctionStringNumber
$eqEqual to
$neNot equal to
$gtGreater than
$gteGreater than or equal to
$ltLess than
$lteLess than or equal to
$inIn array
$ninNot in array

We’re looking to filter based on if lang is equal to ($eq) en. All we do is add this filter condition to our query:

And we’re now returning English-only paragraphs, with a search-time equal to (or even faster) than our unfiltered query.

Another cool filter feature is the ability to add multiple conditions. We could exclude the titles ‘University_of_Kansas’ and ‘University_of_Notre_Dame’ while retaining the lang filter:

Now we’re returning English-only results that are not from the Universities of Kansas or Notre Dame topics.

There are also numeric filters. The SQuAD data doesn’t contain any numerical metadata — so we’ll generate a set of random date values and upsert those to our existing vectors.

First, we use a date_maker function to randomly generate our dates (we could use POSIX format too!), then we’ll use the Dataset.map method to add date to our metadata. After this, we upsert as we did before.

Before we filter by date, let’s see the dates we generated for our previous set of results:

We have dates from 2006 and 2016. Let’s swap this out for a specific date range of 2020 only.

We’ve built some detailed metadata filters with multiple conditions and even numeric ranges. All with relentlessly fast search speeds. But we’re using a small dataset of 40K records, which means we’re missing out on one of the best features of single-stage filtering — let’s experiment with something bigger.

Filtering and Search Speeds

Earlier, we mentioned that applying the single-stage filter can speed up our search while still maintaining the accuracy of a pre-filter. This speedup exists with a small 40K dataset, but it’s masked by the network latency.

So we’re going to use a new dataset. The vectors have been randomly generated using np.random.rand. We’re still using a vector size of 768, but our index contains 1.2M vectors this time.

We will test the metadata filtering through a single tag, tag1, consisting of an integer value between 0 and 100.

Without any filter, we start with a search time of 79.2ms:

Using a greater than $gt condition and steadily increasing the filter scope — as expected, we return faster search times the more we restrict our search scope.

Filter speed test As we increase our tag1 $gt value, the search scope is reduced, making our search with the single-stage filter even faster.

And that’s it! We explored the flexible filter queries and tested the impressive search speeds of the single-stage filter!


Thanks for following with us through the three approaches to metadata filtering in vector similarity search; pre-filtering, post-filtering, and Pinecone’s single-stage filtering.

We hope the article has been helpful! Now you can try our single-stage filtering for your own vector search application.

What will you build?

Upgrade your search or recommendation systems with just a few lines of code, or contact us for help.