Индексы

Елена Дворядкина

Обзор

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

ADQM поддерживает следующие типы индексов для таблиц MergeTree:

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

  • Индексы пропуска данных (вторичные индексы). Когда первичного индекса недостаточно для обеспечения высокой производительности запросов, можно добавить в таблицу индексы пропуска данных — вторичные индексы в ADQM, позволяющие при выполнении запроса пропускать чтение блоков данных (могут быть достаточно большими), которые гарантированно не содержат запрашиваемых значений. Например, такие индексы могут быть эффективны для полнотекстового поиска или при проверках на вхождение значений в определенные списки. В отличие от первичного индекса индексы пропуска данных можно добавлять в существующие таблицы и удалять.

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

РЕКОМЕНДАЦИЯ
В статье Повышение производительности запросов можно найти примеры использования в таблицах индексов различных типов и посмотреть, как они влияют на скорость выполнения запросов.

Разреженный первичный индекс

Данные таблицы MergeTree делятся на части — куски данных (data parts), строки внутри которых сортируются по столбцам первичного ключа. Каждый кусок данных логически делится на гранулы (granules). Гранула — минимальный неделимый набор данных, состоящий из целого количества строк, который считывается при выборке данных. Первая строка гранулы помечается значениями столбцов первичного ключа для этой строки — такая отметка называется засечкой (mark). Для каждого куска данных создается свой индекс — файл с засечками. Таким образом, в ADQM не индексируется каждая отдельная строка, а первичный индекс куска данных имеет одну запись (засечку) на группу строк (гранулу), то есть используется разреженный индекс (sparse index). Вместо непосредственного поиска отдельных строк по всей таблице разреженный первичный индекс позволяет быстро (с помощью бинарного поиска) идентифицировать гранулы, которые могут включать строки, соответствующие фильтру запроса. Затем найденные группы потенциально подходящих строк параллельно загружаются в память для поиска в них строк, точно соответствующих условию фильтрации.

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

Назначение первичного ключа

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

Чтобы назначить таблице MergeTree первичный ключ, используйте выражение ORDER BY или PRIMARY KEY в запросе CREATE TABLE при создании таблицы:

CREATE TABLE <table_name> (<column_name> <column_type>, ...)
ENGINE = MergeTree
ORDER BY <sorting_key_expr>
[PRIMARY KEY <primary_key_expr>];

  • ORDER BY — ключ сортировки в виде одного или нескольких столбцов таблицы. ADQM использует ключ сортировки в качестве первичного ключа, если первичный ключ не задан с помощью выражения PRIMARY KEY.

  • PRIMARY KEY — первичный ключ. По умолчанию первичный ключ совпадает с ключом сортировки ORDER BY, поэтому в большинстве случаев выражение PRIMARY KEY отдельно использовать не нужно. Но при необходимости можно указать первичный ключ (столбцы, значения которых будут записаны как засечки в индексный файл), отличный от ключа сортировки (столбцы, по которым будут упорядочены строки в кусках данных). В этом случае кортеж столбцов первичного ключа должен быть префиксом кортежа столбцов ключа сортировки (например, если первичный ключ — (a, b), то ключ сортировки должен быть (a, b, c…​)).

Для каждой таблицы может быть определен только один первичный ключ. Можно создать таблицу без первичного ключа — для этого используйте синтаксис ORDER BY tuple().

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

Составной первичный ключ

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

  • эффективность фильтрации по дополнительным ключевым столбцам в запросах;

  • степень сжатия файлов данных таблицы.

Когда запрос фильтрует данные по первому ключевому столбцу, ADQM запускает алгоритм бинарного поиска по индексным засечкам этого столбца. Для фильтрации по другим ключевым столбцам применяется менее эффективный алгоритм generic exclusion search. Например, первичный ключ (a, b) будет полезен для ускорения запросов, фильтрующих данные по столбцу a, но не улучшит производительность запросов с фильтрацией по столбцу b, несмотря на то, что столбец b является частью составного первичного ключа. И наоборот, первичный индекс таблицы с ключом (b, a) будет ускорять запросы с фильтрацией по столбцу b, но не оптимизирует запросы, фильтрующие данные по столбцу a.

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

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

Индексы пропуска данных

Для таблиц семейства MergeTree можно также указать индексы пропуска данных (data skipping indexes). Индекс пропуска данных агрегирует некоторую информацию по заданному выражению (столбцу) в блоках данных. Затем эта информация используются при выполнении запросов SELECT для уменьшения объема считываемых с диска данных путем пропуска блоков данных, в которых гарантированно нет совпадений по условию фильтрации запроса. Пропускаемый блок состоит из гранул данных в количестве, равном гранулярности данного индекса.

Управление индексами

Индексы пропуска данных описываются с помощью выражения INDEX в секции описания столбцов запроса CREATE TABLE:

CREATE TABLE <table_name>
(   <column_name> <column_type>, ...
    INDEX <index_name> <index_expr> TYPE <index_type> [GRANULARITY <granularity_value>], ...)
ENGINE = MergeTree
...;

где:

  • <index_name> — имя индекса;

  • <index_expr> — выражение, по которому будет агрегироваться информация (часто это имя столбца);

  • <index_type> — тип индекса, определяющий, какая дополнительная информация о содержимом блока данных будет храниться в индексе (эта информация позволит быстро находить нужные блоки и пропускать все остальные);

  • <granularity_value> — гранулярность индекса, то есть количество гранул данных в пропускаемом блоке (значение по умолчанию — 1).

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

ALTER TABLE <table_name> ADD INDEX <index_name> <index_expr> TYPE <index_type> [GRANULARITY <granularity_value>];

Когда индекс добавляется в существующую таблицу, он не обновляется автоматически. ALTER TABLE изменяет метаданные, поэтому индекс будет рассчитываться только для новых данных, вставляемых в таблицу. Чтобы применить индекс к существующим данным, выполните дополнительную команду:

ALTER TABLE <table_name> MATERIALIZE INDEX <index_name>;

Удалить индексы можно запросами:

  • ALTER TABLE <table_name> DROP INDEX <index_name> — удаляет описание индекса из метаданных таблицы и удаляет индексные файлы с диска;

  • ALTER TABLE <table_name> CLEAR INDEX <index_name> — удаляет файлы индекса с диска без удаления описания индекса из метаданных.

Типы индекса

MinMax

Индекс minmax хранит минимальное и максимальное значение столбца (или выражения) для каждого блока.

Set

Индекс set(<max_rows>) хранит уникальные значения столбца (или выражения) в блоке данных в количестве, не большем чем <max_rows> (0 означает, что ограничений нет). Когда индексированный столбец используется в выражении WHERE, ADQM может считать небольшой набор значений вместо полного столбца. Этот тип индекса хорошо работает, если столбец имеет низкую кардинальность (небольшое количество уникальных значений) в каждом наборе гранул, но высокую кардинальность в целом.

Bloom Filter

Поддерживается три типа индекса на основе фильтра Блума:

  • bloom_filter([<false_positive>]) — фильтр Блума для столбца. Необязательный параметр <false_positive> определяет допустимую частоту получения ложноположительных ответов от фильтра. Возможны значения в диапазоне (0, 1). Значение по умолчанию: 0.025.

    Этот тип индекса поддерживается для следующих типов данных: Int*, UInt*, Float*, Enum, Date, DateTime, String, FixedString, Array, LowCardinality, Nullable, UUID и Map.

  • tokenbf_v1(<size_of_bloom_filter_in_bytes>, <number_of_hash_functions>, <random_seed>) — входная строка разбивается на токены (последовательности символов, разделенные не буквенно-цифровыми символами), а затем токены сохраняются в фильтре Блума. Подходит для поиска точного совпадения в строке (например, когда нужно найти определенную часть URL-адреса или параметр запроса в столбце URL).

    Все три параметра индекса связаны с настройкой фильтра Блума:

    • <size_of_bloom_filter_in_bytes> — размер фильтра в байтах (фильтры большего размера имеют меньше ложноположительных срабатываний);

    • <number_of_hash_functions> — количество хеш-функций, использующихся в фильтре Блума;

    • <random_seed> — состояние генератора случайных чисел для хеш-функций фильтра Блума.

    Этот тип индекса работает только c данными типа String, FixedString или Map.

  • ngrambf_v1(<n>, <size_of_bloom_filter_in_bytes>, <number_of_hash_functions>, <random_seed>) — входная строка разбивается на n-граммы (подстрока из n символов), а затем сохраняется в фильтре Блума. Подходит для полнотекстового поиска, особенно на языках без разрывов слов, таких как китайский. Первый параметр <n> задает размер n-грамм, остальные — аналогичны tokenbf_v1. Этот тип индекса работает только c типами данных String, FixedString и Map.

Inverted

Инвертированный индекс inverted([<n>], [<max_rows_per_posting_list>]) хранит сопоставление уникальных слов (или n-грамм) текстового столбца с указателями на их расположение в таблице (номера строк, в которых они содержатся). Используется для оптимизации полнотекстового поиска по столбцам типов String, FixedString, Array(String), Array(FixedString), Map(String) и Map(String). В настоящее время работает в экспериментальном режиме. Более подробную информацию и пример использования можно получить в статье Полнотекстовый поиск.

Получение информации об индексах

Информацию о существующих индексах можно получить из системных таблиц:

  • system.tables — поле primary_key содержит информацию о первичном ключе таблицы.

    Пример
    SELECT primary_key FROM system.tables WHERE table='table_compound_primary_key';
    ┌─primary_key─┐
│ a, b        │
└─────────────┘

  • system.data_skipping_indices — содержит информацию об индексах пропуска данных во всех таблицах.

    Пример
    SELECT type_full,expr FROM system.data_skipping_indices WHERE table='table_skip_index';
    ┌─type_full─┬─expr─┐
│ set(100)  │ b    │
└───────────┴──────┘

Также можно использовать запросы:

  • SHOW CREATE TABLE <table_name>.

    Пример
    SHOW CREATE TABLE table_skip_index;
    CREATE TABLE default.table_skip_index
(
    `a` UInt64,
    `b` UInt64,
    INDEX my_index b TYPE set(100) GRANULARITY 2
)
ENGINE = MergeTree
PRIMARY KEY a
ORDER BY a
SETTINGS index_granularity = 10000

  • SHOW {INDEX|INDEXES|INDICES|KEYS} FROM <table_name>.

    Пример
    SHOW INDEXES FROM table_skip_index;
    ┌─table────────────┬─non_unique─┬─key_name─┬─seq_in_index─┬─column_name─┬     ┬─index_type─┬─comment─┬─index_comment─┬─visible─┬─expression─┐
│ table_skip_index │          1 │ PRIMARY  │            1 │ a           │ ... │ PRIMARY    │         │               │ YES     │            │
└──────────────────┴────────────┴──────────┴──────────────┴─────────────┴─   ─┴────────────┴─────────┴───────────────┴─────────┴────────────┘
┌─table────────────┬─non_unique─┬─key_name─┬─seq_in_index─┬─column_name─┬─    ┬─index_type─┬─comment─┬─index_comment─┬─visible─┬─expression─┐
│ table_skip_index │          1 │ my_index │            1 │             │ ... │ SET        │         │               │ YES     │ b          │
└──────────────────┴────────────┴──────────┴──────────────┴─────────────┴─    ┴────────────┴─────────┴───────────────┴─────────┴────────────┘

Чтобы убедиться в использовании индексов для конкретного запроса, можно проанализировать выполнение этого запроса используя команду EXPLAIN с параметром indexes.

Пример
EXPLAIN indexes = 1 SELECT * FROM table_skip_index WHERE b=100 OR b=555;
┌─explain──────────────────────────────────────────┐
│ Expression ((Project names + Projection))        │
│   Expression                                     │
│     ReadFromMergeTree (default.table_skip_index) │
│     Indexes:                                     │
│       PrimaryKey                                 │
│         Condition: true                          │
│         Parts: 6/6                               │
│         Granules: 10004/10004                    │
│       Skip                                       │
│         Name: my_index                           │
│         Description: set GRANULARITY 2           │
│         Parts: 1/6                               │
│         Granules: 4/10004                        │
└──────────────────────────────────────────────────┘
Нашли ошибку? Выделите текст и нажмите Ctrl+Enter чтобы сообщить о ней