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

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

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

Вторичные индексы поддержаны также для реплицированных таблиц.

Использование

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

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

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

Пример создания таблиц и вторичного индекса, связывающего их:

yt create table //path/to/table --attributes '{dynamic=true; schema=[{name=key; type=int64; sort_order=ascending}; {name=value; type=string}]}'
yt create table //path/to/index_table --attributes '{dynamic=true; schema=[{name=value; type=string; sort_order=ascending}; {name=key; type=int64; sort_order=ascending}; {name="$empty"; type=int64}]}'
yt create secondary_index --attributes '{table_path="//path/to/table"; index_table_path="//path/to/index/table"; kind=full_sync; table_to_index_correspondence=bijective}'

Изменяемый атрибут table_to_index_correspondence указывает YTsaurus, какое предполагать отношение между строками индексируемой и индексной таблицы (он НЕ характеризует реальное отношение между строками таблиц и пользователь может изменять его самостоятельно). Допустимые значения этого атрибута: bijective, injective, invalid и unknown. Использование индекса с отношением invalid запрещено и приведет к ошибке. injective означает, что в индексной таблице есть строчки, не соответствующие никаким строкам в индексируемой таблице (в такое состояние таблицы могут прийти, например, при построении без даунтайма). bijective означает полное соответствие между строками таблиц. Оба отношения - bijective и injective - являются рабочими состояниями таблиц, о разнице между ними будет сказано ниже. Отношение unknown можно увидеть на индексах, созданных более старыми версиями YTsaurus.

Вторичный индекс может быть создан, только если обе таблицы отмонтированы. После создания вторичного индекса и монтирования таблиц последующие записи в индексируемую таблицу автоматически отображаются в индексной (о построении индексной таблицы поверх имеющихся данных см. далее). Также становится возможным выполнять эффективные select-запросы с фильтрацией по вторичному ключу, используя ключевое слово WITH INDEX. Запрос с индексом выполнится эффективно, если предикат позволяет отсечь ненужные строки из индексной таблицы.

yt select-rows "key, value FROM [//path/to/table] WITH INDEX [//path/to/index/table] where value BETWEEN 0 and 10"

При исполнении запроса с таким синтаксисом система сначала прочитает из индексной таблицы строки, подходящие под предикат where value BETWEEN 0 and 10, а затем выполнит внутреннее соединение (inner join) со строками индексируемой таблицы по общим колонкам для индексов с отношением injective или по первичному ключу для bijective индексов. То есть такой запрос эквивалентен одному из следующих:

yt select-rows "key, value FROM [//path/to/injective/index/table] AS `$IndexTable` JOIN [//path/to/table] ON (`$IndexTable.key`, `$IndexTable.value`) = (key, value) WHERE `$IndexTable.value` BETWEEN 0 and 10"
yt select-rows "key, value FROM [//path/to/bijective/index/table] AS `$IndexTable` JOIN [//path/to/table] ON `$IndexTable.key` = key WHERE `$IndexTable.value` BETWEEN 0 and 10"

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

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

Частичная индексация

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

Это полезно, если запросы, для которых индекс полезен, касаются только некоторой выделяемой части данных. Например, схема таблицы имеет вид [{name=id; sort_order=ascending; type=uint64}; {name=name; type=string}; {name=age; type=int64}; {name=loyalty; type=boolean}; ...], а в запросах вы делаете выборку по возрасту только для строк, в которых loyalty имеет не-null значение. В таком случае вторичный индекс с предикатом not is_null(loyalty) и индексной таблицей со схемой [{name=age; type=int64; sort_order=ascending}; {name=id; sort_order=ascending; type=uint64}; {name=$empty, type=int64}] является оптимальным решением — строки с loyalty=# не попадут в индексную таблицу.

Индекс над списком

Индекс вида kind=unfolding разворачивает строки по колонке со списком значений примитивного типа. Такой индекс позволяет делать выборки строк, в которых индексируемый список содержит определённые значения. Например, строке {id=0; child_ids=[1, 4, 7]} в индексной таблице будут соответствовать строки [{child_ids=1; id=0}; {child_ids=4; id=0}; {child_ids=7; id=0}]. При создании такого индекса необходимо указать атрибут unfolded_column - имя колонки некоторого типа T в индексной таблице, также как и колонки типа List<T> или Optional<List<T>> в индексируемой таблице. В select-запросах ограничение на индексируемое значение можно задавать используя функцию list_contains. Пример: id FROM [//path/to/table] WITH INDEX [//path/to/index/table] where list_contains(child_ids, 1).

Например, пусть строки в таблице со схемой [{name=id; type=int64; sort_order=ascending}; {name=book_name; type=string}; {name=genres; type_v3={type_name=list; item=string}}; ...] описывают книги. Для быстрой выборки по жанрам можно использовать unfolding вторичный индекс над индексной таблицей со схемой [{name=genres; sort_order=ascending; type=string};{name=id; type=int64; sort_order=ascending}; {name=book_name; type=string}] — присутствие в схеме индексной таблицы колонки book_name позволит использовать индексную таблицу без присоединения к индексируемой для запросов, в которых нужны только колонки genres, book_name и id, ещё уменьшая количество чтений и ускоряя выполнение запросов.

Уникальный индекс

Индекс вида kind=unique поддерживает уникальность вторичного ключа в индексируемой таблице. Ключом в схеме индексной таблицы для вторичного индекса такого вида является вторичный ключ, а неключевыми значениями — первичный ключ. При попытке записи, которая привела бы к существованию в индексируемой таблице двух строк с одинаковыми значениями вторичного ключа, пользователю вернётся ошибка UniqueIndexConflict. Параллельный коммит двух транзакций с записями строк с разными первичными ключами и одинаковыми вторичными приведет к падению одной из транзакций с ошибкой TransactionLockConflict.

Шардирование вторичного индекса

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

Копирование и перемещение

В текущей версии YTsaurus нельзя ни копировать ни перемещать ни индексную ни индексируемую таблицы, сохраняя вторичный индекс между ними - при попытке вернётся ошибка. Правильный порядок действий в этом случае таков - отмонтировать таблицы, удалить вторичные индексы, проделать необходимые операции в Кипарисе, пересоздать вторичные индексы с теми же атрибутами, примонтировать таблицы. Альернативно, можно указать параметр allow_secondary_index_abandonment=%true для ваших операций - в таком случае все затронутые вторичные индексы будут удалены автоматически.

Ограничения

• Поскольку select-запрос с использованием индекса выполняет соединение таблиц, чтение должно производиться под транзакцией для получения глобально консистентного среза (по умолчанию select-запросы выполняются с SyncLastCommittedTimestamp, в этом режиме система в общем случае не может гарантировать консистентность между двумя структурами данных).

• Запрещена индексация по агрегирущим колонкам, а также запрещена запись в индексируемую таблицу с блокировкой shared write.

• Запись в индексируемую таблицу map-reduce операцией не отображается в индексной.

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

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

Ограничения, накладываемые на реплицированные таблицы

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

Производительность

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

Построение индекса

Для корректного создания вторичного индекса поверх существующих данных существует скрипт. Он позволит построить вторичный индекс с минимальным для индексируемой таблицы даунтаймом, необходимым на взятие снапшота индексируемой таблицы и её перемонтирования (если только не строится уникальный индекс — для поддержания строгой уникальности необходимо, чтобы в таблицу не происходило записей на протяжении всего построения). После того как скрипт возьмет нужный лок, он самостоятельно примонтирует индексируемую таблицу и её можно будет использовать для чтения и записи. После успешного завершения работы скрипта можно будет использовать индексную таблицу для запросов. Пользователь должен сам проследить за тем, чтобы не задавать запросов с использованием индекса, пока он полностью не построен.

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