Рисуем карту одним 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»). Пользуясь тем, что все они сформированы с едиными параметрами, сольем их в едином пространственном индексе

  registry_set ('__spx_startx', '-180');
  registry_set ('__spx_starty', '35');
  registry_set ('__spx_nx', '3600');
  registry_set ('__spx_ny', '500');
  registry_set ('__spx_stepx', '0.1');
  registry_set ('__spx_stepy', '0.1');
  drop table "xxx"."YYY"."total__spx";
  create table "xxx"."YYY"."total__spx" (
   	"node_" integer, "tab_" integer, "oid_" integer,
  	primary key ("node_", "tab_", "oid_"));
  create procedure mp_total_spx ()
  {
    for select "node_", "oid_" from "xxx"."YYY"."water-polygon__spx" do
    {
      insert into "xxx"."YYY"."total__spx" ("oid_","tab_","node_") 
        values ("oid_", 1, "node_");
      commit work;
    }
    for select "node_", "oid_" from "xxx"."YYY"."vegetation-polygon__spx" do
    {
      insert into "xxx"."YYY"."total__spx" ("oid_","tab_","node_") 
        values ("oid_", 2, "node_");
      commit work;
    }
    for select "node_", "oid_" from "xxx"."YYY"."highway-line__spx" do
    {
      insert into "xxx"."YYY"."total__spx" ("oid_","tab_","node_") 
        values ("oid_", 3, "node_");
      commit work;
    }
    for select "node_", "oid_" from "xxx"."YYY"."building-polygon__spx" do
    {
      insert into "xxx"."YYY"."total__spx" ("oid_","tab_","node_") 
        values ("oid_", 4, "node_");
      commit work;
    }
  };
  mp_total_spx ();
  

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

• Теперь настраиваем работу с индексом аналогично тому, как мы это делали раньше

  create procedure "xxx"."YYY"."total__spx_enum_items_in_box" (
  	in minx double precision, 
  	in miny double precision, 
  	in maxx double precision, 
  	in maxy double precision)
  {
    declare nx, ny integer;
    nx := atoi (registry_get ('__spx_nx'));
    ny := atoi (registry_get ('__spx_ny'));
    declare startx, starty double precision;
    startx := atof (registry_get ('__spx_startx'));
    starty := atof (registry_get ('__spx_starty'));
    declare stepx, stepy double precision;
    stepx := atof (registry_get ('__spx_stepx'));
    stepy := atof (registry_get ('__spx_stepy'));
    declare sx, sy, fx, fy integer;
    sx := cast (floor ((minx - startx)/stepx) as integer);
    fx := cast (floor ((maxx - startx)/stepx) as integer);
    sy := cast (floor ((miny - starty)/stepy) as integer);
    fy := cast (floor ((maxy - starty)/stepy) as integer);
    declare ress any;
    ress := vector(dict_new (), dict_new (), dict_new (), dict_new ());
    for (declare iy integer, iy := sy; iy <= fy; iy := iy + 1)  {
      declare ixf, ixt integer;
      ixf := nx * iy + sx;
      ixt := nx * iy + fx;
      for select "node_", "tab_", "oid_" from "xxx"."YYY"."total__spx" 
          where "node_" >= ixf and "node_" <= ixt do  {
        dict_put (ress["tab_" - 1], "oid_", 0);
      }
    }
    result_names('oid', 'tab');
    declare ix integer;
    for (ix := 0; ix < 4; ix := ix + 1)  {
      declare arr any;
      arr := dict_list_keys (ress[ix], 1);
      gvector_digit_sort (arr, 1, 0, 1);
      foreach (integer oid in arr) do
      { result (oid, ix + 1); }
    }
  };
  
  create procedure view "xxx"."YYY"."v_total__spx_enum_items_in_box" as
  "xxx"."YYY"."total__spx_enum_items_in_box" (minx, miny, maxx, maxy) ("oid" integer, "tab" integer); 
  

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

  select count(*) from "xxx"."YYY"."v_total__spx_enum_items_in_box" as a
  where a.minx = 82.963 and a.miny = 54.9866 
  and a.maxx = 82.98997 and a.maxy = 55.0133;
  select count(*) from "xxx"."YYY"."v_vegetation-polygon_spx_enum_items_in_box" ...
  select count(*) from "xxx"."YYY"."v_water-polygon_spx_enum_items_in_box" ...
  select count(*) from "xxx"."YYY"."v_building-polygon_spx_enum_items_in_box" ...
  select count(*) from "xxx"."YYY"."v_highway-line_spx_enum_items_in_box" ...
  

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

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

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

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

Рисуем карту

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

create procedure mk_test_gif( 
	in cminx double precision, 
	in cminy double precision, 
	in cmaxx double precision, 
	in cmaxy double precision)
{
  declare img any;
  img := img_create (512, 512, cminx, cminy, cmaxx, cmaxy, 1);
  declare cl integer;
  declare bg integer;
  {
    cl := img_alloc_color (img, 0, 0, 255);
    bg := img_alloc_color (img, 0, 0, 255);
    whenever not found goto nf;
    for select blob_to_string(Shape) as data from 
      xxx.YYY."water-polygon" as x, xxx.YYY."v_water-polygon_spx_enum_items_in_box" as a
    where a.minx = cminx and a.miny = cminy and a.maxx = cmaxx and a.maxy = cmaxy 
      and x."_OBJECTID_" = a.oid
      and x.maxx_ >= cminx and x.minx_ <= cmaxx
      and x.maxy_ >= cminy and x.miny_ <= cmaxy
    do  { img_draw_polygone (img, data, cl, bg); }
nf:;
...
  для остальных таблиц примерно то же, дороги рисуются через img_draw_polyline.
...
  }
  declare ptr integer;
  ptr := img_tostr (img);
  img_destroy (img);
  declare image any;
  image := img_fromptr(ptr);
  string_to_file('test.gif', image, -2);                         
  return;
};
mk_test_gif(35., 50., 45., 60.);

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

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

create function mapx_agg_init (inout _agg any)
{;};
create function mapx_agg_acc (
  inout _agg any,
  in _tab integer,
  in _oid integer )
{
  if (_agg is null)  {
    declare img any;
    img := img_create (512, 512, _tab[0], _tab[1], _tab[2], _tab[3], 1);
    _agg := img;
    return 0;
  }  else  {
    return case
      when _tab = 4 then (img_draw_polygone(_agg, (
        select blob_to_string(bl.Shape) from "xxx"."YYY"."building-polygon" as bl 
        where bl."_OBJECTID_" = _oid), 255, 255))
      when _tab = 3 then (img_draw_polyline(_agg, (
        select blob_to_string(hw.Shape) from "xxx"."YYY"."highway-line" as hw 
        where hw."_OBJECTID_" = _oid), 100, 100)) 
      when _tab = 2 then (img_draw_polygone(_agg, (
        select blob_to_string(vg.Shape) from "xxx"."YYY"."vegetation-polygon" as vg
        where vg."_OBJECTID_" = _oid), 10, 10))
      when _tab = 1 then (img_draw_polygone(_agg, (
        select blob_to_string(wt.Shape) from "xxx"."YYY"."water-polygon" as wt 
        where wt."_OBJECTID_" = _oid), 50, 50))
      else 1
    end;
  }
};
create function mapx_agg_final (inout _agg any) returns integer
{
  declare ptr integer;
  ptr := img_tostr (_agg);
  img_destroy (_agg);
  declare image any;
  image := img_fromptr(ptr);
  string_to_file('nskx_ii.gif', image, -2);                      
  return 1;
};
create aggregate mapx_agg (in _tab integer, in _oid integer) returns integer
  from mapx_agg_init, mapx_agg_acc, mapx_agg_final;
create procedure mk_testx_ii_gif( 
	in cminx double precision, 
	in cminy double precision, 
	in cmaxx double precision, 
	in cmaxy double precision)
{
  declare cnt integer;
  select 
      mapx_agg(tab, oid) into cnt
  from (
    select * from (select vector(cminx, cminy, cmaxx, cmaxy) as tab, 0 as oid) as f1
    union all
    (select tab, oid from xxx.YYY."v_total__spx_enum_items_in_box" as a
     where a.minx = cminx and a.miny = cminy and a.maxx = cmaxx and a.maxy = cmaxy) 
  ) f_all;
}
mk_testx_ii_gif(35., 50., 45., 60.);

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

Еще попытка

create procedure mk_testx_gif( 
	in cminx double precision, 
	in cminy double precision, 
	in cmaxx double precision, 
	in cmaxy double precision)
{
  declare img any;
  img := img_create (512, 512, cminx, cminy, cmaxx, cmaxy, 1);
  declare cnt, cnt2 integer;
  declare cl1, bg1 integer;
  cl1 := img_alloc_color (img, 0, 0, 255);
  bg1 := img_alloc_color (img, 0, 0, 255);
  declare cl2, bg2 integer;
  cl2 := img_alloc_color (img, 0, 255, 0);
  bg2 := img_alloc_color (img, 0, 255, 0);
  declare cl3, bg3 integer;
  cl3 := img_alloc_color (img, 255, 100, 0);
  bg3 := img_alloc_color (img, 255, 100, 0);
  declare cl4, bg4 integer;
  cl4 := img_alloc_color (img, 255, 0, 0);
  bg4 := img_alloc_color (img, 255, 0, 0);
  select 
    sum (
      case
        when geom is null then 0
        when geom_type = 2 then (img_draw_polyline(img, geom, cl, bg)) 
        else (img_draw_polygone(img, geom, cl, bg))
      end 
    ) into cnt
  from ( 
    select 
      case
        when a.tab = 4 then (
           select blob_to_string(bl.Shape) from "xxx"."YYY"."building-polygon" as bl 
           where bl."_OBJECTID_" = a.oid)
        when a.tab = 3 then (
           select blob_to_string(hw.Shape) from "xxx"."YYY"."highway-line" as hw 
           where hw."_OBJECTID_" = a.oid)
        when a.tab = 2 then (
           select blob_to_string(vg.Shape) from "xxx"."YYY"."vegetation-polygon" as vg 
           where vg."_OBJECTID_" = a.oid)
        when a.tab = 1 then (
           select blob_to_string(wt.Shape) from "xxx"."YYY"."water-polygon" as wt 
           where wt."_OBJECTID_" = a.oid)
        else ''
      end as geom, 
      case when a.tab = 3 then 2 else 1 end as geom_type,
      case when a.tab = 4 then cl4 
           when a.tab = 3 then cl3 
           when a.tab = 2 then cl2 
           when a.tab = 1 then cl1 else 0 end as cl,
      case when a.tab = 4 then bg4 
           when a.tab = 3 then bg3 
           when a.tab = 2 then bg2 
           when a.tab = 1 then bg1 else 0 end as bg
    from
      xxx.YYY."v_total__spx_enum_items_in_box" as a
    where a.minx = cminx and a.miny = cminy 
           and a.maxx = cmaxx and a.maxy = cmaxy
  ) f_all;
  declare ptr integer;
  ptr := img_tostr (img);
  img_destroy (img);
  declare image any;
  image := img_fromptr(ptr);
  string_to_file('testx.gif', image, -2);
  return;
};
mk_testx_gif(35., 50., 45., 60.);

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

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

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

Выводы

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

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

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

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

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

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

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

PS:

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

Автор: zzeng

Источник