有效地覆盖处理继承

Question

我有以下两种数据结构.

首先,应用于对象三元组的属性列表:

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:我有一种有效的方法来选择给定对象的所有孩子或所有父母.目前这是使用左右索引实现的,但hierarchyid也可以工作.这现在看起来并不重要.
注2:我有触发器确保"对象"列始终包含所有可能的对象,即使它们实际上不必存在(即没有定义父或子).这使得可以使用inner joins而不是效率低得多的outer joins.

目标是:给定一对(Property,Value),返回具有该属性的所有对象三元组,该属性具有显式定义或从父级继承.

注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)也不存在.这是因为该三重从(O2,O4,O5)继承其值P1 ="098",因为它比(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,并且它不能使用任何索引,因为这些值来自多个表的交叉连接.

编辑:根据迈克尔·布恩的建议(谢谢你,迈克尔),我把整个谜题发布到了这里.可以在执行计划中看到,排序操作占整个查询的32%,并且随着总行数的增加而增长,因为所有其他操作都使用索引.

通常在这种情况下我会使用索引视图,但在这种情况下不会,因为索引视图不能包含自连接,其中有六个.

到目前为止,我能想到的唯一方法是创建Objects表的六个副本,然后将它们用于连接,从而启用索引视图.
是时候我会被沦为那种黑客吗？绝望开始了.

Answer 1

您可以通过在索引表中具体化联接（例如 joinresult）来加快速度。这样做的缺点是需要空间并保存到磁盘。但它的优点是能够对慢速部分使用索引。

insert into joinedresult
select Children1.Id as O1, Children2.Id as O2, Children3.Id as O3, tp.Property, tp.Value,Objects1.[depthInTheTree] as O1D,Objects2.[depthInTheTree] as O2D,Objects3. depthInTheTree]  as O3D from  ... (see above)

确保 joinresult 在 [O1,O2,O3,Property,O1D,O2D,O3D] 上有索引，并在运行前清除它。然后

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 O1D descending, O2D descending, O3D descending
    )
    as InheritancePriority
    from joinedresult
)
where InheritancePriority = 1