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

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

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

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

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

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

1. Если в таблице ключом является выражение z(x, y), то индекс должен работать, если в запросе указано условие на x или на y. Для этого потребуется уметь вычислять обратное отображение диапазонов для некоторых функций. 2. Равномерному смешиванию локальности расположения данных может мешать неравномерность распределения значений смешиваемых атрибутов. Для того, чтобы это обойти, мы будем вычислять space filling curve с некоторыми хитрыми эвристиками.