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

Под катом мы займёмся проверкой возможности применения Z-кривой для реализации 8-мерного индекса с прицелом на куб OLAP.

Краткое содержание предыдущих серий.

Ранее (1, 2, 3, 4, 5) было показано, что индекс на основе Z-кривой вполне пригоден для организации пространственного поиска. Он очень близок по скорости (при отсутствии ограничений по кэшу буферов) к традиционно используемому R-дереву, но при этом заметно компактнее, быстрее строится, не боится случайных данных, меньше читает при поиске.

Опасения.

Технически, ничего сложного в реализации такого индекса нет, потребовалось лишь сделать обработку 8-мерного ключа. Размерность 8 была выбрана из технологических соображений, если нужен 7-мерный индекс, можно смело дополнить его нулями по одной из координат, на скорости это почти не отразится, разве что ключ станет длиннее. При необходимости ничего не мешает сделать и более длинный, например 16-мерный ключ.

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

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

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

Для обычного B-дерева, на котором построен наш индекс данная проблема не так уж и страшна — дерево само соблюдает баланс.
В реальности разные размерности имеют и разные шкалы, максимальный экстент может быть сплюснут по одним размерностям и вытянут по другим. Да, конечно, но опять же, это довольно важно при построении многомерных R-деревьев и гораздо менее критично в случае B-деревьев.
Как насчет точности? В текущей реализации допускается до 31 разряда для кодирования значения. Если данные (с плавающей точкой) получены естественным путём, для их кодирования скорее всего хватит и 20 разрядов. Есть конечно и 32-разрядные АЦП, но это скорее экзотика. Понятно, что double содержит 64 разряда, но большинство данных без потерь (или с минимальными потерями) может быть посажено на 31-разрядную решетку. Если это не так, данные подвергались обработке, например, их ус��едняли.

При необходимости разрешение описываемого индекса может быть увеличено. Это вызовет разбухание ключа и деградацию производительности. Тем не менее, пока на странице помещается более одного ключа, они могут быть организованы в виде B-дерева.

С другой стороны, небольшая потеря точности не принципиальна в нашем случае. Ведь мы ищем в интервале по каждой размерности. Для получения корректного результата достаточно взять интервал с запасом и убрать лишнее пост-фильтрацией.
Данные могут иметь иерархическую природу. Например, число кодирует датчик, но датчики сгруппированы, их группы образуют свою иерархию. А хочется делать выборку по целой ветке этой иерархии. Эта проблема решается обходом и нумерацией узлов дерева в прямом порядке. Тогда каждый узел дерева имеет интервал значений — от собственного идентификатора до идентификатора своего последнего потомка.

А интервалы — это как раз то, что нам и нужно для поиска.
Многомерные прямоугольники имеют развитую поверхность и кодирование Z-кривой будет весьма неэффективным. Есть такие опасения, заодно и проверим.

Benchmark

В нижеследующую таблицу сведены результаты по нескольким (описанным ниже) типам запросов.
Данные — 100 000 000 случайных точек, равномерно распределенным в 8-мерном кубе со сторонами [0...1 000 000].

Замеры (как и раньше) проводились на виртуальной машине с двумя ядрами и 4 Гб ОЗУ, поэтому времена не имеют абсолютной ценности, а вот числам прочитанных страниц по прежнему можно доверять.
Времена показаны на вторых прогонах, на разогретом сервере и виртуальной машине. Количества прочитанных буферов — на свеже-поднятом сервере.

Детали

Вот этот коммит: (SHA-1: 36dd...76c7)

gawk -f gendata.awk 〉 data.csv

BEGIN{
  for (i = 0; i < 100000000; i++)
  {
    x = int(1000000 * rand());
    y = int(1000000 * rand());
    z = int(1000000 * rand());
    a = int(1000000 * rand());
    b = int(1000000 * rand());
    c = int(1000000 * rand());
    print "{"x","y","z","a","b","c","a","b"}";
  }
}

обратим внимание, “a” и “b” встречаются дважды, имеем вырожденные данные, настоящая размерность — 6

create table test_points_8d (p integer[8]);
COPY test_points_8d from '/home/.../postgresql/contrib/zcurve/data.csv';
10 minutes

\dt+

Schema |      Name      | Type  |  Owner   |  Size   | Description 
-------+----------------+-------+----------+---------+-------------
public | test_points_8d | table | postgres | 8056 MB |

create index zcurve_test_points_8d on test_points_8d (zcurve_num_from_8coords (p[1], p[2], p[3], p[4], p[5], p[6], p[7], p[8]));
15 minutes

\di+

Schema |         Name           | Type  |  Owner   |     Table     |  Size   | 
--------+-----------------------+-------+----------+---------------+-------+---
 public | zcurve_test_points_8d | index | postgres | test_points_8d | 4743 MB

проверочный запрос

select c, t_row from (select c, (select p from test_points_8d t where c = t.ctid) t_row from zcurve_8d_lookup_tidonly('zcurve_test_points_8d', 237000,291000,845000,152000,585000,193000,152000,585000, 247000,301000,855000,162000,595000,203000,162000,595000) as c) x;

возвращает

     c | t_row 

------+-----------------------------------------------------------

 (0,1) | {237787,291065,845813,152208,585537,193475,152208,585537}

что и требовалось

Тип запроса	NPoints	Nreq	Time(ms)	Reads	Shared Hits
всё по 10 000	1.1e-4	100 000	.46	2.0175	15.3919
всё по 100 000	73.9	10 000	47	57.3063	1604.18
3Х100 000 + 5Х10 000	0.0837	10 000	.9	8.7637	73.8852
2Х100 000 + 6Х10 000	0.0096	10 000	.66	5.1771	40.9089
1 целиком + 1X100 000 + 6X10 000	0.0978	10 000	1.5	24.2122	199.33
2 целиком + 6X10 000	0.9663	10 000	95	115.202	1050.8

где
Тип запроса — одно из следующего

всё по 10 000. Сторона общего экстента — 1 000 000, запросы в виде куба со стороной 10 000, начала запросов равномерно распределены внутри общего экстента. Сторона запроса составляет 1E-2 от максимума. Т.к. у нас 6 независимых параметров, получаем 1E-12 от полного объема. Число точек — 1E8, значит теоретическая вероятность найти точку в таком экстенте примерно 1E-4
всё по 100 000. Экстент запроса в — куб со стороной 100 000, это 1e-1. Т.к. у нас 6 независимых параметров, получаем 1e-6 от объема. Число точек — 1e8, значит среднее число точек в таком запросе 100. С другой стороны, вероятность вылезти за пределы экстента по одной координате — 10%, по любой из 6 — 53% (0.9**6), если среднее вылезание 5%, то тогда вероятность 0.735 (0.95**6), что согласуется с полученным значением
3Х100 000 + 5Х10 000. Запросы сплющены по 5 размерностям
2Х100 000 + 6Х10 000. Запросы сплющены по 6 размерностям
1 целиком + 1X100 000 +6X10 000. Запросы сплющены по 6 размерностям, одна размерность взята целиком, одна — 100 000. Моделируется ситуация, когда одно из значений неизвестно, приходится брать полный интервал по нему.
2 целиком + 6X10 000. Два значения взяты целиком, усугубляем ситуацию с неизвестными.

NPoints — среднее число точек, найденных в запросе
Nreq — размер серии запросов
Time(ms) — среднее время выполнения запроса
Reads — среднее число чтений на запрос
Shared Hits — число попаданий в кэш буферов

Выводы

Как и ожидалось, важную роль в стоимости запроса играет площадь периметра запроса. В самом деле, чем больше периметр, тем потенциально большее число страниц он пересечет, тем больше придётся читать, тем меньше эффективность кэша …

Тем не менее, для кубических запросов стоимость запроса вполне приемлема. В самом деле, для запроса — куба со стороной 100 000, в среднем читается 57 страниц на 74 строки в выдаче. Для того, чтобы прочитать эти 74 строки, скорее всего придётся прочитать еще около 74 страниц.

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

PS: на титульной картинке изображен октеракт — 8-мерный куб
PPS: спасибо Андрею Бородину (Октоника, Екб.) за наводку на тему

Z-order в 8D