Рисуем карту одним select — ом или о пользе многотабличных индексов, eos криптовалюта новости.

Рисуем карту одним select’ом или о пользе многотабличных индексов

Данная статья написана в продолжение серии, повествующей о прототипировании простого и производительного динамического web map сервера. Ранее рассказывалось о том, как в нем устроены пространственные индексы, а так же о том, как можно просто так вот взять и нарисовать пространственный слой. Сейчас мы сделаем это чуть изящнее.

В том, что касается работы с одним слоем мы более-менее разобрались, но ведь в реальности слоёв могут быть десятки, на каждый из них придется делать запрос в пространственном индексе, даже, если в поисковый экстент ничего не попало… Нельзя ли как-то архитектурно вычистить данный процесс и избавиться от заведомо бесполезных действий?

Индексация

Можно, отчего же нет. Но для этого нам придется создать единый пространственный индекс для всех пространственных слоёв. Вспомним, как устроены наши индексы:

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

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

  • Тренироваться как и раньше будем на shape данных, полученных из OSM Russia.
  • Возьмем 4 относительно населенных слоя – водоемы, леса, здания и дороги.
  • В качестве СУБД как и раньше будем использовать OpenSource редакцию OpenLink Virtuoso, официальную Win_x64 сборку версии 7.0.0, взятую с сайта разработчика.
  • Для рисования будем использовать основанный на GD и описанный ранее C плагин, расширяющий набор встроенных функций PL/SQL.
  • Экстент данных возьмем: xmin=-180, ymin=35, xmax=180, ymax=85 градусов.
  • Разобьем этот экстент на блоки по 0.1 ° по широте и долготе. Таким образом получим решетку из 3600Х500 блоков. 0.1° — это около 11 км, многовато для отрисовки на уровне домов, но наша цель в данный момент не максимальная производительность в конкретных условиях, а проверка концепции.
  • Загрузим слои в СУБД так же как и раньше:
    • vegetation-polygon.shp: 657673 элементов, время загрузки 2′ 4»
    • water-polygon.shp: 380868 элементов, время загрузки 1′ 22»
    • building-polygon.shp: 5326421 элементов, время загрузки 15′ 42»
    • highway-line.shp: 2599083 элементов, время загрузки 7′ 56»
  • Теперь есть таблицы с данными (Ex: «xxx».«YYY».«water-polygon») и связанные таблицы с пространственными индексами (Ex: «xxx».«YYY».«water-polygon__spx»). Пользуясь тем, что все они сформированы с едиными параметрами, сольем их в едином пространственном индексе

    Изготовление общего индекса занимает 2’16». Использование курсоров вместо конструкции (insert… select . ) вызвано тем, что в OpenSource-ной версии есть ограничение в 50мб на размер лога одной транзакции в журнале. Данное ограничение легко устранить пересборкой, но это уже другая история.
    Теперь настраиваем работу с индексом аналогично тому, как мы это делали раньше

    Проверяем корректность работы:

    Первый запрос вернул 29158, остальные: 941 + 33 + 20131 + 8053. Совпадает.

Замеряем производительность индекса.

Будем запускать серии из 10000 случайных поисков в квадрате [35. 45,50. 60]° на общем индексе и старым способом. Все запросы выполняются в одном соединении т.е. показывают производительность на одно ядро.

Вывод: да, единый индекс работает быстрее, но результат не поражает воображение. С другой стороны, все 4 наших слоя относительно плотно заселены, опять же немаловажно, что объем данных относительно небольшой для того, чтобы все преимущества единого поиска встали во весь рост. С третьей стороны, это живые данные, как они есть.

Рисуем карту

Первым делом нарисуем ее старым путем, чтобы было с чем сравнивать.

Работа занимает 17.2 сек.

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

К сожалению, нет штатного метода передать агрегату параметры инициализации, поэтому приходится идти на хитрость, подсунуть ему union из данных и строки инициализации, конструировать контекст не в конструкторе, а при получении первой строки.
Как же так, скажет внимательный читатель, был обещан один селект, а там их целая куча! В действительности идентификаторы строк приходят агрегату упорядоченно и потаблично, поэтому кажущиеся подзапросы на самом деле являются организованным руками join’ом.
Итак, время работы 42 секунды. Нда.

Этот запрос работает 17.4 секунды. Таким образом, оптимизатор смог распознать скрытые join’ы и исполнить запрос без особых потерь за красоту. А небольшой выигрыш в работе собственно индекса был съеден возросшей сложностью запроса.

А вот и результат:

В этой невзрачной картинке несколько миллионов объектов.

Нарисовать карту одним запросом не представляет особого труда. Нам даже удалось сделать это не потеряв особо в производительности. Выиграть, правда, тоже не удалось и причина по всей видимости в структуре данных. А структура эта заточена под использование традиционными ГИС.

Например, таблица ‘highway-line’ содержит в себе пару десятков слоев разных типов, отличающихся атрибутами. Обычно, такие таблицы служат основой для всех дорожных слоев, ссылающихся на одну физическую таблицу и отличающихся фильтрами. Конечно, удобнее работать с одной таблицей нежели с двумя десятками (этот момент был и одним из мотивов для данной работы). Опять же, мы имеем общий пространственый индекс для васех этих слоев.

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

Что если мы раскидаем, например, таблицу ‘highway-line’ на кучу подтаблиц по типам и объединим все их в одном пространственном индексе, как делали это выше? Работа с индексом от этого не изменится, нам нужен будет только один поиск в нём. Работа с данными только ускорится т.к. повысится локальность данных — данные одного типа, близкие пространственно чаще будут оказываться рядом на диске. А если данных какого-либо типа нет в поисковом экстенте, они просто не будут обрабатываться. Сколько бы их ни было, это никак не скажется на чтении полезных данных.

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

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

Опять же, традиционно, процессор запросов волен выбирать какими индексами ему пользоваться. Но это не наш случай. Мы можем создать несколько многотабличных индексов и явно указывать, какой индекс служит источником первичного потока данных. Вне зависимости от того, что по этому поводу думает оптимизатор. Приятно видеть, как «древо жизни вечно зеленеет» сквозь «сухую теорию» реляционной модели.

в качестве иллюстрации в шапке статьи использован чудесный ‘план города Парижа’ руки Марка Твена из одноименного рассказа.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *