Companies like Spotify need vast quantities of data accessible at low latency for online services and, increasingly, AI Agents acting on behalf of users. Online services — such as portals and personalization features that use or display a user's listening history — need to look up and paginate through per-user data at interactive speeds. AI Agents answering questions like, "what was I listening to last summer?" need to retrieve a user's data quickly so they can reason over it — filtering, aggregating, or even running SQL locally — to build context for LLM prompts. Both patterns share the same underlying primitive: fast point queries by key over datasets that are often far too large to economically keep resident in a key-value (KV) store like Bigtable or DynamoDB.At Spotify, petabytes reside in Bigtable for online use-cases — but exabytes sit in the GCS data lake. The underlying storage for lakes is fast and getting faster — GCS delivers 30–100ms per request, and S3 Express One Zone and GCS Rapid Storage now offers single-digit millisecond latency. The bottleneck is increasingly not the storage layer itself, 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. They are designed for analytical throughput, not interactive point queries.Random Access Parquet (RAP) bridges this gap. An external index maps keys directly to file locations, and precise ranged reads fetch exactly the bytes needed. RAP operates on the same Parquet files already shared by ML pipelines, notebooks, experimentation platforms, and batch analytics — storing once and paying once, rather than maintaining separate copies in specialized serving systems.How a distributed SQL engine finds the needle in the haystackA user asks an AI agent what they listened to last summer. Just the listening history data spans billions of users across thousands of large daily files, and summer is roughly 90 days. With, let’s say, 1,000 files per day, that is 90,000 individual Parquet files. It is prohibitive to read even a little bit of each within any reasonable time or compute budget for an online use case.There are standard ways to reduce the candidate set. Within each daily partition, files can be further partitioned by key — a technique commonly used to speed up joins that benefits point lookups too when the key is right. From the filename alone, the engine knows whether a given user ID can possibly be in that file. With 1,000 buckets per day, the candidate set drops from 90,000 to 90. Bloom filters on the user ID column can discard files without opening them — cached in a metadata store, they narrow 90 candidates to perhaps the 12 days the user was actually active.We still have to read those 12 files. Each file is large, and finding one user's data within it requires a chain of dependent reads: fetch the footer, parse row group metadata, scan the key column to locate matching rows, then use column and page indexes to find the corresponding pages in each value column. That is multiple, round-trip dependent-fetches to cloud storage per file, per column — and every round-trip contends for IOPS with all the other concurrent queries. Partitioning by key and Bloom filters help select files, but they don't solve the within-file problem.The RAP ApproachThe chain of dependent reads is the fundamental bottleneck, and it applies at every storage tier. Each link costs latency (one round-trip before the next can start) and bandwidth (bytes read just to discover where to read next). On cloud storage, each I/O link costs tens of milliseconds; on local SSD, microseconds; in memory, nanoseconds. The absolute numbers change, but the structure is the same: each step depends on the result of the previous one. Collapsing that chain — replacing dependent reads with a single precomputed lookup — saves both latency and bandwidth regardless of the storage tier. We illustrate the approach over cloud object storage because the per-round-trip cost makes the benefit most dramatic, but the principle is general.Instead of scanning, RAP looks up. An external index maps each key directly to each file and row number where its data resides. Given a key, the reader looks up the index, resolves the row number to page locations using cached file metadata, and issues ranged reads to fetch exactly the pages needed. The index lookup is O(1), the cached page mapping is a low-latency operation, and the data retrieval is a small number of precise ranged reads. Importantly, these reads can be issued in parallel — there are no dependent load chains.The External IndexRAP can operate on any existing Parquet files with no special preparation. The index builder reads footers and page locations for the columns that will be retrieved, scans key columns to build the key-to-location mapping, and writes it out. As new data arrives, each pipeline run produces corresponding index entries. The index grows by appending fragments, not modifying existing ones.The index is a multimap — a single key can have entries across many files and partitions. Each entry is compact: