Skip to content

SYSTEM Cited by 1 source

Random Access Parquet (RAP)

Random Access Parquet (RAP) is a Spotify technique for serving fast point queries by key directly against the Parquet files already in a cloud data lake, without copying the data into a key-value serving store like Bigtable or DynamoDB. It combines an external index (key → exact file + rows) with precise ranged reads that fetch only the needed bytes, collapsing the chain of dependent reads that otherwise dominates single-row lookups over object storage. (Source: sources/2026-07-27-spotify-indexing-the-data-lake-for-online-point-queries-e2d11367)

The problem it solves

At Spotify, petabytes live in Bigtable for online use-cases, but exabytes sit in the GCS data lake. Two workloads want low-latency lookup by key over that lake:

  • Online services (portals, personalization) paginating a user's per-user data at interactive speeds.
  • AI agents answering questions like "what was I listening to last summer?" — retrieving a user's data to filter/aggregate/reason over it as LLM-prompt context.

Both are point queries over the data lake. The obstacle is not storage latency — modern object storage is fast (GCS 30–100ms/request; S3 Express One Zone and GCS Rapid Storage at single-digit ms) — but the query engines on top: distributed SQL engines like Trino and BigQuery add seconds of job-scheduling and query-planning overhead even for a single-row lookup, because they are built for analytical throughput, not interactive point queries (concepts/oltp-vs-olap).

How it works

Instead of scanning, RAP looks up:

  1. Index lookup (O(1)). An external index maps the key directly to each file and row number where its data resides.
  2. Resolve rows → page locations using cached file metadata (a low-latency operation).
  3. Precise ranged reads. Fetch exactly the pages needed, issued in parallel — there are no dependent load chains.

This is fundamentally different from Parquet's built-in PageIndex or Bloom filters, which are probabilistic and only narrow a scan. The external index is definitive: given a key it returns the exact files and rows, eliminating the scan.

The external index

RAP operates on any existing Parquet files with no special preparation. The index builder reads footers and page locations for the columns to be retrieved, scans key columns to build the key→location mapping, and writes it out. It is an append-only multimap — a single key can have entries across many files and partitions; new pipeline runs append new fragments, existing fragments are never modified.

Each entry is compact:

Field Description
key The lookup key (e.g. user ID, possibly compound)
file Which Parquet file (dictionary-encoded ordinal)
row numbers The rows within that file
value count (optional) Number of values, enabling pagination

Rule of thumb: indexing terabytes → gigabytes of index; petabytes → terabytes. Large indexes distribute naturally by hash bucketing.

Optimizations for prepared Parquet files

On unmodified files, RAP reads the entire page containing the target row (potentially a 4MB page to extract 100 bytes). Write-time preparation makes reads smaller and more precise. An external index shifts the balance of Parquet layout tradeoffs: properties that help in-file discovery (fine-grained page indexes, small pages for predicate skipping, dictionary encoding for pushdown) matter less; properties that minimize the final read (fewer round-trips, smaller fetches, contiguous data) matter more. The optimizations fall into three categories:

1. Concentrating a key's data

  • Sorting by key — all rows for a key are contiguous, concentrated into as few pages as possible.
  • Co-grouping — schema so each key appears once with values in repeated/nested columns (SELECT user_id, ARRAY_AGG(STRUCT(...)) ... GROUP BY user_id); one row per key per file without relying on sort order.
  • Coarser partitioning — fewer files a key spans (daily → 365 files/key/ year; weekly → 52). Trades off against partition-pruning granularity for batch queries.

2. Reducing bytes read (one-page-per-key)

  • One page per key — writer flushes a page break at each key change; the entire decompressed page belongs to the target key (no row extraction); page locations can be stored directly in the index entry. ~20 bytes of header overhead per key boundary. Files remain standard Parquet.
  • ZSTD frame resets within pages — keep conventional page sizes but compress each key's rows as a separate ZSTD frame; index stores each frame's byte offset/size. To a standard reader the page decompresses normally (ZSTD frames concatenate); to RAP each frame is independently addressable. Rules out delta/RLE encodings (PLAIN or dictionary only).
  • Storage alignment — ZSTD skippable frames pad between keys to align fetches to 4KB/16KB block boundaries, avoiding straddle reads.

3. Reducing read operations — the biggest single win

  • Blobs and Variants — store point-query fields as one column (JSON, Protobuf, or Parquet Variant) → one read per file. Tradeoff: batch analytics loses per-field pruning inside the blob.
  • Interleaving columns (column-interleaving-for-single-read) — physically write each key's data from different columns adjacent (col A key1, col B key1, col A key2, ...), bridged by ZSTD skippable frames so a conventional reader reads column A sequentially and skips the rest. A RAP reader issues a single contiguous ranged read spanning all columns for a key. Especially useful for partially-shredded Variant columns.
  • Covering indexes and hoisted values (concepts/secondary-index) — the index builder visits every row at build time, so it can hoist small values into the index entry (eliminating the storage read → read count zero), precompute per-key aggregates, and enable predicate pushdown at the index level.

Together these reduce a point query to a single ranged read of a few kilobytes — or eliminate the storage read entirely.

Secondary indexes

A dataset with multiple lookup dimensions (e.g. buyer_id and seller_id) is served by building multiple access structures over the same index entries — hash tables for O(1) exact lookups, sorted indexes for range queries. Adding/removing a secondary index is a serving-layer decision: no pipeline changes, no data rewriting. The file layout favors whichever dimension the data was sorted on; secondary lookups may scatter across more files but the reader coalesces adjacent byte ranges. Space-filling curves (Z-ordering, Hilbert) are complementary — they improve file-layout locality for secondary dimensions.

Why it matters

The defining property of RAP is that it operates on the same Parquet files already in the lake — the files BigQuery scans for weekly aggregates are the same files an AI agent reads for context retrieval. No copy, no ETL, no second storage bill (store-once-serve-both-analytical-and-interactive). This changes the economics of what can be served online: the cost of a point query drops to the cost of a cloud storage read, so historical data, long-tail entities, and low-traffic features all become viable for interactive access. The data lake is no longer batch-only — one dataset, two access patterns.

Seen in

Last updated · 766 distilled / 2,225 read