Indexing the Data Lake for Online Point Queries | Spotify Engineering (opens in new tab)
Random Access Parquet (RAP) enables low-latency point queries directly against massive data lakes. It addresses the mismatch between fast cloud storage and query engines such as Trino or BigQuery, whose planning and scheduling overhead can make single-row lookups take seconds. By indexing keys to exact Parquet files and rows, RAP avoids broad scans and retrieves only the required data while preserving a shared source of truth for analytics, ML, and online services. ## Why Conventional Query Engines Struggle - Online applications and AI agents need fast access to per-user histories, often stored across billions of records. - Keeping all data in systems such as Bigtable or DynamoDB is prohibitively expensive when the lake contains exabytes. - Object storage latency is increasingly suitable for online workloads: - GCS requests typically take 30–100 ms. - S3 Express One Zone and GCS Rapid Storage can offer single-digit millisecond latency. - Distributed SQL engines introduce seconds of scheduling and planning overhead, making them better suited to analytical throughput than point lookups. ## Narrowing the Search Still Leaves a Problem - A 90-day query over daily listening data could involve approximately 90,000 Parquet files. - Key-based partitioning can reduce candidates substantially; with 1,000 buckets per day, the set may fall to 90 files. - Bloom filters can eliminate files that do not contain the requested user, potentially reducing the set to around 12 files. - The remaining files still require multiple dependent reads: - Fetch the Parquet footer. - Parse row-group metadata. - Scan the key column. - Locate relevant pages through column and page indexes. - Read the corresponding value pages. - These sequential, dependent requests consume both latency and cloud-storage bandwidth. ## The RAP Approach - RAP replaces scanning with direct lookup. - An external index maps each key to: - The relevant Parquet file. - The row numbers containing the key. - Optionally, the number of values for pagination. - Cached metadata maps row numbers to page locations. - The reader then issues precise ranged reads for the required pages. - Reads can be performed in parallel because they no longer depend on a chain of discovery operations. - The approach benefits cloud storage, SSDs, and memory because it removes dependent reads at every tier. ## The External Index - RAP works with existing, unmodified Parquet files. - An index builder reads file footers and page locations, scans key columns, and writes key-to-location mappings. - New pipeline output adds index fragments rather than modifying existing index data. - The index is a multimap, allowing one key to occur in multiple files and partitions. - Index size is typically much smaller than the data: - Terabytes of data may produce gigabytes of index. - Petabytes of data may produce terabytes of index. - Large indexes can be distributed using hash bucketing. - Unlike Parquet Bloom filters and PageIndex structures, the external index is definitive: it identifies exact files and rows instead of merely narrowing a scan. - With unmodified files, RAP may still need to read an entire page—for example, several megabytes to retrieve a small value—so write-time preparation can further reduce read cost. ## Preparing Parquet for Faster Point Reads - Once the reader knows the exact key, row, and columns, file layout can prioritize smaller and fewer final reads rather than in-file discovery. - Relevant optimizations fall into three broad categories: - Concentrating a key’s data. - Reducing bytes per read. - Reducing the number of reads. - Sorting by key places a key’s rows together, minimizing the number of pages required. - Hash bucketing deterministically places each key in one file per partition. - Co-grouping can store one row per key with values in repeated or nested structures, such as an array of timestamp, track URI, and duration fields. - Coarser partitioning can reduce how many files a key spans. RAP therefore provides a way to serve interactive point queries from the same Parquet data used for batch analytics, reducing duplication and avoiding specialized serving copies. For latency-sensitive workloads, indexing should be combined with write-time layout decisions that cluster keys and minimize page reads.