Lance Documentation

Lance is an open lakehouse format designed for multimodal AI. It provides a unified file, table, and catalog specification optimized for object storage and AI workflows.

Key Capabilities:

• Hybrid Search: Combines vector similarity, full-text search (BM25), and SQL analytics.
• Fast Random Access: Optimized for random access (up to 100x faster than Parquet/Iceberg) without losing scan performance.
• Multimodal Support: Native handling of images, video, audio, text, and embeddings with efficient blob encoding.
• Data Evolution: Allows adding columns with backfilled values without full table rewrites.
• Versioning: Supports ACID transactions, time travel, and zero-copy versioning.
• Ecosystem: Integrates with Apache Arrow, Pandas, Polars, DuckDB, Spark, Ray, Trino, Flink, and catalogs like Apache Polaris, Unity Catalog, and Apache Gravitino.

Fixed size lists (an Arrow data type) are flattened during structural encoding to simplify compression.

• Primitive types: If the underlying type is primitive, the list is treated as a primitive (e.g., a tensor).
• Structural types: If the underlying type is a struct or list, it is treated as a variable-size list.
• Nullability: If items are nullable, the validity array is stored as a separate buffer (as a buffer in the mini-block for mini-block encoding, or zipped with values for full-zip encoding) rather than using repetition or definition levels.

Lance indices follow these design principles:

• On-demand loading: Indices are only loaded when a query can benefit from them, minimizing memory usage and startup time.
• Progressive loading: Only necessary parts of an index (e.g., specific B-tree pages) are loaded into memory during execution.
• Coalescing: Index segments can be coalesced into larger units than data fragments to reduce the number of files opened and unique structures queried.
• Immutability: Index files are immutable once written. They are modified only by creating new files, ensuring safe caching and consistency.

Lance uses a Log-Structured-Merge (LSM) tree architecture called MemWAL to enable high-performance streaming writes while maintaining read performance for scans, point lookups, vector search, and full-text search.

In this architecture:

• The base table is the main Lance table.
• MemWAL shards are added on top of the base table to scale writes horizontally.
• Writers append data to shards.
• Each shard maintains an in-memory MemTable and a durable Write-Ahead Log (WAL).
• MemTables are periodically flushed as small Lance datasets (SSTables), which are later compacted into the base table.

For tables with a primary key, all rows for the same primary key must map to the same shard to ensure correct last-write-wins upsert semantics.

Lance supports three main categories of indices to accelerate data access:

1. Scalar indices: Accelerate queries on scalar data types (integers, timestamps, strings). Examples include zone maps, B-trees, bitmap indices, and full-text search indices. They typically handle predicates like equality, range, or token matches.
2. Vector indices: Specialized for approximate nearest neighbor (ANN) search on high-dimensional embeddings (e.g., IVF-based layouts, HNSW graphs). They receive a query vector and return row identifiers plus distance scores.
3. System indices: Auxiliary structures for internal table maintenance and row-identifier resolution (e.g., Fragment Reuse Index). These are not intended for direct end-user queries.

Data Overlay Files are an experimental Lance feature used to supply new values for a subset of (row offset, field) cells within a fragment without rewriting the fragment's base data files. This makes updates efficient when only a small fraction of rows or columns change.

Note: This feature is currently experimental and requires feature flag 64 (data overlay files). A reader or writer that does not understand overlay files must refuse a dataset that uses them to avoid returning stale data.

Overlays are one of three mechanisms for in-place data changes in Lance:

1. Deletion files: Remove rows.
2. Data evolution: Add or rewrite whole columns.
3. Data overlays: Change individual cells.

Each vector index in Lance is composed of two distinct Lance files stored within the index directory:

1. Index File (index.idx): Contains the search structure (graph or flat organization) and index-specific schema.
2. Auxiliary File (auxiliary.idx): Acts as the vector storage for quantized vectors, containing the actual vector data (or compressed codes).

All partitions within these files must be written in order.

The BTree index in Lance is a two-level structure designed for efficient range queries and sorted access. It balances memory usage and disk performance by splitting the index into two parts:

1. Upper Layers: Stored in page_lookup.lance, these are designed to be cached in memory. They map value ranges to specific page numbers.
2. Leaves (Sub-indices): Stored in page_data.lance (as a flat file), these contain the actual sorted values and row IDs.

This design allows for high scalability; for example, an index with 1 billion values might only require a few MiB of memory for metadata while narrowing searches down to small 4K value chunks.

When executing a substring query (e.g., CONTAINS(column, "query_string")), Lance follows these steps:

1. Sanitization: The query string is sanitized (remapping \x00 or \xFF to spaces) and any user-applied normalization is performed.
2. Parallel Dispatch: The query is sent to all active segments in the logical index simultaneously.
3. BWT Backward-Search: Each segment performs a BWT backward-search to find pattern occurrences.
4. Row ID Mapping: Matching offsets are mapped back to absolute dataset Row IDs.
5. Union: Results from all segments are unioned to return the final set of matches.