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

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

В 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}'

Вторичный индекс может быть создан, только если обе таблицы отмонтированы. После создания вторичного индекса и монтирования таблиц последующие записи в индексируемую таблицу автоматически отображаются в индексной (о построении индексной таблицы поверх имеющихся данных см. далее). Также становится возможным выполнять эффективные 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) со строками индексируемой таблицы по общим колонкам. То есть такой запрос эквивалетнен следующему:

yt select-rows "key, value FROM [//path/to/index/table] AS IndexTable JOIN [//path/to/table] ON (IndexTable.key, IndexTable.value) = (key, value) 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}]. В схемах таблиц должны присутствовать такие одинаково названные колонки, типы которых соотносятся как list<T> или optional<list<T>> в индексируемой таблице и T в индексной, где 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.

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

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

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

Ограничения

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

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

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

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

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

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

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

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

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