Top-level index configuration

Indices in Lance are split into two levels:

1. Top-level indexes, unique by name
2. Index files, unique by UUID

Each index name has multiple files. The files cover different parts of the dataset.

Right now, we only have messages for index files. Top-level indices are inferred by aggregating over all the index files with the same index name.

We'd like to introduce a proper concept of a top-level index, to make managing the indices easier.

This causes some footguns with indices:

1. Users can't create indices on empty tables
2. If a user creates an index, then updates all the rows covered in that index, the index is deleted.

Designing new messages

Goals

1. Separate file-level and index-level configuration.
2. Allow faster index loading by storing size in manifest. [^1]
3. Allow configuring an index on an empty table.
4. Decouple metadata from implementation details of the index
5. Make it cheaper to retrieve the index type

[^1]: The first thing we do when loading an index file is make a HEAD request to get the size, so we can make a range request later to read the file footer. If we cache the file size in the manifest, we can skip that head request. This can be meaningful savings (30-200ms) in high latency object stores.

FAQ

• Do we agree we can make configuration an implementation detail?
  • Yes, we'd like for this to be pluggable in the future.
• Is there a reason to keep dataset version?
  • It seems to only be used to fill in missing fragment_bitmaps.
• Is there a reason to use column names over field ids?
  • We already use field ids in IndexMetadata message.
• How should we handle backwards compatibility?
  • We should start writing out both forms of index metadata.
  • Newer readers should prefer the V2 metadata.
  • Later, add a feature flag for dropping the old metadata. Turn it off
    only for tables written before.
• How does this relate to Index V3?
  • Index V3 just specifies how vector indices are formatted. They have metadata within themselves. The configuration in this index metadata can be considered a cached copy of that information. Both will still be written for compatibility.

Code

/**
 * Metadata for an index.
 */
message IndexV2 {
  // A 16-byte encoded UUID (endianness?). This unique identifies the index
  // across time. If the index configuration changes, this also changes.
  bytes id = 1;
  // A unique, human-readable name of the index.
  string name = 2;
  // The fields that the index is on.
  repeated int32 field_ids = 3;
  // The index type id. Used to differentiate the index_config message and 
  // let readers determine if they know the index type. The prefix "lance:" is 
  // reserved for indices implemented in the Lance repo.
  string index_type_id = 4;
  // The configuration for the index. This should not change after it is created.
  google.protobuf.Any index_config = 5;
  // The files that make up the index. Each file covers a different part of the
  // dataset.
  repeated IndexFile files = 6;
}

// A file that is part of an index. This file is immutable. Updates to indices
// add new files or remove existing ones.
message IndexFile {
  // A 16-byte encoded UUID (endianness?). This unique identifies the index file.
  // The filename is derived from this UUID.n
  bytes id = 1;
  // The size in bytes of the index file.
  int64 file_size = 2;
  // A serialized roaring bitmap. Contains the fragment ids that are covered by
  // this index. There should not be any overlap between index files. If a
  // fragment is in this bitmap, then all of it's (non-deleted) rows are covered
  // by the index. (There is no partial coverage.)
  bytes fragment_bitmap = 3;
}

Plan

First, we will change the apparent behavior with the current data structures, then we will add the new data structures.

• Behavior change for scalar indices
• Decouple index configuration from dataset size
• Behavior change for vector indices
• Perform proto refactor

Start by reviewing the existing index metadata messages and the current scalar and vector index behavior; the issue does not name files or tests. Compare the proposed IndexV2 and IndexFile messages with the backward-compatibility plan. Done means the listed behavior changes, configuration decoupling, and proto refactor are addressed.