Indexing the Data Lake for Online Point Queries

The Problem: Fast Lookups Over Lake-Sized Data

Companies like Spotify need low-latency access to enormous datasets, not just for online services but increasingly for AI agents acting on behalf of users. An AI agent answering "what was I listening to last summer?" must pull a user's history from a lake that may hold exabytes. This requires the same underlying primitive as any personalization feature: fast point queries by key over datasets too large to live affordably in a key-value store.

The storage layer is no longer the primary obstacle. Cloud object stores now serve individual requests in tens of milliseconds, and tiers like S3 Express One Zone and GCS Rapid Storage reach single-digit millisecond latencies. The bottleneck sits in the query engines above the storage: distributed SQL engines such as Trino and BigQuery add seconds of planning and scheduling overhead for even a single-row lookup. These systems optimize for analytical throughput, not interactive point queries.

Random Access Parquet (RAP) addresses this gap. An external index maps keys directly to file locations, and ranged reads fetch only the required bytes. The approach works on the same Parquet files shared by ML pipelines, notebooks, experimentation platforms, and batch analytics — storing data once rather than duplicating it in serving systems.

Why File Selection Is Not Enough

Consider the scale of the problem: listening history across billions of users, thousands of large daily files, and roughly 90 days of summer. With an estimated 1,000 files per day, that's 90,000 Parquet files to search. Reading even a fraction of each file is prohibitive for an online workload.

Standard pruning techniques help narrow the candidate set. Partitioning files by key — common for speeding joins — also benefits point lookups. If filenames encode user buckets, the engine can discard files where a user ID cannot exist; 1,000 buckets per day reduces the set from 90,000 files to 90. Bloom filters on the user ID column, cached in a metadata store, can prune without opening files, potentially cutting the candidates to the 12 days a user was actually active.

But those 12 files still must be read. Finding one user's rows inside a large file requires dependent round trips: fetch the footer, parse row group metadata, scan the key column to locate matches, then use column and page indexes to find the corresponding pages in value columns. Every round trip adds latency — tens of milliseconds on cloud storage — and competes for IOPS with concurrent queries.

The RAP Approach: A Lookup Instead of a Scan

RAP collapses that chain of dependent reads. An external index maps each key to the file and row numbers where its data lives. Given a key, the reader resolves the row to page locations from cached file metadata and issues parallel ranged reads for exactly those pages. The index lookup is O(1), the page mapping uses cached data, and data retrieval consists of a small number of parallel reads with no dependency chain between them.

The index is a multimap: one key can map to entries across many files and partitions. Each entry is compact:

The builder reads footers and page locations for target columns, scans key columns to build the mapping, and writes index fragments. New data appends fragments rather than modifying existing ones. As a rule of thumb, indexing terabytes yields gigabytes of index; petabytes of data yield terabytes of index, distributed naturally by hash bucketing.

This is fundamentally more powerful than Parquet's built-in PageIndex or Bloom filters. Those structures are probabilistic and narrow a scan. RAP's external index is definitive: given a key, it returns exact file locations and eliminates the scan entirely.

Out of the box, RAP operates on unmodified Parquet files. When the index points to a page, the reader fetches the entire page — potentially 4MB to extract 100 bytes. For latency-sensitive workloads, write-time preparation makes reads smaller and precisely targeted, at the cost of deeper integration with Parquet internals and pipeline processing.

Optimizing Prepared Files for Random Access

An external index changes what the reader knows before touching a file: the precise file, row, and columns needed. The optimizations below target the columns that serve point queries; other columns in the same file can retain layouts suited to batch analytics. Several techniques benefit any reader, but an index shifts the tradeoffs: properties that aid in-file discovery — fine-grained page indexes, small pages for predicate skipping, dictionary encoding — matter less than minimizing the final read: fewer round trips, smaller fetches, contiguous data.

Concentrating Key Data

Sorting by key keeps all rows for a key contiguous within a file, concentrating them into minimal pages. Many pipelines already produce sorted output. Deterministic hash bucketing (Spark, Scio SMB, Iceberg bucket transforms) guarantees each key maps to one file per partition.

Co-grouping restructures the schema so each key appears once with values in nested columns — for instance, SELECT user_id, ARRAY_AGG(STRUCT(timestamp, track_uri, duration_ms)) FROM streams GROUP BY user_id. This yields one row per key per file without relying on physical sort order.

Coarser partitioning cuts the number of files a key spans. Daily partitioning means 365 files per key per year; weekly drops that to 52. Fewer files means fewer index entries and fewer parallel reads — at the cost of reducing partition-pruning granularity for batch queries.

Reducing Bytes Read

Even when the index points at the exact page, that page can dwarf the target row. Several techniques shrink the fetch size.

One page per key flushes pages at key boundaries. Each decompressed page then belongs to a single key, so no row extraction is needed and page locations can be stored directly in the index entry — no separate page index required. Files remain standard Parquet; key boundaries add roughly 20 bytes of page header overhead. Resetting the compressor at boundaries rarely hurts the compression ratio, though this is data-dependent. One side effect: a PageIndex in such files grows with the key count, not the page count.

ZSTD frame resets offer an alternative when one-page-per-key would bloat the PageIndex. Conventional page sizes remain, but each key's rows compress as an independent ZSTD frame within the page. The index stores byte offset and size per column per frame, enabling direct addressing. To standard readers the page decompresses normally — ZSTD frames concatenate seamlessly. To RAP, each frame is independently addressable. The constraint is that frames must be interpretable on their own, which rules out delta and run-length encodings. PLAIN and dictionary encodings qualify but may be less compact for some types; for blobs, JSON, and flat value columns the tradeoff is usually acceptable.

Storage alignment uses ZSTD skippable frames to pad between keys so fetches align to storage block boundaries (4KB or 16KB). A fetch straddling a boundary requires reading two blocks. Alignment avoids that penalty on local disk, where IOPS are a direct constraint. Cloud providers don't bill per I/O, but underlying disks still benefit. Files remain valid Parquet.

Reducing Read Operations

Fetching a key's values across N columns requires N parallel reads, consuming N× the request capacity and pushing per-key latency toward the tail. Cutting the read count is the largest single win.

Blobs and variants store random-access fields as a single column — JSON, Protobuf, or Parquet Variant — making one read per file sufficient. This suits how online applications consume data, as documents rather than field sets. Batch analytics loses per-field pruning and predicate pushdown inside the blob in exchange.

Interleaving columns handles cases where some columns serve point queries and others serve analytics. The writer physically interleaves column data per key: key 1's column A, key 1's column B, key 2's column A, and so on. ZSTD skippable frames bridge between columns, each remaining a valid compressed stream. A conventional reader decodes column A sequentially while the decompressor skips column B data. RAP issues a single contiguous read spanning all needed columns — effectively a row-major pivot for selected columns without breaking Parquet compatibility. The tradeoff: conventional readers scanning one interleaved column also pull dead space from co-located columns, multiplying I/O for single-column scans. OS caching absorbs this on local storage; cloud readers need to coalesce overlapping reads. The technique shines for partially-shredded Variant columns, where typed columns enable fast vectorized analytics and the adjacent variant blob enables single-read access with minimal overhead for analytic readers.

Covering indexes and hoisted values exploit the fact that index construction visits every row. Small values can be copied directly into the index entry — a covering index that eliminates the storage read entirely. Pre-computed aggregates (per-key event counts, total play time, category breakdowns) are available at index-lookup speed. Hoisted values also enable predicate pushdown at index level, filtering entries before any storage I/O occurs.

Applied together, these optimizations reduce a point query on a data lake to a single ranged read of a few kilobytes — or eliminate the storage read altogether.

Serving Multiple Lookup Dimensions

Real datasets rarely have a single natural key. A transaction log, for instance, will be queried by buyer_id in one request and seller_id in another. RAP accommodates this by letting you build multiple access structures over the same underlying index entries, one per dimension. Exact-match lookups land on hash tables for O(1) access; sorted structures are there when you need range scans.

Adding a secondary index is purely a serving-layer operation. There is no pipeline change and no rewrite of the source data. The trade-off is physical: the file layout is optimized for the dimension on which the data was originally sorted, so secondary lookups can scatter across more files. The reader handles that by coalescing adjacent byte ranges automatically, minimizing the number of read requests sent to storage.

Space-filling curves—Z-ordering and Hilbert curves included—are a complementary technique rather than a competing one. They operate at the file-layout level to improve data locality for secondary dimensions, while secondary indexes supply the direct access paths for queries.

What Changes for the Lake

The defining property of RAP is that it runs against the same Parquet files that already sit in the data lake. The files a scheduled job scans for a weekly aggregate report are the same ones an AI agent reads for context retrieval. No copy, no ETL step, no separate storage bill for a second system.

That changes the economics of what can be served interactively. Teams routinely prune what goes into a KV store because per-gigabyte costs force prioritization; only the hottest data justifies the expense. With RAP, the cost of a point query falls to roughly the cost of a cloud storage read. Historical records, long-tail entities, and low-traffic features all become reasonable candidates for online access. An AI agent no longer needs to restrict its context to whatever fits in a KV store—it can reach back across months or years of history, spanning the full breadth of the lake.

The lake is no longer a batch-only destination. One dataset now serves both analytical and interactive patterns, with the same storage backing two different access modes.