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

Компания	Яндекс
Учебный семестр	Осень 2018
Учебный курс	3-4-й курс
Максимальное количество студентов, выбравших проект: ?

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

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

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

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