Adventures with the Approximate Nearest Neighbor Search in Vespa
TL;DR: when using targetHits << hits in nearestNeighbor in Vespa, the hit count depends on the actual query embedding value and filters.
Context¶
Recently, I’ve been working on introducing the approximate nearest neighbor (ANN) search using Vespa for an eCommerce search application. Overall, it was a lot of fun and the search experience has improved: latencies are low and relevance is “better”.
However, one corner case was a bit unexpected: when searching with an applied filter there were more hits than without a filter. In other words, more restrictive query returns more hits than a less restrictive one. Crazy, right?
Setup¶
When defining the AB test we’ve tried to be as conservative as possible.
This was primarily to reduce the risk of matching too many “irrelevant” documents by ANN.
One requirement then became to limit the number of hits from ANN in the overall list of search results.
To achieve that we’ve set the targetHits=1 while hits was set to a lot bigger value.
Intuitively, one would expect that in the final search results there would be at most targetHits * N (where N is the number of Vespa content nodes handling the search) hits that are matched with the nearestNeighbor operator.
The overall query looks like this: select * from ann where _filters_ AND (_lexical_matches_ OR _ann_).
Problem¶
During the AB test we’ve got a complaint from a user that after applying a filter the number of hits increases instead of decreasing! The ticket even contained a video that showed exactly that. And the problem is reproducible. Exciting! Let’s get to work.
Investigation¶
The very first thing that came to my mind was that some consistent partial timeouts are happening for the ANN query without a filter and, therefore, fewer hits are being returned. But the timeout hypothesis was quickly ruled out because both queries were returning results way faster than the set timeout.
Next, we’ve checked how many hits there were from the ANN.
It turned out that all hits were from the ANN query, i.e. no lexical matches.
But not exactly 1 * N hits in the filter-less case but a bit less than 2 * N (probably due to distanceThreshold parameter and other HNSW settings).
The difference can be explained by the fact that the targetHits is not a hard limit but only a target, i.e. Vespa promises to get at least targetHits hits with ANN, but it can expose more for ranking.
Anyway, applying a filter on ANN search should decrease the total number of hits, right?
Instead of that, the number of hits increased to 500+ which is way more than 2*N.
Next, followed a session of changing random stuff and seeing what happens.
Soon, a parameter was identified which changed the behaviour: ranking.matching.approximateThreshold.
When the parameter value is set to less than 0.11 then the number of hits is as expected: equal to the filter-less query.
Having learned that, some guru meditation followed.
After which it became clear that different search paths were executed depending on the parameter value.
For full overview on different search paths, see this great blogpost.
When the hit count estimate is LESS than set by the ranking.matching.approximateThreshold then the exact search with pre-filters is executed: all filtered documents are scored by the vector distance metric (HNSW is skipped).
And therefore, many hits.
When the hit count estimate is MORE than set by the ranking.matching.approximateThreshold then the ANN search using HNSW with pre-filters is executed: having a list of filtered documents the HNSW is being searched for targetHits nearest neighbors.
And therefore, only few hits due to the fact that targetHits hints/limits how many hits are needed.
Mitigation¶
The is no mitigation implemented to that situation yet.
The main reason being is that in an index of 100+M docs it is very rare that when a search query returns few hit (less than one webpage) somebody would apply a filter on top.
On mobile, this problem is even less visible.
Also, as the time goes we’ll get more confident with ANN and targetHits should increase to a bigger value so that the problem will be even less visible.
Demo¶
I’ve prepared a small Vespa application that demonstrates what can happen when targetHits << hits.
from vespa.package import (ApplicationPackage, Field, Schema, Document, RankProfile, HNSW)
from vespa.deployment import VespaDocker
from vespa.io import VespaResponse
vap = ApplicationPackage(
name="anncornercase",
schema=[
Schema(
name="ann",
document=Document(
fields=[
Field(
name="filter",
type="int",
indexing=["attribute", "summary"],
attribute=["fast-search"],
),
Field(
name="embedding",
type="tensor<float>(d0[1])",
indexing=["attribute", "index"],
ann=HNSW(
distance_metric="euclidean",
max_links_per_node=16,
neighbors_to_explore_at_insert=200,
))
]
),
rank_profiles=[
RankProfile(
name="ann",
inputs=[
("query(q)", "tensor<float>(d0[1])"),
],
first_phase="closeness(field, embedding)"
)
]
)
]
)# Running this cell recreates the Docker container With Vespa
# which takes about 1 minute
vespa_docker = VespaDocker(container_image="vespaengine/vespa:8.411.13")app = vespa_docker.deploy(application_package=vap)# Create and feed 100 dummy docs
docs = [
{
'id': f'{i}',
'fields': {
'filter': i,
'embedding': [i]
}
} for i in range(100)]
def callback(response: VespaResponse, document_id: str):
if not response.is_successful():
print(f"Error when feeding document {document_id}: {response.get_json()}")
app.feed_iterable(docs, schema="ann", namespace="ann", callback=callback)resp = app.query(body={
'yql': 'select * from ann where ({targetHits:1}nearestNeighbor(embedding, q))',
'hits': 10,
'ranking': 'ann',
"input.query(q)": [2.0]
})
resp.hits[{'id': 'id:ann:ann::2',
'relevance': 1.0,
'source': 'anncornercase_content',
'fields': {'sddocname': 'ann', 'documentid': 'id:ann:ann::2', 'filter': 2}}]With an embedding [2.0] we get 1 hit, exactly as targetHits.
resp = app.query(body={
'yql': 'select * from ann where ({targetHits:1}nearestNeighbor(embedding, q))',
'hits': 10,
'ranking': 'ann',
"input.query(q)": [50.0]
})
len(resp.hits)1With embedding [50.0] we get 1 hits (expected). So, number of hits doesn’t depend on the embedding value.
Now, let’s add a filter AND filter < 5 to the query.
resp = app.query(body={
'yql': """
select *
from ann
where ({targetHits:1}nearestNeighbor(embedding, q)) AND filter < 5
""",
'hits': 10,
'ranking': 'ann',
'input.query(q)': [2.0]
})
len(resp.hits)2Now we get 2 hits (unexpected)! After adding a restrictive filter we get more hits!
Anyway, there are clearly 5 documents (ids 0..4) that satisfy the filter but for some reason the nearestNeighbor retrieved 2 documents.
NOTE: that number is not stable, in other re-feeds, you might get anywhere from 1 to 4 hits.
Let’s change filter to filter < 50 and see what happens.
resp = app.query(body={
'yql': """
select *
from ann
where ({targetHits:1}nearestNeighbor(embedding, q)) AND filter < 50
""",
'hits': 10,
'ranking': 'ann',
'input.query(q)': [2.0]
})
len(resp.hits)1Once again unexpected: we get 1 hit while clearly there are 50 filter matching documents.
Remember that with a more restrictive filter < 5 we got 2 hits!
Interesting.
In the next example, let’s go crazy and run the same query with different embeddings from 0 to 99.
hit_counts = []
for i in range(100):
resp = app.query(body={
'yql': """
select *
from ann
where ({targetHits:1}nearestNeighbor(embedding, q)) AND filter < 5
""",
'hits': 10,
'ranking': 'ann',
"input.query(q)": [i]
})
hit_counts.append(len(resp.hits))
print(hit_counts)[1, 3, 2, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
From the results above we see that most of the time it returns 3 hits.
But for some reason with embeddings from 0 to 5 we get [1, 3, 2, 4, 3] hits.
NOTE: the numbers varies from run to run.
Now, let’s try with filter < 50:
hit_counts = []
for i in range(100):
resp = app.query(body={
'yql': """
select *
from ann
where ({targetHits:1}nearestNeighbor(embedding, q)) AND filter < 50
""",
'hits': 10,
'ranking': 'ann',
"input.query(q)": [i]
})
hit_counts.append(len(resp.hits))
print(hit_counts)[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Lets try targetHits=2`:
hit_counts = []
for i in range(100):
resp = app.query(body={
'yql': """
select *
from ann
where ({targetHits:2}nearestNeighbor(embedding, q)) AND filter < 50
""",
'hits': 10,
'ranking': 'ann',
"input.query(q)": [i]
})
hit_counts.append(len(resp.hits))
print(hit_counts)[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
We’ve got 2 hits for all embeddings.
We can clearly see that when filter matches large portion of the index we get as many hits as set with targetHits.
Now, let’s try with targetHits=1, filter < 50, and ranking.matching.approximateThreshold=0.99:
hit_counts = []
for i in range(100):
resp = app.query(body={
'yql': """
select *
from ann
where ({targetHits:1}nearestNeighbor(embedding, q)) AND filter < 50
""",
'hits': 10,
'ranking': 'ann',
"input.query(q)": [i],
"ranking.matching.approximateThreshold": 0.99,
})
hit_counts.append(len(resp.hits))
print(hit_counts)[1, 3, 2, 4, 5, 4, 3, 4, 5, 6, 8, 6, 7, 9, 7, 8, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
What?! A variety of hits from 1 to 10!
In most cases, the number of hits is 10 because our hits=10. Why in some cases we get less hits? I don’t know for sure but my guess is that the query tensor that is “closer” to the tensors that during the HNSW construction were added later can traverse more nodes.
In the particular example changing the ranking.matching.approximateThreshold=0.49 always gives 1 hit. Notice the relation to filter < 50.
hit_counts = []
for i in range(100):
resp = app.query(body={
'yql': """
select *
from ann
where ({targetHits:1}nearestNeighbor(embedding, q)) AND filter < 50
""",
'hits': 10,
'ranking': 'ann',
"input.query(q)": [i],
"ranking.matching.approximateThreshold": 0.49,
})
hit_counts.append(len(resp.hits))
print(hit_counts)[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Why would anyone change the ranking.matching.approximateThreshold? Sometimes doing exact NN is faster than doing ANN, e.g. when filters match up to 1M docs. Searching through HNSW takes a long time when query is not “similar” to the filters, e.g. query=‘red dress’ and filter is for shoes category.
In my case that parameter was set to 0.15. Do your own benchmarks to find the optimal value.
Anyway, that is all for this time.
Let’s clean our Vespa instance and call it a day.
app.delete_all_docs(content_cluster_name='anncornercase_content', schema='ann')vespa_docker.container.stop()
vespa_docker.container.remove()Fin¶
Various nuances of ANN search should be advertised a little bit more. That would allow for better planning for introducing ANN into search, prevent some confusion while looking at the actual results, and save some time overall. I hope that the demo was informative. I encourage you to play with the setup and let me know what unexpected results you’re getting. That’s it for this time. Bye!