Архив метки: Программирование

Про суррогатные ключи

Если выполнить SQL-запрос:

  1. SELECT id FROM <таблица>

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

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

Для начала, давайте подумаем, зачем вообще нужны первичные ключи. Распространённая, хоть и неправильная, точка зрения состоит в том, что первичный ключ позволяет однозначно идентифицировать строку в таблице. Люди, которые так отвечают, путают причину и следствие: на самом деле первичные ключи нужны для того, чтобы гарантировать отсутствие одинаковых строк. Когда это требование уже выполнено, можно утверждать, что первичный ключ однозначно определяет конкретную строку в таблице. Если быть чуть более строгим, то однозначно указывать на строку может как первичный ключ, так и подмножество столбцов первичного ключа, и даже столбцы, которые в первичный ключ не входят (такое часто наблюдается, в ситуациях, когда программисты бездумно создают суррогатные ключи) — всё зависит от того, как спроектирована таблица.

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

На этом моменте многие могут возразить, что «естественный» первичный ключ может содержать несколько столбцов и таскать его из родительской таблицы в дочернюю — плохая идея. Я тут одновременно и не согласен (т.к. на идеологическом уровне в этом нет ничего плохого) и согласен (т.к. понимаю, что это влечёт накладные расходы). Я пока не седовласый теоретик, поэтому в таких ситуациях советую использовать суррогатный ключ, но обязательно накладывать на потенциальный ключ ограничение уникальности. Т.о. мы одновременно защищаемся от появления в таблице семантически одинаковых строк, и получаем возможность передавать в процедуры, запросы и просто дочерние таблицы одиночное целое значение.

Безусловно, есть и другие ситуации, когда суррогатные ключи нужны. Например, в организациях есть табельные номера сотрудников — идеальный пример для использования автоинкрементных уникальных значений. Да что там говорить, каждый из вас сможет придумать множество ситуаций, где суррогатные ключи нужны. Но, прошу, не надо впихивать их в каждую таблицу!

P.S. Если вы всё-таки не можете отказаться от суррогатных ключей, то хотя бы начните делать их GUIDами.

О хранении деревьев

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

CREATE TABLE Data
    (
      ID INT NOT NULL
             IDENTITY
             PRIMARY KEY
    , Data NVARCHAR(55) NOT NULL
    )

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

ALTER TABLE dbo.Data ADD ParentID INT REFERENCES dbo.Data(ID)

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

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

Как мне кажется, оптимальным решением для хранения деревьев в БД является разделение данных как таковых и их иерархии в разные сущности. Для хранения иерархии вводится вспомогательная таблица. Эта таблица хранит все существующие пути по дереву, а не только те, которые описывают связь родитель-потомок.

CREATE TABLE DataTree
    (
      ParentID INT NOT NULL
                   REFERENCES dbo.Data ( ID )
    , ChildID INT NOT NULL
                  REFERENCES dbo.Data ( ID )
    , Level INT NOT NULL
    , PRIMARY KEY ( ParentID , ChildID )
    )

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

  • Добавить элемент в иерархическую структуру в качестве корня;
  • Удалить элемент, являющийся листом (листом называют элементы, не имеющие потомков), из иерархической структуры;
  • Задать элементу нового родителя.
    Все остальные команды, изменяющие иерархию, могут быть выражены через эти три. Рассмотрим для начала три базовые команды.

Добавление нового элемента

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

CREATE PROCEDURE DataTree_AddElementAsRoot @ElementID INT
AS
BEGIN
    SET NOCOUNT ON

    INSERT  dbo.DataTree
            ( ParentID , ChildID , Level )
    VALUES
            ( @ElementID , @ElementID , 1 )
END

Удаление листа

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

CREATE PROCEDURE dbo.DataTree_DeleteLeaf @ElementID INT
AS
BEGIN
    SET NOCOUNT ON

    IF NOT EXISTS ( SELECT
                              *
                      FROM
                              dbo.DataTree AS dt
                      WHERE
                              ( 1 = 1 )
                              AND ( dt.ParentID = @ElementID )
                              AND ( dt.Level > 1 ) )
    DELETE FROM
            dbo.DataTree
    WHERE
            ( 1 = 0 )
            OR ( ParentID = @ElementID )
            OR ( ChildID = @ElementID )
END

Задание нового родителя

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

CREATE PROCEDURE DataTree_MoveElement
    @MoveID INT
  , @ParentID INT
AS
BEGIN
    SET NOCOUNT ON

    DELETE FROM
            dbo.DataTree
    WHERE
            ( 1 = 1 )
            AND ( ChildID IN ( SELECT
                                        tc.ChildID
                                FROM
                                        dbo.DataTree AS tc
                                WHERE
                                        ( 1 = 1 )
                                        AND ( tc.ParentID = @MoveID ) ) )
            AND ( ParentID IN ( SELECT
                                         tp.ParentID
                                 FROM
                                         dbo.DataTree AS tp
                                 WHERE
                                         ( 1 = 1 )
                                         AND ( tp.ChildID = @MoveID )
                                         AND ( tp.ParentID <> tp.ChildID ) ) )

    INSERT  INTO dbo.DataTree
             (
                     ParentID
                   , ChildID
                   , Level
             )
             SELECT
                     supertree.ParentID
                   , subtree.ChildID
                   , supertree.Level + subtree.Level
             FROM
                     dbo.DataTree AS supertree
                     CROSS JOIN dbo.DataTree AS subtree
             WHERE
                     ( 1 = 1 )
                     AND ( supertree.ChildID = @ParentID )
                     AND ( subtree.ParentID = @MoveID )
END

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

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

Иерархия должностей

Иерархия должностей

С помощью описанных выше процедур мы создали записи в БД. Теперь, предположим, мы хотим узнать всех сотрудников, подчиняющихся директору IT. Для этого выполним простой запрос:

SELECT
    dt.ParentID
  , dtp.Data
  , dt.ChildID
  , dtc.Data
  , dt.Level
FROM
    dbo.DataTree AS dt
    INNER JOIN dbo.Data AS dtp
        ON ( 1 = 1 )
           AND ( dtp.ID = dt.ParentID )
    INNER JOIN dbo.Data AS dtc
        ON ( 1 = 1 )
           AND ( dtc.ID = dt.ChildID )
WHERE
    ( 1 = 1 )
    AND ( dt.ParentID <> dt.ChildID )
    AND ( dt.ParentID = 1 )
ORDER BY
    dt.Level
ParentID Data ChildID Data Level
1 IT-директор 2 Руководитель управления разработки и сопровождения ПО 2
1 IT-директор 3 Руководитель отдела методологии и анализа ПО 2
1 IT-директор 4 Руководитель управления технической поддержки 2
1 IT-директор 5 Старший программист 3
1 IT-директор 8 Руководитель группы тестирования 3
1 IT-директор 10 Аналитик 3
1 IT-директор 11 Руководитель отдела системного администрирования 3
1 IT-директор 12 Системный администратор 4
1 IT-директор 9 Тестировщик 4
1 IT-директор 6 Ведущий программист 4
1 IT-директор 7 Инженер-программист 5

В результате мы видим не только непосредственных подчинённых IT-директора, но и всю цепочку иерархий с уровнями. Если нам надо получить только непосредственных подчинённых — просто добавим ограничение на уровень:

SELECT
    dt.ParentID
  , dtp.Data
  , dt.ChildID
  , dtc.Data
  , dt.Level
FROM
    dbo.DataTree AS dt
    INNER JOIN dbo.Data AS dtp
        ON ( 1 = 1 )
           AND ( dtp.ID = dt.ParentID )
    INNER JOIN dbo.Data AS dtc
        ON ( 1 = 1 )
           AND ( dtc.ID = dt.ChildID )
WHERE
    ( 1 = 1 )
    AND ( dt.ParentID <> dt.ChildID )
    AND ( dt.ParentID = 1 )
    AND ( dt.Level = 2 )
ORDER BY
    dt.Level
ParentID Data ChildID Data Level
1 IT-директор 2 Руководитель управления разработки и сопровождения ПО 2
1 IT-директор 3 Руководитель отдела методологии и анализа ПО 2
1 IT-директор 4 Руководитель управления технической поддержки 2

Самое интересное в этой структуре то, что все уровни относительны. Т.е.относительно IT-директора тестировщик находится на четвёртом уровне вложенности, а вот относительно руководителя группы тестирования на втором:

SELECT
    dt.ParentID
  , dtp.Data
  , dt.ChildID
  , dtc.Data
  , dt.Level
FROM
    dbo.DataTree AS dt
    INNER JOIN dbo.Data AS dtp
        ON ( 1 = 1 )
           AND ( dtp.ID = dt.ParentID )
    INNER JOIN dbo.Data AS dtc
        ON ( 1 = 1 )
           AND ( dtc.ID = dt.ChildID )
WHERE
    ( 1 = 1 )
    AND ( dt.ParentID <> dt.ChildID )
    AND ( dt.ParentID = 8 )
    AND ( dt.Level = 2 )
ORDER BY
    dt.Level
ParentID Data ChildID Data Level
8 Руководитель группы тестирования 9 Тестировщик 2

Определить цепочку руководителей тоже не составит труда:

SELECT
    dt.ParentID
  , dtp.Data
  , dt.ChildID
  , dtc.Data
  , dt.Level
FROM
    dbo.DataTree AS dt
    INNER JOIN dbo.Data AS dtp
        ON ( 1 = 1 )
           AND ( dtp.ID = dt.ParentID )
    INNER JOIN dbo.Data AS dtc
        ON ( 1 = 1 )
           AND ( dtc.ID = dt.ChildID )
WHERE
    ( 1 = 1 )
    AND ( dt.ParentID <> dt.ChildID )
    AND ( dt.ChildID = 7 )
ORDER BY
    dt.Level
ParentID Data ChildID Data Level
6 Ведущий программист 7 Инженер-программист 2
5 Старший программист 7 Инженер-программист 3
2 Руководитель управления разработки и сопровождения ПО 7 Инженер-программист 4
1 IT-директор 7 Инженер-программист 5

Как по мне, простота выборки с лихвой компенсирует всю «сложность» создания иерархии. Если вы не согласны — с радостью поспорю в комментариях.

P.S. Также особенностью этого способа хранения деревьев является встроенная поддержка корректности. За счёт ограничения первичного ключа не удастся замкнуть дерево в цикл.

Про GUID-ы и INT-ы

Последнее время я часто думаю о том, чтобы начать использовать в новых таблицах в качестве суррогатного первичного ключа не привычные большинству целые числа INT IDENTITY (1,2,3, …), а глобальные уникальные идентификаторы GUID (5e09962e-1de5-48a6-a71e-fb9c5ec58b01, 5aeae3ec-fccf-4739-bde6-09d3577fa121, …). Большинств коллег с некоторым недопониманием и вялым сопротивлением отнеслись к моей инициативе, поэтому я решил написать этот пост в котором расскажу о плюсах данного подхода и совсем немного (я же всё-таки предвзят) упомяну о минусах.

Начну с минусов

Даже визуально заметно, что GUID гораздо «длиннее» чем число. Это приводит сразу к двум проблемам.

  • Во-первых, GUID-ы тяжело использовать человеку, т.е. просто написать список идентификаторов в секции WHERE по памяти уже не удастся, придётся копировать.
  • Во-вторых, GUID действительно занимает в четыре раза больше места, чем INT. При простом хранении данных в базе это не так уж страшно, но может стать проблемой, когда возникнет необходимость добавить очередное поле в индекс. Мой, пусть не очень большой, но всё-таки опыт подсказывает, что «пухлые» индексы возникают в основном в ненормализованных БД, так что вторая проблема на самом деле вызвана не столько GUID-ами как таковыми, сколько неправильными архитектурными решениями.
  • В-третьих, почти все коллеги обращают внимание на тот факт, что таблицу нельзя упорядочить по столбцу с GUID-ам, получив тем самым псевдовремя. На это замечание у меня сразу два возражения: во-первых, псевдовремя порочно по сути своей (всегда можно использовать настоящее время), во-вторых, столбцу с псевдоключом можно задать значение по умолчанию равное NEWSEQUENTIALID(), тогда до перезагрузки сервера значения в данном столбце таблицы будут возрастать.

Теперь давайте о плюсах

GUID не зря называют глобальным уникальным идентификатором. Его значения статистически уникальны.

  • Т.е. мы легко можем создавать новые идентификаторы без непосредственного доступа к базе (например, в мобильном приложении) и быть уверенными, что их вставка не приведёт к конфликтам (при этом, конечно, нельзя использовать полученные значения для вставки в столбец со значением по умолчанию NEWSEQUENTIALID, но на практике это нужно относительно редко).
  • Это же свойство статистической уникальности приводит к тому, что каждый новый GUID выглядит случайным, что автоматически усложняет и делает практически невозможным подбор корректных значений в URL-адресах, используемых для подтверждения регистрации, восстановлений пароля и т.п.
  • Третьим несомненным плюсом является огромное (можно для простоты считать, что бесконечное) количество различных возможных значений. Всем кажется, что типа INT хватит всем и навсегда. Я тоже так думал, ровно до того момента, пока не заметил, как коллеги три дня искали ошибку, вызванную тем, что в таблице банально закончились новые идентификаторы.
  • Ну и наконец, ещё одно полезное свойство глобальной уникальности GUID-ов, которое окончательно склонило меня к их использованию. Если у нас в таблице t2 есть два столбца t2ID, являющийся суррогатным ключом таблицы t2, и t1ID, ссылающийся на суррогатный ключ таблицы t1, то вполне можно допустить обидную опечатку, написав в предикате соединения t2ID вместо t1ID или наоборот (я, например, часто так ошибаюсь). В случае использования INT-ов, такой очевидно ошибочный JOIN скорее всего даст на выходе непустой набор строк. Невнимательный программист не только не заметит ошибку, но и вставит полученный набор данных в какую-нибудь другую таблицу. Результат предсказать довольно тяжело, но я точно могу сказать, что ни к чему хорошему это не приведёт. Если же в столбцах хранились GUID, даже самый невнимательный программист удивится, почему простой JOIN даёт пустой набор строк. В результате в коде будет на одну ошибку меньше. По-моему, ошибку всегда лучше предотвратить, если есть такая возможность.

Как всегда, если у вас есть замечания, предложения, или вы просто хотите поспорить — милости прошу в комментарии.

P.S. Уже после публикации мне подсказали ещё несколько плюсов:

  • Говорят, что GUID-ы также незаменимы при репликации БД, но тут у меня опыта нет, поэтому утверждать не берусь.
  • Часто бывают ситуации, когда используются значения по умолчанию. Например, каждой новой заявке в техподдрежку по умолчанию присваивается статус «Ожидает назначения специалисту» (ID этого статуса 0). Вся система стабильно работает, но ровно до того момента, пока руководство не решит, что необходим новый статус по умолчанию (например, «Заявка создана» с ID 4). На первый взгляд доработать систему просто, надо в параметрах по умолчанию заменить 0 на 4, но довольно быстро вы поймёте, что значений 0 у вас в базе огромное количество, и понять, какое из них относится к заявкам, а какое к каким-то другим бизнес-процессам очень тяжело.

О вреде NULL

Давайте рассмотрим следующую ситуацию: у нас есть информация о поставщиках (название и город) и о покупателях (ФИО и город).

CREATE TABLE #Vendor
    (
      Name NVARCHAR(15)
    , City NVARCHAR(15)
    )
CREATE TABLE #Customer
    (
      Name NVARCHAR(15)
    , City NVARCHAR(15)
    )

Есть в Моске одна компания «Рога и копыта» (далее по тексту Р&К):

INSERT  #Vendor ( Name , City ) VALUES ( 'Рога и копыта' , 'Москва' )

Эта компания хочет начать экспансию в другие регионы (не в Москву), и при этом готова работать с кем угодно, главное, чтобы не из Киева. Понятно, что такие условия во многом выдуманные и бессмысленные (ну а какими ещё им быть, если они основаны на политических мотивах), но для нашего рассмотрения они подходят идеально. Запрос для поиска подходящих клиентов тривиален:

SELECT
    v.Name AS 'VendorName'
  , c.Name AS 'ClientName'
FROM
    #Vendor AS v
  , #Customer AS c
WHERE
    ( v.Name = 'Рога и копыта' )
    AND (
          ( v.City <> c.City )
          OR ( c.City <> 'Киев' )
        )

Рассмотрим одного очень богатого кочевника Тыгындыка:

INSERT  #Customer ( Name , City ) VALUES ( 'Тыгындык' , NULL )

Место его жительства нам не известно. Но давайте проверим, является ли он потенциальным клиентом для Р&К: если он живёт в Киеве, то является потенциальным клиентом по первому условию (v.City <> c.City), если же он живёт в любом(!) другом городе, то он является потенциальным клиентом по второму условию (c.City <> ‘Киев’). Тем не менее, указанный выше тривиальный запрос не вернёт нам Тыгындыка.
Всё дело в том, как работает трёхзначная логика:

Условие Результат Пояснение
v.City <> c.City UNKNOWN Любое сравнение с NULL всегда UNKNOWN, потому что NULL трактуется, как «неизвестно»
c.City <> ‘Киев’ UNKNOWN Любое сравнение с NULL всегда UNKNOWN, потому что NULL трактуется, как «неизвестно»

( v.City <> c.City )

OR ( c.City <> ‘Киев’ )

UNKNOWN Так как обе логические величины UNKNOWN, то и OR над ними тоже UNKNOWN.

( v.Name = ‘Рога и копыта’ )

AND ( ( v.City <> c.City ) OR ( c.City <> ‘Киев’ ) )

UNKNOWN Если немного подумать, станет очевидно, что TRUE И UNKNOWN тоже UNKNOWN

То есть по строгим правилам трёхзначной логики, Тыгындык не является потенциальным клиентам для Р&К, но в тоже самое время выше я показал, что с точки зрения общечеловеческой логики он вполне подходит под заданные критерии.
Т.о. бизнес потерял клиента только потому, что кто-то не написал NOT NULL при объявлении таблицы.

Разбиение полигонов

На работе я постоянно сталкиваюсь со множеством интересных задач. Недавно мне понадобилось построить тепловую карту практически на чистом SQL. Не знаю оптимально ли моё решение или нет, но я поступил следующим образом:

  1. Разбил участок карты на множество маленьких полигонов;
  2. Для каждого полигона вычислил «теплоту»;
  3. При отображении на клиенте каждый маленький полигон закрашивается своим цветом, зависящим от вычисленной на втором шаге «теплоты».

В результате на клиенте можно наблюдать подобные картины:

Тепловая карта

Тепловая карта

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

  1. SET QUOTED_IDENTIFIER ON
  2. SET ANSI_NULLS ON
  3. GO
  4. — =============================================
  5. — Author:          Горьков А.Г.
  6. — Description:     Разбивает заданный полигон на множество «квадратных» полигонов
  7. — =============================================
  8. CREATE FUNCTION dbo.fnT_PolygonToGrid
  9.     (
  10.       @Polygon GEOMETRY — Обрабатываемый полигон
  11.     , @CellCount INT— Количество «квадратов» в результате разбиения
  12.     , @PartitionType INT  — 0 — в результате разбиения и по ширине, и по высоте будет НЕ БОЛЕЕ чем @CellCount «квадратов» 1 —  в результате разбиения и по ширине, и по высоте будет НЕ МЕНЕЕ чем @CellCount «квадратов»
  13.     )
  14. RETURNS @Grid TABLE
  15.     (
  16.       Cell GEOMETRY NOT NULLa
  17.     )
  18. AS
  19. BEGIN
  20.        — Получаем описывающий прямоугольник для участка
  21.     DECLARE @EnvelopePolygon GEOMETRY = @Polygon.STEnvelope()
  22.     DECLARE @EnvelopeWidth FLOAT = @EnvelopePolygon.STPointN(3).STX  @EnvelopePolygon.STPointN(1).STX
  23.     DECLARE @EnvelopeHeight FLOAT = @EnvelopePolygon.STPointN(3).STY  @EnvelopePolygon.STPointN(2).STY
  24.        — Получаем левый нижний угол описывающего прямоугольника
  25.     DECLARE @xStart FLOAT = @EnvelopePolygon.STPointN(1).STX
  26.     DECLARE @yStart FLOAT = @EnvelopePolygon.STPointN(1).STY
  27.        — Вычисляем шаги по широте и долготе
  28.     DECLARE @CellWidth FLOAT = @EnvelopeWidth / @CellCount
  29.     DECLARE @CellHeight FLOAT = @EnvelopeHeight / @CellCount
  30.        — Таблица с результирующей сеткой
  31.     DECLARE @RAWGrid TABLE ( geom GEOMETRY )
  32.        — Отдельная таблица для мультиполигонов, получившихся при разбиении
  33.     DECLARE @MultiPolygons TABLE
  34.         (
  35.           MultiPolygon GEOMETRY
  36.         )
  37.     DECLARE @MultiPolygon GEOMETRY= NULL
  38.     DECLARE @i INT = NULL
  39.        /*
  40.        В зависимости от типа разбиения подбираем длину стороны ячейки
  41.        */
  42.     IF @PartitionType = 1
  43.     BEGIN
  44.         IF @CellHeight < @CellWidth
  45.             SET @CellWidth = @CellHeight
  46.         ELSE
  47.             SET @CellHeight = @CellWidth
  48.     END
  49.     ELSE
  50.     BEGIN
  51.         IF @CellHeight > @CellWidth
  52.             SET @CellWidth = @CellHeight
  53.         ELSE
  54.             SET @CellHeight = @CellWidth
  55.     END
  56.        /*
  57.        Заполняем таблицу равномерной сеткой
  58.        В результате такого разбиения в ячейках могут присутствовать не только
  59.        обычные полигоны, но и мультиполигоны, с которыми мы разберемся ниже
  60.     */
  61.     DECLARE
  62.         @x INT = 0
  63.       , @y INT = 0
  64.     WHILE @y * @CellHeight <= @EnvelopeHeight
  65.     BEGIN
  66.         WHILE @x * @CellWidth <= @EnvelopeWidth
  67.         BEGIN
  68.             INSERT  INTO @RAWGrid
  69.             VALUES
  70.                     ( Geometry::STPolyFromText(‘POLYGON((‘ + CAST(@xStart + ( @x * @CellWidth ) AS VARCHAR(32)) + ‘ ‘ + CAST(@yStart + ( @y * @CellHeight ) AS VARCHAR(32)) + ‘,’ + CAST(@xStart + ( ( @x + 1 ) * @CellWidth ) AS VARCHAR(32)) + ‘ ‘ + CAST(@yStart + ( @y * @CellHeight ) AS VARCHAR(32)) + ‘,’ + CAST(@xStart + ( ( @x + 1 ) * @CellWidth ) AS VARCHAR(32)) + ‘ ‘ + CAST(@yStart + ( ( @y + 1 ) * @CellHeight ) AS VARCHAR(32)) + ‘,’ + CAST(@xStart + ( @x * @CellWidth ) AS VARCHAR(32)) + ‘ ‘ + CAST(@yStart + ( ( @y + 1 ) * @CellHeight ) AS VARCHAR(32)) + ‘,’ + CAST(@xStart + ( @x * @CellWidth ) AS VARCHAR(32)) + ‘ ‘ + CAST(@yStart + ( @y * @CellHeight ) AS VARCHAR(32)) + ‘))’ , 4326) )
  71.             SET @x = @x + 1
  72.         END
  73.         SET @x = 0
  74.         SET @y = @y + 1
  75.     END
  76.        /*
  77.        Сохраняем обычные полигоны в итоговую таблицу
  78.     */
  79.     INSERT  INTO @Grid
  80.             SELECT
  81.                 geom.STIntersection(@Polygon)
  82.             FROM
  83.                 @RAWGrid
  84.             WHERE
  85.                 ( 1 = 1 )
  86.                 AND ( geom.STIntersection(@Polygon).STGeometryType() = ‘Polygon’ )
  87.        /*
  88.        Сохраняем мультиполигоны во временную таблицу
  89.     */
  90.     INSERT  INTO @MultiPolygons
  91.             SELECT
  92.                 geom.STIntersection(@Polygon)
  93.             FROM
  94.                 @RAWGrid
  95.             WHERE
  96.                 ( 1 = 1 )
  97.                 AND ( geom.STIntersection(@Polygon).STGeometryType() = ‘MultiPolygon’ )
  98.        /*
  99.        Разбиваем мультиполигоны на обычные полигоны и переносим их в итоговую тбалицу
  100.        */
  101.     DECLARE c CURSOR
  102.     FOR
  103.     SELECT
  104.         @MultiPolygon
  105.     FROM
  106.         @MultiPolygons
  107.     OPEN c
  108.     FETCH c INTO @MultiPolygon
  109.     WHILE @@FETCH_STATUS = 0
  110.     BEGIN
  111.         SET @i = 1
  112.         WHILE @i <= @MultiPolygon.STNumGeometries()
  113.         BEGIN
  114.             INSERT  INTO @Grid
  115.                     ( Cell )
  116.             VALUES
  117.                     ( @MultiPolygon.STGeometryN(@i) )
  118.             SET @i = @i + 1
  119.         END
  120.         FETCH NEXT FROM c INTO @MultiPolygon
  121.     END
  122.     CLOSE c
  123.     DEALLOCATE c
  124.     RETURN
  125. END
  126. GO

Пожалуй, наиболее интересный момент здесь, это параметр — @PartitionType. Он показывает, как именно надо разбивать исходный полигон на части: чтобы в результате разбиения по ширине и высоте было НЕ БОЛЕЕ или НЕ МЕНЕЕ, чем @CellCount полигонов. Проще всего разницу пояснить на конкретном примере:

Виды разбиения

Виды разбиения

В первом случае @PartitionType=0, а во втором @PartitionType=1.