Further ideas for optimizing vector functions.

[mayya-sharipova]

Here are more ideas for optimizing brute-force computations in vectors that needs investigation. Some of these ideas come with the changes in APIs:

1. Use an optimized formula for l2norm -- euclidean distance:
   Instead of computing l2norm as sqrt((d1-q1)^2 + (d2-q2)^2 ...), compute it as sqrt(||d||^2 + ||q||^2 - 2dq), where:

• |||d|| — doc vector magnitude is precomputed during indexing (may be we can also precomputed squared version of it)
• ||q|| — query vector magnitude is precomputed once during query
• dq — dot product, we already have an optimized computation for it.

---

2. Only ranking is needed
   We can use a trank_scores parameter of a search request (by default = true)

GET /_search
{
    "track_scores": false,
    "query" : {
        "script_score" : { ...}
    }
}

This allows several optimizations during query:

• l2norm — we don't need to do the final sqrt. Also, if you use an optimized version of l2norm from Query DSL: Terms Filter #1 we can skip calculation of ||q||^2
• cosineSimilarity — similarly, we can skip calculation of query vector magnitude

---

3. Document vectors are already normalized
   We introduce a new parameter for dense_vector field:

 "my_vector": {
    "type": "dense_vector",
    "dims": 100,
    "normalized": true
  }

This allows:

• indexing optimization: we don't need to compute doc vector lengths on indexing
• query optimization:
  • cosineSimilarity: we don't need to retrieve/compute doc vector magnitude, we don't need to computer query vector magnitude (as queries are also supposed to be normalized)
  • l2norm: if we use l2norm from the Query DSL: Terms Filter #1, then the formula for normalized vectors will be converted to sqrt(2 - 2dq). If we also don't care about scores, the formula will be 1 - dq.

---

4. Painless script optimization
   Inquire from the painless team how to bring DenseVectorScriptDocValues to the constructor to make only once per query a check that the query's number of dims is equal to docs' number of dims.

cc: @jtibshirani

[elasticmachine]

Pinging @elastic/es-search

[jtibshirani]

While working on #46294, I ran some experiments that might give some further ideas:

• I tried moving away from the scripting framework and prototyped a vector_score query that accesses doc values directly. It improved the average QPS from 63.78 to 75.43 on the dataset random-s-100-angular.
• We also experimented with unrolling the combined decoding + dot product loop. This showed an improvement in microbenchmarks and on my platform improved average QPS from 63.78 to 74.44 on random-s-100-angular. However on some platforms, unrolled dot product was substantially slower in microbenchmarks. For example, on @mayya-sharipova's Linux server (40 core Intel Xeon, open jdk 11.0.1), unrolling took 151.91 ns versus a baseline of 122.68 ns.

I don't have proper benchmark results, but in previous experiments I also tried using an optimized formula for L2 norm (1), taking shortcuts when only ranking is needed (2) and avoiding validation of the query vector length on every function call (4). I wasn't able to get major gains from these optimizations -- just wanted to make a note so we don't spend too much time on API discussion without first checking that the changes will help.

[mayya-sharipova]

@jtibshirani Thank you for the ideas. Indeed it makes sense first to run benchmarks before making changes to any APIs.

I tried moving away from the scripting framework and prototyped a vector_score query that accesses doc values directly. It improved the average QPS from 63.78 to 75.43 on the dataset random-s-100-angular.

A user also reported 25% performance drop by moving from accessing doc values directly to script_score

[mayya-sharipova]

Closing this issue as the work on vectors is mostly done in Lucene for ANN search.