Indices in Lance¶

Lance treats indices as independent, redundant data structures layered on top of table row identifiers. This keeps the file format free of built-in search structures and lets index formats evolve independently from the table layout.

Lance supports three main categories of indices to accelerate data access: scalar indices, vector indices, and system indices.

Scalar indices accelerate queries on scalar data types such as integers, timestamps, and strings. This includes primary skipping structures such as zone maps as well as secondary structures such as B-trees, bitmap indices, and full-text search indices. They typically accept predicates such as equality, range, set-membership, or token matches and return matching row identifiers.

Vector indices are specialized for approximate nearest neighbor search on high-dimensional embeddings. Examples include IVF-based layouts and HNSW graphs. Instead of scalar predicates, vector indices receive a query vector and return row identifiers plus distance scores.

System indices are auxiliary structures that support internal table maintenance and row-identifier resolution. They are not queried directly by end users. Examples include the Fragment Reuse Index, which supports efficient remapping after compaction.

Design¶

Lance indices are designed with the following design choices in mind:

1. Indices are loaded on demand: A dataset can be loaded and read without loading any indices. Indices are only loaded when a query can benefit from them. This design minimizes memory usage and speeds up dataset opening time.
2. Indices can be loaded progressively: indices are designed so that only the necessary parts are loaded into memory during query execution. For example, when querying a B-tree index, it loads a small page table to figure out which pages of the index to load for the given query, and then only loads those pages to perform the indexed search. This amortizes the cost of cold index queries, since each query only needs to load a small portion of the index.
3. Indices can be coalesced to larger units than fragments. Indices are much smaller than data files, so it is efficient to coalesce index segments to cover multiple fragments. This reduces the number of index files that need to be opened during query execution and then number of unique index data structures that need to be queried.
4. Index files are immutable once written, similar to data files. They can be modified only by creating new files. This means they can be safely cached in memory or on disk without worrying about consistency issues.

Basic Concepts¶

An index in Lance is defined over a specific column (or multiple columns) of a dataset. It is identified by its name.

An index is made up of multiple index segments, identified by their unique UUIDs. Each segment is an independent, self-contained index covering a subset of the data.

Each index segment covers a disjoint subset of fragments in the dataset. The segments must cover all rows in the fragments they cover, with one exception: if a fragment has delete markers at the time of index creation, the index segment is allowed to not contain the deleted rows. The fragments an index covers are those recorded in the fragment_bitmap field.

Index segments together do not need to cover all fragments. This means an index isn't required to be fully up-to-date. When this happens, engines can split their queries into indexed and unindexed subplans and merge the results.

Consider the example dataset in the figure above:

• The dataset contains three fragments with ids 0, 1, 2. Fragment 1 has 10 deleted rows, indicated by the deletion file.
• There is an index called "id_idx", which has two segments: one covering fragments 0 and another covering fragment 1. Fragment 2 is not covered by the index. Queries using this index will need to query both segments and then scan fragment 2 directly. Additionally, when querying the segment covering fragment 1, the engine will need to filter out the 10 deleted rows.
• There is another index called "vec_idx", which has a single segment covering all three fragments. Because it covers all fragments, queries using this index do not need to scan any fragments directly. They do, however, need to filter out the 10 deleted rows from fragment 1.

Index Storage¶

The content of each index is stored at the _indices/{UUID} directory under the base path. We call this location the index directory. The actual content stored in the index directory depends on the index type. These can be arbitrary files defined by the index implementation. However, often they are made up of Lance files containing the index data structures. This allows reuse of the existing Lance file format code for reading and writing index data.

Creating and Updating Index Segments¶

Index segments are created and updated through a transactional process:

1. Build the index data: Read the relevant column data from the fragments to be indexed and construct the index data structures. Write these to files in a new _indices/{UUID} directory, where {UUID} is a newly generated unique identifier.

2. Prepare the metadata: Create an IndexMetadata message with:

3. uuid: The newly generated UUID
4. name: The index name (must match existing segments if adding to an existing index)
5. fields: The columns the index is keyed on, in key order.
6. covering_fields: An independent declaration of the columns whose values the index carries, letting a query that only projects those columns be answered without a fragment take. A field may appear in both lists when the index carries a value it is also keyed on. Empty for an index that carries no extra columns. Declaring a column here does not by itself make it servable -- see Serving carried columns.
7. fragment_bitmap: The set of fragment IDs covered by this segment
8. index_details: Index-specific configuration and parameters
9. version: The format version of this index type

10. See the full protobuf definition in table.proto.

11. Commit the transaction: Write a new manifest that includes the new index segment in its IndexSection. This is done atomically using the same transaction mechanism as data writes.

When updating a column in place (without deleting the row), the engine must remove the affected fragment IDs from the fragment_bitmap field of any index segment whose fields or covering_fields include that column. This marks those fragments as needing re-indexing without invalidating the entire segment and prevents invalid data from being read from the index.

Index Compatibility¶

Before using an index segment, engines must verify they support it:

1. Check the index type: The index_details field contains a protobuf Any message whose type URL identifies the index type (e.g., B-tree, IVF, HNSW). If the engine does not recognize the type, it should skip this index segment.

2. Check the version: The version field in IndexMetadata indicates the format version of the index segment. If the engine does not support this version, it should skip this index segment. This allows index formats to evolve over time while maintaining backwards compatibility.

When an engine cannot use an index segment, it should fall back to scanning the fragments that would have been covered by that segment.

Covering-field contracts¶

A manifest that uses independent key and covering declarations must set FLAG_COVERED_INDEX_METADATA and FLAG_INDEPENDENT_COVERING_FIELDS in both its reader and writer feature flags. In this contract, fields contains only the key fields and covering_fields separately contains the carried fields. The lists have no positional relationship and may overlap. The index dependency set is their union.

For backwards compatibility, a manifest with FLAG_COVERED_INDEX_METADATA but without FLAG_INDEPENDENT_COVERING_FIELDS uses the legacy contract: the carried columns form the trailing suffix of fields in emission order, so covering_fields equals fields[len(fields) - len(covering_fields)..]. A column the index is both keyed on and carries appears twice, once as a key and once in the carried suffix: fields = [1, 1] with covering_fields = [1] is keyed on 1 and carries 1. Readers must select the contract from the manifest flags before interpreting any IndexMetadata.

Activating independent declarations¶

Setting FLAG_INDEPENDENT_COVERING_FIELDS reinterprets every IndexMetadata in the manifest's index section, so a writer must not set it while any entry remains in legacy form. A legacy fields = [vector, payload] with covering_fields = [payload] reads under the new contract as keyed on both columns, and a query on payload would then be planned against an index that is really keyed on vector.

Activation is therefore a single atomic manifest change. A writer that sets the flag must normalize every entry of the index section in that same manifest to the key prefix: replace fields with fields[..len(fields) - len(covering_fields)] and leave covering_fields unchanged. For example, fields = [1, 1] with covering_fields = [1] becomes fields = [1] with covering_fields = [1]. A writer that cannot normalize an entry must not set the flag; it may instead set the flag only on a manifest in which no entry declares covering fields at all. No committed manifest may set the flag while holding a legacy-form entry.

A commit that loses a conflict and retries must normalize the index section of the manifest it is retrying against rather than the one it first read, so an entry another writer committed in between is never carried forward unnormalized.

Derived manifests retain the flag. Every manifest built from one that sets it keeps the bit set, unless a writer converts every entry back to the legacy contract in one atomic change of its own. Because FLAG_COVERED_INDEX_METADATA is recomputed from covering declarations on every commit, a writer that sets FLAG_INDEPENDENT_COVERING_FIELDS must also keep FLAG_COVERED_INDEX_METADATA set in both feature words whenever the independent bit is set, including manifests with no covering entries and manifests that drop the last covering index. The two bits are retained together until an atomic reverse conversion clears them together.

Serving carried columns¶

IndexMetadata.covering_fields records the columns an index segment declares it carries. It does not establish that the segment's storage holds their values.

The segment's storage schema is authoritative. Before answering a query from a carried column, an engine must confirm that column is present and bound to the declared logical field in the storage it opened, and fall back to a take against the base table when it cannot. A segment whose metadata identifies a column its storage does not hold is a legal state, not corruption: a maintenance operation that cannot carry the payload through a rebuild is permitted to withdraw it and leave the covering_fields listed in the metadata.

Loading an index¶

When loading an index:

1. Get the offset to the index section from the index_section field in the manifest.
2. Read the index section from the manifest file. This is a protobuf message of type IndexSection, which contains a list of IndexMetadata messages, each describing an index segment.
3. Read the index files from the _indices/{UUID} directory under the dataset directory, where {UUID} is the UUID of the index segment.

The IndexMetadata message contains important information about the index segment:

• uuid: the unique identifier of the index segment.
• fields: the columns the index is keyed on, in key order.
• covering_fields: the independently declared columns whose values the index carries alongside its own data. A field may also occur in fields. Empty for an index that carries no extra columns. Every id in covering_fields names a top-level field. Covering a struct column carries the whole struct, its children included, as one column. This declaration is not authoritative for what the segment can serve -- see Serving carried columns and the legacy interpretation under Covering-field contracts.
• fragment_bitmap: the set of fragment IDs covered by this index segment.
• index_details: a protobuf Any message that contains index-specific details, such as index type, parameters, and storage format. This allows different index types to store their own metadata.

message IndexSection {
  repeated IndexMetadata indices = 1;

}

message IndexMetadata {
  // Unique ID of an index. It is unique across all the dataset versions.
  UUID uuid = 1;

  /* The columns the index is keyed on, in key order. These refer to file.Field.id.
   *
   * On a stable-row-ID table, -3 may reference the logical _rowid column even
   * though it is absent from the user schema. This identity is independent of
   * whether a fragment stores its row IDs inline or in a hidden data column.
   * An index on this field must store physical row addresses as its payload.
   *
   * When the manifest has feature flag 1 << 13, this list contains only key
   * fields. `covering_fields` independently declares the values the index
   * carries.
   *
   * Without feature flag 1 << 13, the legacy contract applies: the carried fields
   * form the trailing suffix of this list in emission order.
   */
  repeated int32 fields = 2;

  // Index name. Must be unique within one dataset version.
  string name = 3;

  // The version of the dataset this index was built from.
  uint64 dataset_version = 4;

  /* A bitmap of the included fragment ids.
   *
   * This may by used to determine how much of the dataset is covered by the
   * index. This information can be retrieved from the dataset by looking at
   * the dataset at `dataset_version`. However, since the old version may be
   * deleted while the index is still in use, this information is also stored
   * in the index.
   *
   * The bitmap is stored as a 32-bit Roaring bitmap.
   */
  bytes fragment_bitmap = 5;

  /* Details, specific to the index type, which are needed to load / interpret the index
   *
   * Indices should avoid putting large amounts of information in this field, as it will
   * bloat the manifest.
   *
   * Indexes are plugins, and so the format of the details message is flexible and not fully
   * defined by the table format.  However, there are some conventions that should be followed:
   *
   * - When Lance APIs refer to indexes they will use the type URL of the index details as the
   *   identifier for the index type.  If a user provides a simple string identifier like
   *   "btree" then it will be converted to "/lance.table.BTreeIndexDetails"
   * - Type URLs comparisons are case-insensitive.  Thereform an index must have a unique type
   *   URL ignoring case.
   */
  google.protobuf.Any index_details = 6;

  // The minimum lance version that this index is compatible with.
  optional int32 index_version = 7;

  /* Timestamp when the index was created (UTC timestamp in milliseconds since epoch)
   *
   * This field is optional for backward compatibility. For existing indices created before
   * this field was added, this will be None/null.
   */
  optional uint64 created_at = 8;

  /* The base path index of the data file. Used when the file is imported or referred from another dataset.
   * Lance use it as key of the base_paths field in Manifest to determine the actual base path of the data file.
   */
  optional uint32 base_id = 9;

  /* List of files and their sizes for this index segment.
   * This enables skipping HEAD calls when opening indices and allows reporting
   * of index sizes without extra IO.
   * If this is empty, the index files sizes are unknown.
   */
  repeated IndexFile files = 10;

  /* The fields whose values this index co-locates alongside its own data, so a
   * query projecting only those columns can be answered from the index without
   * a take against the base table.
   *
   * When the manifest has feature flag 1 << 13, this declaration is independent
   * of `fields` and has no positional relationship to it. A field may occur in
   * both lists when the index carries a value it is also keyed on. Consumers
   * must use the union of `fields` and `covering_fields` as the index dependency
   * set.
   *
   * Without feature flag 1 << 13, the legacy contract applies: the carried columns
   * form the trailing suffix of `fields` in emission order. A column the
   * index is both keyed on and carries appears twice, once as a key and once in
   * the carried suffix.
   *
   * Empty for an index that carries no extra columns, which is every index
   * written before this field existed.
   *
   * This declaration is not authoritative for what the segment can actually
   * serve. The segment's own storage schema is: a reader must confirm the
   * storage carries a column before answering a query from it, and fall back to
   * a take against the base table otherwise. A declaration naming columns the
   * storage does not hold is a legal state, not corruption -- a maintenance
   * operation that cannot carry the values through a rebuild is permitted to
   * withdraw the payload while leaving this declaration in place.
   */
  repeated int32 covering_fields = 11;

  /* Optional reference to a clustering definition in the same manifest.
   * When present, the ID must be non-zero. Requires FLAG_OBJECT_METADATA (1 << 17)
   * in writer_feature_flags; no clustering reader flag is required.
   */
  optional uint32 clustering_id = 12;

  /* Arbitrary metadata associated with this index segment, like Manifest.table_metadata.
   * Entries must remain valid after changes to the segment. Changes to the same
   * segment preserve all entries, including unknown keys. New segments do not
   * inherit entries automatically. Requires writer flag 1 << 17 while nonempty.
   */
  map<string, string> metadata = 13;

}

Index Segment Metadata¶

Like Manifest.table_metadata, IndexMetadata.metadata is a map<string, string> for arbitrary metadata associated with the index segment. It may be empty. Use namespaced keys and small values. Any metadata stored here must remain valid after changes to the segment.

• Changed segments preserve all entries, including unknown ones.
• New segments do not automatically inherit metadata.

A nonempty map requires FLAG_OBJECT_METADATA (1 << 17) in writer_feature_flags. Readers may ignore it.

Handling deleted and invalidated rows¶

Since index segments are immutable, they may contain references to rows that have been deleted or updated. These should be filtered out during query execution.

There are four situations to consider:

1. A fragment has some deleted rows. A few of the rows in the fragment have been marked as deleted, but some of the rows are still present. The row addresses from the deletion file should be used to filter out results from the index.
2. A fragment has been completely deleted. This can be detected by checking if a fragment ID present in the fragment bitmap is missing from the dataset. Any row addresses from this fragment should be filtered out.
3. A fragment has had one of the index's columns updated in place. This cannot be detected just by examining metadata. To prevent reading invalid data, the engine should filter out any row addresses that are not in the index's current fragment_bitmap. The column need not be one the index is keyed on: every column in the union of fields and covering_fields counts. A carried column can be updated while the keyed column is untouched, and a segment left covering that fragment would answer from an obsolete carried value.
4. A fragment has an updated value in an overlay file. This can be detected by checking if any of the fragments in the index's fragment_bitmap have overlay files. For each overlay whose committed_version is greater than the index segment's dataset_version, the overlay carries updated values not reflected in the index, so its covered rows must be excluded from index results. Excluded rows are re-evaluated against their current (overlaid) values on the flat path — dropping them without re-evaluation would silently lose rows that match under the new value. Exclusion is field-aware: only overlays covering a column in the union of the index's fields and covering_fields matter. Restricting this to the keyed columns would leave a fragment covered after an overlay updated a carried one, and the index would then serve a stale carried value. You may exclude just the affected rows or the whole fragment; the latter is simpler and safer but re-evaluates more rows than necessary. See Data Overlay Files for the exclusion set, re-evaluation, and correctness invariant.

Compaction and remapping¶

When fragments are compacted, the row addresses of the rows in the fragments change. This means that any index segments referencing those fragments will no longer point to existing row addresses. There are three ways to handle this:

1. Do nothing and let the index segment not cover those fragments anymore. This approach is simple and valid, but it means compaction can immediately make an index out-of-date. This is the worst options for query performance.

2. Immediately rewrite the index segments with the row addresses remapped. This approach ensures the index is kept up-to-date, but it incurs significant write amplification during compaction.

3. Create a Fragment Reuse Index that maps old row addresses to new row addresses. This allows readers to remap the row addresses in memory upon reading the index segments. This approach adds some IO and computation overhead during query execution, but avoids write amplification during compaction.

Stable Row ID for Index¶

Indices can optionally use stable row IDs instead of row addresses. A stable row ID is a logical identifier that remains constant even when rows are moved during compaction.

Benefits:

• No remapping needed after compaction
• Updates only invalidate the index if data in the union of its fields and covering_fields changes

Tradeoffs:

• Requires an additional lookup to translate stable row IDs to physical row addresses at query time

This feature is currently experimental. Performance evaluation is ongoing to determine when the tradeoff is worthwhile.