- PVSM.RU - https://www.pvsm.ru -
«Давным-давно, кажется, в прошлую пятницу» автору попалась на глаза статья [1], в которой сравниваются разные популярные методы индексации небесных объектов. По причине неровного дыхания к этой теме пришлось разбираться в тонкостях и делать выводы.
Вы спросите: «Кому вообще интересны эти небесные объекты?» и даже: «Ну и при чём здесь 2ГИС?» и будете отчасти правы. Ведь методы пространственного индексирования являются универсальной ценностью.
Обычно, имея дело с геоданными, мы работаем с локальной проекцией на плоскость и тем самым отмахиваемся от искажений. В масштабах планеты это сделать труднее — начинают выпирать астрономические проблемы.
Что касается объёмов данных, уже сейчас в OSM более 4 млрд точек и 300 млн дорог. Это соизмеримо с масштабами, характерными для звёздных объектов. Да и помимо всего прочего, звёздные атласы — отличный стенд для разработки и отладки пространственных алгоритмов.
Обещанные тонкости и выводы под катом.
Проблемы индексации небесных объектов — это борьба с полярными координатами.
Так как объекты традиционно имеют координаты RA/DEC (широта/долгота), длина градуса долготы зависит от широты, а на полюсах возникают сингулярности. Поэтому при поиске в окрестностях некоторой точки приходится при построении поискового экстента учитывать широту этой точки. А хотелось бы спрятать эти подробности внутрь индекса.
В случае пространственного join’а опять же хочется не нагружать процессор SQL разными интимными подробностями.
Итак, основные внешние требования к методу индексирования («пикселизации») небесных объектов таковы [2]:
Конечно, использование СУБД накладывает свои ограничения: номер «пикселя» должен легко вычисляться, индекс должен быть компактным, поисковый запрос должен порождать умеренное количество подзапросов.
Известно довольно много сферических многогранников [3], смежные методы (HEALPix [4], HTM [5]). Можно, кроме того, предпринять мощение сферы таким вот (или аналогичным) методом:
(Правильный семиугольный паркет порядка 3 в модели Пуанкаре на диске [6])
Но тот, кто придумает для этого варианта дешёвый способ переводить координаты в номер пикселя и получать набор пикселей по конусу, рискует вызвать дьявола.
В упомянутой статье сравниваются различные популярные методы индексации, реализованные в Postgres.
Детали сравнения:
Относительные результаты таковы:
На что следует обратить внимание?
Самое время задать вопрос из разряда «а что, если...».
Если сделать гибрид PGSphere и Q3C, где вместо R-дерева используется трёхмерный низкоуровневый Z-order. Почему Z-order, что в нём хорошего? Как минимум, такой метод индексации автоматически удовлетворяет трём первичным внешним требованиям, которые сформулированы в начале статьи. Есть и «внутренние» плюсы.
Один из самых известных примеров самоподобной кривой, заметающей квадрат, является Гильбертова кривая [12]. Другой, чуть менее известный пример — z-order [9].
Наш порядок обхода несколько отличается от канонического, но это не принципиально.
Всякой паре x-битных чисел (x,y) ставится в соответствие 2x-битный z по следующему простому правилу. Биты чисел x, y соединяются в одно число, просто чередуясь друг с другом. При этом биты числа x занимают чётные позиции (если начинать отсчёт с 0), а биты числа y — нечётные.
Для квадрата 64х64 это выглядит так:
Z-order очень удобен для индексации, так как может быть реализован как обычное B-дерево с целочисленным ключом. Однако есть проблемы с эффективным поиском по нему.
Синий прямоугольник на картинке — поисковый запрос. Каждый раз, когда он пересекает кривую, порождается (или заканчивается) непрерывный интервал значений ключей.
Следовательно, если мы каждый такой интервал будем обрабатывать отдельным подзапросом, получим значительные накладные расходы, так как немалая часть этих интервалов пусты, а каждый подзапрос — это проход по дереву индекса.
Если же искать в одном интервале от начала до конца экстента, это равносильно тому, как если бы мы проиндексировали одну только Y-координату и фильтровали по ней.ля запроса в 1/10 от экстента слоя по x&y (1/100 слоя) будет просмотрена 1/10 индекса — КПД 10%, для запроса в 1/100 экстента слоя по x&y (1/10000 слоя) будет просмотрена 1/100 индекса — КПД 1%.
Этим и объясняется, почему данный метод редко используют в СУБД. Вот и в Q3C он в блочном варианте. Хотя самоподобие наделяет его чудесной особенностью — адаптацией к неравномерно распределённым данным. Кроме того, непрерывные отрезки кривой могут накрывать значительные области пространства, что полезно, если суметь этим воспользоваться.
Эффективный (но весьма низкоуровневый) способ работы с Z-order есть [13], но об этом, возможно, позже. Способ этот распространяется и на трёхмерный индекс.
Впрочем, поведение Z-order в трёхмерном пространстве слабо изучено и требует тщательной проверки. Чем мы и займёмся.
Что мы хотим увидеть?
Как вообще оценить критерий пригодности способа индексации для обработки пространственных данных?
Как уже говорилось [14], что бы мы ни делали, файл индекса на физическом носителе (нумерация страниц) одномерен, и расположить дву(много)мерные данные без разрывов невозможно.
Самоподобные кривые дают нам возможность минимально соблюсти локальность ссылок, то есть пространственно близкие объекты и на диске будут чаще находиться рядом. Самой приятной в этом отношении является кривая Гильберта, но она дорога с вычислительной точки зрения. Z-order как раз является компромиссом между требованиями к вычислительной простоте и локальности данных.
Но всё же сплошь и рядом близкие точки будут оказываться далеко друг от друга. Как же оценить степень «несовершенства» индексации?
Во-первых, будем исходить из того, что пространственный индекс расположен на страницах дерева. И если две точки попали на одну страницу, значит они физически близки, даже если соответствующие им Z-значения сильно отличаются.
Во-вторых, пространственный поиск осуществляется в некотором экстенте, следовательно, чем меньшее число страниц попало в этот экстент, тем выше скорость обработки запроса.
В-третьих, если поисковый запрос меньше характерного размера страницы, индекс тем «качественней», чем больше вероятность, что поиск ограничится одной страницей.
Итак, можно сформулировать общее правило:
«хороший» метод индексации минимизирует суммарный периметр страниц индекса.
Стоило бы придумать формальный критерий оценки качества, но иногда лучше один раз увидеть всё глазами, чем жонглировать цифрами. А получив общее понимание ситуации можно заняться и формализацией.
uint32_t key3ToBits[8] = {
0, 1, 1 << 3, 1 | (1<<3),
(1 << 6), (1 << 6) | 1, (1 << 6) | (1 << 3), 1 | (1 << 3) | (1 << 6),
};
uint64_t xy2zv(uint32_t x, uint32_t y, uint32_t z)
{
uint64_t ret = 0;
for (int i = 0; i < 7; i++)
{
uint64_t tmp = (key3ToBits[x & 7] << 2) |
(key3ToBits[y & 7] << 1) |
(key3ToBits[z & 7]);
ret |= tmp << (i * 9);
x >>= 3; y >>= 3; z >>= 3;
}
return ret;
}
Для того чтобы разместиться в 64 битах, мы допускаем для исходных координат разрешение в 21 бит.
Для первой серии нанесём на верхнюю полусферу единичного радиуса точки с шагом в полградуса по широте и долготе.
Центральная часть полусферы выглядит так (в порядке генерации, команда gnuplot: ‘splot ‘data’ w l;’):
Теперь мы построим Z-значения для каждой точки и отсортируем в соответствии с этими значениями. Значения посажены на решётку в интервалах 0...2 000 000 (т.е. 21 бит). Для контроля будем строить также картину для 2-мерного z-order (только x&y, без z).
Фрагмент 3d, общий вид обхода сверху. Кроме «прострелов» (от переходов через степень 2-ки) по x&y видны также кольцевые «прострелы» по z.
То же для 2d.
Теперь будем симулировать распределение данных по страницам на диске. Предположим, что на страницу попадает 1000 элементов. Тогда первые 1000 элементов в отсортированном массиве попадут на первую страницу и т.д. Для наглядности представлен обход страницы, но он не важен – как мы уже выяснили, важен периметр.
Первые 1000 значений. |
Значения с 9000 по 10000. |
Значения с 19000 по 20000. |
Значения с 60000 по 61000. Поскольку сфера в этом месте практически выположилась, 2d и 3d совпадают. |
Значения с 120000 по 121000. Попали на узел. |
Теперь приготовим 150 000 случайных точек на сфере и проделаем всё то же с ними.
Общий вид на обход сверху теперь такой:
Полярная область ничем не выделяется, и это радует.
Она практически одинакова для обоих случаев.
Первые 1000 значений. |
Значения с 9000 по 10000. |
Значения с 19000 по 20000. |
Значения с 60000 по 61000. |
Значения с 120000 по 121000. |
Впрочем, кроме достоинств, он обладает и всеми недостатками своего двухмерного варианта, причём в гипертрофированном виде. Если мы попытаемся искать в таком индексе «в лоб», выискивая непрерывные интервалы значений, нас ждёт разочарование, этих интервалов стало ещё больше. В сущности, «в лоб» можно искать только в очень небольших экстентах.
Как уже упоминалось, метод работы с таким индексом есть. Но это уже совсем другая история.
Отдельное спасибо хочется выразить Саше Артюшину из компании DataEast [15] за концептуальное участие.
Автор: 2ГИС
Источник [16]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/129020
Ссылки в тексте:
[1] статья: http://skyview.gsfc.nasa.gov/xaminblog/index.php/tag/pgsphere/
[2] таковы: http://www.sai.msu.su/~megera/wiki/SkyPixelization
[3] сферических многогранников: https://ru.wikipedia.org/wiki/%D0%A1%D1%84%D0%B5%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D0%B3%D1%80%D0%B0%D0%BD%D0%BD%D0%B8%D0%BA
[4] HEALPix: https://en.wikipedia.org/wiki/HEALPix
[5] HTM: https://msdn.microsoft.com/en-us/library/aa964138(v=sql.90).aspx
[6] Правильный семиугольный паркет порядка 3 в модели Пуанкаре на диске: https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%BA%D0%B5%D1%82_(%D0%B3%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%8F)#/media/File:PavageHypPoincare2.svg
[7] HAVERSINE: https://en.wikipedia.org/wiki/Haversine_formula
[8] Q3C: https://github.com/segasai/q3c
[9] Z-order: https://en.wikipedia.org/wiki/Z-order_curve
[10] 2MASS: https://ru.wikipedia.org/wiki/2MASS
[11] PGSPHERE: https://github.com/akorotkov/pgsphere
[12] Гильбертова кривая: https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%B2%D0%B0%D1%8F_%D0%93%D0%B8%D0%BB%D1%8C%D0%B1%D0%B5%D1%80%D1%82%D0%B0
[13] есть: https://habrahabr.ru/post/204254/
[14] говорилось: https://habrahabr.ru/post/186564/
[15] DataEast: http://dataeast.ru/
[16] Источник: https://habrahabr.ru/post/302606/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.