Source-linked AI summary
Lance: Efficient Random Access in Columnar Storage through Adaptive Structural Encodings
Weston Pace, Chang She, Lei Xu, Will Jones, Albert Lockett, Jun Wang, Raunak Shah
TL;DR
AI workloads increasingly require both sequential scans and random access, while NVMe caching exposes shortcomings in existing columnar formats. The paper evaluates Arrow, Parquet, and Lance through structural encodings, finding that Lance balances random access and full scans without the trade-offs associated with highly tuned Parquet.
Problem
Search-oriented machine-learning workflows require random access that columnar formats and cloud storage have historically handled poorly.
Source: §1 · p. 1Method
The paper compares Arrow, Parquet, and Lance on NVMe using structural encodings for repetition, validity, compression, and nested data.
Source: §1 · p. 2, §2.2 · p. 3, §4.2.3 · p. 6Results
Lance alternates structural encodings based on data width and balances random access with full scans without trade-offs in scan performance or RAM utilization.
Source: §7 · p. 12Takeaways & Limitations
Lance-style encodings can reduce search-cache requirements, avoid row-group-size configuration, and support additional nested-data capabilities.
Source: §7 · p. 12Coalesced-access benefits decline at billion-row scale and depend on data type, compression ratio, and available page cache.
Source: §5.4 · p. 8
Abstract
from arXiv · showhide
The growing interest in artificial intelligence has created workloads that require both sequential and random access. At the same time, NVMe-backed storage solutions have emerged, providing caching capability for large columnar datasets in cloud storage. Current columnar storage libraries fall short of effectively utilizing an NVMe device's capabilities, especially when it comes to random access. Historically, this has been assumed an implicit weakness in columnar storage formats, but this has not been sufficiently explored. In this paper, we examine the effectiveness of popular columnar formats such as Apache Arrow, Apache Parquet, and Lance in both random access and full scan tasks against NVMe storage. We argue that effective encoding of a column's structure, such as the repetition and validity information, is the key to unlocking the disk's performance. We show that Parquet, when configured correctly, can achieve over 60x better random access performance than default settings. We also show that this high random access performance requires making minor trade-offs in scan performance and RAM utilization. We then describe the Lance structural encoding scheme, which alternates between two different structural encodings based on data width, and achieves better random access performance without making trade-offs in scan performance or RAM utilization.
1 INTRODUCTION
Modern machine-learning workloads combine full scans with random-access search, exposing limitations in columnar formats and cloud storage. The paper reevaluates these formats for NVMe-backed storage and introduces Lance to improve structural encoding.
1 INTRODUCTION
- Search workloads require many random I/O operations because requested subsets are not aligned with a primary index.This creates challenges for both columnar file formats and cloud storage.Source: §1 · p. 1
- NVMe supports hundreds of thousands of IOPS and reaches maximum random-access throughput with 4KiB reads, unlike S3’s larger-read and lower-IOPS profile.The benchmark compares sequential and random reads on NVMe and S3.Source: §1 · p. 1
- NVMe caching offers a more affordable alternative to keeping cloud data entirely in memory, especially for read-only files used with multi-version concurrency control.Caching services such as WekaFS and JuiceFS provide this storage layer.Source: §1 · p. 2
- The paper addresses limited benchmarking of columnar formats for search workflows by analyzing NVMe performance and introducing the Lance format.The analysis extends prior work on Parquet and cloud storage.Source: §1 · p. 2
1.1 Overview
- Structural encoding can worsen random access through extra IOPS, read amplification, or compute overhead beyond the one-or-more IOPS required per column.The overview frames structural encoding as the mechanism behind these access costs.Source: §1.1 · p. 2
2 COLUMNAR STORAGE
Columnar formats organize data into file, chunk, page, and structural-encoding layers that balance compression, scanning, and random access. This section defines the formats, compression behaviors, and evaluation criteria used to study those trade-offs.
2 COLUMNAR STORAGE
- Columnar storage separates file-level structure from structural encodings that split nested data into arrays or buffers.The examined formats share major components, while their structural encodings differ.Source: §2 · p. 2, §2.1 · p. 2
- Parquet prioritizes compression and scanning, while Arrow preserves its in-memory representation with minimal copying and Lance targets balance between scans and random access.The study uses parquet-rs version 54, Arrow IPC 1.5, and experimental Lance 2.1.Source: §2 · p. 2
2.1 File Format
- Row groups and column chunks organize parallel scans, whereas pages combine buffers such as offsets, validity, and repetition levels and control random-access read amplification.Lance uses disk pages and may use miniblock chunks, while Arrow has no equivalent page concept.Source: §2.1 · pp. 2–3
2.2 Compression
- Transparent encodings permit individual-value extraction when locations and lengths are known, while opaque encodings require multiple values to be decompressed.Lance can apply LZ4 independently to very large values, making that use transparent.Source: §2.2 · p. 3
- Sparse compression removes nulls and saves space but complicates indexed access, whereas dense compression preserves positions with filler data at higher space cost.This distinction directly affects random-access behavior.Source: §2.2 · p. 3
2.3 Evaluation Criteria
- Random-access evaluation emphasizes IOPS and read amplification, while full-scan evaluation emphasizes compression and total disk data read.Searches assume a warm search cache; full scans do not assume metadata is cached.Source: §2.3 · p. 3
3 COLUMNAR ENCODING STRATEGIES
Structural encoding converts nested columns into disk buffers, and its design determines random-access I/O, read amplification, and scheduling. Parquet uses page-based flattened columns, while Arrow uses dense buffers and layered offsets or validity bitmaps, producing different access trade-offs.
3 COLUMNAR ENCODING STRATEGIES
- Structural encoding converts nested arrays into leaf nodes and determines buffer layout, compression choices, read amplification, and access scheduling.Compressive encoding then independently compresses the resulting leaf arrays or buffers.Source: §3 · pp. 3–4
3.1 Parquet Structural Encoding Scheme
- Parquet flattens nested data into leaf columns with item, repetition-level, and definition-level buffers, compressed in pages.Pages preserve the structural information for the values they contain.Source: §3.1 · p. 4
- A page offset index enables binary search to locate the page for a row, requiring one I/O per page but incurring page-size read amplification.Reducing page size can improve random access.Source: §3.1 · p. 4
- Parquet supports efficient random access, but expensive compression can limit disk utilization and page indexes can require excessive RAM for large data types.The RAM issue is especially relevant for vectors.Source: §3.1 · p. 4
3.2 Arrow Structural Encoding Scheme
- Arrow flattens nested data into dense leaf columns using placeholder bytes, layered offsets, and validity bitmaps instead of repetition and definition levels.Arrow has no pages or chunking, and its available general compression can make the entire column chunk opaque.Source: §3.2 · p. 4
- Uncompressed Arrow suits in-memory random access because it avoids read amplification, decode cost, page indexes, and search caches.These properties do not directly address disk I/O constraints.Source: §3.2 · p. 4
- For multi-buffer disk access, Arrow requires more I/Os than Parquet because nested and variable-width values are spread across multiple buffers.A List<String> with nulls can require 5 IOPS per value across three access phases.Source: §3.2 · p. 4
- Transparent compression can preserve Arrow random access for simple types, but complex types still require excessive I/O, limiting Arrow-based approaches.The same trade-off makes extremely small row groups ineffective for full scans.Source: §3.2 · p. 4
4 LANCE STRUCTURAL ENCODING SCHEME
Lance uses adaptive structural encodings to target predictable random access while preserving scan efficiency: full zip for large types and miniblocks for small types. Repetition indices, compression-aware layouts, and optional struct packing determine the resulting I/O, compute, cache, and projection trade-offs.
4 LANCE STRUCTURAL ENCODING SCHEME
- At most 1 IOP is targeted for fixed-width random access and at most 2 IOPS for variable-width random access, with performance intended to remain consistent across nesting, data size, and compression.The design also targets full-scan performance comparable with Parquet.Source: §4 · pp. 4–5
4.1 Full Zip Encoding
- Large types use full zip encoding when values are at least 128 bytes, while small types use miniblocks to reduce scan-time computation.Full zip is suitable for embeddings, tensors, images, and large text; miniblocks accept read amplification for more efficient vectorized processing.Source: §4.1 · p. 5, §4.2 · p. 6
4.1.1 Repetition and Definition Levels.
- Full zip combines repetition and definition levels with each leaf-column buffer, placing a control word before every value and lengths before variable-width values.Values are compressed before zipping, while transparent compression preserves independent value decoding; fixed-width nulls retain filler bytes to preserve random-access ranges.Source: §4.1 · p. 5, §4.1.1 · p. 5, §4.1.2 · p. 5
4.1.4 Repetition Index.
- The full-zip repetition index enables variable-width random access by locating value offsets, supporting range reads in 2 IOPS without being read during full scans.Run-length encoded columns can likewise be read in 2 IOPS, but the repetition index increases on-disk size and was not implemented in Lance 2.1.Source: §4.1.4 · p. 6, §4.1.5 · p. 6
4.2 Mini-block Encoding
- Miniblocks store repetition, definition, and data buffers in compressed chunks, improving vectorized encoding and decoding but requiring an entire chunk to retrieve one value.Chunks target 1–2 disk sectors, and chunk metadata is designed to keep the search cache small; variable-size lists additionally require a repetition index to identify relevant chunks.Source: §4.2 · p. 6, §4.2.1 · p. 6, §4.2.3 · p. 6
4.2.3 Repetition Index.
- Miniblock repetition indices store N + 1 integers per chunk to support nested lookups, although the Lance 2.1 reader and writer currently support only one list-lookup level.The index tracks completed lists and flattened items at successive nesting levels.Source: §4.2.3 · pp. 6–7
4.2.4 Search Cache.
- Lance’s search cache depends on the encoding: full zip requires none, while miniblocks require metadata and possibly repetition-index or compression auxiliary data.For 1 billion rows without a repetition index, the stated maximum cache is 1.28 GiB, compared with Parquet’s 20 GiB example for large columns.Source: §4.2.4 · p. 7
4.3 Struct Packing
- Struct packing combines a struct’s fields into one column to reduce random-access IOPS, but it requires fetching and discarding unprojected fields.Packing the entire record effectively converts Lance into row-based storage for uses such as out-of-core sorting and hash joins.Source: §4.3 · p. 7
5 METHODS
The experiments benchmark structural encodings for random access on NVMe, using direct format libraries and controls designed to limit coalesced-access effects. They show that dataset scale, page cache, data type, and library configuration materially affect measured performance.
5 METHODS
- Experiments use a Samsung 970 EVO Plus 2TB NVMe drive and Intel i7-10700K CPU, whose measured peak is 850K random reads per second at 4KiB and 3,400MiB/s.Source: §5 · p. 7
- Parquet random access reaches 350,000 rows per second with optimized configuration versus 5,500 rows per second by default on small scalars.The comparison illustrates the gap between format capability and typical high-level library settings.Source: §5 · p. 7
5.1 Lance
- Lance tests use the Rust crate directly with 1 Mi rows per file and 8 MiB disk pages, while Parquet tests use parquet-rs row selectors with tuned row-group and thread combinations.Source: §5.1 · p. 7, §5.2 · p. 7
5.3 Arrow
- Arrow structural encodings are evaluated through Lance 2.0 because the available Arrow IPC reader and writer APIs did not provide good performance.Lance 2.0 follows the Arrow-style strategy but represents null lists with special offsets instead of a dedicated validity bitmap.Source: §5.3 · pp. 7–8
5.4 Coalesced Access
- Coalesced access combines nearby I/O requests or benefits from page-cache residency, but its gains depend on data type, dataset size, compression ratio, and available page cache.At billions of rows, even very small scalars are unlikely to benefit; experiments therefore use large random datasets, including one billion rows for small types.Source: §5.4 · p. 8
6 EXPERIMENTS
The experiments validate how structural encodings affect random access and full scans, test whether the introduced strategies preserve compression, and examine column packing.
6 EXPERIMENTS
- The experiments evaluate structural-encoding effects on random access and full scans, verify compression, and explore column packing’s effect on random access.Source: §6 · p. 8
6.1 Random Access
Random-access tests compare Parquet, Arrow-style Lance 2.0, and Lance 2.1 across varied data types and nesting on large random datasets. Lance 2.1 generally ties or beats Parquet while avoiding Arrow-style penalties for strings and nesting, though small accesses remain below NVMe potential.
6.1.1 Parquet.
- Parquet performs strongly on smaller data types with one 8KiB IOP per row, while larger data types approach the disk baseline.Its structural encoding places all buffers needed for an array in that single IOP.Source: §6.1.1 · p. 8, Figure 10 · p. 9
- Parquet performance depends strongly on page size: larger pages increase coalesced access but their larger I/Os outweigh those gains, causing performance to decline quickly.At 8KiB pages, only scalars exceed peak disk IOPS; at 64KiB, most data types can exceed it before larger-I/O costs dominate.Source: §6.1.1 · p. 9
6.1.2 Arrow.
- Arrow-style Lance 2.0 exceeds Parquet on simple types but performs worse on strings and string-lists because their additional IOPS are substantial.Extra IOPS for fixed-width validity buffers are less harmful because coalesced access can effectively treat validity as search-cache data.Source: §6.1.2 · p. 9, Figure 11 · p. 9
- Nested Arrow-style data incurs an additional IOP for each validity or offsets buffer, whereas Lance 2.1 avoids that additional IOP.Validity is less noticeable on NVMe because the buffers are small and benefit from coalesced I/O; list offsets are more consequential.Source: §6.1.2 · p. 9
- Lance 2.1 generally ties or beats Parquet, recovers performance on string data, gains robustness to nesting, and slightly underperforms Lance 2.0 on simpler types.The experiments used datasets large enough to avoid repeated indices and make coalesced-I/O benefits unlikely; the baseline was the disk maximum without coalesced-I/O benefits.Source: §6.1 · p. 8, §6.1.3 · p. 9
6.1.3 Lance.
- Lance’s full-zip encoding is lighter weight and performs better across all tested data sizes, with a larger advantage when data is already in memory.Source: §6.1.3 · p. 10, Figure 12 · p. 10
6.1.4 Profiling Small Access Performance.
- Both Parquet and Lance fall short of NVMe capabilities for small accesses, likely because I/Os span 2–3 disk sectors and pread64 adds system-call and decompression overhead.The paper leaves io_uring, sector alignment, and transparent encodings for future investigation.Source: §6.1.4 · p. 10
6.2 Compression Analysis
Compression experiments assess whether Parquet and Lance preserve effective compression and full-scan performance across representative machine-learning data scenarios. The results show that Lance’s structural encodings can compress as efficiently as Parquet.
6.2 Compression Analysis
- The evaluation uses practical ML-oriented datasets and compares Lance compression with Parquet using Snappy and dictionary encoding for full-scan tests.Source: §6.2 · p. 10
- Lance’s structural encodings can compress as efficiently as Parquet across the evaluated data scenarios.Figure 13 reports compression ratios for representative names, prompts, dates, reviews, code, images, embeddings, and websites.Source: Figure 13 · p. 10, §6.2 · p. 10
- Full-scan and compression analysis is limited to Parquet and Lance because available Arrow IPC and ORC implementations make compressed Arrow-style random access impossible.The paper notes that Arrow-style compression could support random access with dependency-free encodings, but does not establish better compression ratios.Source: §6.2 · p. 10
6.3 Full Scan
The full-scan experiments compare Parquet and Lance structural encodings on NVMe, showing that Lance generally matches or exceeds Parquet while using one configuration across data types.
6.3.1 Parquet.
- Parquet reaches only about half of peak disk bandwidth for many encodings, indicating that its scans do not fully utilize NVMe.The experiments selected the best result across tested page-size and row-group combinations.Source: §6.3.1 · p. 11, Figure 14 · p. 11
- Parquet’s scan inefficiency is attributed to I/O scheduling: readers alternate between waiting for I/O and decoding, allowing the disk to sit idle while cores decode.Adding threads does not prevent all cores from becoming busy and leaving the disk underutilized.Source: §6.3.1 · p. 11
- 8KB Parquet pages provide the best scan score in every category except embeddings, where their normalized score is 0.997.The result indicates that 8KB pages suit both random access and full scans against NVMe.Source: §6.3.1 · p. 11
- Parquet row-group tuning is difficult because smaller types generally prefer larger groups, larger types prefer smaller groups, and one size must serve every column.The dates column failed with a 1Ki row group because it produced more than 216 row groups.Source: §6.3.1 · p. 11, Figure 15 · p. 11
6.3.2 Lance.
- Lance achieves full-scan performance equal to or greater than Parquet in nearly all tested cases while exploiting NVMe in both random-access and scan scenarios.The comparison uses file reads per second so compression effectiveness contributes to performance, rather than measuring disk throughput alone.Source: §6.3.2 · pp. 11–12
- Lance still has optimization room: LZ4 cases may be CPU-bound on decompression, while names and dates may need more efficient I/O scheduling.These limitations qualify the otherwise strong full-scan results.Source: §6.3.2 · p. 12
- Lance’s miniblock encoding reduces full-scan CPU work per value when scans are not I/O-bound, motivating its use for small data types.Per-value unzipping becomes expensive without vectorization, whereas miniblocks do less work during scans.Source: §6.3.2 · p. 12, Figure 17 · p. 12
6.4 Struct Packing
The struct-packing experiment measures the trade-off between accessing all fields together and scanning one field in isolation.
6.4 Struct Packing
- Packing multiple fields improves random access when all fields are requested but reduces isolated single-field scan speed.Without compression, loading one field costs the same as loading the entire struct, exposing the structural trade-off directly.Source: §6.4 · p. 12
- Packed structs make random-access performance fall more slowly as field count increases, while single-field full-scan performance drops approximately linearly.The experiment evaluates structs containing 2, 3, 4, and 5 fields using random data and small scalar fields without compression.Source: §6.4 · p. 12, Figure 18 · p. 12
7 CONCLUSION
The conclusion presents structural encoding as a central lens for evaluating columnar formats and introduces Lance as a functional scheme balancing performance across data widths.
7 CONCLUSION
- Lance alternates between two structural encodings to balance performance on small and large data types.The paper reports a fully functional reader and writer using this scheme.Source: §7 · p. 12
- Lance-style encodings use a smaller search cache, avoid row-group-size configuration, and support struct packing, lists across pages, and nested repetition indices.Parquet and Lance both achieve solid full-scan and random-access performance, while Arrow-style encodings require too many IOPS for nested random access.Source: §7 · p. 12
- Both Parquet and Lance can effectively utilize NVMe storage, although both still have room for improvement.The conclusion frames these results as support for structural-encoding analysis rather than as a claim that either format is fully optimized.Source: §7 · p. 12
8 FUTURE WORK
The future-work discussion argues that structural encodings should adapt to storage settings and data types rather than be fixed universally.
8 FUTURE WORK
- Different structural encodings may better suit in-memory storage, NVMe arrays, S3, or new data types such as variant encodings.The paper also identifies Lance row-storage with a packed top-level struct as an unexplored comparison.Source: §8 · p. 12
- Future file formats should avoid baking in one structural encoding and instead expose configurable strategies for multipurpose use.The authors connect configurability with avoiding a proliferation of single-purpose formats.Source: §8 · p. 12