У меня есть две следующие структуры данных.
Первый, список свойств, применяемых к тэгам объектов:
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; O4 - из O2 и O1; O3 - от O1; и O5 - из O3 и O1 в этом порядке приоритета.
ПРИМЕЧАНИЕ 1. У меня есть эффективный способ выбрать всех детей или всех родителей данного объекта. В настоящее время это выполняется с левыми и правыми индексами, но иерархия также может работать. Сейчас это не кажется важным.
ПРИМЕЧАНИЕ 2: У меня есть тигр, чтобы убедиться, что столбец "Объект" всегда содержит все возможные объекты, даже если они действительно не должны быть там (т.е. Не имеют родителя или детей). Это позволяет использовать inner join, а не значительно меньше effecient outer join s.
Цель: если задана пара (Свойство, значение), верните все тройки объектов, у которых есть это свойство с таким значением, которое явно определено или унаследовано от родителя.
ПРИМЕЧАНИЕ 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( ... ) выполняет следующие действия: для каждой уникальной комбинации объектов triple и property она сортирует все значения на расстоянии предков от тройки до родителей, на которые наследуется значение, а затем я выбираю только самый первый из полученных в результате список значений.
Подобный эффект может быть достигнут с помощью операторов GROUP BY и ORDER BY, но я просто обнаруживаю, что функция окна семантически очищается (планы выполнения, которые они дают, идентичны).
Дело в том, что мне нужно выбрать ближайшего из своих предшественников, и для этого мне нужно сгруппировать, а затем отсортировать внутри группы.
И, наконец, теперь я могу просто фильтровать набор результатов с помощью свойства и значения.
Эта схема работает. Очень надежно и предсказуемо. Это оказалось очень мощным для бизнес-задачи, которую он реализует.
Единственная проблема: она awfuly медленно.
Можно отметить, что объединение семи таблиц может замедлить работу, но на самом деле это не узкое место.
В соответствии с фактическим планом выполнения, который я получаю от SQL Management Studio (а также SQL Profiler), узким местом является сортировка.
Проблема в том, что для удовлетворения моей оконной функции сервер должен сортировать по Children1.Id, Children2.Id, Children3.Id, tp.Property, Parents1.[depthInTheTree] descending, Parents2.[depthInTheTree] descending, Parents3.[depthInTheTree] descending, и не может быть никаких индексов, которые он может использовать, потому что значения исходят от кросс-соединения нескольких таблиц.
EDIT: По предложению Майкла Буэна (спасибо, Майкл), я опубликовал всю загадку для sqlfiddle здесь, В плане выполнения можно видеть, что операция Sort учитывает 32% всего запроса, и это будет расти с количеством полных строк, поскольку все остальные операции используют индексы.
Обычно в таких случаях я бы использовал индексированное представление, но не в этом случае, потому что индексированные представления не могут содержать самосоединения, из которых шесть.
Единственный способ, о котором я могу думать до сих пор, - создать шесть экземпляров таблицы Objects, а затем использовать их для соединений, что позволит индексировать представление.
Пришло ли время, что я буду сведен к таким хакам? Наступает отчаяние.
