Data indexes

Important

This feature is experimental. The API and performance characteristics are subject to change.

This guide covers data indexes: what they are, how to create and use them, and how they can improve query performance.

A data index maps key values in one or more key columns to the row sets that contain them. Every data index is backed by a table that stores the row sets in a column called dh_row_set. Many table operations use a data index if one is present. Data indexes help in two ways:

  • They let filters, exact and relational joins, as-of and range joins, sorts, and aggregations look up each key's rows in the index instead of reading the key columns of every row.
  • They let several operations share the work of grouping a table's rows by key. Without an index, each join or aggregation on a table repeats that grouping. With a data index, those operations can start from the index instead, which can make them faster and use less memory.

Data indexes work on ticking data too. On a refreshing table, the index updates as rows tick, so operations that use it stay current.

An index can also make a query slower. See Performance for when an index helps.

Create a data index

Create a data index from a source table and one or more key columns with data_index:

Warning

A data index you create with data_index is weakly reachable. Assign the index to a variable to ensure it does not get garbage collected.

Important

Creating a data index doesn't compute it. Deephaven computes the index the first time one of these happens:

  • A table operation that can use the index looks at it. Joins and sorts compute the index to check its size, even when they then don't use it.
  • You access the index's table property.
  • You write the table to Parquet with that index.

where never computes an index you create with data_index. See Filter.

The first operation that computes an index pays for it, even if it then reads the table directly. This is an important detail when you measure performance.

View an index's contents

To see an index's contents, retrieve its backing table with the table property:

The source table in the above example doesn't create a very interesting data index. Each key value in X only appears once. The following example better illustrates a data index:

When looking at source, we can see that the value 100 in column X appears in rows 0 and 5. The value 101 appears in rows 1 and 6, 102 in rows 2 and 7, and so on. Each value in dh_row_set holds the rows where that row's key value appears. Let's look at an example for more than one key column.

There are only four unique keys in X and Y together. The resultant column dh_row_set shows the row sets in which each unique key appears.

In the previous examples, the key values repeat in a fixed pattern, so the row sets do too: key 100 appears in every fifth row. Key values in real data rarely follow a pattern like this, so don't assume that the rows for a key are evenly spaced or next to each other. In the following example, each row gets a random key:

Each row set in source_index now holds an irregular set of row keys, which change every time the example runs. Because the index is backed by an ordinary table, you can query it like any other table. In this example, result filters it to show only the row sets for keys 100 and 102.

Retrieve and verify a data index

You can check for or retrieve a data index with two functions:

  • has_data_index: Returns a boolean indicating whether a data index exists for the table and the given key column(s).
  • data_index: When you pass create_if_absent=False, returns the existing data index, or None if no usable index exists. It doesn't create an index.

The following example creates a data index on Key1 and Key3, then uses has_data_index to check which key column combinations have an index. Finally, it tries to retrieve an index on Key2 without creating one. No such index exists, so the result is None.

Usage in queries

You don't pass a data index to a table operation. If a table has a data index that an operation can use, the engine finds it and uses it, except in the cases listed under Performance, where reading the table directly is faster. The following table operations can use data indexes:

Note

Whether an operation can use a DataIndex depends on the index's key columns:

  • Joins that can use an index, aggregations, and select_distinct use an index only when its key columns exactly match the operation's key columns. For as-of joins and range_join, the index must match the join's exact-match columns. For example, an aggregation by column X does not use an index on columns X and Y.
  • where can use an index whose key columns include the filtered column.
  • where_in and where_not_in can use an index on all or some of their key columns.
  • Sorts can use an index on all of the sort columns, or a single-column index on the first sort column.

The sections below give details for filters, joins, sorts, and aggregations.

The code blocks in the following subsections use these tables:

Filter

The engine uses single- and multi-column indexes to speed up most filter types, not only exact matches, through the predicate pushdown framework. Two rules decide whether where uses an index:

  • The index's key columns must include the filtered column. For example, an index on Key1 and Key2 can speed up a filter on Key1.
  • On average, each key value must appear in many of the rows being filtered. Predicate pushdown gives the exact threshold.

How where uses a data index depends on the kind of index:

  • A table-level data index covers the whole table. You create one with data_index, and Deephaven registers one when it reads saved indexes from Parquet. where never computes a table-level index. It uses one only after one of these computes it:
  • A file-level data index is one stored on disk with the data, such as an index written with Parquet. Nothing has to compute it first. The engine uses it to filter that file without loading the entire index into memory.

Note

Support for using data indexes with most filter types, beyond exact matches, came with the predicate pushdown framework. File-level data indexes support this starting in Deephaven 0.40.0, and table-level data indexes starting in Deephaven 41.0.

The following filters can use the index created at the top of the code block. The example accesses the index's table property before filtering:

The results are the same with or without the index. The index changes only how the engine finds the matching rows.

The following example can only use the index for the first filter:

When you filter one table by another with where_in or where_not_in, the engine looks for a data index on the table being filtered. It prefers an index on all of the key columns, but it also uses an index on some of them. Unlike where, these methods compute the index if it hasn't been computed yet. Like where, they use the index only when, on average, each key value appears in many of the rows being filtered. Both filters in the following example can use source_k1_k2_index:

Join

Each method for exact and relational joins and as-of and range joins can use a left table index, a right table index, both, or neither:

MethodCan use indexes?Can use left table index?Can use right table index?
exact_join✅✅🚫
natural_join✅✅🚫
aj✅✅✅
raj✅✅✅
join🚫🚫🚫
left_outer_join🚫🚫🚫
full_outer_join✅✅✅
multi_join🚫🚫🚫
range_join✅✅🚫

full_outer_join starts with a left_outer_join, which can't use indexes. It uses indexes only through the two other operations it is built from:

  • A select_distinct on the left table.
  • A natural_join with the right table as its left table and those distinct keys as its right table.

The comparison table marks natural_join as unable to use a right table index because it never reads the right table's rows through one. Natural join describes the one case where it looks at a right table index.

Natural join

Without data indexes, a natural_join reads the key values of every row in the left table and hashes them to match each row with the right table. If the left table has a data index on the join keys, the engine can read the index instead. The index has one row per unique key, so reading it can be faster than scanning every row of the left table.

Whether the engine uses each index depends on whether the tables are refreshing, on the sizes of the tables and the index, and on the join's type, a NaturalJoinType:

  • Left table index: If either table is refreshing, the engine uses it. If both tables are static and type is ERROR_ON_DUPLICATE (the default) or EXACTLY_ONE_MATCH, the engine uses it only if the index has no more rows than the right table.
  • Right table index: With the default type or EXACTLY_ONE_MATCH, the engine never uses it. With FIRST_MATCH or LAST_MATCH, the engine reads it only to size its hash table and to decide whether to build from the left table's index. It still reads the right table's rows directly.

The following example creates an index on Key1 and Key2 for both source and source_right, then joins the tables with natural_join. The engine decides whether to use each index as follows:

  • The join uses the default type, so the engine ignores the right table's index, source_right_k1_k2_index.
  • The left table's index, source_k1_k2_index, matches the join keys, so the engine checks its size. Checking the size computes the index if nothing has computed it yet.
  • source_k1_k2_index has 517 rows and source_right has 400. Both tables are static, so the join reads source directly instead of using the index.

As-of join

Data indexes can speed up the exact match in an aj or an raj, because the engine no longer has to group each table's rows by key. The following example can use both indexes, because their key column matches the join's exact-match column:

Sort

Sort operations can use both full and partial indexes.

  • A full index matches all sort columns, in any order.
  • A partial index is a single-column index on the first sort column.

When a full index is present, the engine only needs to sort the index rows. Two limits apply:

  • The engine skips a full index that has at least half as many rows as the table being sorted, because sorting the table directly is faster. It then sorts without any index, even if a single-column index on the first sort column exists.
  • On a refreshing table, the index speeds up only the initial sort. The engine sorts later updates without it.

When a sort operation uses a partial index, the engine sorts the first column using the index and sorts the remaining columns without one. The engine doesn't use a multi-column index that covers only some of the sort columns.

The following sort_descending operation uses the index because the index's key columns match the sort columns, even though the operation lists them in a different order:

The following sort operation uses the index when sorting the first key column only:

The following sort operation does not use any index, because no index on source covers Key3, the first sort column:

Aggregate

Without a data index, an aggregation must first group rows by their key values and then calculate on each group. The index lets the engine skip the grouping step and start calculating right away. The following aggregation uses the index because the index's key columns match the aggregation's key columns:

Data index inheritance

A table derived from an indexed table inherits its data indexes unless the operation changes the row set or any indexed data.

A table you subscribe to from another worker does not inherit that worker's indexes. To still benefit from an index, filter the table on the worker that publishes it, then subscribe to the filtered result.

Persist data indexes with Parquet

Deephaven can save data indexes along with your data when you write a table to Parquet files. By default, write saves every index on the table. Export to Parquet lists the defaults of the other write functions. To save only some indexes, pass their key columns in the index_columns argument. If you name an index that doesn't exist yet, Deephaven creates a temporary one just for the write.

When you load static data from a Parquet file, Deephaven also finds any saved indexes and registers them on the table. It reads an index from disk only when an operation uses it.

The following example writes a table to Parquet twice and reads it back after each write:

  • The first write names the index key columns. source has no indexes yet, so Deephaven creates them temporarily for the write.
  • The second write names no index columns, so Deephaven saves every index that exists on source.

Partitioning columns as data indexes

A partitioning column is a column whose values come from the directory layout of a partitioned dataset, such as the Date=2024-01-01 directories in a key-value partitioned Parquet directory. Deephaven automatically creates a data index for each partitioning column. The engine first uses partitioning column values to choose which files to read. After that, it uses the partitioning column indexes like any other data index in query operations.

Warning

Do not create data indexes on partitioning or grouping columns. Deephaven automatically manages indexes for these columns internally. Adding a manual data index can interfere with this process and cause unexpected behavior. For example, passing a partitioning column by itself as an index in index_columns when you write a key-value partitioned Parquet directory raises an error. Calling data_index on a partitioning column returns the index Deephaven already created.

Performance

Data indexes improve performance when used in the right context. If used in the wrong context, data indexes can make performance worse. Use the following guidelines to decide whether an index helps:

  • A data index is more likely to help performance if the rows that share a key value are stored near each other in memory. This avoids index fragmentation and poor data access patterns.
  • Reusing a data index multiple times is necessary to overcome the cost of initially computing the index.
  • Generally speaking, the higher the key cardinality, the better the performance improvement. Key cardinality is the number of distinct key values.

Even when a usable index exists, the engine skips it in these cases:

  • where, where_in, and where_not_in use an index only when, on average, each key value appears in many of the rows being filtered. See Predicate pushdown for details.
  • A sort skips an index on all of the sort columns when the index has at least half as many rows as the table.
  • A natural_join of two static tables with the default type or EXACTLY_ONE_MATCH uses the left table's index only if the index has no more rows than the right table.

Benchmark scripts

If you're interested in how data indexes affect query performance, the scripts below measure each operation with and without indexes. You'll notice that performance improves in some cases and gets worse in others.

This first script sets up the tests:

Here's a follow-up script that runs each test on low- and high-cardinality data, with and without data indexes. The low-cardinality case has 700 unique I and J key pairs (100 × 7), and the high-cardinality case has 99,700 (100 × 997):

The benchmark turns off memoization for the whole server. To turn it back on when you finish, run jpy.get_type("io.deephaven.engine.table.impl.QueryTable").setMemoizeResults(True).

It can also be helpful to plot the results. The following Deephaven Express bar chart groups the four timings for each operation:

For each operation, compare its time with and without indexes at the same cardinality, then check the differences against the guidelines at the start of Performance.