How Converged Indexes Work: Inside Rockset’s Search and Analytics Engine

Traditional databases force engineers to make architectural trade-offs at design time. If you need low-latency point lookups by identifier, you choose a row-oriented database (or B-Tree index). If you need aggregations across billions of records, you choose a columnar database. If you require arbitrary filtering on nested attributes, you turn to an inverted index search engine like Elasticsearch.

Rockset bypasses this dilemma through a concept known as Converged Indexing. Instead of forcing developers to declare secondary indexes in advance or deploy multiple specialized database engines, Rockset indexes every attribute of every ingested document in three distinct representations simultaneously: Row-oriented, Columnar, and Inverted (Search).

All three index models are mapped into a single, unified key-value abstraction powered by RocksDB Cloud.

---

1. The Foundation: RocksDB Cloud as a Sorted Key-Value Store

Rockset relies on RocksDB Cloud (a cloud-native extension of Meta’s LSM-tree-based key-value store) for persistence. A fundamental property of RocksDB is that all keys are stored in lexicographical order across in-memory MemTables and on-disk SST files (Sorted String Tables).

Because keys are strictly sorted:

• Range queries (Seek + sequential iteration) over a common key prefix are exceptionally fast.
• Keys sharing identical prefixes are physically colocated in the same SST blocks or adjacent memory locations, minimizing random disk I/O.

To exploit this property, Rockset does not store raw JSON documents as monolithic binary blobs. Instead, each incoming document is shredded into multiple individual key-value pairs designed to optimize different access patterns.

---

2. Anatomical Breakdown of a Converged Index

Consider an ingested document representing a movie:

{
  "_id": 7,
  "name": "Avengers",
  "year": 2012
}

Instead of inserting this object under key 7, Rockset breaks down the document into three index representations:

flowchart TD
    Doc["Document: {_id: 7, name: 'Avengers', year: 2012}"] --> Row["Row Store: r.doc_id.attr"]
    Doc --> Col["Column Store: c.attr.doc_id"]
    Doc --> Inv["Search/Inverted Store: s.attr.val.doc_id"]
    
    Row --> RocksDB[(RocksDB Cloud Sorted SSTs)]
    Col --> RocksDB
    Inv --> RocksDB

A. Row-Oriented Index (r.*)

• Key Structure: r.<document_id>.<attribute_name>
• Value: <attribute_value>

For document ID 7:

• Key: r.7.name $\rightarrow$ Value: Avengers
• Key: r.7.year $\rightarrow$ Value: 2012

Because keys are sorted lexicographically, all keys starting with r.7. are stored contiguously on disk. To retrieve the entire document, the engine performs a single prefix range scan (r.7.*), reconstructs the original JSON document, and returns it.

B. Column-Oriented Index (c.*)

• Key Structure: c.<attribute_name>.<document_id>
• Value: <attribute_value>

For document ID 7:

• Key: c.name.7 $\rightarrow$ Value: Avengers
• Key: c.year.7 $\rightarrow$ Value: 2012

Here, the attribute name precedes the document ID in the key. Consequently, every document’s year attribute (c.year.1, c.year.2, …, c.year.7) is packed contiguously in memory and on disk. This layout allows analytical queries to scan a single column without reading any other document attributes.

C. Inverted / Search Index (s.*)

• Key Structure: s.<attribute_name>.<attribute_value>.<document_id>
• Value: null (or minimal metadata)

For document ID 7:

• Key: s.name.Avengers.7 $\rightarrow$ Value: null
• Key: s.year.2012.7 $\rightarrow$ Value: null

By embedding the attribute value directly into the key before the document ID, Rockset builds an inverted index. All documents where year == 2012 share the exact prefix s.year.2012.. Filtering queries can directly point to this prefix and rapidly collect all matching document IDs.

---

3. Query Optimization and Execution Paths

When a query arrives at Rockset’s aggregator tier, it is parsed, analyzed, and handed to the cost-based query optimizer. The optimizer determines which index prefix will yield the lowest I/O cost.

graph LR
    Query[Incoming SQL Query] --> Optimizer{Query Optimizer}
    Optimizer -->|Point Lookup by ID| R_Scan["Prefix Scan: r.<doc_id>.*"]
    Optimizer -->|Column Aggregation / Group By| C_Scan["Prefix Scan: c.<attr>.*"]
    Optimizer -->|Selective Filter / Search| S_Scan["Prefix Scan: s.<attr>.<val>.*"]

Scenario 1: Point Lookup

SELECT * FROM movies WHERE _id = 7;

• Target Prefix: r.7.*
• Execution: Performs a prefix scan on r.7.. RocksDB seeks to the first key matching r.7. and scans until the prefix changes. All fields (name, year) are colocated in contiguous memory blocks, reconstructing the full row with minimal disk seek overhead.

Scenario 2: Column Aggregation / Group By

SELECT year, count(*) FROM movies GROUP BY year;

• Target Prefix: c.year.*
• Execution: The engine does not touch the name attribute or load complete rows. It scans the contiguous key range starting at c.year., streaming only the year values and document IDs directly into the aggregation pipeline.

Scenario 3: High-Selectivity Search Query

SELECT count(*) FROM movies WHERE year = 2011;

• Target Prefix: s.year.2011.*
• Execution: Rather than scanning every movie row or every columnar entry for year, the optimizer targets the inverted index prefix s.year.2011.. The engine scans the matching key range and counts the keys directly. Because the search term is part of the key itself, evaluation is near-instantaneous.

---

4. Addressing Common Distributed System Concerns

Decomposing a single document into 6+ key-value pairs introduces two immediate architectural concerns: storage amplification and write amplification.

A. Storage Overhead vs. Operational Convenience

Indexing every field in three distinct layouts causes significant data fan-out. However, this design accepts increased storage footprint in exchange for guaranteed predictable query latencies and zero index administration. Users never experience query regressions due to unindexed columns, eliminating the operational complexity of manual index maintenance.

B. Mitigating Write Amplification via LSM-Trees

In traditional B-Tree based storage engines, updating multiple indexes requires multiple random disk writes.

Because Rockset uses RocksDB (an LSM-tree engine):

1. In-Memory Buffering: Key-value pairs generated from a document are written sequentially to an in-memory MemTable and append-only write-ahead log (WAL).
2. Sequential Flushes: When the MemTable fills, it is flushed to disk as an immutable, sequential SST file.
3. Sequential Writes: Even though one document fans out into six or more key-value pairs, they are written to disk in a consolidated, sequential batch rather than scattered random writes, preventing disk thrashing.

---

Summary of Key Representations

Index Type	Key Format	Value	Best Suited For
Row Index	r.<doc_id>.<attr_name>	<attr_val>	SELECT * WHERE _id = X (Full document retrieval)
Column Index	c.<attr_name>.<doc_id>	<attr_val>	SELECT avg(price), sum(qty) (Aggregations & Projections)
Search Index	s.<attr_name>.<attr_val>.<doc_id>	null	WHERE status = 'FAILED' (Point filters & Search)

By leveraging the native ordering of LSM-tree key-value stores, Converged Indexing enables point lookups, analytical aggregations, and inverted search predicates to run efficiently side-by-side within a single database engine.