Cluster base data in accordance with index structure

Dear colleagues, this is related to Issue #2064, but I decided to create a separate Issue, since it is more general (not confined to HNSW). Without data clustering, processing top-k queries for huge k currently is infeasible over object storage (henceforth OBS).

Current situation

Scenario: Top-k query for large k over an IVF index in Lance, data is stored in OBS. In this case, the bottleneck is not the index search, but the "take" phase, when the result vectors are requested over OBS.

The result vectors are needed for:

• for getting all required result columns from the result vectors or
• for computing exact distances during reranking.

Currently, the result vectors are scattered within fragments and across many fragments. Thus, Lance cannot group the requests into a few range I/O requests, leading to hundreds of thousands of random access requests to OBS. It also makes local caches largely useless.

Solution proposal

Main idea

So as to exploit the fact that all requested row IDs come from a subset of IVF partitions, reorder base table rows so that rows from
the same IVF partitions will be close on disk.

Challenges that need to be addressed

• Challenge 1: Reorder the base table without duplicating the index building work.
• Challenge 2: There may be more than one index over the data set, so reordering the base data according to one vector index will not help accelerating the "take" phase during search over other indices.
• Challenge 3: Ingestion of new data needs not only updating the vector index, but also needs to maintain the order of the base data according to the index / indices.

Approach

Towards Challenge 1: Interleaved index building and base data reordering

In order not to require index rebuilding after base table reordering, use the following process.

• Step 1: Lance workers train IVF centroids on a data sample (in the same way as it is done now).
• Step 2: Instead of the current procedure of assigning all vectors to IVF partitions, a job is started (potentially a
  distributed job involving Spark) that
  • for each vector in the base data set finds the correct IVF partition,
  • writes the vector into a Lance fragment corresponding to IVF partition,
  • merges and repartitions the fragments so that vectors from the same IVF partition lie in the same fragment and are sorted by partition ID.
• Step 3: Lance then writes the partition postings according to the reorganized data fragments.

Towards Challenge 2: Space-filling curves

The above procedure optimizes the base data layout according to one IVF index. As a result

• queries over this IVF index will profit from the accelerated "take" phase,
• queries over other indices (vector or scalar) will still suffer from hundreds of thousands of random point requests.

As an example, let's say we have different IVF indices built over the same data set. Then the goal is to reorder and repartition the data set so that

• if two vectors are in the same partition within any IVF index,
• then the two vectors will be close in base data layout on disk.

For a small number of indices (say three), one can order the data according to a space filling curve.

• A space filling curve can map 3D coordinates into 1D space (a linear order) so that points close in the 3D space will be close in the linear order.
• In this particular example, the coordinates in 3D space are just the three partition IDs of the record in the three IVF indices.

Ordering the data according to such a space filling curve will improve data locality and thus

• allow grouping point requests into physical range I/O requests more frequently,
• improve cache efficiency by improving data locality (pages will already be in cache).

Examples for such space filling curves

• Z-order (for 2D)
• Hilbert Curves.

They are used, for example, by DataBricks in dynamic data clustering. Also, I see that Lance already contains a Hilbert curve implementation for its scalar R-Tree spatial index.

Towards Challenge 3: LSM-style ingestion and compaction

To maintain index validity and the physical data layout according to partition IDs (or the space filling curves), ingest new data LSM-style, where SST files are kept sorted and are compacted according to the order given by the space filling curve.

This will at least reduce the work of ingesting and index building up to the point where, due to distribution drift of the ingested data, centroid quality and recall degenerate. In this case, the centroids, index partitions, and data layout need to be recomputed.

Review the existing IVF index-building flow, the take phase over object storage, fragment repartitioning, and the existing Hilbert-curve implementation for the scalar R-Tree. Compare the proposed layouts for one or multiple IVF indices and the LSM-style ingestion approach. Done requires a validated design that addresses reordering, index validity, multiple indices, and ongoing ingestion without redundant index rebuilding.