Gestion de l'inheritance avec annulation efficace

J'ai 3 réponses possibles.

Le violon sql pour votre question est ici: http://sqlfiddle.com/#!3/7c7a0/3/0

Le violon sql pour ma réponse est ici: http://sqlfiddle.com/#!3/5d257/1

Avertissements:

1. L'Analyseur de requêtes n'est pas suffisant . J'ai remarqué qu'un certain nombre de réponses ont été rejetées car leurs plans de requête sont plus chers que la requête d'origine. L'parsingur est seulement un guide. Selon l'set de données, le matériel et le cas d'utilisation réels, les requêtes plus coûteuses peuvent renvoyer des résultats plus rapidement que les requêtes less coûteuses. Vous devez tester dans votre environnement.
2. L'parsingur de requêtes est inefficace – même si vous trouvez un moyen de supprimer l'étape la plus coûteuse d'une requête, cela ne fait souvent aucune différence pour votre requête.
3. Les modifications apscopes aux requêtes seules atténuent rarement les problèmes de schéma / design . Certaines réponses ont été rejetées car elles impliquaient des modifications au niveau du schéma, telles que des triggersurs et des tables supplémentaires. Les requêtes complexes qui résistent à l'optimization sont un signe fort que le problème est avec la design sous-jacente ou avec mes attentes. Vous pouvez ne pas l'aimer, mais vous devrez peut-être accepter que le problème n'est pas résoluble au niveau de la requête.
4. La vue indexée ne peut pas contenir de clause row_number () / partitition – Le fait de contourner le problème d'auto-jointure en créant six copys d'objects n'est pas suffisant pour vous permettre de créer la vue indexée que vous avez suggérée. Je l'ai essayé dans ce sqlfiddle . Si vous supprimez le commentaire de la dernière instruction "create index", vous obtenez une erreur car votre vue "contient une fonction de classment ou de window d'agrégation".

Réponses fonctionnelles:

1. Left Join au lieu de row_number () – Vous pouvez utiliser une requête qui utilise des jointures à gauche pour exclure les résultats qui ont été redéfinis plus bas dans l'arborescence. Supprimer le "order by" finalement de cette requête supprime en fait le sort qui vous a affligé! Le plan d'exécution de cette requête est toujours plus cher que l'original, mais consultez la clause de non-responsabilité n ° 1 ci-dessus.
2. Vue indexée pour une partie de la requête – En utilisant de la magie de requête sérieuse (basée sur cette technique ), j'ai créé une vue indexée pour une partie de la requête. Cette vue peut être utilisée pour améliorer la requête de question initiale ou répondre # 1.
3. Actualiser dans un tableau bien indexé – Quelqu'un d'autre a suggéré cette réponse, mais ils pourraient ne pas l'avoir bien expliqué. À less que votre jeu de résultats ne soit très volumineux ou que vous n'effectuiez des mises à jour très fréquentes des tables sources, actualiser les résultats d'une requête et utiliser un triggersur pour les maintenir à jour est une excellente façon de contourner ce problème. Une fois que vous avez créé une vue pour votre requête, il est assez facile de tester cette option. Vous pouvez réutiliser la réponse n ° 2 pour accélérer le triggersment, puis l'améliorer au fil du time. (Vous parlez de créer six copys de vos tables, essayez ceci en premier.Il garantit que la performance pour le select que vous aimez sera aussi bonne que possible.)

Voici la partie schéma de ma réponse de sqlfiddle:

 Create Table Objects ( Id int not null identity primary key, LeftIndex int not null default 0, RightIndex int not null default 0 ) alter table Objects add ParentId int null references Objects CREATE TABLE TP ( Object1 int not null references Objects, Object2 int not null references Objects, Object3 int not null references Objects, Property varchar(20) not null, Value varchar(50) not null ) insert into Objects(LeftIndex, RightIndex) values(1, 10) insert into Objects(ParentId, LeftIndex, RightIndex) values(1, 2, 5) insert into Objects(ParentId, LeftIndex, RightIndex) values(1, 6, 9) insert into Objects(ParentId, LeftIndex, RightIndex) values(2, 3, 4) insert into Objects(ParentId, LeftIndex, RightIndex) values(3, 7, 8) insert into TP(Object1, Object2, Object3, Property, Value) values(1,2,3, 'P1', 'abc') insert into TP(Object1, Object2, Object3, Property, Value) values(1,2,3, 'P2', 'xyz') insert into TP(Object1, Object2, Object3, Property, Value) values(1,3,4, 'P1', '123') insert into TP(Object1, Object2, Object3, Property, Value) values(2,4,5, 'P1', '098') create index ix_LeftIndex on Objects(LeftIndex) create index ix_RightIndex on Objects(RightIndex) create index ix_Objects on TP(Property, Value, Object1, Object2, Object3) create index ix_Prop on TP(Property) GO ---------- QUESTION ADDITIONAL SCHEMA -------- CREATE VIEW TPResultView AS Select O1, O2, O3, Property, Value 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.LeftIndex desc, Objects2.LeftIndex desc, Objects3.LeftIndex desc ) as Idx from tp -- Select corresponding objects of the sortingple inner join Objects as Objects1 on Objects1.Id = tp.Object1 inner join Objects as Objects2 on Objects2.Id = tp.Object2 inner join Objects as Objects3 on Objects3.Id = tp.Object3 -- Then add all possible children of all those objects inner join Objects as Children1 on Children1.LeftIndex between Objects1.LeftIndex and Objects1.RightIndex inner join Objects as Children2 on Children2.LeftIndex between Objects2.LeftIndex and Objects2.RightIndex inner join Objects as Children3 on Children3.LeftIndex between Objects3.LeftIndex and Objects3.RightIndex ) as x WHERE idx = 1 GO ---------- ANSWER 1 SCHEMA -------- CREATE VIEW TPIntermediate AS select tp.Property, tp.Value , Children1.Id as O1, Children2.Id as O2, Children3.Id as O3 , Objects1.LeftIndex as PL1, Objects2.LeftIndex as PL2, Objects3.LeftIndex as PL3 , Children1.LeftIndex as CL1, Children2.LeftIndex as CL2, Children3.LeftIndex as CL3 from tp -- Select corresponding objects of the sortingple inner join Objects as Objects1 on Objects1.Id = tp.Object1 inner join Objects as Objects2 on Objects2.Id = tp.Object2 inner join Objects as Objects3 on Objects3.Id = tp.Object3 -- Then add all possible children of all those objects inner join Objects as Children1 WITH (INDEX(ix_LeftIndex)) on Children1.LeftIndex between Objects1.LeftIndex and Objects1.RightIndex inner join Objects as Children2 WITH (INDEX(ix_LeftIndex)) on Children2.LeftIndex between Objects2.LeftIndex and Objects2.RightIndex inner join Objects as Children3 WITH (INDEX(ix_LeftIndex)) on Children3.LeftIndex between Objects3.LeftIndex and Objects3.RightIndex GO ---------- ANSWER 2 SCHEMA -------- -- Partial calculation using an indexed view -- Circumvented the self-join limitation using a black magic technique, based on -- http://jmkehayias.blogspot.com/2008/12/creating-indexed-view-with-self-join.html CREATE TABLE dbo.multiplier (i INT PRIMARY KEY) INSERT INTO dbo.multiplier VALUES (1) INSERT INTO dbo.multiplier VALUES (2) INSERT INTO dbo.multiplier VALUES (3) GO CREATE VIEW TPIndexed WITH SCHEMABINDING AS SELECT tp.Object1, tp.object2, tp.object3, tp.property, tp.value, SUM(ISNULL(CASE Mi WHEN 1 THEN Objects.LeftIndex ELSE NULL END, 0)) as PL1, SUM(ISNULL(CASE Mi WHEN 2 THEN Objects.LeftIndex ELSE NULL END, 0)) as PL2, SUM(ISNULL(CASE Mi WHEN 3 THEN Objects.LeftIndex ELSE NULL END, 0)) as PL3, SUM(ISNULL(CASE Mi WHEN 1 THEN Objects.RightIndex ELSE NULL END, 0)) as PR1, SUM(ISNULL(CASE Mi WHEN 2 THEN Objects.RightIndex ELSE NULL END, 0)) as PR2, SUM(ISNULL(CASE Mi WHEN 3 THEN Objects.RightIndex ELSE NULL END, 0)) as PR3, COUNT_BIG(*) as ID FROM dbo.tp cross join dbo.multiplier M inner join dbo.Objects on (Mi = 1 AND Objects.Id = tp.Object1) or (Mi = 2 AND Objects.Id = tp.Object2) or (Mi = 3 AND Objects.Id = tp.Object3) GROUP BY tp.Object1, tp.object2, tp.object3, tp.property, tp.value GO -- This index is mostly useless but required create UNIQUE CLUSTERED index pk_TPIndexed on dbo.TPIndexed(property, value, object1, object2, object3) -- Once we have the clustered index, we can create a nonclustered that actually addresses our needs create NONCLUSTERED index ix_TPIndexed on dbo.TPIndexed(property, value, PL1, PL2, PL3, PR1, PR2, PR3) GO -- NOTE: this View is not indexed, but is uses the indexed view CREATE VIEW TPIndexedResultView AS Select O1, O2, O3, Property, Value FROM ( select Children1.Id as O1, Children2.Id as O2, Children3.Id as O3, tp.Property, tp.Value, row_number() over( partition by tp.Property, Children1.Id, Children2.Id, Children3.Id order by tp.Property, Tp.PL1 desc, Tp.PL2 desc, Tp.PL3 desc ) as Idx from TPIndexed as TP WITH (NOEXPAND) -- Then add all possible children of all those objects inner join Objects as Children1 WITH (INDEX(ix_LeftIndex)) on Children1.LeftIndex between TP.PL1 and TP.PR1 inner join Objects as Children2 WITH (INDEX(ix_LeftIndex)) on Children2.LeftIndex between TP.PL2 and TP.PR2 inner join Objects as Children3 WITH (INDEX(ix_LeftIndex)) on Children3.LeftIndex between TP.PL3 and TP.PR3 ) as x WHERE idx = 1 GO -- NOTE: this View is not indexed, but is uses the indexed view CREATE VIEW TPIndexedIntermediate AS select tp.Property, tp.Value , Children1.Id as O1, Children2.Id as O2, Children3.Id as O3 , PL1, PL2, PL3 , Children1.LeftIndex as CL1, Children2.LeftIndex as CL2, Children3.LeftIndex as CL3 from TPIndexed as TP WITH (NOEXPAND) -- Then add all possible children of all those objects inner join Objects as Children1 WITH (INDEX(ix_LeftIndex)) on Children1.LeftIndex between TP.PL1 and TP.PR1 inner join Objects as Children2 WITH (INDEX(ix_LeftIndex)) on Children2.LeftIndex between TP.PL2 and TP.PR2 inner join Objects as Children3 WITH (INDEX(ix_LeftIndex)) on Children3.LeftIndex between TP.PL3 and TP.PR3 GO ---------- ANSWER 3 SCHEMA -------- -- You're talking about making six copys of the TP table -- If you're going to go that far, you might as well, go the sortinggger route -- The performance profile is much the same - slower on insert, faster on read -- And instead of still recalculating on every read, you'll be recalculating -- only when the data changes. CREATE TABLE TPResult ( Object1 int not null references Objects, Object2 int not null references Objects, Object3 int not null references Objects, Property varchar(20) not null, Value varchar(50) not null ) GO create UNIQUE index ix_Result on TPResult(Property, Value, Object1, Object2, Object3) --You'll have to imagine this sortinggger, sql fiddle doesn't want to do it --CREATE TRIGGER tr_TP --ON TP -- FOR INSERT, UPDATE, DELETE --AS -- DELETE FROM TPResult -- -- For this example we'll just insert into the table once INSERT INTO TPResult SELECT O1, O2, O3, Property, Value FROM TPResultView 

Interrogez une partie de ma réponse de sqlfiddle:

 -------- QUESTION QUERY ---------- -- Original query, modified to use the view I added SELECT O1, O2, O3, Property, Value FROM TPResultView WHERE property = 'P1' AND value = 'abc' -- Your assertion is that this order by is the most expensive part. -- Sometimes converting queries into views allows the server to -- Optimize them better over time. -- NOTE: removing this order by has no effect on this query. -- ORDER BY O1, O2, O3 GO -------- ANSWER 1 QUERY ---------- -- A different way to get the same result. -- Query optimizer says this is more expensive, but I've seen cases where -- it says a query is more expensive but it returns results faster. SELECT O1, O2, O3, Property, Value FROM ( SELECT A.O1, A.O2, A.O3, A.Property, A.Value FROM TPIntermediate A LEFT JOIN TPIntermediate B ON A.O1 = B.O1 AND A.O2 = B.O2 AND A.O3 = B.O3 AND A.Property = B.Property AND ( -- Find any rows with Parent LeftIndex sortingplet that is greater than this one (A.PL1 < B.PL1 AND A.PL2 < B.PL2 AND A.PL3 < B.PL3) OR -- Find any rows with LeftIndex sortingplet that is greater than this one (A.CL1 < B.CL1 AND A.CL2 < B.CL2 AND A.CL3 < B.CL3) ) -- If this row has any rows that match the previous two cases, exclude it WHERE B.O1 IS NULL ) AS x WHERE property = 'P1' AND value = 'abc' -- NOTE: Removing this order _DOES_ reduce query cost removing the "sort" action -- that has been the focus of your question. -- Howeer, it wasn't clear from your question whether this order by was required. --ORDER BY O1, O2, O3 GO -------- ANSWER 2 QUERIES ---------- -- Same as above but using an indexed view to partially calculate results SELECT O1, O2, O3, Property, Value FROM TPIndexedResultView WHERE property = 'P1' AND value = 'abc' -- Your assertion is that this order by is the most expensive part. -- Sometimes converting queries into views allows the server to -- Optimize them better over time. -- NOTE: removing this order by has no effect on this query. --ORDER BY O1, O2, O3 GO SELECT O1, O2, O3, Property, Value FROM ( SELECT A.O1, A.O2, A.O3, A.Property, A.Value FROM TPIndexedIntermediate A LEFT JOIN TPIndexedIntermediate B ON A.O1 = B.O1 AND A.O2 = B.O2 AND A.O3 = B.O3 AND A.Property = B.Property AND ( -- Find any rows with Parent LeftIndex sortingplet that is greater than this one (A.PL1 < B.PL1 AND A.PL2 < B.PL2 AND A.PL3 < B.PL3) OR -- Find any rows with LeftIndex sortingplet that is greater than this one (A.CL1 < B.CL1 AND A.CL2 < B.CL2 AND A.CL3 < B.CL3) ) -- If this row has any rows that match the previous two cases, exclude it WHERE B.O1 IS NULL ) AS x WHERE property = 'P1' AND value = 'abc' -- NOTE: Removing this order _DOES_ reduce query cost removing the "sort" action -- that has been the focus of your question. -- Howeer, it wasn't clear from your question whether this order by was required. --ORDER BY O1, O2, O3 GO -------- ANSWER 3 QUERY ---------- -- Returning results from a pre-calculated table is fast and easy -- Unless your are doing many more inserts than reads, or your result -- set is very large, this is a fine way to compensate for a poor design -- in one area of your database. SELECT Object1 as O1, Object2 as O2, Object3 as O3, Property, Value FROM TPResult WHERE property = 'P1' AND value = 'abc' ORDER BY O1, O2, O3 

Vous pouvez accélérer cela en matérialisant la jointure dans une table indexée, par exemple joinresult. Cela a l'inconvénient de nécessiter de l'espace et de l'save sur le disque. Mais il a l'avantage de pouvoir utiliser un index pour la partie lente.

 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) 

Assurez-vous que joinresult possède un index sur [O1, O2, O3, Propriété, O1D, O2D, O3D] et effacez-le avant de l'exécuter. alors

 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 

Avez-vous essayé un index (ou définir le pk) avec la colonne "Valeur" d'abord, la colonne "Propriété" en second, la colonne "Object1" en troisième, la colonne "Object2" en quasortingème et la colonne "Object3" en cinquième? Je suppose que "Value" est plus ressortingctif que "Property".

Je suppose également que vous avez défini la colonne Id comme key primaire et une relation de key étrangère entre ParentId et Id.

Comment fonctionne cette requête ?:

  with -- First, get all combinations that match the property/value pair. validTrip as ( select Object1, Object2, Object3 from TriplesAndProperties where value = @value and property = @property ), -- Recursively flatten the inheritance hierarchy of Object1, 2 and 3. o1 as ( select Id, 0 as InherLevel from Objects where Id in (select Object1 from validTrip) union all select rec.Id, InherLevel + 1 from Objects rec inner join o1 base on rec.Parent = base.[Object] ), o2 as ( select Id, 0 as InherLevel from Objects where Id in (select Object2 from validTrip) union all select rec.Id, InherLevel + 1 from Objects rec inner join o2 base on rec.Parent = base.[Object] ), o3 as ( select Id, 0 as InherLevel from Objects where Id in (select Object3 from validTrip) union all select rec.Id, InherLevel + 1 from Objects rec inner join o3 base on rec.Parent = base.[Object] ) -- select the Id sortingple. select o1.Id, o2.Id, o3.Id N -- match every option in o1, with every option in o2, with every option in o3. from o1 cross join o2 cross join o3 -- order by the inheritance level. order by o1.InherLevel, o2.InherLevel, o3.InherLevel; 

Les requêtes hiérarchiques , c'est-à-dire WITH RECURSIVE ... ou les équivalents propriétaires tels que CONNECT BY sont vos amis dans ce cas.

La recette pour résoudre votre problème particulier est la suivante: Commencer à partir et remonter à l'agrégation de racine et exclure tout ce qui a déjà été trouvé.

I am guessing that your table is fairly big. Hence the slowness. In that case I am also guessing that you have multiple properties (2 to many). I this case I would suggest you move the "where property= 'P1'" inside the CTE. This would filter a good portion of the data making your query as fast as up to the number of properties times faster.

Something like : http://sqlfiddle.com/#!3/7c7a0/92/0

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.

Option 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.

Option 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 .