Эффективная обработка наследования с переопределением

У меня есть следующие две структуры данных.

Сначала , список свойств, применяемых к тройкам объектов:

Object1  Object2  Object3 Property  Value
     O1       O2       O3       P1  "abc"
     O1       O2       O3       P2  "xyz"
     O1       O3       O4       P1  "123"
     O2       O4       O5       P1  "098"

Второй , дерево наследования:

O1
    O2
        O4
    O3
        O5

Или рассматривать как отношение:

Object    Parent
    O2        O1
    O4        O2
    O3        O1
    O5        O3
    O1      null

Семантика этого заключается в том, что O2 наследует свойства от O1; О4 -из О2 и О1; О3 -от О1; и O5 -от O3 и O1, в порядке старшинства.
ПРИМЕЧАНИЕ 1:У меня есть эффективный способ выбрать всех детей или всех родителей данного объекта. В настоящее время это реализовано с левым и правым индексами, но иерархия также может работать. Сейчас это не кажется важным.
ПРИМЕЧАНИЕ 2:У меня есть тигры, которые следят за тем, чтобы столбец «Объект» всегда содержал все возможные объекты, даже если они на самом деле не должны быть там (, т.е. не имеют определенных родителей или детей ). Это позволяет использовать inner joins, а не сильно менее эффективные outer joins.

Цель:Учитывая пару (Свойство, Значение ), вернуть все тройки объектов, которые имеют это свойство с этим значением, определенным явно или унаследованным от родителя.

ПРИМЕЧАНИЕ 1:Тройка объектов (X,Y,Z)считается «родителем» тройки (A,B,C), если верно, что либо X = A, либо X is a parent of A, и то же верно для (Y,B)и (Z,C).
ПРИМЕЧАНИЕ 2:Свойство, определенное в более близком родительском элементе, «отменяет» то же свойство, определенное в более удаленном родительском элементе.
ПРИМЕЧАНИЕ 3:Когда (A,B,C )имеет двух родителей-(X1,Y1,Z1 )и (X2,Y2,Z2 ), тогда (X1,Y1,Z1 )считается «ближайшим» родителем, когда:
(a )X2 является родителем X1 или
(b )X2 = X1 и Y2 является родителем Y1,или
(c )X2 = X1 и Y2 = Y1, а Z2 является родителем Z1

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

Например, учитывая пару (P1, "abc" ), результирующий набор троек будет:

 O1, O2, O3     -- Defined explicitly
 O1, O2, O5     -- Because O5 inherits from O3
 O1, O4, O3     -- Because O4 inherits from O2
 O1, O4, O5     -- Because O4 inherits from O2 and O5 inherits from O3
 O2, O2, O3     -- Because O2 inherits from O1
 O2, O2, O5     -- Because O2 inherits from O1 and O5 inherits from O3
 O2, O4, O3     -- Because O2 inherits from O1 and O4 inherits from O2
 O3, O2, O3     -- Because O3 inherits from O1
 O3, O2, O5     -- Because O3 inherits from O1 and O5 inherits from O3
 O3, O4, O3     -- Because O3 inherits from O1 and O4 inherits from O2
 O3, O4, O5     -- Because O3 inherits from O1 and O4 inherits from O2 and O5 inherits from O3
 O4, O2, O3     -- Because O4 inherits from O1
 O4, O2, O5     -- Because O4 inherits from O1 and O5 inherits from O3
 O4, O4, O3     -- Because O4 inherits from O1 and O4 inherits from O2
 O5, O2, O3     -- Because O5 inherits from O1
 O5, O2, O5     -- Because O5 inherits from O1 and O5 inherits from O3
 O5, O4, O3     -- Because O5 inherits from O1 and O4 inherits from O2
 O5, O4, O5     -- Because O5 inherits from O1 and O4 inherits from O2 and O5 inherits from O3

Заметим, что в этом списке отсутствует тройка (O2, O4, O5 ). Это связано с тем, что свойство P1 определено явно для тройки (O2, O4, O5 ), и это предотвращает наследование тройкой этого свойства от (O1, O2, O3 ). Также обратите внимание, что тройка (O4, O4, O5 )также отсутствует. Это связано с тем, что эта тройка наследует свое значение P1="098" от (O2, O4, O5 ), потому что она является более близким родителем, чем (O1, O2, O3 ).

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

select Children1.Id as O1, Children2.Id as O2, Children3.Id as O3, tp.Property, tp.Value
from TriplesAndProperties tp

-- Select corresponding objects of the triple
inner join Objects as Objects1 on Objects1.Id = tp.O1
inner join Objects as Objects2 on Objects2.Id = tp.O2
inner join Objects as Objects3 on Objects3.Id = tp.O3

-- Then add all possible children of all those objects
inner join Objects as Children1 on Objects1.Id [isparentof] Children1.Id
inner join Objects as Children2 on Objects2.Id [isparentof] Children2.Id
inner join Objects as Children3 on Objects3.Id [isparentof] Children3.Id

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

select * from
(
    select 
        Children1.Id as O1, Children2.Id as O2, Children3.Id as O3, tp.Property, tp.Value,
        row_number() over( 
            partition by Children1.Id, Children2.Id, Children3.Id, tp.Property
            order by Objects1.[depthInTheTree] descending, Objects2.[depthInTheTree] descending, Objects3.[depthInTheTree] descending
        )
        as InheritancePriority
    from
   ... (see above)
)
where InheritancePriority = 1

. Оконная функция row_number() over(... )делает следующее :для каждой уникальной комбинации тройки объектов и свойства, она сортирует все значения по наследственному расстоянию от тройки до родителей, от которых наследуется значение, а затем я выбираю только самое первое из полученного списка значений. Аналогичного эффекта можно добиться с помощью операторов GROUP BYи ORDER BY, но я просто считаю, что оконная функция семантически чище (планы выполнения, которые они выдают, идентичны ). Дело в том, что мне нужно выбрать ближайших предков, а для этого мне нужно сгруппировать, а затем отсортировать внутри группы.

И наконец,теперь я могу просто отфильтровать набор результатов по свойствам и значениям.

Эта схема работает. Очень надежно и предсказуемо. Он оказался очень мощным для бизнес-задачи, которую он реализует.

Единственная проблема в том, что это ужасно медленно .
Кто-то может заметить, что объединение семи таблиц может замедлять работу, но на самом деле это не является узким местом.

Согласно фактическому плану выполнения, который я получаю от SQL Management Studio (, а также от SQL Profiler ), узким местом является сортировка. Проблема в том, что для того, чтобы удовлетворить мою оконную функцию, сервер должен сортировать по Children1.Id, Children2.Id, Children3.Id, tp.Property, Parents1.[depthInTheTree] descending, Parents2.[depthInTheTree] descending, Parents3.[depthInTheTree] descending, и не может быть никаких индексов, которые он может использовать, потому что значения поступают из перекрестного соединения нескольких таблиц.

РЕДАКТИРОВАТЬ:По предложению Майкла Буэна (спасибо, Майкл ), я разместил всю головоломку на sqlfiddle здесь . В плане выполнения видно, что на операцию Sort приходится 32% всего запроса, и это число будет расти с увеличением общего количества строк, поскольку все остальные операции используют индексы.

Обычно в таких случаях я бы использовал индексированное представление, но не в этом случае, потому что индексированные представления не могут содержать self -соединения, которых шесть.

Единственный способ, который я могу придумать, — это создать шесть копий таблицы Objects, а затем использовать их для объединений, тем самым обеспечивая индексированное представление.
Пришло ли время, что я буду низведен до таких писак? Наступает отчаяние.