ANN search improvements

[jtibshirani]

This meta issue tracks our work on ANN search. It is not an exhaustive plan and items might be changed/ added over time.

Features

• [x] #81788 @jtibshirani
• [x] https://github.com/elastic/elasticsearch/issues/87625 @jtibshirani
• [x] https://github.com/elastic/elasticsearch/issues/84929
• [x] Support other vector element types
  • https://github.com/elastic/elasticsearch/issues/48322
  • https://github.com/elastic/elasticsearch/issues/89784
• [ ] #72068
• [x] Support sparse vectors of terms with fractional weights (for approaches like SPLADE)
• [ ] Add support for ANN algorithm that does not require all vectors to be held in memory (?)
• [ ] Can we remove need for tuning by automatically choosing good index + search parameters (?)
• [ ] Investigate support for "maximum inner product search" (dot product similarity with unnormalized vectors)

Enhancements

• [x] https://github.com/elastic/elasticsearch/issues/84801
• [x] https://github.com/elastic/elasticsearch/issues/89561
• [x] https://github.com/elastic/elasticsearch/issues/89713
• [x] https://github.com/elastic/elasticsearch/issues/90323
• [x] https://github.com/elastic/elasticsearch/issues/87490 @jtibshirani
• [x] https://github.com/elastic/elasticsearch/issues/91187
• [x] https://github.com/elastic/elasticsearch/issues/91260
• [x] Ability to measure recall of ANN query by comparing to exact scan
• [x] Support for reciprocal rank fusion to combine traditional query and ANN results
• [ ] https://github.com/elastic/elasticsearch/issues/91526
• [x] https://github.com/elastic/elasticsearch/issues/91527
• [ ] https://github.com/elastic/rally-tracks/issues/408
• [ ] https://github.com/elastic/rally-tracks/issues/407
• [ ] https://github.com/elastic/elasticsearch/issues/96779

Performance improvements

Search performance

• [x] Handle hierarchy in HNSW graph @mayya-sharipova
• [x] Streamline lookups in case when all docs have a vector @mayya-sharipova
• [x] Investigate recall gap between Lucene and hnswlib (resolved in LUCENE-10527, available in ES 8.3)
• [x] https://github.com/elastic/elasticsearch/pull/89782
• [ ] https://github.com/elastic/elasticsearch/issues/90700
• [ ] https://github.com/elastic/elasticsearch/issues/88921

Indexing performance

• [x] Speed up HNSW flush + merge by writing vectors to file @jtibshirani
• [x] Reuse data structures across HnswGraph invocations @jtibshirani
• [x] Reexamine graph diversity checks
• [x] Build HNSW graph during indexing instead of on flush (LUCENE-10592, available in ES 8.5)
• [x] Reuse HNSW graphs when merging segments?

Tech Debt

• [x] Revisit our temporary workaround class PerFieldKnnVectorsFormatFieldMapper?
• [x] https://github.com/elastic/rally-tracks/issues/234
• [x] https://github.com/elastic/rally/issues/1549
• [x] https://github.com/apache/lucene/issues/10665
• [x] https://github.com/apache/lucene/issues/11758
• [x] Remove VectorValues#randomAccess
• [x] Remove VectorValues#binaryValue
• [ ] Revisit design of VectorSimilarityFunction
• [ ] https://github.com/elastic/elasticsearch/issues/91523

[elasticmachine]

Pinging @elastic/es-search (Team:Search)

[S-Dragon0302]

@jtibshirani https://github.com/elastic/elasticsearch/issues/72068, Is there an online time node or version

[benwtrent]

Support sparse vectors of terms with fractional weights (for approaches like SPLADE)

This is possible with the use of rank_features mapping and a term query with boosting over the features. If performance issues arise here, then we can revisit making a specific mapping.

[JakeWinter]

Is there any documentation on applying SPLADE retrieval using rank_features mapping? @benwtrent

[benwtrent]

@JakeWinter not yet, We will have something documented soon. But rank_features has been around for a while now and it has always worked just fine for this use case. Its just not well advertised.

PUT sparse_index
{
"rank_features_field": {
"feature_0": 1.2,
"feature_14": 0.2,
...
}
}

Then search is:

POST sparse_index/_search
{
  "query": {
    "bool": {
      "min_should_match": 1
      "should": [
      {"rank_feature": {"field": "rank_features_field.feature_0", "linear": {}, "boost": 0.4}},
      {"rank_feature": {"field": "rank_features_field.feature_12", "linear": {}, "boost": 12.1}},
...
      ]
    }
  }
}

boost is the feature score output from our sparse model. linear does similar scoring to the SPLADE++ paper (dot-product of sparse dimensions).

[S-Dragon0302]

Does ann search support scroll? @jtibshirani

[benwtrent]

@S-Dragon0302 , could you clarify by what you mean by "scroll"? Do you mean find k nearest neighbors, and then on a second call find [k, 2*k] neighbors?

Or that you can use scroll over BM25 combined with the results of the k nearest neighbors?

[S-Dragon0302]

@S-Dragon0302，你能解释一下你所说的“滚动”是什么意思吗？你的意思是找到k最近的邻居，然后在第二次调用时找到[k, 2*k]邻居？

或者你可以使用 scroll over BM25 结合 k 个最近邻居的结果？

@S-Dragon0302 , could you clarify by what you mean by "scroll"? Do you mean find k nearest neighbors, and then on a second call find [k, 2*k] neighbors?

Or that you can use scroll over BM25 combined with the results of the k nearest neighbors?

https://www.elastic.co/guide/en/elasticsearch/reference/8.5/scroll-api.html

[benwtrent]

@S-Dragon0302 that doesn't really answer my question. What is the behavior you expect from KNN results?

Right now, the original global top k found can be paginated, and so can the query. You can use: https://www.elastic.co/guide/en/elasticsearch/reference/8.5/paginate-search-results.html#search-after

[mu4farooqi]

For anyone planning to use Elasticsearch for Hybrid Search (Sparse and Dense Embeddings), I have written a small tutorial. It covers SPLADE++ as well.

https://ufarooqi.com/blog/hybrid-search-with-elasticsearch/

[elasticsearchmachine]

Pinging @elastic/es-search-relevance (Team:Search Relevance)