File Format

Dataset Directory

A Lance Dataset is organized in a directory.

/path/to/dataset:
    data/*.lance  -- Data directory
    latest.manifest -- The manifest file for the latest version.
    _versions/*.manifest -- Manifest file for each dataset version.
    _indices/{UUID-*}/index.idx -- Secondary index, each index per directory.
    _deletions/*.{arrow,bin} -- Deletion files, which contain ids of rows
      that have been deleted.

A Manifest file includes the metadata to describe a version of the dataset.

// Manifest is a global section shared between all the files.
message Manifest {
  // All fields of the dataset, including the nested fields.
  repeated lance.file.Field fields = 1;

  // Fragments of the dataset.
  repeated DataFragment fragments = 2;

  // Snapshot version number.
  uint64 version = 3;

  // The file position of the version auxiliary data.
  //  * It is not inheritable between versions.
  //  * It is not loaded by default during query.
  uint64 version_aux_data = 4;

  // Schema metadata.
  map<string, bytes> metadata = 5;

  message WriterVersion {
    // The name of the library that created this file.
    string library = 1;
    // The version of the library that created this file. Because we cannot assume
    // that the library is semantically versioned, this is a string. However, if it
    // is semantically versioned, it should be a valid semver string without any 'v'
    // prefix. For example: `2.0.0`, `2.0.0-rc.1`.
    string version = 2;
  }

  // The version of the writer that created this file.
  //
  // This information may be used to detect whether the file may have known bugs
  // associated with that writer.
  WriterVersion writer_version = 13;

  // If presented, the file position of the index metadata.
  optional uint64 index_section = 6;

  // Version creation Timestamp, UTC timezone
  google.protobuf.Timestamp timestamp = 7;

  // Optional version tag
  string tag = 8;

  // Feature flags for readers.
  //
  // A bitmap of flags that indicate which features are required to be able to
  // read the table. If a reader does not recognize a flag that is set, it
  // should not attempt to read the dataset.
  //
  // Known flags:
  // * 1: deletion files are present
  uint64 reader_feature_flags = 9;

  // Feature flags for writers.
  //
  // A bitmap of flags that indicate which features are required to be able to
  // write to the dataset. if a writer does not recognize a flag that is set, it
  // should not attempt to write to the dataset.
  //
  // The flags are the same as for reader_feature_flags, although they will not
  // always apply to both.
  uint64 writer_feature_flags = 10;

  // The highest fragment ID that has been used so far.
  //
  // This ID is not guaranteed to be present in the current version, but it may
  // have been used in previous versions.
  // 
  // For a single file, will be zero.
  uint32 max_fragment_id = 11;

  // Path to the transaction file, relative to `{root}/_transactions`
  //
  // This contains a serialized Transaction message representing the transaction
  // that created this version.
  //
  // May be empty if no transaction file was written.
  //
  // The path format is "{read_version}-{uuid}.txn" where {read_version} is the
  // version of the table the transaction read from, and {uuid} is a 
  // hyphen-separated UUID.
  string transaction_file = 12;
} // Manifest

Fragments

DataFragment represents a chunk of data in the dataset. Itself includes one or more DataFile, where each DataFile can contain several columns in the chunk of data. It also may include a DeletionFile, which is explained in a later section.

// Data fragment. A fragment is a set of files which represent the
// different columns of the same rows.
// If column exists in the schema, but the related file does not exist,
// treat this column as nulls.
message DataFragment {
  // Unique ID of each DataFragment
  uint64 id = 1;

  repeated DataFile files = 2;

  // File that indicates which rows, if any, should be considered deleted.
  DeletionFile deletion_file = 3;

  // Number of original rows in the fragment, not counting deletions. To compute
  // the current number of rows, subtract `deletion_file.num_deleted_rows` from
  // this value.
  uint64 physical_rows = 4;
}

// Lance Data File
message DataFile {
  // Relative path to the root.
  string path = 1;
  // The ids of the fields/columns in this file.
  //
  // In Lance v1 IDs are assigned based on position in the file, offset by the max
  // existing field id in the table (if any already). So when a fragment is first
  // created with one file of N columns, the field ids will be 1, 2, ..., N. If a
  // second, fragment is created with M columns, the field ids will be N+1, N+2,
  // ..., N+M.
  //
  // In Lance v1 there is one field for each field in the input schema, this includes
  // nested fields (both struct and list).  Fixed size list fields have only a single
  // field id (these are not considered nested fields in Lance v1).
  //
  // This allows column indices to be calculated from field IDs and the input schema.
  //
  // In Lance v2 the field IDs generally follow the same pattern but there is no
  // way to calculate the column index from the field ID.  This is because a given
  // field could be encoded in many different ways, some of which occupy a different
  // number of columns.  For example, a struct field could be encoded into N + 1 columns
  // or it could be encoded into a single packed column.  To determine column indices
  // the column_indices property should be used instead.
  //
  // In Lance v1 these ids must be sorted but might not always be contiguous.
  repeated int32 fields = 2;
  // The top-level column indices for each field in the file.
  //
  // If the data file is version 1 then this property will be empty
  //
  // Otherwise there must be one entry for each field in `fields`.
  //
  // Some fields may not correspond to a top-level column in the file.  In these cases
  // the index will -1.
  //
  // For example, consider the schema:
  //
  // - dimension: packed-struct (0):
  //   - x: u32 (1)
  //   - y: u32 (2)
  // - path: string (3)
  // - embedding: fsl<768> (4)
  //   - fp64
  // - borders: fsl<4> (5)
  //   - simple-struct (6)
  //     - margin: fp64 (7)
  //     - padding: fp64 (8)
  //
  // One possible column indices array could be:
  // [0, -1, -1, 1, 3, 4, 5, 6, 7]
  //
  // This reflects quite a few phenomenon:
  // - The packed struct is encoded into a single column and there is no top-level column
  //   for the x or y fields
  // - The string is encoded into two columns
  // - The embedding is encoded into a single column (common for FSL of primitive) and there
  //   is not "FSL column"
  // - The borders field actually does have an "FSL column"
  //
  // The column indices table may not have duplicates (other than -1)
  repeated int32 column_indices = 3;
  // The major file version used to create the file
  uint32 file_major_version = 4;
  // The minor file version used to create the file
  //
  // If both `file_major_version` and `file_minor_version` are set to 0,
  // then this is a version 0.1 or version 0.2 file.
  uint32 file_minor_version = 5;
} // DataFile

The overall structure of a fragment is shown below. One or more data files store the columns of a fragment. New columns can be added to a fragment by adding new data files. The deletion file (if present), stores the rows that have been deleted from the fragment.

Every row has a unique id, which is an u64 that is composed of two u32s: the fragment id and the local row id. The local row id is just the index of the row in the data files.

File Structure

Each .lance file is the container for the actual data.

At the tail of the file, a Metadata protobuf block is used to describe the structure of the data file.

message Metadata {
  // 4 was used for StatisticsMetadata in the past, but has been moved to prevent
  // a bug in older readers.
  reserved 4;

  // Position of the manifest in the file. If it is zero, the manifest is stored
  // externally.
  uint64 manifest_position = 1;

  // Logical offsets of each chunk group, i.e., number of the rows in each
  // chunk.
  repeated int32 batch_offsets = 2;

  // The file position that page table is stored.
  //
  // A page table is a matrix of N x M x 2, where N = num_fields, and M =
  // num_batches. Each cell in the table is a pair of <position:int64,
  // length:int64> of the page. Both position and length are int64 values. The
  // <position, length> of all the pages in the same column are then
  // contiguously stored.
  //
  // Every field that is a part of the file will have a run in the page table.
  // This includes struct columns, which will have a run of length 0 since 
  // they don't store any actual data.
  //
  // For example, for the column 5 and batch 4, we have:
  // ```text
  //   position = page_table[5][4][0];
  //   length = page_table[5][4][1];
  // ```
  uint64 page_table_position = 3;

  message StatisticsMetadata {
    // The schema of the statistics.
    //
    // This might be empty, meaning there are no statistics. It also might not 
    // contain statistics for every field.
    repeated Field schema = 1;

    // The field ids of the statistics leaf fields.
    //
    // This plays a similar role to the `fields` field in the DataFile message.
    // Each of these field ids corresponds to a field in the stats_schema. There
    // is one per column in the stats page table.
    repeated int32 fields = 2;

    // The file position of the statistics page table
    //
    // The page table is a matrix of N x 2, where N = length of stats_fields. This is
    // the same layout as the main page table, except there is always only one
    // batch.
    //
    // For example, to get the stats column 5, we have:
    // ```text
    //   position = stats_page_table[5][0];
    //   length = stats_page_table[5][1];
    // ```
      uint64 page_table_position = 3;
  }

  StatisticsMetadata statistics = 5;
} // Metadata

Optionally, a Manifest block can be stored after the Metadata block, to make the lance file self-describable.

In the end of the file, a Footer is written to indicate the closure of a file:

+---------------+----------------+
| 0 - 3 byte    | 4 - 7 byte     |
+===============+================+
| metadata position (uint64)     |
+---------------+----------------+
| major version | minor version  |
+---------------+----------------+
|   Magic number "LANC"          |
+--------------------------------+

Feature Flags

As the file format and dataset evolve, new feature flags are added to the format. There are two separate fields for checking for feature flags, depending on whether you are trying to read or write the table. Readers should check the reader_feature_flags to see if there are any flag it is not aware of. Writers should check writer_feature_flags. If either sees a flag they don’t know, they should return an “unsupported” error on any read or write operation.

Fields

Fields represent the metadata for a column. This includes the name, data type, id, nullability, and encoding.

Fields are listed in depth first order, and can be one of (1) parent (struct), (2) repeated (list/array), or (3) leaf (primitive). For example, the schema:

a: i32
b: struct {
    c: list<i32>
    d: i32
}

Would be represented as the following field list:

name	id	type	parent_id	logical_type
a	1	LEAF	0	"int32"
b	2	PARENT	0	"struct"
b.c	3	REPEATED	2	"list"
b.c	4	LEAF	3	"int32"
b.d	5	LEAF	2	"int32"

Encodings

Lance uses encodings that can render good both point query and scan performance. Generally, it requires:

1. It takes no more than 2 disk reads to access any data points.

2. It takes sub-linear computation (O(n)) to locate one piece of data.

Plain Encoding

Plain encoding stores Arrow array with fixed size values, such as primitive values, in contiguous space on disk. Because the size of each value is fixed, the offset of a particular value can be computed directly.

Null: TBD

Variable-Length Binary Encoding

For variable-length data types, i.e., (Large)Binary / (Large)String / (Large)List in Arrow, Lance uses variable-length encoding. Similar to Arrow in-memory layout, the on-disk layout include an offset array, and the actual data array. The offset array contains the absolute offset of each value appears in the file.

+---------------+----------------+
| offset array  | data array     |
+---------------+----------------+

If offsets[i] == offsets[i + 1], we treat the i-th value as Null.

Dictionary Encoding

Directory encoding is a composite encoding for a Arrow Dictionary Type, where Lance encodes the key and value separately using primitive encoding types, i.e., key are usually encoded with Plain Encoding.

Dataset Update and Schema Evolution

Lance supports fast dataset update and schema evolution via manipulating the Manifest metadata.

Appending is done by appending new Fragment to the dataset. While adding columns is done by adding new DataFile of the new columns to each Fragment. Finally, Overwrite a dataset can be done by resetting the Fragment list of the Manifest.

Deletion

Rows can be marked deleted by adding a deletion file next to the data in the _deletions folder. These files contain the indices of rows that have between deleted for some fragment. For a given version of the dataset, each fragment can have up to one deletion file. Fragments that have no deleted rows have no deletion file.

Readers should filter out row ids contained in these deletion files during a scan or ANN search.

Deletion files come in two flavors:

1. Arrow files: which store a column with a flat vector of indices

2. Roaring bitmaps: which store the indices as compressed bitmaps.

Roaring Bitmaps are used for larger deletion sets, while Arrow files are used for small ones. This is because Roaring Bitmaps are known to be inefficient for small sets.

The filenames of deletion files are structured like:

_deletions/{fragment_id}-{read_version}-{random_id}.{arrow|bin}

Where fragment_id is the fragment the file corresponds to, read_version is the version of the dataset that it was created off of (usually one less than the version it was committed to), and random_id is a random i64 used to avoid collisions. The suffix is determined by the file type (.arrow for Arrow file, .bin for roaring bitmap).

// Deletion File
//
// The path of the deletion file is constructed as:
//   {root}/_deletions/{fragment_id}-{read_version}-{id}.{extension}
// where {extension} is `.arrow` or `.bin` depending on the type of deletion.
message DeletionFile {
  // Type of deletion file, which varies depending on what is the most efficient
  // way to store the deleted row ids. If none, then will be unspecified. If there are
  // sparsely deleted rows, then ARROW_ARRAY is the most efficient. If there are
  // densely deleted rows, then BIT_MAP is the most efficient.
  enum DeletionFileType {
    // Deletion file is a single Int32Array of deleted row ids. This is stored as
    // an Arrow IPC file with one batch and one column. Has a .arrow extension.
    ARROW_ARRAY = 0;
    // Deletion file is a Roaring Bitmap of deleted row ids. Has a .bin extension.
    BITMAP = 1;
  }

  // Type of deletion file. If it is unspecified, then the remaining fields will be missing.
  DeletionFileType file_type = 1;
  // The version of the dataset this deletion file was built from.
  uint64 read_version = 2;
  // An opaque id used to differentiate this file from others written by concurrent
  // writers.
  uint64 id = 3;
  // The number of rows that are marked as deleted.
  uint64 num_deleted_rows = 4;
} // DeletionFile

Deletes can be materialized by re-writing data files with the deleted rows removed. However, this invalidates row indices and thus the ANN indices, which can be expensive to recompute.

Committing Datasets

A new version of a dataset is committed by writing a new manifest file to the _versions directory. Only after successfully committing this file should the _latest.manifest file be updated.

To prevent concurrent writers from overwriting each other, the commit process must be atomic and consistent for all writers. If two writers try to commit using different mechanisms, they may overwrite each other’s changes. For any storage system that natively supports atomic rename-if-not-exists or put-if-not-exists, these operations should be used. This is true of local file systems and cloud object stores, with the notable except of AWS S3. For ones that lack this functionality, an external locking mechanism can be configured by the user.

Conflict resolution

If two writers try to commit at the same time, one will succeed and the other will fail. The failed writer should attempt to retry the commit, but only if it’s changes are compatible with the changes made by the successful writer.

The changes for a given commit are recorded as a transaction file, under the _transactions prefix in the dataset directory. The transaction file is a serialized Transaction protobuf message. See the transaction.proto file for its definition.

The commit process is as follows:

1. The writer finishes writing all data files.

2. The writer creates a transaction file in the _transactions directory. This files describes the operations that were performed, which is used for two purposes: (1) to detect conflicts, and (2) to re-build the manifest during retries.

3. Look for any new commits since the writer started writing. If there are any, read their transaction files and check for conflicts. If there are any conflicts, abort the commit. Otherwise, continue.

4. Build a manifest and attempt to commit it to the next version. If the commit fails because another writer has already committed, go back to step 3.

5. If the commit succeeds, update the _latest.manifest file.

When checking whether two transactions conflict, be conservative. If the transaction file is missing, assume it conflicts. If the transaction file has an unknown operation, assume it conflicts.

External Manifest Store

If the backing object store does not support *-if-not-exists operations, an external manifest store can be used to allow concurrent writers. An external manifest store is a KV store that supports put-if-not-exists operation. The external manifest store supplements but does not replace the manifests in object storage. A reader unaware of the external manifest store could read a table that uses it, but it might be up to one version behind the true latest version of the table.

The commit process is as follows:

1. PUT_OBJECT_STORE mydataset.lance/_versions/{version}.manifest-{uuid} stage a new manifest in object store under a unique path determined by new uuid

2. PUT_EXTERNAL_STORE base_uri, version, mydataset.lance/_versions/{version}.manifest-{uuid} commit the path of the staged manifest to the external store.

3. COPY_OBJECT_STORE mydataset.lance/_versions/{version}.manifest-{uuid} mydataset.lance/_versions/{version}.manifest copy the staged manifest to the final path

4. PUT_EXTERNAL_STORE base_uri, version, mydataset.lance/_versions/{version}.manifest update the external store to point to the final manifest

Note that the commit is effectively complete after step 2. If the writer fails after step 2, a reader will be able to detect the external store and object store are out-of-sync, and will try to synchronize the two stores. If the reattempt at synchronization fails, the reader will refuse to load. This is to ensure the that the dataset is always portable by copying the dataset directory without special tool.

The reader load process is as follows:

1. GET_EXTERNAL_STORE base_uri, version, path then, if path does not end in a UUID return the path

2. COPY_OBJECT_STORE mydataset.lance/_versions/{version}.manifest-{uuid} mydataset.lance/_versions/{version}.manifest reattempt synchronization

3. PUT_EXTERNAL_STORE base_uri, version, mydataset.lance/_versions/{version}.manifest update the external store to point to the final manifest

4. RETURN mydataset.lance/_versions/{version}.manifest always return the finalized path, return error if synchronization fails

Statistics

Statistics are stored within Lance files. The statistics can be used to determine which pages can be skipped within a query. The null count, lower bound (min), and upper bound (max) are stored.

Statistics themselves are stored in Lance’s columnar format, which allows for selectively reading only relevant stats columns.

Statistic values

Three types of statistics are stored per column: null count, min value, max value. The min and max values are stored as their native data types in arrays.

There are special behavior for different data types to account for nulls:

For integer-based data types (including signed and unsigned integers, dates, and timestamps), if the min and max are unknown (all values are null), then the minimum/maximum representable values should be used instead.

For float data types, if the min and max are unknown, then use -Inf and +Inf, respectively. (-Inf and +Inf may also be used for min and max if those values are present in the arrays.) NaN values should be ignored for the purpose of min and max statistics. If the max value is zero (negative or positive), the max value should be recorded as +0.0. Likewise, if the min value is zero (positive or negative), it should be recorded as -0.0.

For binary data types, if the min or max are unknown or unrepresentable, then use null value. Binary data type bounds can also be truncated. For example, an array containing just the value "abcd" could have a truncated min of "abc" and max of "abd". If there is no truncated value greater than the maximum value, then instead use null for the maximum.

Warning

The min and max values are not guaranteed to be within the array; they are simply upper and lower bounds. Two common cases where they are not contained in the array is if the min or max original value was deleted and when binary data is truncated. Therefore, statistic should not be used to compute queries such as SELECT max(col) FROM table.

Page-level statistics format

Page-level statistics are stored as arrays within the Lance file. Each array contains one page long and is num_pages long. The page offsets are stored in an array just like the data page table. The offset to the statistics page table is stored in the metadata.

The schema for the statistics is:

<field_id_1>: struct
    null_count: i64
    min_value: <field_1_data_type>
    max_value: <field_1_data_type>
...
<field_id_N>: struct
    null_count: i64
    min_value: <field_N_data_type>
    max_value: <field_N_data_type>

Any number of fields may be missing, as statistics for some fields or of some kind may be skipped. In addition, readers should expect there may be extra fields that are not in this schema. These should be ignored. Future changes to the format may add additional fields, but these changes will be backwards compatible.

However, writers should not write extra fields that aren’t described in this document. Until they are defined in the specification, there is no guarantee that readers will be able to safely interpret new forms of statistics.