Indexing the Data Lake for Online Point Queries

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.

Related reading

• Spotify · Jun 10, 2026

  Encoding Your Domain Expert: The Context Layer Behind Spotify's Data Assistant

  Spotify developed an AI data assistant, Vedder, to scale access to over 70,000 internal datasets without overwhelming domain experts. Because raw warehouse schemas omit critical semantic nuances and overwhelm LLM context windows, engineers implemented a domain-owned context layer organized into clusters. Each cluster contains profiled datasets, expert-curated business documentation, and vetted question-and-SQL pairs that guide a ReAct-based agent. Automated query history extraction proved insufficient on its own, as domain curators accepted only 12.5% of inferred query pairs due to noise. Deployed across Slack, IDEs, and a dedicated web interface, the system maintains reliability through continuous cluster health monitoring that flags schema drift and degraded examples.

  Spotify Engineering

• Spotify · Jun 3, 2026

  Coding Is No Longer the Constraint: Scaling Developer Experience to Teams and Agents at Spotify