How Rockset’s Converged Index Powers Real-Time Analytics

Rockset makes it easier to serve modern data applications at scale and at speed. From personalization and gaming to logistics or IoT, Rockset automatically and continuously ingests and indexes structured and semi-structured data at scale for a solution that supports latency-sensitive queries for real-time analytics.

How do we do that? Built on open-source RocksDB, a high-performance, distributed storage engine, the Converged Index™, is an important component of our real-time database. In this blog post, we explain how our Converged Index works and how it lets us index data efficiently as well as run complex queries at millisecond latency on massive data sets. You can also view Igor’s video, where he discusses how the Converged Index works:

Embedded content: https://www.youtube.com/watch?v=bAiky7w6A3E

Converged Index = Row Index + Columnar Index + Search Index

At the end of the day, our Converged Index indexes all the fields in all the documents that you store in Rockset in a single system that combines a row index, a columnar index and a search index.

The row index refers to storing data in row orientation, which is fairly standard in databases. It optimizes for row lookups and is how Postgres and MySQL are organized. We’ll spend most of this post describing how the columnar index and search index complement the row index by accelerating complex analytics.

The Columnar Index

In the columnar index, each column is stored separately. Columnar storage is often used in analytical databases and data warehouses like Snowflake and Amazon Redshift. It delivers two key advantages:

• There is great potential for data compression because data that looks similar is stored closer together.
• When executing a query, Rockset can scan and operate on large batches of columnar data in order to achieve very efficient vectorized processing. The result: remarkably fast queries.

Figure 1: Columnar storage of documents with three fields

The simple example shown in Figure 1 is a representation of how columnar storage is achieved in Rockset. On the left you see two documents (doc 0 and doc 1) that each have the same three fields: “name,” “interests”, and “last_active”. On the right, you see how the columnar storage of those documents looks. The values for the "name" column are stored close together as a list of document IDs (0, 1) plus the value of that column for that document ID (“Igor”, “Dhruba”). We do the same thing for the "interests" and the "last_active" columns.

Note that for the “interests” column, which can hold multiple values, the data is in an array. Here we store the document ID plus the array index. So Igor is interested in databases (0.0) and snowboarding (0.1), while Dhruba is interested in cars (1.0) and databases (1.1).

The Search Index

In the search index, also known as an inverted index and used in search engines like Elasticsearch, Rockset stores the map between a value and the list of document IDs that contain that value. For queries, this means quick retrieval of a list of document IDs that match a particular predicate.

Figure 2: Search index of documents with three fields

Although still separated by column, now instead of a document ID mapping to a value, a value is mapped to a document ID. The value “name” = “Dhruba” is mapped to document ID 1, while the value “name” = “Igor” is mapped to document ID 0. The same is done for the “interests” and “last_active” values.

How the Converged Index Works

The Rockset Converged Index is the combination of a row index, a columnar index and a search index built on top of a key-value store abstraction. Rockset uses RocksDB, but any key-value store will do. Each document stored in the Converged Index maps to many key-value pairs in the key-value store.

Figure 3: Converged Index maps to key-value pairs

The example shown in Figure 3 uses two simplified documents that have only one field, “name.” On the right side, you can see all the key-value pairs that Rockset would generate and hold in a store for those two documents. Rockset generates many key-value pairs from each document because it automatically stores the data in multiple types of indexes.

The first two key-value pairs are from the Row Index. Take note of how the key is constructed. We use “R” to denote the RowStore in the key and use the document ID (0, 1) followed by the column (name). This approach lets us store all values for a particular document close together, as you would in any rowstore. The row index gives us very low point lookup latencies.

The next two key-value pairs are from the Column Index, where the key components are flipped. We use “C” to denote the ColumnStore, then use the column (name) followed by the document ID (0, 1). We store all the values for a particular column close together, which delivers fast scan-times as well as better compression.

And finally, for the search index, we actually put the value into the key and store the document ID as a suffix. We use “S” to denote the Search Index, followed by the column (name), the value (Dhruba, Igor), and lastly the document ID (0, 1). So, for example, if you're looking for all documents where name = Dhruba, you would be able to quickly find all keys in your key-value stores with the prefix S.name.Dhruba.

Final Note

Our Converged Index delivers both fast analytical queries and fast search queries in the same system. Rockset automatically builds the multiple indexes described above on all data that is ingested, so users can get strong performance on different types of queries without any performance tuning. We have also built a query optimizer that automatically chooses the optimal index for any given query.

Learn more about Rockset’s Converged Index and architecture in our product white paper. Or try Rockset on your queries and your data by creating an account here.