Оптимизация запросов к пространственным данным в SQL Server 2012

Ссылка на оригинальную статью: http://social.technet.microsoft.com/wiki/contents/articles/9694.tuning-spatial-point-data-queries-in-sql-server-2012.aspx

Авторы: Ed Katibah, Milan Stojic, Michael Rys, Nicholas Dritsas

Технические рецензенты: Chuck Heinzelman

Введение

Оптимизация запросов к пространственным данным требует особого подхода. В SQL Server 2012 был представлен ряд нововведений, помогающих в достижении этой цели.

Ниже мы рассмотрим основные рекомендации и подходы к решению этой задачи.

Оптимизируйте кластерный индекс для первичного ключа

Для того, чтобы создать индекс на столбец с пространственными данными, в таблице должен присутствовать первичный ключ. SQL Azure в дополнение к этому требует, чтобы на первичный ключ был создан кластеризованный индекс.

Основы пространственных индексов

Выполнение запроса к пространственным данным с использованием индекса происходит в 2 этапа: первичной фильтрации (с использованием пространственного индекса) и вторичной фильтрации (наложение исходного фильтра). Таким образом, при выполнении запроса вида “STDistance() < x”, SQL Server выполнит следующие операции:

  • определит набор ячеек-кандидатов
  • произведёт поиск по пространственному индексу (первичная фильтрация)
  • объединит полученные значения с базовой таблицей, чтобы получить набор пространственных объектов
  • отфильтрует все ложно найденные объекты путём выполнения первоначальной пространственной операции (вторичный фильтр)

                                              

Избежать вторичной фильтрации можно используя операцию Filter(@x)=1 вместо STIntersects(@x)=1. В этом случае производительность запроса будет значительно выше, но при этом в результирующей выборке возможно наличие ложно выбранных объектов. Если пространственный запрос не очень велик, то для HHHH пространственного индекса, погрешность будет составлять около 100-200 метров, при использовании типа Geography.

Оператор STDistance(@x) < @range может быть заменён на Filter(@x.BufferWithTolerance(@range,1,1)) = 1

Если возврат объектов ложно определённых, как удовлетворяющие условию, неприемлем, то производительность дисковых операций с базовой таблицей всё равно может быть оптимизирована.

Любой пространственный индекс уже опимизирован для минимизации дисковых операций. Ячейки расположены в специальном порядке таким образом, чтобы пространственно более близкие ячейки, были также и физически близко расположены. Следующая иллюстрация демонстрирует порядок расположения ячеек (в SQL Server используется заполнение пространства кривой Гильберта).

 

Таким образом, данные считываемые с диска при выполнении поиска по пространственному индексу могут выглядеть следующим образом:

 

Однако, поскольку для получения самих объектов, необходимо выполнять объединение с базовой таблицей, операции чтения при выполнения поиска по кластеризованному индекcу для базовой таблицы могут выглядеть следующим образом:

 

Это влечёт за собой чтение с диска гораздо большего числа страниц и, как следствие, оказывает негативное влияние на общую производительность пространственного запроса.

Таким oбразом, для улучшения производительности при поиске по кластерному индексу, необходимо чтобы первичный ключ коррелировал с расположением ячеек в пространственном индексе. Этого возможно достичь путём добавления координат точек к кластеризованному индексу

Для примера, возьмём следующую таблицу, содержащую столбец с координатами точек:

CREATE TABLE [dbo].[Points](
       [id]   [int] NOT NULL,
       [type] [int] NOT NULL,
       [geo] [geography] NULL
  PRIMARY KEY CLUSTERED 
    ( 
       [id] ASC,
       [type] ASC
));

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

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

Важно отметить, что колонки с координатами точки должны быть первыми двумя колонками, входящими в первичный ключ. Для геометрических координат, они должны быть в порядке x, y.  Для географических данных они должны быть в порядке широта, долгота.

Для приведённого примера, необходимо расширить схему следующим образом, создав 2 новые вычисляемые хранимые колонки, и добавив эти новые колонки в кластеризованный первичный индекс (обратите внимание на использование встроенных методов Lat и Long для получения индивидуальных координат):

CREATE TABLE [dbo].[Points](
  [id]   [int] NOT NULL,
  [type] [int] NOT NULL,
  [geog] [geography] NOT NULL,
  [geo_lat]  AS ([geog].[Lat])  PERSISTED NOT NULL, -- *
  [geo_lon]  AS ([geog].[Long]) PERSISTED NOT NULL, -- *
  PRIMARY KEY CLUSTERED 
    (
      [geo_lat] ASC, 
      [geo_lon] ASC, 
      [id] ASC,
      [type] ASC
));

* not null для использования в первичном ключе

ПРИМЕЧАНИЕ: Сохранение значений x,y / широты,долготы для пространственных объектов в кластеризованном ключе добавляет к ключу 16 байт , которые затем дублируются как в базовой таблице, так и в самом пространственном индексе, равно как и во всех некластеризованных индексах, добавляемых к таблице. Стандартной практикой для кластеризованных индексов является минимизация размера ключа. И хотя это может потенциально увеличить производительность пространственного индекса, необходимо помнить о потенциально негативных последствиях.

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

По умолчанию, основываясь на общих данных, пространственный индекс рекомендовалось создавать с размером сетки на уровне MEDIUM.  Так выглядело первоначальное определение индекса:

CREATE SPATIAL INDEX [table_geog_sidx] 
  ON [dbo].[table]([geog])
    USING  GEOGRAPHY_GRID 
      WITH (GRIDS =(LEVEL_1 = MEDIUM,
                    LEVEL_2 = MEDIUM,
 
                   LEVEL_3 = MEDIUM,
                    LEVEL_4 = MEDIUM), 
            CELLS_PER_OBJECT = 16;

Производительность запроса к пространственным данным зачастую может быть значительно улучшена путём выбора для конкретных пространственных форм и их распределения настроек пространственного индекса отличающихся от настроек по умолчанию. В случае точечных данных, было обнаружено, что в большинстве, если не во всех случаях, производительность сетки, установленной на HIGH на всех уровнях, превосходит все прочие конфигурации. Поскольку мы работаем с точечными данными, то параметр CELLS_PER_OBJECT не играет роли и может быть установлен в любое допустимое значение (1-8192). Вот пространственный индекс, в котором сетка настроена на оптимальную конфигурацию для точек: все уровни в значении HIGH:

CREATE SPATIAL INDEX [table_geog_sidx] 
  ON [dbo].[table]([geog])
    USING  GEOGRAPHY_GRID 
      WITH (GRIDS =(LEVEL_1 = HIGH,
                    LEVEL_2 = HIGH,
                    LEVEL_3 = HIGH,
                    LEVEL_4 = HIGH), 
            CELLS_PER_OBJECT = 16;

 
Рассмотрите возможность использования сферической модели земли для географических данных

Если вы используете SQL Azure или SQL Server 2012 и требование точности географических данных не требует обязательного использования эллиптической модели земли, то дополнительное увеличение производительности можно получить, благодаря использованию более простых математических вычислений, для пространственной системы координат в сферической модели. В дополнение к этому функции STDistance(), STLength() и ShortestLineTo() оптимизированы таким образом, что работают на сфере быстрее, чем на эллипсоиде.

В SQL Server 2012 и SQL Azure в представление sys.spatial_reference_systems была добавлена запись для сферической модели. Эта запись имеет идентификатор пространственной ссылки (SRID) = 104001 и определена как "единичная сфера (unit sphere)".

"Родными" единицами измерения для единичной сферы являются радианы. Для получения значений в единицах измерения физического мира, таких как длина и площадь, выраженная в метрах, достаточно просто умножить результат на радиус желаемой сферы, как показано ниже:

  • Для линейных величин (длина, расстояние, размер буферной зоны):   длина * (радиус сферы)
  • Для значений площади:  площадь * (радиус сферы) * (радиус сферы)

В нашем примере, первоначально, координаты были определены во всемирной геодезической системе координат 1984 года (WGS84).  В SQL Server и SQL Azure, она определяется индентификатором пространственной ссылки (SRID) 4326. Это наиболее распространённая система координат, используемая для географических данных (большинство коммерческих пространственных данных, также как и GPS-приёмники, используют именно эту координатную систему). Для многих картографических приложений в вебе, использующих WGS84 (карты Bing, Google и др.), радиус сферы составляет 6,378,137 метров (“Сферическая проекция Меркатора”).

Для того, чтобы обновить SRID для всех точек в таблице с пространственными данными на идентификатор единичной сферы можно использовать следующий оператор T-SQL (обратите внимание на использование метода STSrid):

UPDATE Points
  SET geog.STSrid = 104001

 
Тестирование производительности

Для того, чтобы протестировать указанные рекомендации, был использован клиентский сценарий и данные.  Чтобы дать понимание объема запросов, в качестве примера приведём следующую процедуру:

 /****** Object:  StoredProcedure [dbo].[TEST]    Script Date: 12/13/2011 3:14:50 PM ******/
SET ANSI_NULLS ON
GO

SET QUOTED_IDENTIFIER ON
GO

ALTER PROCEDURE [dbo].[TEST]
AS
BEGIN
  -- SET NOCOUNT ON added to prevent extra result sets from
  -- interfering with SELECT statements.
 
 --set statistics time on
  --set statistics IO on

  SET NOCOUNT ON;
  DECLARE @Location geography,
          @continent integer

 
 SELECT @Location = CI.city_center_coordinates,
         @continent = CO.continent_id
    FROM dbo.geo2_city AS CI
      INNER JOIN dbo.geo2_country AS CO ON CO.country_id = CI.country_id
    WHERE CI.city_id = 9395
      AND CI.rec_status > -1
      AND CO.rec_status > -

      SET @location = geography::Point(@location.Lat, @location.Long, 4326)

      SELECT GI.geo_id, GI.geo_info.STDistance(@Location)
        FROM db_core.dbo.geo_informations2 AS GI with(nolock,
            INDEX(SIndx_geography_informations2)) 
          INNER JOIN  dbo.product_hotels (nolock) AS PH 
            ON (PH.hotel_id = GI.geo_id) 
          WHERE GI.geo_type = 7
            AND PH.rec_status = 1
            AND PH.region_id = 2 

            AND GI.geo_info.STDistance(@Location) < 10000
END    

Для ясности обсуждения, ниже представлен оператор T-SQL до оптимизации, который получает основные пространственные данные, используемые в хранимой процедуре (пространственные методы SQL Server выделены). Он соответствует выделенному оператору T-SQL в хранимой процедуре.

SELECT p.geo_id, p.geo_info.STDistance(@Location)
 
FROM Points AS p WITH(nolock,   
      INDEX(SIndx_geography_informations)) –- исходный, неоптимизированный индекс
    WHERE GI.geo_info.STDistance(@Location) < 10000 -– 10KM (10,000 метров)

Когда координатная система была изменена с  SRID=4326 на SRID=104001, было необходимо переписать запрос следующим образом для того, чтобы учесть изменение единиц измерения координатной системы и обеспечить использование нового оптимизированного пространственного индекса:

SELECT GI.geo_id, GI.geo_info.STDistance(@Location) * 6378137 
  FROM Points_UnitSphere AS GI WITH(nolock,   
      INDEX(geo_info_HHHH_sidx)) –- оптимизированный индекс 
    WHERE GI.geo_info.STDistance(@Location) * 6378137 < 10000 – 10KM

Использование умножения в предикате WHERE, влечёт за собой игнорирование пространственного индекса в плане выполнения (на самом деле, если написать запрос таким образом, то компилятор запроса укажет на то, что указание на использование пространственного индекса некорректно). Для того, чтобы этого избежать, можно переписать запрос следующим образом:

SELECT p.id, p.info.STDistance(@Location) * 6378137 
  FROM Points_UnitSphere AS p WITH(nolock,   
      INDEX(geo_info_HHHH_sidx))  
    WHERE GI.geo_info.STDistance(@Location) < 10000/6378137 -- 10KM

 
Заключение

Кратко просуммируем методы потенциального увеличения производительности при работе с пространственными данными:

  • Для точечных данных, создайте пространственный индекс со значением “HIGH” для всех уровней сетки
  • Используйте операцию Filter для избежания вторичной фильтрации
  • Создайте кластеризованный первичный ключ на таблицу с точечными данными, используя индивидульные компоненты координат точек
  • Для типа данных Geography, используйте сферическую модель Земли вместо эллиптической системы
  • Используйте указание spatial_window_max_cells query для более тонкой настройки производительности

До оптимизации, использование метода STDistance в условиях SELECT и WHERE давало среднюю производительность в 30 миллисекунд.

После оптимизации (новая таблица с кластеризованным первичным ключом, базирующимся на координатах точек, новый пространственный индекс, и использование методов, оптимизированных для работы со сферой), использование STDistance в условиях SELECT and WHERE дало среднюю производительно в 18 milliseconds.

Описание

Время исполнения в мс(среднее*)

Исходный пространственный запрос

30

Оптимизированный пространственный запрос

18

* каждый запрос для этого теста был исполнен 1,000 раз для определения среднего времени