Strategic Query Shaping for Vespa Hybrid Search

TL;DR:¶

In Vespa, when combining exact nearest neighbor search with weakAnd, it is often more efficient to distribute your filters: (filters AND ENN) OR (filters AND weakAnd). This performs better than the nested approach: filters AND (ENN OR weakAnd).

Context¶

Hybrid search typically means combining vector and lexical retrievers. Also, a fact of life is that anything useful typically also requires good ol’ filtering. Therefore, it is natural to write queries like:

SELECT * 
FROM docs
WHERE filters AND (nearestNeighbor OR weakAnd)

The issue¶

When nearestNeighbor means executing exact nearest neighbors (ENN) search, and it is combined through OR with weakAnd, then you might experience elevated latencies, maybe even timeouts, for seemingly no good reason.

Let’s demonstrate the issue with a small example application.

Experimental setup¶

The setup runs on Vespa version 8.673.18.

For full details check the notebook.

Schema has three fields:

id: an attribute with fast-search for filtering on int values;
embedding: a tensor with one indexed float dimension for the nearest neighbor search;
lexical: string field with an index for weakAnd queries.

Source:

Jupyter Notebook

schema doc {
    document doc {
        field id type int {
            indexing: attribute
            attribute {
                fast-search
            }
        }
        field embedding type tensor<float>(x[1]) {
            indexing: attribute
        }
        field lexical type string {
            indexing: index
            index: enable-bm25
        }
    }
}

Let’s index 100,000 documents with some random data.

Queries¶

The baseline YQL:

Source:

Jupyter Notebook


SELECT *
FROM sources *
WHERE
 (id> 1)
 AND (
   ({targetHits: 1000, approximate: false}nearestNeighbor(embedding, query_embedding))
   OR
   ({targetHits: 1000, defaultIndex: "lexical"}userInput(@query_str))
  )

The alternative YQL:

Source:

Jupyter Notebook


SELECT *
FROM sources *
WHERE
  (id> 1 AND ({targetHits: 1000, approximate: false}
              nearestNeighbor(embedding, query_embedding))
  OR
  (id> 1 AND ({targetHits: 1000, defaultIndex: "lexical"}userInput(@query_str))))

This clearly preserves the matching logic, it just duplicates the filter id>1 to both branches. However, the execution of the queries is very different!

targetHits is set to relatively high 1000 to make the query to do a bit more work to emphasize the difference.

Execution¶

The baseline query without tracing takes consistently about 12 ms. While the alternative query takes about 7 ms. That is about 56% faster in an index of just 100k docs for the same logic: both queries have provided 5692 docs for the first phase ranking. Why then the difference in latency?

Traces¶

Given that the ranking profile is the same, and it gets the same number of hits, let’s focus on the matching phase.

Baseline matching phase summary:

Source:

Jupyter Notebook

match profiling for thread #0 (total time was 91.847 ms)
┌────────┬──────────┬─────────┬──────┬────────────────────────────────────────────────┐
│ seeks  │ total_ms │ self_ms │ step │ query tree                                     │
├────────┼──────────┼─────────┼──────┼────────────────────────────────────────────────┤
│   5693 │   91.847 │   9.503 │ S    │  And[1]                                        │
│ 105690 │    2.840 │   2.628 │ S    │  ├── Attribute{int32,fs}[2] id:<range>         │
│  99998 │   77.513 │  12.364 │ N    │  ├── Or[3]                                     │
│ 100198 │    6.139 │   6.139 │ N    │  │   ├── NearestNeighbor[4]                    │
│  99998 │   59.010 │  35.133 │ N    │  │   └── WeakAnd[5]                            │
│  99998 │    3.928 │   3.906 │ N    │  │       ├── SourceBlender[6]                  │
│     37 │    0.022 │   0.022 │ N    │  │       │   └── MemoryTerm[7] lexical:27110   │
│  99998 │    3.959 │   3.944 │ N    │  │       ├── SourceBlender[8]                  │
│     24 │    0.015 │   0.015 │ N    │  │       │   └── MemoryTerm[9] lexical:6334    │
│  99998 │    4.027 │   4.014 │ N    │  │       ├── SourceBlender[10]                 │
│     29 │    0.013 │   0.013 │ N    │  │       │   └── MemoryTerm[11] lexical:10140  │
│  99998 │    4.046 │   4.027 │ N    │  │       ├── SourceBlender[12]                 │
│     36 │    0.019 │   0.019 │ N    │  │       │   └── MemoryTerm[13] lexical:22335  │
│  99998 │    3.967 │   3.939 │ N    │  │       ├── SourceBlender[14]                 │
│     58 │    0.027 │   0.027 │ N    │  │       │   └── MemoryTerm[15] lexical:22040  │
│  99998 │    3.951 │   3.939 │ N    │  │       └── SourceBlender[16]                 │
│     33 │    0.012 │   0.012 │ N    │  │           └── MemoryTerm[17] lexical:2716   │
│  99999 │    2.416 │   2.204 │ N    │  └── WhiteList[18]                             │
└────────┴──────────┴─────────┴──────┴────────────────────────────────────────────────┘

Alternative matching phase summary:

Source:

Jupyter Notebook

match profiling for thread #0 (total time was 21.827 ms)
┌───────┬──────────┬─────────┬──────┬────────────────────────────────────────────────────┐
│ seeks │ total_ms │ self_ms │ step │ query tree                                         │
├───────┼──────────┼─────────┼──────┼────────────────────────────────────────────────────┤
│  5693 │   21.827 │   1.129 │ S    │  And[1]                                            │
│  5693 │   20.494 │   0.914 │ S    │  ├── Or[2]                                         │
│  5492 │   19.203 │   9.370 │ S    │  │   ├── And[3]                                    │
│ 99998 │    3.764 │   3.764 │ S    │  │   │   ├── Attribute{int32,fs}[4] id:<range>     │
│ 99998 │    6.070 │   6.070 │ N    │  │   │   └── NearestNeighbor[5]                    │
│   213 │    0.377 │   0.059 │ S    │  │   └── And[6]                                    │
│   213 │    0.249 │   0.073 │ S    │  │       ├── WeakAnd[7]                            │
│    38 │    0.027 │   0.013 │ S    │  │       │   ├── SourceBlender[8]                  │
│    37 │    0.014 │   0.014 │ S    │  │       │   │   └── MemoryTerm[9] lexical:27110   │
│    25 │    0.027 │   0.016 │ S    │  │       │   ├── SourceBlender[10]                 │
│    24 │    0.012 │   0.012 │ S    │  │       │   │   └── MemoryTerm[11] lexical:6334   │
│    30 │    0.022 │   0.011 │ S    │  │       │   ├── SourceBlender[12]                 │
│    29 │    0.011 │   0.011 │ S    │  │       │   │   └── MemoryTerm[13] lexical:10140  │
│    37 │    0.026 │   0.013 │ S    │  │       │   ├── SourceBlender[14]                 │
│    36 │    0.013 │   0.013 │ S    │  │       │   │   └── MemoryTerm[15] lexical:22335  │
│    59 │    0.047 │   0.023 │ S    │  │       │   ├── SourceBlender[16]                 │
│    58 │    0.024 │   0.024 │ S    │  │       │   │   └── MemoryTerm[17] lexical:22040  │
│    34 │    0.028 │   0.017 │ S    │  │       │   └── SourceBlender[18]                 │
│    33 │    0.011 │   0.011 │ S    │  │       │       └── MemoryTerm[19] lexical:2716   │
│   212 │    0.069 │   0.069 │ N    │  │       └── Attribute{int32,fs}[20] id:<range>    │
│  5692 │    0.204 │   0.204 │ N    │  └── WhiteList[21]                                 │
└───────┴──────────┴─────────┴──────┴────────────────────────────────────────────────────┘

Matching latency dropped by 76% (comparable to what we’ve seen without the tracing overhead), from 91.8 ms down to 21.8 ms.

When looking closer, the biggest difference is in the weakAnd seeks: baseline evaluated 99,998 docs, while the alternative evaluated only 213 docs. The NearestNeighbor seeked about the same number of documents: 100198 vs. 99998.

It looks like when the baseline query was executed, weakAnd couldn’t prune any documents. Probably because weakAnd is combined with NearestNeighbor through the OR operator, and given that all docs match ENN, weakAnd is forced to evaluate OR on all query terms for each document which is a lot of work! In case you wonder, distanceThreshold doesn’t help.

Now imagine, if you have millions of documents per content node, then depending on the query terms and filtering ratio, you now have multi second latency and probably timeouts due to unnecessary work in the matching phase.

Discussion¶

What other aspects do we know?

HNSW index¶

Even if the tensor field has an HNSW index, when filters are very restrictive, Vespa executes ENN. And if your query has the same shape, you might experience high latencies.

When the approximate nearest neighbor (ANN) search is executed, then there is no such problem. Primarily because the actual ANN hits are found during the blueprint phase (a.k.a., the query planning phase, i.e., before matching) and during the matching phase those hits are represented as a strict iterator over a bitvector, on top it gives a correct hit estimate (i.e. <=targetHits), which allows weakAnd to prune documents, which in turn makes the search fast.

Lexical search with AND¶

If your lexical retriever is configured with grammar: "all" (i.e., all terms are required to match), then you’re not affected by this issue. But probably you have low lexical recall to fight against, tradeoffs.

Source:

Jupyter Notebook

yql_and = """
           SELECT *
           FROM sources *
           WHERE
               (id> 1)
             AND (
               ({targetHits: 1000, approximate: false}nearestNeighbor(embedding, query_embedding))
              OR
               ({targetHits: 1000, defaultIndex: "lexical", grammar: "all"}userInput(@query_str))
               )
           """
request = {
    "yql": yql_and,
    "query_str": "27110 6334 10140 22335 22040 2716",
    "input.query(query_embedding)": [0.5],
    "presentation.timing": True,
    "hits": 1,
}
client.query(body=request).json

{'root': {'children': [{'fields': {'documentid': 'id:doc:doc::96960',
     'sddocname': 'doc'},
    'id': 'id:doc:doc::96960',
    'relevance': 0.24059506636028924,
    'source': 'test_content'}],
  'coverage': {'coverage': 100,
   'documents': 100000,
   'full': True,
   'nodes': 1,
   'results': 1,
   'resultsFull': 1},
  'fields': {'totalCount': 5493},
  'id': 'toplevel',
  'relevance': 1.0},
 'timing': {'querytime': 0.007, 'searchtime': 0.008, 'summaryfetchtime': 0.0}}

Same 7 ms as in the alternative query.

Disadvantages of the alternative query¶

There must be a comment about why it makes sense to duplicate the filters.
The YQL is more complicated for seemingly no good reason.
The filters are checked twice in each OR branch.
Maybe one day this optimization will be obsolete, as Vespa might improve the query planner.

Future work¶

What if there are more retrievers combined with OR operator, e.g. wand? What about match-phase? Not everything is crystal clear for me about the Vespa query execution, but I’m getting there.

Conclusion¶

When confronted with ENN and high latencies, the instinct is to throw more search threads at the problem and continue with your life. Even though this helps to some extent, you might be better off writing your queries in a way that the query execution is more efficient.

If you’re working with the hybrid search, feel free to try this query rewrite.

P.S.: where are those nice tables coming from?¶

Vespa CLI has a vespa inspect profile command which, given a Vespa response with the trace data, prints many nice summary tables.

A script that combines querying and visualizing traces in one command is here:


#!/bin/bash

# Wrap querying and trace visualizations
# Accepts all params that `vespa query` accepts.
# Virtual pipes are needed because `vespa inspect profile` doesn't support reading from stdin.

# Usage:
# ./vespa-query-inspect --file=query.json -t 'http://localhost:8080'

# 1. Create a virtual pipe file in your current directory
mkfifo v_profile

# 2. Start the query in the background with all the params from invoking this script
# It will "hang" there until something reads from the other side.
vespa query --profile "$@" \
  --profile-file=v_profile 2> /dev/null > /dev/null &

# 3. Tell the inspector to read from that virtual file
vespa inspect profile -f v_profile

# 4. Clean up the pipe when done
rm v_profile

P.P.S.: What if no filters are present?¶

Surprisingly, the query is fast because weakAnd prunes (!) docs freely even when ENN is combined through OR:

Source:

Jupyter Notebook

match profiling for thread #0 (total time was 4.903 ms)
┌───────┬──────────┬─────────┬──────┬────────────────────────────────────────────────┐
│ seeks │ total_ms │ self_ms │ step │ query tree                                     │
├───────┼──────────┼─────────┼──────┼────────────────────────────────────────────────┤
│  5691 │    4.903 │   1.046 │ S    │  And[1]                                        │
│  5691 │    3.670 │   0.942 │ S    │  ├── Or[2]                                     │
│  5491 │    1.762 │   1.762 │ S    │  │   ├── NearestNeighbor[3]                    │
│   213 │    0.965 │   0.059 │ S    │  │   └── WeakAnd[4]                            │
│    38 │    0.126 │   0.009 │ S    │  │       ├── SourceBlender[5]                  │
│    37 │    0.116 │   0.116 │ S    │  │       │   └── MemoryTerm[6] lexical:27110   │
│    25 │    0.121 │   0.011 │ S    │  │       ├── SourceBlender[7]                  │
│    24 │    0.109 │   0.109 │ S    │  │       │   └── MemoryTerm[8] lexical:6334    │
│    30 │    0.125 │   0.015 │ S    │  │       ├── SourceBlender[9]                  │
│    29 │    0.109 │   0.109 │ S    │  │       │   └── MemoryTerm[10] lexical:10140  │
│    37 │    0.156 │   0.020 │ S    │  │       ├── SourceBlender[11]                 │
│    36 │    0.136 │   0.136 │ S    │  │       │   └── MemoryTerm[12] lexical:22335  │
│    59 │    0.233 │   0.013 │ S    │  │       ├── SourceBlender[13]                 │
│    58 │    0.220 │   0.220 │ S    │  │       │   └── MemoryTerm[14] lexical:22040  │
│    34 │    0.146 │   0.012 │ S    │  │       └── SourceBlender[15]                 │
│    33 │    0.133 │   0.133 │ S    │  │           └── MemoryTerm[16] lexical:2716   │
│  5690 │    0.187 │   0.187 │ N    │  └── WhiteList[17]                             │
└───────┴──────────┴─────────┴──────┴────────────────────────────────────────────────┘