Оптимизация работы с геометрическими данными

Для оптимизации поисковых операций с участием геометрических данных необходимо использовать индексы. Индексирование геометрических данных в СУБД ЛИНТЕР выполняется с помощью B-дерева.

Значения, хранящиеся в индексе, представляют собой значения геометрического типа MBR (Minimum Bounding Rectangle, минимальный ограничительный прямоугольник). В БД MBR-значение хранится в виде двух точек ((MINX,MINY),(MAXX,MAXY)). Все координаты имеют тип double.

Нижняя и верхняя граница оператора BETWEEN для геометрических данных задают левый нижний и правый верхний угол прямоугольника, при полном или частичном попадании в который оператор BETWEEN возвращает значение True (Истина).

Другие операторы сравнения ( >,< .=,<  >, >=,< =) также используют MBR.

Для сравнения двух объектов геометрических типов используется их MBR. Сначала сравнивается левый нижний угол (x, потом y), потом правый верхний угол (x, потом y). Если у какого-то MBR соответствующая координата при сравнении больше, то этот объект считается больше, если равны – сравнение продолжается. Если все соответствующие координаты равны, считается, что объекты равны между собой.

Команды создания индекса для столбцов геометрических типов данных имеют тот же синтаксис, что и команды создания простого индекса (см. документ «СУБД ЛИНТЕР. Справочник по SQL», пункт «Создание индекса»). Поддерживается создание составного индекса для геометрических типов данных.

Примечание

При расчете длины индекса необходимо учесть, что на каждый столбец геометрического типа данных дополнительно добавляется 16 байт (4 значения DOUBLE – ограничивающий прямоугольник).

Пример создания простого индекса:

CREATE OR REPLACE TABLE POINT_TEST(P POINT);
CREATE INDEX P ON POINT_TEST;

Пример создания составного индекса:

CREATE OR REPLACE TABLE LSPOINT_TEST(P POINT, LS LINESTRING);
CREATE INDEX "TEST" ON LSPOINT_TEST(P,LS);

Примечание

Есть возможность реализовать конструкции PRIMARY KEY, FORAIGN KEY (включая ON UPDATE CASCADE, ON DELETE CASCADE), UNIQUE с участием геометрического индекса, но практическое их использование вызывает сомнение с точки зрения логики.

Пример

  1. Создаем тестовую таблицу из 65543 записей:

    CREATE OR REPLACE TABLE POINT_TEST(P POINT);
    INSERT INTO POINT_TEST VALUES('POINT (100,100)');
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    INSERT INTO POINT_TEST SELECT * FROM POINT_TEST;
    
    INSERT INTO POINT_TEST VALUES('POINT (1 1)');
    INSERT INTO POINT_TEST VALUES('POINT (1 1)');
    INSERT INTO POINT_TEST VALUES('POINT (0 1)');
    INSERT INTO POINT_TEST VALUES('POINT (1 2)');
    INSERT INTO POINT_TEST VALUES('POINT (0 0)');
    INSERT INTO POINT_TEST VALUES('POINT (0 0)');
    INSERT INTO POINT_TEST VALUES('POINT (2 0)');
  2. Выполняем поисковый запрос без использования индекса:

    SELECT AsText(P) FROM POINT_TEST WHERE P BETWEEN PointFromText('POINT (1 1)')
    AND PointFromText('POINT (1 2)');
     INL : начальное время : 21:41:37.00 конечное время :  21:41:37.31
    
    |POINT (1 1)                             |
    |POINT (1 1)                             |
    |POINT (1 2)                             |
     INL : выдано строк     : 3
     
  3. Создаем индекс и повторно выполняем поисковый запрос:

    CREATE INDEX "TEST" ON POINT_TEST(P);
     INL : начальное время : 21:44:45 конечное время :  21:44:47
    SELECT AsText(P) FROM POINT_TEST WHERE P BETWEEN PointFromText('POINT (1 1)')
    AND PointFromText('POINT (1 2)');
     INL : начальное время : 21:45:05 конечное время :  21:45:05
    
    |POINT (1 1)                             |
    |POINT (1 1)                             |
    |POINT (1 2)                             |
     INL : выдано строк     : 3
  4. Анализируем результаты: без использования индекса время выполнения запроса повышается с 0.00 секунд до 0.31 секунды.