Spotify Cuts Data Lake Query Latency to Sub-Second Without Duplication

Spotify has shipped Random Access Parquet (RAP), an external indexing layer enabling sub-second point queries directly against Parquet files in its GCS-based data lake without copying data into Bigtable, DynamoDB, or other serving stores. The system closes a gap that has forced data teams at scale to choose between storage cost and query latency.

The problem is concrete at scale. Spotify parks petabytes in Bigtable for low-latency serving, but exabytes live in GCS. Replicating even a fraction into a key-value store to make it queryable is economically untenable. Cloud storage now delivers 30–100ms per request; GCS Rapid Storage and S3 Express One Zone drop to single-digit milliseconds. The real bottleneck is query planning overhead. Trino and BigQuery add seconds of scheduling work even for single-row lookups.

Chain-of-dependent-reads is RAP's core problem. A point query for one user's listening history across 90 days with 1,000 Parquet files per day starts with 90,000 candidate files. Key-based partitioning plus Bloom filters prune to roughly 12 files. Each still requires sequential round-trips: fetch footer, parse row-group metadata, scan the key column, resolve page offsets for each value column. On cloud storage each costs tens of milliseconds. Chained, that is hundreds of milliseconds before a single byte of user data arrives.

RAP collapses the chain to a single O(1) lookup. An external index maps each key directly to file and row numbers. The reader hits the index, resolves row numbers to byte ranges using cached file metadata, and issues parallel ranged reads. No dependent round-trips. Index entries are compact: key, file (dictionary-encoded ordinal), row numbers, and optional value count for pagination. Rule of thumb: indexing a petabyte produces a terabyte of index; terabytes produce gigabytes.

Write-side layout changes eliminate remaining amplification. Even with a perfect index, readers fetch a full 4MB page to extract maybe 100 bytes of useful data. Spotify sorts Parquet output by lookup key, aligns page boundaries to key transitions, and uses interleaved column layout co-locating related value columns. Covering indexes cache enough value data inside the index itself to satisfy some queries without opening any Parquet file. The trade-off is modest index and file size growth for queries resolving in kilobytes.

Secondary indexes extend the model without pipeline changes. Hash-based indexes serve exact lookups across dimensions; sorted indexes handle range queries. Both are managed at the serving layer, letting teams add access paths—buyer ID, seller ID, session ID—without touching upstream jobs or rewriting data.

The practical forcing function is AI agents. Agents answering temporal questions like "what was I listening to last summer?" need to page through months of per-user history at interactive speeds. That data volume has always exceeded what key-value stores can economically hold. RAP lets the same Parquet datasets feed batch analytics, ML training, notebooks, and agent context from a single copy.

Evaluation point: if your team maintains a lake-data replica in a KV store purely for point-query latency, RAP warrants direct assessment. Indexing overhead is bounded, Parquet files stay immutable, and write-side layout changes are incremental enough to apply per-table without pipeline rewrites.