Vote: Vector Index Details

[wjones127]

I'd like to propose a message for Vector Index Details:

• There is one message VectorIndexDetails.
• Top-level fields like target_partition_size for IVF configuration.
• Optional HnswIndexDetails means HNSW only used if present. For example, IVF_PQ index would leave that field empty.
• compression field can hold one of the compression types, or be empty for flat.
• I tried to keep this configuration to be what is necessary to build an index, and exclude index build results (like the IVF centroids or PQ codebook) and runtime parameters (like max_iters or sample_rate). Idea is you should be able to create an index with a fixed config and that config should be stable over lifetime of the index.

// Details for vector indexes, stored in the manifest's index_details field.
message VectorIndexDetails {
  VectorMetricType metric_type = 1;

  // The target number of vectors per partition.
  // 0 means unset.
  uint64 target_partition_size = 2;

  // Optional HNSW index configuration. If set, the index has an HNSW layer.
  optional HnswIndexDetails hnsw_index_config = 3;

  message ProductQuantization {
    uint32 num_bits = 1;
    uint32 num_sub_vectors = 2;
  }
  message ScalarQuantization {
    uint32 num_bits = 1;
  }
  message RabitQuantization {
    enum RotationType {
      FAST = 0;
      MATRIX = 1;
    }
    uint32 num_bits = 1;
    RotationType rotation_type = 2;
  }

  // An unset compression oneof means flat / no quantization.
  oneof compression {
    ProductQuantization pq = 4;
    ScalarQuantization sq = 5;
    RabitQuantization rq = 6;
  }
}

// Hierarchical Navigable Small World (HNSW) index details, used as an optional configuration for IVF indexes.
message HnswIndexDetails {
  // The maximum number of outgoing edges per node in the HNSW graph. Higher values
  // means more connections, better recall, but more memory and slower builds.
  // Referred to as "M" in the HNSW literature.
  uint32 max_connections = 1;
  // "construction exploration factor": The size of the dynamic list used during
  // index construction.
  uint32 construction_ef = 2;
}

A full set of changes are drafted here: #6099

[Xuanwo]

Does this mean that we need to have a format change to add new algos?

[wjones127]

Does this mean that we need to have a format change to add new algos?

As a rule of thumb, anything that changes the Lance proto files is a format change and needs a vote. Really anything that changes the on-disk formats needs a vote.

Pure algorithmic changes that don't affect the on-disk representation aren't a format change and don't need a vote.

You could make an index that is a plugin and has an independent proto defining it's details. Then that wouldn't be part of the core format and would need a vote. Still would need to be careful about forward and backwards compat.

[westonpace]

Then that wouldn't be part of the core format and would need a vote

Just to be clear you mean "wouldn't need a vote"?

[westonpace]

+1 though it seems tedious to have to vote on this sort of minutia

// An unset compression oneof means flat / no quantization.

I'd say we should add an empty message for flat. I always interpret "unset" as "default" and "flat compression" feels more like a deliberate choice than an intelligent default.

// The target number of vectors per partition.
// 0 means unset.
uint64 target_partition_size = 2;

Will this be stable for the lifetime of the index? I'd almost prefer...

// The target rows per partition will be sqrt(num_rows) and scale with
// the size of the dataset.  However, the target rows per partition can
// never fall below min_rows_per_partition and this fallback value will
// be used at lower scales
message SqrtWithFallback {
    uint64 min_rows_per_partition = 0;
}

// The target will always be target_rows_per_partition
// regardless of how many rows exist in the dataset
message ExplicitTarget {
    uint64 target_rows_per_partition = 0;
}

...

oneof target_partition_size {
  SqrtWithFallback sqrt_with_fallback = 2;
  ExplicitTarget explicit_target = 3;
}

It's strange to think of max_iters and sample_rate as "runtime parameters" but not construction_ef and max_connections but I fear that is bike shedding.