Vector Index V3 (0.3?)

[chebbyChefNEQ]

This issue tracks a new iteration of vector index in lance. A few learning we want to fix in this iteration/refactor:

• the index build path currently uses inheritance like function calls. (it takes 6-7 layers of functions doing various minor setups to get to the actual build)
• for each new index type we add, we need to write a brand new write_*_index function.
• making extensions in the current indexing scheme is very difficult
• For the foreseeable future our index structure will be IVF_<sub_index>_<quantization>

This refactor will take in place in a few stages

Stage 1 -- clean up index build

Milestone 1 -- IVF Flat

• [ ] Support any distance type in IVF
• [ ] Support any numerical type in IVF
• [ ] Support binary vector + Hamming distance

Goal

• [ ] create a standard QuantizationBuilder trait
• [ ] create a standard IVFShuffler trait
• [ ] create a modular IVF index builder, where we can plugin different index types and quantization to IVF
  • [ ] for num_partition=1 there should be a special optimization where the centroid is omitted, unless the subindex type requires residualization
  • [ ] create a standard SubIndexBuilder trait
  • [ ] this trait should return a handle to read a single Struct, in which we have {index_data: [...], metadata: [...]}
  • [ ] this Struct will be later stitched with Structs from other partitions into a StructArray and saved to a lance_file::v2 file
  • [ ] this trait may also specify metadata() -> Vec<u8>before building. This metadata will be stored as part of the schema metadata. (NOTE: this must be known before opening the file writer, dynamically determined metadata from post-build can not be stored here)
• [ ] Move to lance_file::v2 file format
• [ ] the new builder needs to support optimize_index

Stage 2 -- Simplify and implement query path for new index version

TBD

Stage 3 -- Move existing index to the new builder

TBD

Stage 4 -- Delete old indexing code, old query path remains.

TBD

Stage 5 -- Fully deprecate old index format (V1 and V2)

TBD

[wjones127]

for each new index type we add, we need to write a brand new write_*_index function.

More generally, I would like to see the methods we need to implement per index type moved into a main trait. Another example of a function we have to implement for each index is the optimize_ ones. Might be nice to write a draft of what those traits could be. Many of these are probably at the higher level (general index including scalar and FTS) rather than specific to vector indices.