Просмотр исходного текста страницы Дополнительные индексные структуры для пропуска блоков данных в таблицах

{{Карточка_командного_проекта
|name=Дополнительные индексные структуры для пропуска блоков данных в таблицах
|company=Яндекс
|semester=Осень 2018
|course=3-4
|number_of_students=?
|categorize=yes
}}

В большинстве СУБД есть возможность создавать вторичные индексы. Вторичный индекс обычно представляет собой дерево, которое позволяет найти расположение записей по некоторому ключу. Но в аналитических СУБД вторичные индексы редко применяются в чистом виде.

Причина состоит в том, что для одного запроса требуется, как правило, прочитать большое количество записей - в этом случае мы могли бы найти эти записи по индексу, но прочитать их с диска было бы всё-равно сложно: если данные не расположены более-менее локально, то для их чтения пришлось бы делать много дисковых seek-ов и разжимать много сжатых блоков. Поэтому в ClickHouse (и в других похожих системах) есть только один индекс, по которому данные более-менее упорядочиваются (clustered index), что обеспечивает возможность эффективно читать диапазоны по этому ключу.

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

Тем не менее, вместо индекса ""в чистом виде"", можно реализовать некоторые маленькие структуры, которые позволят пропускать отдельные блоки данных (data skipping).
Суть в том, что на каждый блок данных сохраняется ещё небольшая выжимка. Примеры:
- minmax индекс - минимальное и максимальное значение столбца в блоке;
- список всех уникальных значений, если столбец имеет мало уникальных значений (например, меньше 10);
- небольшой bloom filter из всех значений; для строк можно использовать триграмный bloom filter для поиска подстрок.