Вторичные индексы

Индексы — вспомогательные структуры в базах данных, позволяющие находить подходящие под определенный критерий данные без необходимости их полного перебора, а также получать отсортированные выборки без выполнения фактической сортировки, требующей обработки полного набора всех сортируемых данных.

Данные в строковых таблицах YDB всегда проиндексированы по первичному ключу. Это означает, что получение любой записи из строковой таблицы с заданными значениями полей, составляющих первичный ключ, всегда будет занимать минимальное фиксированное время, вне зависимости от общего количества записей в строковой таблице. Также наличие индекса по первичному ключу позволяет получить любой последовательный диапазон записей по возрастанию или убыванию первичного ключа. Время исполнения такой операции будет зависеть только от количества получаемых записей, но не зависеть от общего количества записей в строковой таблице.

Для того, чтобы воспользоваться аналогичными возможностями для любых полей или комбинаций полей строковой таблицы, по ним могут быть построены дополнительные индексы, называемые вторичными индексами.

В транзакционных системах использование индексов позволяет сократить или исключить деградацию производительности и повышение стоимости выполнения запросов при росте объема хранимых данных.

В данной статье описаны основные операции по работе со вторичными индексами и даны ссылки на подробные материалы по каждой операции. Информация о разных типах вторичных индексов и особенностях их устройства находится в статье Вторичные индексы раздела "Концепции".

Создание вторичных индексов

Вторичный индекс является объектом схемы данных и может быть определен при создании таблицы командой YQL CREATE TABLE, или добавлен к ней позднее командой YQL ALTER TABLE.

Команда создания индекса table index add поддерживается в YDB CLI.

Так как индекс содержит собственные данные, являющиеся производными от данных в строковой таблице, то при создании индекса на существующей таблице с данными будет выполнена операция начального построения индекса, которая может занимать продолжительное время. Данная операция выполняется в фоновом режиме, не блокирует работу с таблицей, но до окончания построения новым индексом воспользоваться будет невозможно.

Использование индекса возможно только в порядке включенных в него полей. Если в индексе два поля a и b, то такой индекс может быть эффективно использован для запросов вида:

• WHERE a = $var1 AND b = $var2;
• WHERE a = $var1;
• WHERE a > $var1, а также другие операторы сравнения;
• WHERE a = $var1 AND b > $var2, а также любые другие операторы сравнения, но первое поле должно проверяться на равенство.

При этом, такой индекс не может быть применен для следующих запросов:

• WHERE b = $var1;
• WHERE a > $var1 AND b > $var2, точнее эта запись будет равнозначна WHERE a > $var1 с точки зрения применения индекса;
• WHERE b > $var1.

С учетом описанной выше особенности, бесполезно пытаться заранее индексировать все возможные комбинации колонок в таблице в расчете на быстрое исполнение любых запросов. Индекс - это всегда компромисс между скоростью поиска и записи, а также занимаемым данными местом в хранилище. Индексы создаются под конкретные выборки и условия поиска, которые будут делаться приложением в базе данных.

Применение вторичных индексов при выборке данных

Для обращения к строковой таблице по вторичному индексу его имя должно быть явно указано в секции VIEW после имени таблицы, как описано в статье про команду SELECT YQL. Например, для получения из строковой таблицы Заказов (orders) выборки заказов клиента с заданным ID (id_customer) запрос будет выглядеть следующим образом:

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

, где idx_customer — имя вторичного индекса на строковой таблице orders, первым в котором указано поле id_customer.

Без указания секции VIEW для выполнения такого запроса будет полностью просканирована строковая таблица orders.

В транзакционных приложениях подобные информационные запросы выполняются с использованием поcтраничного вывода данных, что исключает рост стоимости и времени исполнения при увеличении количества записей, подходящих под условия фильтрации. Описанный на примере первичного ключа подход к написанию постраничных запросов применим также и к колонкам, включенным во вторичный индекс.

Также реализована экспериментальная возможность выбора вторичного индекса для использования в запросе в автоматическом режиме. Алгоритм выбора на данный момент является rule-based и использует только текст запроса для автоматического выбора вторичного индекса.

Автоматическое использование индексов при выборке

Явное указание секции VIEW имеет приоритет над решением оптимизатора о использовании вторичных индексов. То есть запрос

SELECT * FROM `Table` VIEW Index

гарантированно будет производить выборку с использованием индекса Index.

Для явного указания чтения с использованием первичного ключа следует использовать следующую конструкцию:

SELECT * FROM `Table` VIEW PRIMARY KEY

Критерии выбора вторичного индекса

Выбор индекса используемого для чтения происходит во время оптимизации запроса при определении диапазонов строк, которые необходимо прочитать (predicate pushdown). Индексы, как и основная таблица представляют из себя набор строк упорядоченных по набору ключевых колонок.

Выбор между чтениями с использованием индекса и c использованием первичного ключа происходит на основе следующих метрик:

1. Необходимость дополнительного чтения из основной таблицы. Если в индексе присутствуют все нужные для запроса колонки, то дополнительные чтения не требуются.
2. Длина точечного префикса предиката для ключа соответствующей таблицы. То есть, предикат ограничивает некоторый набор колонок являющихся первыми компонентами ключа точечными условиями: =, IN, IS NULL. Здесь приоритет отдается индексам, для которых зафиксированы все индексируемые колонки или основной таблице если точечным является первичный ключ целиком.
3. Количество использованных колонок в границах диапазона для чтения. В следующем запросе к таблице Table с первичным ключом (Key1, Key2, Key3)

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

чтение будет производиться в диапазоне (($param4, $param5), ($param1, $param2, $param3)) и таким образом количество использованных колонок будет равно 3. Аналогично 2 здесь отдается предпочтение индексам для которых использованы все индексируемые колонки.

Способы чтения ранжируются между собой в соответствии с критерием 2, при равенстве с критерием 3 и дополнительно учитывается критерий 1.

Примеры автоматического выбора индексов

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. Выражение для диапазона — (($p1; $p2), ($p1)]. Длина точечного префикса для Index12 — 1, для остальных индексов — 0.

SELECT * FROM Table WHERE Key = $p1 and SubKey1 = $p2 And SubKey2 = $p2 — индекс не будет использоваться. При выборе скана основной таблицы используется все 3 колонки [Key, Fk1, Fk2], длина точечного префикса 3.`

SELECT * FROM Table WHERE Key = $p1 and SubKey2 = $p2 — вторичные индексы не будут использоваться. При выборе любого вторичного индекса используется 1 колонка, точечный префикс также не более 1 при любом варианте выбора индекса.

SELECT * FROM Table WHERE Key >= $p1 and SubKey1 = $p2 And SubKey2 = $p3 — должен быть выбран Index12, так как при его выборе в получающемся диапазоне [[Fk1; Fk2; Key], [Fk1; Fk2]) получится длина точечного префикса — 2, и будут использоваться 3 колонки.

SELECT * FROM Table WHERE Key = 2 and SubKey2 = 3 — вторичные индексы не должны быть использованы. В случае чтения по PK и при использовании любого из вторичных индексов точечный префикс состоит не более чем из одной колонки. Также используется не более одной колонки.

SELECT * FROM Table WHERE SubKey1 > 2 — Должен быть выбран Index12. Только при использовании Index12 будет нетривиальный диапазон для чтения.

SELECT * FROM Table WHERE SubKey2 = 2 — Может быть выбран любой из Index21 и Index212. При использовании вышеупомянутых индексов длина точечного префикса будет 1. Количество использованных колонок также максимизируется при выборе Index21 и Index212

SELECT Value2 FROM Table WHERE SubKey2 = 2 — Должен быть выбран Index212. При использовании Index21 и Index212 длина точечного префикса будет 1, но при использовании Index212 не нужно чтение основной таблицы.

SELECT * FROM Table WHERE SubKey2 > 2 — Будут использованы Index21 или Index212, так как читаемый диапазон нетривиален только при их использовании.

SELECT * FROM Table WHERE SubKey1 = 2 — Будет использован Index12, так как при его использовании длина точечного префикса будет 1, а в остальных случаях 0.

Проверка стоимости запроса

Любой запрос в транзакционном приложении необходимо проверять с точки зрения того, сколько он выполнил операций ввода-вывода в базе данных и сколько CPU было потрачено на его исполнение. Также необходимо убедиться, что эти цифры не растут бесконечно с ростом объема базы данных. В YDB после выполнения каждого запроса возвращается статистика, содержащая необходимую для анализа информацию.

При использовании YDB CLI вывод статистики после исполнения команды yql включается опцией --stats. Все YDB SDK также содержат структуры, содержащие статистику после исполнения запросов. При исполнении запросов в UI рядом с закладкой результатов также присутствует закладка со статистикой.

Обновление данных с использованием вторичного индекса

Команды YQL изменения записей (UPDATE, UPSERT, REPLACE) не позволяют указать на использование вторичного индекса для поиска данных, поэтому попытка выполнить UPDATE ... WHERE indexed_field = $value приведет к полному сканированию строковой таблицы. Чтобы избежать этого, можно предварительно выполнить SELECT по индексу с получением значения первичного ключа, а затем выполнить UPDATE по первичному ключу. Также можно воспользоваться инструкцией UPDATE ON.

Чтобы обновить данные в строковой таблице table1, выполните запрос:

$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

Удаление данных с использованием вторичного индекса

Для удаления данных по вторичному индексу используется SELECT c предикатом по вторичному индексу, а затем вызывается инструкция DELETE ON.

Чтобы удалить все данные о сериалах с нулевым количеством просмотров в строковой таблице series, выполните запрос:

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

Атомарная замена вторичного индекса

Существующий вторичный индекс можно заменить атомарно. Это может быть полезно, например, для замены индекса на покрывающий. Для работающих приложений эта операция прозрачна — в момент замены индекса произойдет инвалидация скомпилированных запросов.

Атомарно заменить существующий индекс можно с помощью команды YDB CLI ydb table index rename с параметром --replace.

Производительность записи в строковой таблицы со вторичными индексами

Для работы вторичных индексов необходимы дополнительные структуры данных. Поддержка этих структур приводит к повышению стоимости операций изменения данных в строковых таблицах.

При синхронном обновлении индексов транзакция подтверждается только после записи всех необходимых данных, как в строковой таблице, так и в синхронных индексах. Это приводит как к увеличению времени исполнения, так и к необходимости применения распределенных транзакций даже при добавлении или изменении записей в единственной партиции.

Асинхронно обновляемые индексы сохраняют возможность применения одношардовых транзакций, однако гарантируют только консистентность "в конечном счете", и все равно создают нагрузку на базу данных.