Как эффективно объединить две иерархии в SQL Server?

Question

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

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

Обязательно, обработка, которая должна быть выполнена, будет выглядеть как-токак это:

For each row, RS, in the staging table:
    If there is not already a row with the same Id as RS in the main table:
         Find the parent, PS, of the staging row
         Find the row, PM, in the main table that has the same node ID as PS
         Create a new child, RM of row PM
         Set PM's ID equal to the ID of RS

Важно, что этот подход будет работать только в том случае, если дерево в промежуточной таблице отсортировано / пройдено в порядке широты - это так, что при обнаружении RS гарантируется, что егоу родительского PS уже есть соответствующая строка в главной таблице.

До сих пор единственный способ добиться этого на SQL-сервере - это навести курсор на промежуточную таблицу (которая уже отсортирована) и вызватьхранимая процедура для каждой строки, которая по существу выполняет именно то, что описано выше, завершается SELECT MAX (), чтобы найти наивысший иерархический объект, который уже существует как дочерний элемент PM, чтобы дочерний элемент мог быть добавлен уникальным образом.

Это очень неэффективный подход и слишком медленный для моих целей.Есть ли лучший способ?

Для фона, это своего рода проверка осуществимости, которую я делаю.Мне нужно выяснить, могу ли я быстро выполнить эту операцию внутри SQL Server.Если окажется, что я не могу, мне придется сделать это по-другому, за пределами базы данных.Объединение деревьев присуще (на самом деле, в некотором смысле, является ) проблемной областью, поэтому структурирование данных по-разному или более широкое представление и попытка каким-либо образом избежать выполнения этой операции не являетсяопция.

Обновление

По запросу, вот конкретный пример.

Таблицы "staging" и "main" имеют одинаковые два столбца:

   hierarchy_id of type hierarchyid
   node_id of type bigint

Исходное содержание

основное:

 hierarchy_id    node_id
 /1/             1
 /1/1/           2
 /1/2/           3
 /1/3/           4

постановка:

 hierarchy_id    node_id
 /1/             1
 /1/1/           3
 /1/2/           5
 /1/1/1/         6

Желаемое содержимое

main:

 hierarchy_id    node_id
 /1/             1
 /1/1/           2
 /1/2/           3
 /1/3/           4
 /1/4/           5
 /1/2/1/         6

Обратите внимание, что узел в промежуточной таблице сierarchy_id / 1/1 / соответствует узлу hiearchy_id / 1/2 / в целевой таблице (именно поэтому важен идентификатор_узла - нельзя просто скопировать значения имя_иерархии).Также обратите внимание, что новый узел с node_id 6 добавляется в качестве дочернего элемента правильного родителя, а тот с node_id 3, поэтому важен иерархический идентификатор - он определяет древовидную структуру (отношения родитель / потомок) для любых новых узлов.Любое решение должно учитывать оба аспекта.

Answer 1

Моделирование вашей иерархии таким образом приведет к проблемам.Столбецierarchy_id нарушает первую нормальную форму, и процесс слияния будет склонен к обновлению аномалий, если вы не сериализуете / не получите доступ к узкому месту.

Вы должны рассмотреть таблицу только с node_id и parent_id, посмотрите, как онатривиализирует вашу проблему слияния

node_id   parent_id
1         NULL
2         1
3         2
4         3

node_id   parent_id
1         NULL
3         1
5         2
6         1

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

Answer 2

Мы работаем над продуктом, который требует аналогичного решения. После долгих исследований этого и других подходов мы пришли к выводу, что метод иерархии не для нас.

Итак, как прямой ответ на ваш вопрос: лучшего способа сделать это с помощью этого подхода нет.

Взгляните на Модели вложенных множеств и Модель списка смежности .

Оба из них являются гораздо более элегантными и эффективными решениями для этой конкретной задачи проектирования.

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

Answer 3

Вот решение, которое перемещает строки от источника @S к цели @T по одному уровню за раз.Чтобы упростить задачу, я добавил корневой узел, чтобы всегда иметь родительский подарок, который используется при создании нового HierarcyID.

Я никогда не использовал HierarchyID, поэтому могут быть абсолютно более эффективные способы сделать это, но он долженпо крайней мере, быть более эффективным, чем делать это по одной строке за раз.

-- Target table
declare @T table 
(
  hierarchy_id hierarchyid primary key,
  node_id bigint
)

insert into @T values
('/',             0), -- Needed for simplicity
('/1/',           1),
('/1/1/',         2),
('/1/2/',         3),
('/1/3/',         4)

-- Source table
declare @S table 
(
  hierarchy_id hierarchyid primary key,
  node_id bigint
)

insert into @S values
('/',               0),
('/1/',             1),
('/1/1/',           3),
('/1/2/',           5),
('/1/1/1/',         6)

declare @lvl int = 1

-- Move rows from @S to @T for each level
while exists(select *
             from @S
             where hierarchy_id.GetLevel() = @lvl)
begin

  insert into @T
  select T.hierarchy_id.GetDescendant(C.MaxID, null),
         S.node_id
  from (select S1.node_id, S2.node_id as ParentID
        from @S as S1
          inner join @S as S2
            on S1.hierarchy_id.GetAncestor(1) = S2.hierarchy_id
        where S1.hierarchy_id.GetLevel() = @lvl and
              S1.node_id not in (select node_id
                                 from @T)
       ) as S
    inner join @T as T
      on S.ParentID = T.node_id
    outer apply (select max(hierarchy_id) as MaxID
                 from @T as T2
                 where T.hierarchy_id = T2.hierarchy_id.GetAncestor(1)) as C       

    set @lvl = @lvl + 1
end

select *, hierarchy_id.ToString()
from @T
where hierarchy_id <> hierarchyid::GetRoot()  

Результат:

hierarchy_id  node_id  (No column name)
------------  -------  ----------------
0x58          1        /1/
0x5AC0        2        /1/1/
0x5B40        3        /1/2/
0x5B56        6        /1/2/1/
0x5BC0        4        /1/3/
0x5C20        5        /1/4/