👑 Global vector index

[MBkkt]

Description

Implement a global vector index for DataShards to speedup such and similar requests for row-oriented tables:

SELECT * FROM t ORDER BY SomeDistance(t.embedding, target)

Steps

1. Design vector index

Overall internal design doc

2. Prototype vector index in C++ SDK

• Flat vector index Add flat vector index example to C++ SDK #6262
• KMeans tree vector index [DRAFT] C++ SDK example: vector index #5075
  We decided to don't merge it, because it's too difficult code for C++ SDK

3. Implement build (construction) of vector index

Internal design doc

• DDL: add vector index syntax
  ADD Vector index USING syntax #6602
  Adjust vector index settings #10542

SchemeShard

• create index impl tables
  Vector index build preparation in SchemeShard #6809
  Refactoring index in schemeshard #6879
  Fixes for multiple implementation tables in vector index #6854
• main build loop: fill stage of build_index__progress
  Add reinit step for build vector index #9176
  Vector index coordination [1/N] #10461
  Vector index coordination [2/N] #10462

DataShard scans

• global sample Add SampleK #6853
• global recompute
• global reshuffle Add reshuffle kmeans actor scan  #9725
• local kmeans (sample, recompute, reshuffle) Add local kmeans actor scan #8756

SchemeShard requests coordination

• global sample Add sample k collect for first level of vector index table #7412
• global recompute
• global reshuffle Vector index coordination [3/N] #10498
• local kmeans Parallel local kmeans in schemeshard #11539

Leftovers

• vector index should use reserved name for additional column in posting impl table #7258
• Add reinit step for build vector index #9176
• Rename tmp index impl tables to build index impl tables #9868
• Fix some vector index leftovers: schemeshard #9925
• Vector index coordination: enable local kmeans case #10497
• Adjust vector index settings #10542
• Vector index coordination: fix issues #10889
• Fix vector index billing #11174
• Don't use random scan cookie for build index #11256
• Add stop condition for kmeans #11617
• Fix: vector index description wasn't persisted #11969
• Some fixes in vector index schema #12727

4. Implement search vector index

• kmeans tree vector index search #12639

5. Implement DML vector index

TODO kqp/datashard

Some plans

• Make partition for final posting table before filling it

Possible improvements

• Compact postings
• Use filter for primary keys and covered columns