Integrate ANN search

[jtibshirani]

Background

Currently Elasticsearch supports storing vectors through the dense_vector field type and using them when scoring documents. This allows users to perform an exact k-nearest neighbors (kNN) search by scanning all documents. This work builds on that functionality to support fast, approximate nearest neighbor search (ANN). The implementation will use Lucene's new ANN support, which is based on the HNSW algorithm. Since Lucene will ship ANN in its upcoming 9.0 release, this feature will only target Elasticsearch 8.x.

Our plan is to extend the dense_vector field type to support adding vectors to an ANN index. We'll then add a new REST endpoint focused on kNN search. This new endpoint will be marked 'experimental' in the first release, as we expect to make API improvements in response to feedback. At first the endpoint will only perform kNN, but we'll follow-up with support for filtering, hybrid retrieval, aggregations, and more. We are really looking forward to everyone's feedback, which will help define the feature and set its direction.

Implementation Plan

Phase 0: Help prepare Lucene's HNSW implementation

• Run benchmarks to more deeply understand performance (https://issues.apache.org/jira/browse/LUCENE-9937)
• Ensure Lucene API has required features and plugin points
  • https://issues.apache.org/jira/browse/LUCENE-9905
  • https://issues.apache.org/jira/browse/LUCENE-9908
  • https://issues.apache.org/jira/browse/LUCENE-10040
  • https://issues.apache.org/jira/browse/LUCENE-10146
• Help resolve vector-related blockers to releasing Lucene 9.0

Phase 1: Basic ANN support

• Update dense_vector field type to support ANN indexing
  • Extend dense_vector to support indexing vectors #78491
  • Support cosine similarity in kNN search #79500
  • Add support for configuring HNSW parameters #79193
• Add new API that supports ANN
  • Add new kNN search endpoint #79013
  • Don't always rewrite the Lucene query in search phases #79358
  • Disallow kNN searches on nested vector fields #79403
  • Ensure kNN search respects authorization #79693
• Fix issues that pop up in Lucene
  • https://issues.apache.org/jira/browse/LUCENE-10147
  • https://issues.apache.org/jira/browse/LUCENE-10228
• Performance testing and improvements
  • Load knn vectors format with mmapfs #78724
  • Add vectors search track rally-tracks#217
• Update documentation
  • Update dense_vector docs with kNN indexing options #80306
  • Add docs for kNN search endpoint #80378
  • [DOCS] Add high-level guide for kNN search #80857

Future Plans: Improvements to functionality and performance

• Support ANN with filtering #81788
• Support search timeouts and cancellation
• Support "hybrid retrieval", where kNN results are combined with matches from another query
• Narrow performance gap between Lucene HNSW and nmslib
  • https://issues.apache.org/jira/browse/LUCENE-10054
• Support other vector element types (bfloat16, integers, etc.)
  • Add a field type for high-dimensional bit vectors. #48322
  • Support for more numerical types in the dense_vector field #72067
• Figure out best way to support "maximum inner product search" (dot product similarity with unnormalized vectors)
• Allow representing a document with multiple embeddings (dense vectors) #72068

[elasticmachine]

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

[MLnick]

Very excited to see this!

Support cosine similarity instead of dot product (?)

IMO both should be supported. Similar items via cosine sim is a very common use case, as is dot product (for e.g. recommendations).

[jtibshirani]

@MLnick thanks for the feedback, I updated the plan to make sure we cover both. Dot product may need special handling as it's not a true metric (for example doesn't satisfy the triangle inequality). I've also seen dot product used as an optimized cosine similarity, by normalizing all vectors to unit length beforehand -- this is more straightforward to support.