[sql] 効率的なオーバーライドによる継承の処理



2 Answers

これを高速化するには、結合されたテーブル、たとえばjoinedresultで結合を具体化します。 これにはスペースを必要とし、ディスクに保存するという欠点があります。 しかし、それは遅い部分のインデックスを使用できるという利点があります。

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)

joinedresultに[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
Question

私は以下の2つのデータ構造を持っています。

まず 、オブジェクトトリプルに適用されるプロパティのリスト:

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 :私は、実際にそこにいなくても(すなわち、親または子が定義されていなくても)、常に「オブジェクト」列にすべてのオブジェクトが含まれていることを確認します。 これにより、効果的でないouter joinよりもむしろinner joinを使用することが可能になります。

目的は :(Property、Value)のペアを指定すると、明示的に定義された、または親から継承されたその値を持つプロパティを持つすべてのオブジェクトトリプルを返します。

注記1X = AまたはX is a parent of AいずれかX is a parent of Aあり、同じことが真である場合(X,Y,Z)トリプル(X,Y,Z)のオブジェクトはトリプル(A,B,C) 「親」とみなされる(Y,B)および(Z,C)
注2 :より親に定義されたプロパティは、より遠い親に定義された同じプロパティを "上書き"する。
注3 :(A、B、C)に2つの親 - (X1、Y1、Z1)と(X2、Y2、Z2)がある場合、(X1、Y1、Z1)
(a)X2がX1の親であるか、または
(b)X2 = X1であり、Y2がY1の親であるか、または
(c)X2 = X1かつY2 = Y1であり、Z2はZ1の親である

言い換えれば、トリプルの祖先における「近さ」は、最初にトリプルの最初の成分に基づいて定義され、次に第2の成分に、次に第3の成分に基づいて定義される。 このルールは、祖先に関してトリプルの部分的な順序を明確にします。

たとえば、(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)も存在しないことに注意してください。 これは、(O1、O2、O3)より親が近いため、トリプルは(O2、O4、O5)からP1 = "098"の値を継承するからです。

これを行う簡単な方法は次のとおりです。 まず、プロパティが定義されているすべてのトリプルに対して、すべての可能な子トリプルを選択します。

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

しかし、これはすべての話ではありません:いくつかのトリプルがいくつかの親から同じプロパティを継承する場合、このクエリは矛盾する結果をもたらすでしょう。 したがって、第2のステップは、これらの矛盾する結果のうちの1つだけを選択することである。

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

window関数row_number() over( ... )は以下のようになります:オブジェクトtripleとpropertyの固有の組み合わせごとに、値を継承している親にトリプルから先祖の距離ですべての値をソートします。結果のリストの最初のものだけを選択してください。 GROUP BYステートメントとORDER BYステートメントでも同様の効果が得られますが、ウィンドウ関数が意味論的により洗練されている(実行計画は同じです)。 要点は、祖先に最も寄与しているものを選択する必要があります。そのために、グループ内でグループ化して並べ替える必要があります。

最後に、プロパティと値で結果セットを単純にフィルタリングすることができます。

このスキームは機能します。 非常に信頼性高く予測可能です。 それは、それが実装するビジネスタスクにとって非常に強力であることが証明されています。

唯一の問題は、 それはおかしく遅いです。
1つは、7つのテーブルの結合が遅くなる可能性があることを指摘するかもしれませんが、それは実際にはボトルネックではありません。

実際の実行計画によれば、私はSQL Management Studio(SQLプロファイラだけでなく)から取得していますが、ボトルネックはソートです。 問題は、私のウィンドウ関数を満たすために、サーバーはChildren1.Id, Children2.Id, Children3.Id, tp.Property, Parents1.[depthInTheTree] descending, Parents2.[depthInTheTree] descending, Parents3.[depthInTheTree] descendingであり、値は複数のテーブルのクロス結合から来るため、使用できるインデックスはありません。

編集:マイケルBuenの提案(ありがとう、マイケル)、私はhere sqlfiddleに全体のパズルを投稿しhere 。 実行計画では、ソート操作がクエリ全体の32%を占め、他のすべての操作でインデックスを使用するため、合計行数が増えることになります。

通常、そのような場合はインデックス付きビューを使用しますが、インデックス付きビューには6個のセルフ・ジョインを含めることができないため、この場合は使用しません。

これまで考えることができる唯一の方法は、Objectsテーブルを6つ作成し、それらを結合に使用してインデックス付きのビューを有効にすることです。
私はそのような種類のハックに陥る時が来たのですか? 絶望はに設定されます。




階層的な問合せ 、つまりWITH RECURSIVE ...またはCONNECT BYようなプロプライエタリなものは、この場合はあなたの友人です。

あなたの特定の問題を解決するためのレシピは次のとおりです。休暇から出発して、ルート集計に上昇し、既に見つかったものは除外します。




Caching is the KEY to making a query faster. It reduces the calculations you must make. You want to create an index, because you want to CACHE , and save WORK . Below are two possibilities to do this.

オプション1

The SQL database sorts because of your windowing function. And you say the windowing function is too slow as it is.

I don't know how well this will work, but it might work.

Instead of sorting by a number of columns, you could try sorting by a single column - "closeness".

Let's define closeness as some abstract integer for now. Instead of your windowing function, you can instead have the following SQL:

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 closeness DESC
        )
        as InheritancePriority
    from
    ... (see above)
)
where InheritancePriority = 1

closeness can be a column defined in the TriplesAndProperties table. For each object, you can define its "closeness", as the distance it is away from the root node (O1). Then the we can define closeness(tuple) = closeness(Object1)*100+closeness(Object2)*10+closeness(Object3)

This way, the tuple with furtherest from the root is what you want.

To avoid sorting, you just have to make sure that closeness is indexed.

オプション2

I am VERY sure that this will work.

Define your TriplesAndProperties table to have the columns: Object1, Object2, Object3, Property, Value, Effective_Object1, Effective_Object2, Effective_Object3, Closeness .

Notice that here I also define closeness as a column.

When you insert/update a tuple into your table, (X,Y,Z), instead, you want to insert:

(X,Y,Z,Property,Value,X,Y,Z,0)
(X,Y,Z,Property,Value,X,Y,Z.child,1)
(X,Y,Z,Property,Value,X,Y,Z.grandchild,2)
(X,Y,Z,Property,Value,X,Y.child,Z,10)
(X,Y,Z,Property,Value,X,Y.child,Z.child,11)
(X,Y,Z,Property,Value,X,Y.child,Z.grandchild,12)
(X,Y,Z,Property,Value,X,Y.grandchild,Z,20)
(X,Y,Z,Property,Value,X,Y.grandchild,Z.child,21)
(X,Y,Z,Property,Value,X,Y.grandchild,Z.grandchild,22)
...
...

This means that instead of inserting/updating/destroying a single row in your table, you are inserting up to ~20 rows. That's not too bad.

Then your query is VERY EASY.

You just say:

SELECT * FROM
    (
    SELECT Effective_Object1, Effective_Object2, Effective_Object3, Property, Value,
        row_number() over( 
            partition by Effective_Object1, Effective_Object2, Effective_Object3, Property
            order by Closeness DESC
        ) AS InheritancePriority FROM TriplesAndProperties
     ) WHERE InheritancePriority = 1;

In this option, you have to make sure closeness is indexed, you can just index by the tuple (Effective_Object1, Effective_Object2, Effective_Object3, Property, Closeness).

In both cases, you have some amount of caching , which is data which doesn't add any additional information as such, but which caches a certain amount of calculation or work .




Related