Secondary indexes

Indexes are auxiliary structures within databases that help find data by certain criteria without having to search an entire database and retrieve sorted samples without actually sorting, which would require processing the entire dataset.

Data in a YDB table is always sorted by the primary key. That means that retrieving any entry from the table with specified field values comprising the primary key always takes the minimum fixed time, regardless of the total number of table entries. Indexing by the primary key makes it possible to retrieve any consecutive range of entries in ascending or descending order of the primary key. Execution time for this operation depends only on the number of retrieved entries rather than on the total number of table records.

To use a similar feature with any field or combination of fields, additional indexes called secondary indexes can be created for them.

In transactional systems, indexes are used to limit or avoid performance degradation and increase of query cost as your data grows.

This article describes the main operations with secondary indexes and gives references to detailed information on each operation. For more information about various types of secondary indexes and their specifics, see Secondary indexes in the Concepts section.

Creating secondary indexes

A secondary index is a data schema object that can be defined when creating a table with the CREATE TABLE YQL command or added to it later with the ALTER TABLE YQL command.

The table index add command is supported in the YDB CLI.

Since an index contains its own data derived from table data, when creating an index on an existing table with data, an operation is performed to initially build an index. This may take a long time. This operation is executed in the background and you can keep working with the table while it's in progress. However, you can't use the new index until its build is completed.

An index can only be used in the order of the fields included in it. If an index contains two fields, such as a and b, you can effectively use it for queries such as:

• WHERE a = $var1 AND b = $var2.
• WHERE a = $var1.
• WHERE a > $var1 and other comparison operators.
• WHERE a = $var1 AND b > $var2 and any other comparison operators in which the first field must be checked for equality.

This index can't be used in the following queries:

• WHERE b = $var1.
• WHERE a > $var1 AND b > $var2, which is equivalent to WHERE a > $var1 in terms of applying the index.
• WHERE b > $var1.

To effectively limit the result of a query using the LIMIT command, you must use one-way sorting in the ORDER BY command:

• WHERE a = $var1 AND b > $var2 ORDER BY a, b DESC LIMIT 1, all index rows that match the filter conditions will be read;
• WHERE a = $var1 AND b > $var2 ORDER BY a DESC, b DESC LIMIT 1, only one row will be read.

Considering the above, there's no use in pre-indexing all possible combinations of table columns to speed up the execution of any query. An index is always a compromise between the lookup and write speed and the storage space occupied by the data. Indexes are created for specific queries and search criteria made by an app in the database.

Using secondary indexes when selecting data

For a table to be accessed by a secondary index, its name must be explicitly specified in the VIEW section after the table name as described in the article about the YQL SELECT statement. For example, a query to retrieve orders from the orders table by the specified customer ID (id_customer) looks like this:

DECLARE $customer_id AS Uint64;

SELECT *
FROM   orders VIEW idx_customer AS o
WHERE  o.id_customer = $customer_id

Where idx_customer is the name of the secondary index on the orders table with the id_customer field specified first.

If no VIEW section is specified, making a query like this results in a full scan of the orders table.

In transactional applications, such information queries are executed with paginated data output. This eliminates an increase in the cost and time of query execution if the number of entries that meet the filtering conditions grows. The described approach to writing paginated queries using the primary key can also be applied to columns that are part of a secondary index.

An experimental capability to automatically select a secondary index for use in a query is also available. The selection algorithm is currently rule-based and uses only the query text to automatically select a secondary index.

Automatic use of indexes when selecting data

Explicitly specifying the VIEW section takes priority over the optimizer's decision to use secondary indexes. That is, the query

SELECT * FROM `Table` VIEW Index

is guaranteed to perform selection using the Index index.

To explicitly specify reading using the primary key, use the following construct:

SELECT * FROM `Table` VIEW PRIMARY KEY

Criteria for selecting a secondary index

The index used for reading is selected during query optimization when determining the row ranges that need to be read (predicate pushdown). Indexes, like the main table, are a set of rows ordered by a set of key columns.

Selection between reading using an index and reading using the primary key is based on the following metrics:

1. Need for additional reads from the main table. If the index contains all columns required for the query, no additional reads are needed.
2. Length of the point prefix of the predicate for the corresponding table's key. That is, the predicate constrains a set of columns that are the first components of the key with point conditions: =, IN, IS NULL. Priority is given to indexes for which all indexed columns are fixed, or to the main table if the entire primary key is point-fixed.
3. Number of columns used in the read range bounds. In the following query to the Table table with primary key (Key1, Key2, Key3)

SELECT * FROM `Table` WHERE (Key1, Key2, Key3) < ($param1, $param2, $param3) AND (Key1, Key2) > ($param4, $param5)

reading will be performed in the range (($param4, $param5), ($param1, $param2, $param3)), and thus the number of used columns will be 3. Similarly, preference is given to indexes for which all indexed columns are used.

Read methods are ranked against each other according to criterion 2, with ties broken by criterion 3, and criterion 1 is additionally taken into account.

Examples of automatic index selection

CREATE TABLE `Table` (
     Key Int32,
     SubKey1 Int32,
     SubKey2 String,
     Value1 String,
     Value2 String,
     PRIMARY KEY (Key, SubKey1, SubKey2),
     INDEX Index12 GLOBAL ON (SubKey1, SubKey2),
     INDEX Index21 GLOBAL ON (SubKey2, Value1),
     INDEX Index212 GLOBAL ON (SubKey2) COVER (Value2)
);

SELECT * FROM Table WHERE SubKey1 = $p1 and SubKey2 > $p2 — Index12 will be used. The range expression is (($p1; $p2), ($p1)]. The point prefix length for Index12 is 1; for other indexes, it is 0.

SELECT * FROM Table WHERE Key = $p1 and SubKey1 = $p2 And SubKey2 = $p2 — no index will be used. When selecting a scan of the main table, all 3 columns are used: [Key, Fk1, Fk2], and the point prefix length is 3.

SELECT * FROM Table WHERE Key = $p1 and SubKey2 = $p2 — secondary indexes will not be used. When selecting any secondary index, 1 column is used, and the point prefix is also at most 1 for any index choice.

SELECT * FROM Table WHERE Key >= $p1 and SubKey1 = $p2 And SubKey2 = $p3 — Index12 should be selected, because when it is selected, the resulting range [[Fk1; Fk2; Key], [Fk1; Fk2]) yields a point prefix length of 2, and 3 columns are used.

SELECT * FROM Table WHERE Key = 2 and SubKey2 = 3 — secondary indexes should not be used. When reading by PK or using any of the secondary indexes, the point prefix consists of at most one column. Also, at most one column is used.

SELECT * FROM Table WHERE SubKey1 > 2 — Index12 should be selected. Only when using Index12 will the read range be non-trivial.

SELECT * FROM Table WHERE SubKey2 = 2 — either Index21 or Index212 may be selected. When using the indexes mentioned above, the point prefix length will be 1. The number of used columns is also maximized when selecting Index21 and Index212.

SELECT Value2 FROM Table WHERE SubKey2 = 2 — Index212 should be selected. When using Index21 and Index212, the point prefix length will be 1, but when using Index212, no read from the main table is required.

SELECT * FROM Table WHERE SubKey2 > 2 — Index21 or Index212 will be used, because the read range is non-trivial only when using them.

SELECT * FROM Table WHERE SubKey1 = 2 — Index12 will be used, because when using it, the point prefix length will be 1, whereas in other cases it is 0.

Checking the cost of queries

Any query made in a transactional application should be checked in terms of the number of I/O operations it performed in the database and how much CPU was used to run it. You should also make sure these indicators don't continuously grow as the database volume grows. YDB returns statistics required for the analysis after running each query.

If you use the YDB CLI, select the --stats option to enable printing statistics after executing the yql command. All YDB SDKs also contain structures with statistics returned after running a query. If you make a query in the UI, you'll see a tab with statistics next to the results tab.

Updating data using a secondary index

The UPDATE, UPSERT, and REPLACE YQL record modification statements don't permit specifying a secondary index to perform a search for data, so an attempt to make an UPDATE ... WHERE indexed_field = $value will result in a full scan of the table. To avoid this, you can first run SELECT by index to get the primary key value and then run UPDATE by the primary key. You can also use UPDATE ON.

To update data in the table1 table, run the query:

$to_update = (
    SELECT pk_field, $f1 AS field1, $f2 AS field2, ...
    FROM   table1 VIEW idx_field3
    WHERE  field3 = $f3)

UPDATE table1 ON SELECT * FROM $to_update

Deleting data using a secondary index

To delete data by secondary index, use SELECT with a predicate by secondary index and then call DELETE ON.

To delete all data about series with zero views from the series table, run the query:

DELETE FROM series ON
SELECT series_id
FROM series VIEW views_index
WHERE views = 0;

Atomic replacement of a secondary index

You can atomically replace a secondary index. This can be useful if you want your index to become covering. This operation is totally transparent for your running applications: when you replace the index, the compiled queries are invalidated.

To replace an existing index atomically, use the YDB CLI command ydb table index rename with the --replace parameter.

Performance of data writes to tables with secondary indexes

You need additional data structures to enable secondary indexes. Support for these structures makes table data update operations more costly.

During synchronous index updates, a transaction is only committed after all the necessary data is written in both a table and synchronous indexes. As a result, it takes longer to execute it and makes it necessary to use distributed transactions even if adding or updating entries in a single partition.

Indexes that are updated asynchronously let you use single-shard transactions. However, they only guarantee eventual consistency and still put a load on the database.