Recursive (Instead Of) Trigger
in [Programming SQL]
|
From: --CELKO-- on 22 Apr 2010 14:18 >> The nested sets model does not scale compared to other solutions.<< Next month I will be consulting in Chicago for a company that makes a product which extracts data from SAP into SQL Server for reporting. The emails with the negations specifically thanked me for the Nested Sets model. Several years ago, I re-designed a portal control package with the Nested Sets model. The schema was reduced from about sixty tables to six. We tested it on tree with seven levels and about 100K nodes. The performance improvement 2-3 orders of magnitude. In fairness, the old code had gotten a bit out of hand. People had added data integrity checking in triggers and code and we were able to do it in the DDL instead. >> To remove nodes not only do you have to delete the node rows but you also have to update the left/right columns to "fix" the order that the nested sets model relies on (hardly relational!). << No, you don't have to updated (lft, rgt) values if all you want to use is the containment property. If you want to use the "algebraic" property to get the size of subtrees, then you close gaps and that is easily done. The nice part is that the tree structure is in a table with very short rows (two integers and the foreign key to the nodes are, say, 16 to 20 bytes per row), so a lot of them fit into a data page. Use a clustered index and most operations use a simple table scan that starts at lft value and stops at the matching rgt. But why be abstract? Bill, here is the code: /* remove subtree rooted at given node */ CREATE PROCEDURE DeleteSubtree (@my_node_id <type>) AS BEGIN -- remove subtree DELETE FROM NestTree WHERE node_id IN (SELECT Subtree.node_id FROM NestTree AS Root, NestTree AS Subtree WHERE Root.node_id = @my_node_id AND Root.lft BETWEEN Subtree.lft AND Subtree.rgt); -- close gaps option UPDATE NestTree SET lft = (SELECT COUNT(*) FROM LftRgt.seq_nbr WHERE seq_nbr <= lft), rgt = (SELECT COUNT(*) FROM LftRgt.seq_nbr WHERE seq_nbr <= rgt); END; I am assuming you have a view defined this way, but these days, you might use a CTE on the UPDATE statement instead. CREATE VIEW LftRgt (seq_nbr) AS SELECT lft FROM NestTree UNION ALL SELECT rgt FROM NestTree; I left a WHERE clause off of the UPDATE statement so that the entire tree will be compressed. If you are sure that this procedure is working on a tree without any prior gaps in it, then add it and get another boost in performance. >> Concurrency problems are abound with a nested sets implementation that has even a slightly volatile hierarchy. << One of the projects I know of that was done with a Nested Sets model was a newsgroup, like this one. They like the performance since it was better than their previous Adjacency List model and made no mention of concurrency problems. Since subtrees are contiguous in physical storage with a clustered index, page locking works fairly well. The trick is to use a higher percentage of free space when you have a volatile hierarchy. But that applies to other models as well.
From: Bill Cohagan on 22 Apr 2010 15:35 Scott Thanks. Since posting my question I also found the docs you quoted. I was originally misled by interpreting "nesting" to be equivalent to "recursion" which of course it is not, at least in the context of BOL regarding SQL Server. So now I understand the behavior I'm seeing. Still looking for a reasonable solution however. "Scott Morris" wrote: > "Bill Cohagan" <BillCohagan(a)discussions.microsoft.com> wrote in message > news:E6D0D7A2-8407-4751-8BB7-813F7A25905E(a)microsoft.com... > > I've got a recursive Instead Of Delete trigger which I'm forced to use due > > to > > SQL 2005/2008 prohibiting cycles in cascade operations. I'm getting a > > (surprising) RI error when I single step through the trigger body and > > reach > > the point of the recursive Delete operation. Even though I do a "Step > > Into" I > > immediately get the error without reentering at the top of the trigger > > code. > > This leads me to believe that the Instead Of Trigger is NOT being invoked > > on > > the recursive call. That would explain both the RI error *and* that Step > > Into > > doesn't behave as expected. > > > > I've reviewed several threads here regarding recursive triggers and saw > > one > > "offhand" remark that Instead Of triggers are never invoked recursively, > > but > > no details were offered. > > This is exactly what BOL states (ref: create trigger tsql statement): > ms-help://MS.SQLCC.v10/MS.SQLSVR.v10.en/s10de_6tsql/html/edeced03-decd-44c3-8c74-2c02f801d3e7.htm > > If an INSTEAD OF trigger defined on a table executes a statement against the > table that would ordinarily fire the INSTEAD OF trigger again, the trigger > is not called recursively. Instead, the statement is processed as if the > table had no INSTEAD OF trigger and starts the chain of constraint > operations and AFTER trigger executions. For example, if a trigger is > defined as an INSTEAD OF INSERT trigger for a table, and the trigger > executes an INSERT statement on the same table, the INSERT statement > executed by the INSTEAD OF trigger does not call the trigger again. The > INSERT executed by the trigger starts the process of performing constraint > actions and firing any AFTER INSERT triggers defined for the table. > > > > . >
From: Bill Cohagan on 22 Apr 2010 15:36 Celko Thanks for the response. At the moment I don't have the freedom to muck with the schema; however I'll take a look at your approach for future reference. Regards, Bill "--CELKO--" wrote: > >> What I'm attempting is to delete a subtree in a table which contains parent pointers .. or how best to implement this sort of thing in general.<< > > Use the Nested Sets model instead of mimicking pointer chains in SQL. > No need for recursive procedural code, just use a single declarative > DELETE FROM statement and forget about triggers. You might also get a > copy of TREES & HIERARCHIES IN SQL for more code and other (more > relational) ways to do this. > . >
From: Bill Cohagan on 22 Apr 2010 15:37 Tony I'll take a look at the articles/examples you pointed to. Thanks for the response. Bill "Tony Rogerson" wrote: > > Use the Nested Sets model instead of mimicking pointer chains in SQL. > > No need for recursive procedural code, just use a single declarative > > DELETE FROM statement and forget about triggers. You might also get a > > copy of TREES & HIERARCHIES IN SQL for more code and other (more > > relational) ways to do this. > > The nested sets model does not scale compared to other solutions. > > To remove nodes not only do you have to delete the node rows but you also > have to update the left/right columns to "fix" the order that the nested > sets model relies on (hardly relational!). > > Whilst other methods rely on pointer chains - the nested set relies on > ordering down the nodes. > > A good reference point with many examples is here: > http://dev.mysql.com/tech-resources/articles/hierarchical-data.html > > Concurrency problems are abound with a nested sets implementation that has > even a slightly volatile hierarchy. > > --ROGGIE-- > > "--CELKO--" <jcelko212(a)earthlink.net> wrote in message > news:94ef22de-c89a-4e36-8233-02be7e11998f(a)h16g2000prf.googlegroups.com... > >>> What I'm attempting is to delete a subtree in a table which contains > >>> parent pointers .. or how best to implement this sort of thing in > >>> general.<< > > > > Use the Nested Sets model instead of mimicking pointer chains in SQL. > > No need for recursive procedural code, just use a single declarative > > DELETE FROM statement and forget about triggers. You might also get a > > copy of TREES & HIERARCHIES IN SQL for more code and other (more > > relational) ways to do this. > > . >
From: Erland Sommarskog on 22 Apr 2010 18:00 Bill Cohagan (BillCohagan(a)discussions.microsoft.com) writes: > Thanks. Since posting my question I also found the docs you quoted. I > was originally misled by interpreting "nesting" to be equivalent to > "recursion" which of course it is not, at least in the context of BOL > regarding SQL Server. So now I understand the behavior I'm seeing. Still > looking for a reasonable solution however. Well, since we don't know any details about your problem, it's difficult to help. I would suggest that you post: o CREATE TABLE statements for your tables. o INSERT statements with sample data. o The desired result given the sample on some DELETE operation. o Which version of SQL Server you are using. It helps if you can trim down tables to show the essentials only. -- Erland Sommarskog, SQL Server MVP, esquel(a)sommarskog.se Links for SQL Server Books Online: SQL 2008: http://msdn.microsoft.com/en-us/sqlserver/cc514207.aspx SQL 2005: http://msdn.microsoft.com/en-us/sqlserver/bb895970.aspx SQL 2000: http://www.microsoft.com/sql/prodinfo/previousversions/books.mspx
First
|
Prev
|
Next
|
Last
Pages: 1 2 3 Prev: DBCC MemoryStatus memory_node_id = ... Next: first (and last) |