Прикручиваем пространственный индекс к ничего не подозревающей OpenSource СУБД

Мне всегда нравилось, когда заголовок однозначно говорит о том, что будет дальше, например, «Техасская резня бензопилой». Поэтому под катом мы действительно будем добавлять пространственный поиск к СУБД, в которой его изначально не было. Вводная Попробуем обойтись без общих слов про важность и полезность пространственного поиска. На вопрос, почему было не взять открытую СУБД с уже встроенным пространственным поиском, ответ будет такой: «хочешь сделать что-то хорошо, делай это сам»(С). А если серьезно, мы попробуем показать, что большинство практических пространственных задач может быть решено на на вполне рядовом десктопе без перенапряжения и особых затрат.

В качестве подопытной СУБД будем использовать открытую редакцию OpenLink Virtuoso. В её платной версии доступна пространственная индексация, но это совсем другая история. Почему именно эта СУБД? Автору она нравится. Быстрая, легкая, мощная. Скопировал-запустил-все работает. Будем пользоваться только штатными средствами, никаких С-плагинов или специальных сборок, лишь официальная сборка и текстовый редактор.

Некоторым образом делят пространство поиска на блоки
Все блоки нумеруются
Каждому индексируемому объекту присваивается один или несколько номеров блоков, в которых он расположен
При поиске экстент расщепляется на блоки и для каждого блока или непрерывной цепочки блоков из обычного целочисленного индекса (B-дерево) достаются все объекты, которые им принадлежат.

Старый добрый Igloo (или другая заметающая кривая) ограниченной точности. Пространство разрезается решеткой, шагом которой (обычно) является характерный размер индексируемого объекта. Ячейки нумеруются как X…xY…yZ…z… т.е. склеиванием номеров ячеек по нормалям. . Название происходит от Hierarchical Equal Area iso-Latitude Pixelisation. Этот метод предназначен для разбиения сферической поверхности с целью избежать основного недостатка Igloo – разной площади под ячейками на разной широте. Сфера разделяется на 12 равных по площади участков, каждый из которых в дальнейшем иерархически делится на 4 под — участка. Иллюстрация к этому методу вынесена в шапку статьи
Hierarchical Triangular Mesh (HTM).Это схема последовательного приближения к сфере с помощью треугольников, начиная с 8 стартовых, каждый из которых иерархически разбивается на 4 под — треугольника
Одной из наиболее известных схем блочных индексов, является GRID. Пространственные данные рассматриваются как частный случай многомерного индекса. При этом:
1. пространство режется на части с помощью решетки
2. получившиеся ячейки некоторым образом нумеруются
3. данные, попавшие в конкретную ячейку, хранятся вместе
4. значения атрибутов переводятся в номера ячеек по осям с помощью “директории”, предполагается, что она невелика и размещается в памяти
5. если “директория” велика, она разбивается на уровни a la дерево
6. при изменении, решетка может адаптироваться, ячейки или столбцы расщепляться или, наоборот, сливаться
3-уровневый GRID, основанный на Z-order используется DB2, 4-уровневый GRID, основанный на варианте кривой Гильберта использован в MS SQLServer 2008

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

посадим точки на узлы решетки 4000Х4000 с началом в (0,0) и шагом 1.
получим квадрат из 16 млн точек.
ячейку блочного индекса примем за 10Х10,
таким образом у нас 400Х400 ячеек в каждой по 100 точек.

Для генерации данных будем использовать вот такой скрипт на AWK(пусть, будет 'data.awk'):

Возьмем официальный билд с сайта компании. Автор использовал последнюю версию 7.0.0 (x86_64), но это не принципиально, можно взять любую другую.
Устанавливаем, если нет, Microsoft Visual C++ 2010 Redistributable Package (x64)
Выбираем директорию для опытов и копируем туда libeay32.dll, ssleay32.dll, isql.exe, virtuoso-t.exe из архивной 'bin' и virtuoso.ini из архивной 'database '
Запускаем сервер с помощью 'start virtuoso-t.exe +foreground', разрешаем файерволу открыть порты
Тестируем доступность сервера командой 'isql localhost:1111 dba dba'. После установления соединения вводим, например. 'select 1;' и убеждаемся, что сервер жив.

Схема данных Для начала создадим таблицу точек, ничего лишнего:

Теперь собственно индекс: где node_ — идентификатор ячейки пространства. Обратим внимание, что, хотя, индекс создается как таблица, оба поля присутствуют в первичном ключе и, следовательно, упакованы в дерево.

Настраиваем параметры индекса:

Системная функция registry_set позволяет записывать строковые пары имя/значение в системный реестр — это намного быстрее, чем держать их во вспомогательной таблице и все еще покрыто транзакциями.

Триггер на запись: Кладем все это в, например, 'sch.sql' и исполняем посредством Загрузка данных После того, как схема готова, можно заливать данные. Заняло это у автора 45 минут (

6000 в секунду) на Intel i7-3612QM 2.1GHz c 8Gb памяти. Размер памяти, занятый при этом сервером, был около 1 Gb, размер базы на диске — 540Mb, т.е.

34 байт на точку и ее индекс. Теперь следует убедиться, что результат корректен, вводим в isql Оба запроса должны выдать 16 000 000.

Как ориентир можно использовать данные, опубликованные здесь: . Получены они на PostgreSQL(Linux), 2.2GHz Xeon. С одной стороны, данные получены 9 лет назад. С другой, в данном случае, узким местом являются дисковые операции, а случайный доступ к диску за истекший период ускорился не столь уж значительно. А вот здесь мы можем почерпнуть, что время пространственной индексации соизмеримо с временем заливки собственно данных. Следует отметить, что заливка данных с последующей индексацией происходит (по очевидным причинам) существенно быстрее, нежели индексация на лету. Но нас более будет интересовать именно индексация на лету т.к. для практических целей более интересна пространственная СУБД, а не пространственная поисковая система.

И еще, нельзя не отметить, что при заливке пространственных данных очень важен порядок их заливки. И в данной работе и в упомянутой выше порядок подачи точек был идеальным (или близким к нему) с точки зрения пространственного индекса. Если данные перемешать, производительность упадет весьма драматично вне зависимости от выбранной СУБД. Если данные приходят произвольно, можно порекомендовать накапливать их в отстойнике, по мере его переполнения сортировать и заливать порциями.

Число: (139 — 91) * (295 — 228) = 3216
Среднее по X: (139 + 91 — 1) / 2 = 114.5 (-1 т.к. правая граница исключена)
Среднее по Y: (295 + 228 — 1) / 2 = 261 (. )

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

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

📎📎📎📎📎📎📎📎📎📎