# Indexing the Data Lake for Online Point Queries

[Spotify](https://yomu.fyi/company/spotify) · Spotify Engineering · Jul 27, 2026

**Type:** Problem & solution

## Summary

Online services and AI agents require low-latency point queries over massive datasets that are economically impractical to store entirely in key-value systems like Bigtable or DynamoDB. While cloud object storage offers rapid request latency, traditional distributed query engines like Trino and BigQuery introduce seconds of planning and scheduling overhead along with dependent file reads. Random Access Parquet addresses this limitation by using an external index mapping keys directly to exact Parquet files and row locations. Readers execute O(1) index lookups and issue parallel ranged reads to fetch only the required bytes without scanning footers or metadata. By running directly against existing data lake files, this architecture eliminates separate storage copies and allows shared analytical data to serve interactive online lookups.

## Context

Online services and AI agents require interactive point queries over user data, but keeping exabytes of historical data resident in key-value stores like Bigtable or DynamoDB is cost-prohibitive. Although cloud object storage latency is low, distributed SQL engines such as Trino and BigQuery add seconds of query planning overhead and suffer from round-trip dependent read chains when locating specific rows across thousands of Parquet files.

## Approach / What changed

Random Access Parquet (RAP) builds an external multimap index that maps lookup keys directly to dictionary-encoded file ordinals and row numbers. Given a key, readers perform an O(1) index lookup and issue parallel, precise ranged reads directly against object storage to fetch target pages. RAP supports unmodified Parquet files and can be optimized using key sorting, co-grouping, coarser partitioning, column interleaving, and covering indexes with hoisted values.

## Takeaways

- Distributed SQL engines struggle with interactive point queries because locating row data in Parquet files requires multiple dependent cloud storage round-trips to read footers, row group metadata, and column indexes.
- The external index acts as a compact multimap linking keys to file and row numbers, turning probabilistic page scans into definitive O(1) lookups that enable parallel ranged byte reads.
- Covering indexes can hoist small values or precomputed aggregates directly into index entries during the build phase, enabling predicate pushdown and eliminating storage reads entirely.

**Tags:** [Architecture](https://yomu.fyi/topic/architecture), [Data Pipelines](https://yomu.fyi/topic/data-pipelines), [Performance](https://yomu.fyi/topic/performance), [Scalability](https://yomu.fyi/topic/scalability)

[Read original post](https://engineering.atspotify.com/2026/7/indexing-the-data-lake-for-online-point-queries)