- PVSM.RU - https://www.pvsm.ru -
Неоднократно доводилось слышать мнение, что из всех заметающих кривых [1]. именно кривая Гильберта [2] наиболее перспективна для пространственной индексации. Мотивируется это тем, что она не содержит разрывов и потому в некотором смысле “хорошо устроена”. Так ли это на самом деле и при чем здесь пространственная индексация, разберёмся под катом.
Завершающая статья из цикла:
Почему не работает прямолинейный подход при
пространственной индексации заметающими кривыми,
Презентация алгоритма [3]
3D и очевидные оптимизации [4]
8D и перспективы в OLAP [5]
3D на сфере, как это выглядит [6]
3D на сфере, benchmarks [7]
Как насчет индексации неточечных объектов? [8].
Кривая Гильберта обладает замечательным свойством — расстояние между двумя последовательными точками на ней всегда равно единице (шагу текущей детализации, если точнее). Поэтому данные с не сильно отличающимися значениями кривой Гильберта находятся недалеко друг от друга (обратное, кстати, неверно — расположенные рядом точки могет очень сильно отличаться по значению). Ради этого свойства её используют, например, для
Что касается пространственных данных, свойства кривой Гильберта позволяют увеличить локальность ссылок и повысить эффективность кэша СУБД, как здесь [13], где перед использованием таблицы рекомендуют дополнить её колонкой с вычисленным значением и отсортировать по этой колонке.
В пространственном поиске кривая Гильберта присутствует в Гильбертовых R-деревьях [14], где основная идея (очень грубо) — когда приходит время расщепить страницу на двух потомков — сортируем все элементы на странице по значениям центроидов и делим пополам.
Но нас больше интересует другое свойство кривой Гильберта — это самоподобная заметающая кривая. Что позволяет использовать ее в индексе на основе B-дерева. Речь идёт о способе нумерации дискретного пространства.
Итак, откуда берётся это интуитивное ощущение, что кривая Гильберта хороша для пространственной индексации? Да в ней нет разрывов, расстояние между любыми последовательными точками равно шагу дискретизации. Ну и что? Какова связь между этим фактом и потенциально высокой производительностью?
В самом начале [15] мы сформулировали правило — «хороший» метод нумерации минимизирует суммарный периметр страниц индекса. Речь идёт о страницах B-дерева, на которых в конце концов окажутся данные. Другими словами — производительность индекса определяется числом страниц, которые придётся прочитать. Чем меньше страниц приходится в среднем на запрос эталонного размера, тем выше (потенциальная) производительность индекса.
С этой точки зрения кривая Гильберта выглядит очень перспективно. Но это интуитивное ощущение на хлеб не намажешь, поэтому проведём численный эксперимент.
Вот так это выглядит в виде графиков.
Теперь стоит хотя бы из любопытства посмотреть как при фиксированном размере запроса (2D 100X100) ведет себя число прочитанных страниц в зависимости от размера страницы.
Хорошо заметны “ямы” в Z-order, соответствующие размерам 128, 256 и 512. И “ямки” в 192, 384, 768. Не такие уж и большие.
Как мы видим, разница может достигать 10%, но почти везде это в пределах статистической погрешности. Тем не менее везде кривая Гильберта ведёт себя лучше чем Z-кривая. Не сильно, но лучше. По-видимому, эти 10% и есть оценка сверху потенциального эффекта, которого можно достичь, перейдя на кривую Гильберта. Стоит ли овчинка выделки? Попробуем узнать.
Использование кривой Гильберта в пространственном поиске сталкивается с рядом трудностей. Например, само вычисление ключа из 3 координат занимает (у автора) около 1000 тактов, примерно в 20 раз больше, чем то же для zcurve. Возможно, существует какой то более эффективный метод, кроме того есть мнение, что уменьшение числа прочитанных страниц окупает любое усложнение работы. Т.е. диск — более дорогой ресурс чем процессор. Поэтому мы будем в первую очередь ориентироваться именно на чтения буферов, а времена просто примем к сведению.
Что касается алгоритма [3]поиска. Вкратце, он базируется на двух идеях —
Но в отличие от бинарного поиска в нашем случае разбиение не делит пополам число располагаемых элементов, а происходит по геометрическому принципу.
Из самоподобия заметающих кривых следует, что если взять квадратную (кубическую) решетку, выходящую из начала координат с шагом в степень двойки, то любой элементарный куб в этой решетке содержит один интервал значений. Следовательно, рассекая поисковый запрос по узлам этой решетки можно разбить исходный произвольный подзапрос на непрерывные интервалы. После чего каждый из этих интервалов вычитывается из дерева.
Всё это одинаково справедливо и для кривой Гильберта и для Z-order.
Однако:
Это приводит к тому, что необходимо модифицировать исходный алгоритм.
Для начала изменился интерфейс работы с ключом.
Модифицированный алгоритм поиска выглядит так:
Рассмотрим на примере запроса в экстенте [524000,0,484000 …525000,1000,485000].
Вот так выглядит исполнение запроса для Z-order — ничего лишнего.
Subqueries — все порождённые подзапросы, results — найденные точки,
lookups — запросы к B-дереву.
Поскольку диапазон пересекает 0x80000, стартовый экстент получается размером в весь экстент слоя. Всё самое интересное слилось в центре, рассмотрим поподробнее.
Обращают на себя внимание «скопления» подзапросов на границах. Механизм их возникновения примерно таков — допустим, очередной разрез отсёк от границы поискового экстента узкую полоску, например, шириной 3. Причем, в этой полоске даже нет точек, но мы то этого не знаем. А проверить сможем только в тот момент, когда минимальное значение диапазона подзапроса попадёт в пределы поискового экстента. В результате алгоритм станет резать полоску вплоть до подзапросов размером в 2 и 1 и только тогда сможет сделать запрос к индексу чтобы убедиться, что там ничего нет. Или есть.
На число прочитанных страниц это не влияет, все такие проходы по В-дереву приходятся на кэш, но объем проделанной работы впечатляет.
Ну что же, осталось выяснить сколько в действительности было прочитано страниц и сколько времени всё это заняло. Следующие значения получены на тех же данных и тем же способом, что и ранее [4]. Т.е. 100 000 000 случайных точек в [0...1 000 000, 0...0, 0...1 000 000].
Замеры проводились на скромной виртуальной машине с двумя ядрами и 4 Гб ОЗУ, поэтому времена не имеют абсолютной ценности, а вот числам прочитанных страниц по прежнему можно доверять.
Времена показаны на вторых прогонах, на разогретом сервере и виртуальной машине. Количества прочитанных буферов — на свеже-поднятом сервере.
NPoints | Nreq | Type | Time(ms) | Reads | Hits |
---|---|---|---|---|---|
1 | 100 000 | zcurve rtree hilbert |
.36 .38 .63 |
1.13307 1.83092 1.16946 |
3.89143 3.84164 88.9128 |
10 | 100 000 | zcurve rtree hilbert |
.38 .46 .80 |
1.57692 2.73515 1.61474 |
7.96261 4.35017 209.52 |
100 | 100 000 | zcurve rtree hilbert |
.48 .50 … 7.1 * 1.4 |
3.30305 6.2594 3.24432 |
31.0239 4.9118 465.706 |
1 000 | 100 000 | zcurve rtree hilbert |
1.2 1.1 … 16 * 3.8 |
13.0646 24.38 11.761 |
165.853 7.89025 1357.53 |
10 000 | 10 000 | zcurve rtree hilbert |
5.5 4.2 … 135 * 14 |
65.1069 150.579 59.229 |
651.405 27.2181 4108.42 |
100 000 | 10 000 | zcurve rtree hilbert |
53.3 35...1200 * 89 |
442.628 1243.64 424.51 |
2198.11 186.457 12807.4 |
1 000 000 | 1 000 | zcurve rtree hilbert |
390 300…10000* 545 |
3629.49 11394 3491.37 |
6792.26 3175.36 36245.5 |
где
Npoints — среднее число точек в выдаче
Nreq — число запросов в серии
Type — ‘zcurve’ — исправленный алгоритм с гиперкубами и разбором numeric, используя его внутреннюю структуру,;’rtree’- gist only 2D rtree; ‘hilbert’ — тот же алгоритм что и для zcurve, но для кривой Гильберта, (*) — для того, чтобы сравнить время поиска приходилось уменьшать серию в 10 раз для того, чтобы страницы умещались в кэш
Time(ms) — среднее время выполнения запроса
Reads — среднее число чтений на запрос. Самая важная колонка.
Shared hits — число обращений к буферам
* — разброс значений вызван высокой нестабильностью результатов, если нужные буфера успешно находились в кэше, то наблюдалось первое число, в случае массовых промахов — второе. Фактически, второе число характерно для заявленного Nreq, первое — в 5-10 раз меньшего.
Немного удивляет, что “наколеночная” оценка преимуществ кривой Гильберта дала довольно точную оценку реального положения дел.
Видно, что на запросах, где размер выдачи соизмерим или более размера страницы, кривая Гильберта начинает вести себя лучше по числу промахов мимо кэша. Выигрыш, впрочем, составляет единицы процентов.
С другой стороны, интегральное время работы для кривой Гильберта примерно вдвое хуже оного у Z-кривой. Допустим, автор выбрал не самый эффективный способ вычисления кривой, допустим, что-то можно было сделать поаккуратнее. Но ведь вычисление кривой Гильберта объективно тяжелее Z-кривой, для работы с ней действительно надо предпринимать существенно больше действий. Ощущение такое, что отыграть это замедление с помощью нескольких процентов выигрыша в чтении страниц не удастся.
Да, можно сказать, что в высококонкурентной среде каждое чтение страницы обходится дороже десятков тысяч вычислений ключа. Но ведь число успешных попаданий в кэш у кривой Гильберта заметно больше, а они проходят через сериализацию и в конкурентной среде тоже чего-то стоят.
Вот и подошло к концу эпическое повествование о возможности и особенностях пространственных и/или многомерных индексов на основе самоподобных заметающих кривых, построенных на B-деревьях.
За это время (кроме того, что такой индекс реализуем) мы выяснили что по сравнению с традиционно применяемым в данной области R-деревом
Автор: Борис Муратшин
Источник [17]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/postgresql/265741
Ссылки в тексте:
[1] заметающих кривых: https://en.wikipedia.org/wiki/Space-filling_curve
[2] кривая Гильберта: 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
[3] Презентация алгоритма: https://habrahabr.ru/post/319810/
[4] 3D и очевидные оптимизации: https://habrahabr.ru/post/323192/
[5] 8D и перспективы в OLAP: https://habrahabr.ru/post/331420/
[6] 3D на сфере, как это выглядит: https://habrahabr.ru/post/302606/
[7] 3D на сфере, benchmarks: https://habrahabr.ru/post/338088/
[8] Как насчет индексации неточечных объектов?: https://habrahabr.ru/post/339060/
[9] управление цветовой палитрой: http://people.csail.mit.edu/jaffer/Color/CSDR
[10] здесь: https://drum.lib.umd.edu/handle/1903/804
[11] здесь: http://repository.upenn.edu/cgi/viewcontent.cgi?article=1010&context=ese_papers
[12] DB2: https://www.redbooks.ibm.com/redbooks/pdfs/sg248213.pdf
[13] здесь: https://www.ibm.com/developerworks/data/library/techarticle/dm-0510stolze/index.html
[14] Гильбертовых R-деревьях: https://en.wikipedia.org/wiki/Hilbert_R-tree
[15] начале: https://habrahabr.ru/company/2gis/blog/302606/
[16] выложено : https://github.com/bmuratshin/zcurve
[17] Источник: https://habrahabr.ru/post/340100/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.