Яндекс, [email protected]

ClickHouse - открытая колоночная СУБД, позволяющая выполнять аналитические запросы в интерактивном режиме по данным, обновляемым в реальном времени. ClickHouse разработан в Яндексе для задач Яндекс.Метрики - второй по величине системы веб-аналитики в мире.

Доклады про ClickHouse:

• https://yadi.sk/i/BjbWmnrM3QMo22
• https://www.youtube.com/watch?v=PLMSA_gDdyM
• https://www.youtube.com/watch?v=C17XU8JXdcU

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

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

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

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

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

• minmax индекс - минимальное и максимальное значение столбца в блоке;
• список всех уникальных значений, если столбец имеет мало уникальных значений (например, меньше 10);
• небольшой bloom filter из всех значений; для строк можно использовать триграмный bloom filter для поиска подстрок.

Методы индексации данных на основе space filling curves.

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

Часто при проектировании базы данных в ClickHouse, трудно выбрать порядок столбцов ключа в кортеже. Для примера, в базе данных рекламной системы, ключевыми столбцами является идентификатор рекламодателя (кто заказывал рекламу) и идентификатор рекламной площадки (на каком сайте размещена реклама). Отчёты надо строить иногда для рекламодателя, а иногда - для рекламной площадки. То есть, первым столбцом в ключе может быть или тот, или другой идентификатор. В этом случае разумным является выбрать такой порядок столцбов, от которого будут выигрывать большинство запросов; а другие запросы будут выполняться медленно. Либо хранить таблицу в двух вариантах (копиях).

Тем не менее возникает вопрос - можно ли упорядочить данные по некоторому отношению порядка, которое будет средним (компромиссным) между несколькими вариантами, и будет работать хорошо в обеих случаях? Ответом на этот вопрос являются space filling curves. https://en.wikipedia.org/wiki/Z-order_curve В результате, если данные упорядочивать по z(attr1, attr2...), то мы получим нечто среднее между упорядочиванием данных по одному атрибуту и по другому атрибуту.

Для реализации предстоит решить несколько проблем.