SQL Antipatterns Strike Back! Slides

Written by

I presented my tutorial at the MySQL Conference & Expo today. I have fun preparing it and presenting it, and I got many good questions and comments from the audience. Thanks to everyone for coming and participating!

I have uploaded my slides with a Creative Common 3.0 license to my SlideShare account: http://www.slideshare.net/billkarwin

For those who did not get to see my tutorial, I’m presenting some selections from it during a 45-minute session at the MySQL Camp on Wednesday at 2:00pm, under the title “Practical Object-Oriented Models in SQL.”

See you next year!

Comments

43 responses to “SQL Antipatterns Strike Back! Slides”

April 21, 2009

Sheeri K. Cabral

Bill, can you edit http://forge.mysql.com/wiki/MySQLConf2009MondayNotes to put a link to your slides?

Reply
May 7, 2009

Anonymous

Hey Bill, great presentation! a lot of hidden gems in this one.

I have one question – you skipped quickly over the depth column in the closure table model, but how do you actually calculate it? it seems less straightforward than I thought initially

Reply
May 8, 2009

Bill Karwin

@erangalp: Calculate depth as you insert a node.

The depth of the degenerate path (a node’s path to itself) is always zero.

Then when you copy its ancestors’ paths, add 1 to the depth of each path.

Reply
May 9, 2009

pytrin

Though if I insert the ancestor path using the query you suggested in the presentation, it makes no distinction to depth. Is there a way to do this in a simple manner, or do I have to calculate per depth level per node insertion?

Reply
May 9, 2009

Bill Karwin

Here’s a query to insert a new node #8 as a child of node #5 in the Closure Table design, including calculation of the depth:

INSERT INTO TreePaths (ancestor, descendant, depth)
SELECT 8, 8, 0
UNION ALL
SELECT ancestor, 8, depth+1
FROM TreePaths 
WHERE descendant = 5;

Or are you trying to fill in the depth values for a populate TreePaths table? That’s a bit tricker than providing the depth value for each node as you insert it.

Reply
May 14, 2009

Anonymous

Hi Bill
Thanks for putting this on slideshare – it’s really helping me.
I’m working with a tree of about 25,000 nodes, using a simple ParentID approach. The main load is querying for arbitrary subtrees, so I’m interested in nested sets and the closure table (which is new to me).
Do you know of accessible introductions to using closure tables? I’m not having much luck just googling.

Reply
May 14, 2009

Bill Karwin

It seems that Nested Sets has become the most popular to write about, among the “fancy” tree implementations.

Vadim Tropashko writes about the “Transitive Closure Relation” in his blog (http://vadimtropashko.wordpress.com/nested-sets-and-relational-division/) and also in his book “SQL Design Patterns” he covers it in the context of representing general graphs, not just trees.

This is the same thing as my Closure Table, but he approaches it from a much deeper theoretical direction.

Reply
May 14, 2009

Bill Karwin

Sorry – Tropashko also calls it the “Transitive Adjacency Relation.”

Reply
May 14, 2009

Anonymous

Very helpful – thank you.
I’m moving towards the sense that I would use the classic adjacency list as the “canonical representation” of the tree, and then periodically populate a different representation.
Then I’d use the adjacency list for some queries (get parent, get children) and the other representation for other queries (get all descendants, get all ancestors).
So far I’ve found three other kinds of representation I could use – nested sets, materialised path, and closure table. Of which the latter looks to be simplest to both populate and query.
Do that seem a good way to go?

Reply
May 14, 2009

Bill Karwin

Sure, that seems fine. The plain Adjacency List design is good for certain types of queries, but bad for querying whole subtrees.

FWIW, I have written applications that used the Closure Table alone, without the traditional Adjacency List, and it worked out fine.

Another option if you need to query trees only from the root node (and not arbitrary internal subtrees), is to use a hybrid approach with Adjacency List (the parent_id column): add one more column “root_id” so every descendant knows its root ancestor.

So querying a whole tree is as simple: SELECT * FROM Comments WHERE root_id = 1;

Reply
May 15, 2009

Anonymous

Good thoughts.
I have to find arbitrary subtrees anywhere in the hierarchy.
In fact there’s also an emerging need to find the “extended family” of a node, by which I mean “find all the descendants of an ancestor of this node, where the ancestor is of a particular type”.
This was looking hard just with an adjacency list approach – but I think it will be simple with a closure table.

Reply
July 24, 2009

Jean-Rubin L

Hi,
I found your slides on Slideshare after posting a question on phpfreaks and believe it I've been using it a lot. Not just for the closure table approach but for enums and other goodies that were in there so thank you for this document.

I have question regarding the closure table. I have a tree structure that is working well. Now I want to copy a node and all its children and I am having a hard time finding the right approach to do it. When I copy for instance node A with children B and C, it will create Notes A' B' C' with new IDs ( I have an auto-incrementprimary key) Reproducing the relationship OF A, B and C poses me a challenge however. In the closure table you have the relations regarding the original nodes but you cannot build reproduce the relation with the new nodes as they were just created and there's no information about them in the closure table. Do you have any suggestion as to how I should tackle this? Thanks in advance,
JR from Montreal

Reply
July 25, 2009

Bill Karwin

@Jean-Rubin: Good question. Relocating or cloning a subtree in the Closure Table or Nested Sets designs isn't very easy.

For the case you describe, I'd recommend creating a temp table that maps the node id's of the old subtree to the node id's of the cloned subtree.

CREATE TEMPORARY TABLE NodeMap (
original_id BIGINT PRIMARY KEY,
clone_id BIGINT NOT NULL
);

Then if you can query an original subtree (rooted at node #4 for instance), you can insert a clone subtree with equivalent structure but using the cloned nodes:

INSERT INTO ClosureTable (ancestor, descendant)
SELECT n1.clone_id, n2.clone_id
FROM ClosureTable c
JOIN NodeMap n1 ON (c.ancestor = n1.original_id)
JOIN NodeMap n2 ON (c.descendant = n2.original_id)
WHERE c.ancestor = 4;

Reply
July 25, 2009

Jean-Rubin L

This comment has been removed by a blog administrator.

Reply
October 26, 2009

Warren Benedetto

Bill, awesome presentation. I have returned to your slides many times over the last few months, especially the section on closure tables.

I'm just curious … suppose I wanted to sever a child tree (and all of its descendants) and move it to a new parent. If the new parent is at a different depth in the tree than the old one, all the depths will need to be recalculated.

It seems the easiest thing to do would be to DELETE the child and its descendants (from the TreePath table), then INSERT them with the new parent. Then there would be no need to re-calculate the depths.

However, I'm wondering if there's a more efficient way to do it, via an UPDATE query. Any thoughts on how such a query might be structured? If it's possible, would it be more efficient than the DELETE/INSERT method?

Reply
October 26, 2009

Jean-Rubin L

Warren, it's funny you should mention that. I am currently working on moving nodes around in the tree. Your question is very valid but just my two cents: even if you use a delete / update, the depth of the new nodes will probably change as the insertion may take place at a different level. So far I have systematically removed the child nodes and recalculated the ancestor-descendant-depth combination. Hopes this helps a little, JR

Reply
October 26, 2009

Bill Karwin

@Warren: Consider a transformation of a tree like (A (B (D (F (H, I))), C (E (G)))) -> (A (B (D), C (E (G (F (H, I))))))

That is, move a subtree F with its children H and I. Old parent is D. New parent is G.

Paths within the subtree (e.g. FF, HH, II, FH, and FI) don't need to change at all. Keep in mind the "depth" is really pathlength, not the level in the tree.

Paths from ancestor nodes into the subtree have to be recalculated, up to the common ancestor of the old parent and the new parent.

I can update paths from D and simply change the parent to G, and pathlengths stay the same.

I can delete paths from B into the moving subtree.

And I can insert new paths from C and E into the subtree, generating the paths I need by joining CE and CG to the paths inside the subtree, and adding 1 to the pathlengths.

Paths from A into the subtree need to add 1 to pathlength because the length from A to G is 1 greater than the length from A to D.

Hmm. I'm thinking I could write a whole book showing how to do each type of tree operation with each type of hierarchical data design. Maybe that'll be my next book.

Reply
March 24, 2010

Arthur Layese

Bill,

Thanks for the great presentation, I learned a lot.

I would like to ask if there's a way I can dump all the hierarchies in a single query using a closure table? For example I have a following tree:

rootree
– 1stbranch
– midbranch
– corebranch
– leafnodes
– lastbranch
– lastleaf

and I want to display it like:

rootree -> 1stbranch
rootree -> midbranch
rootree -> midbranch -> corebranch
rootree -> midbranch -> corebranch -> leafnodes
rootree -> lastbranch
rootree -> lastbranch -> lastleaf

Is this possible with a single query alone? What are other alternatives to achieve this on a closure table approach?

Thanks.

Reply
March 24, 2010

Bill Karwin

Hi @Arthur, thanks for the question. I've posted a new blog entry to answer this: http://karwin.blogspot.com/2010/03/rendering-trees-with-closure-tables.html

Reply
March 25, 2010

Arthur Layese

Hi Bill,

That's a great solution. Thanks a lot.

Reply
March 25, 2010

Arthur Layese

Bill,

I'm very much interested in enumeration table model and found out that there's a missing sample implementation on how to do the ordering of the leaf nodes. Again for a given example:

rootree -> 1stbranch
rootree -> midbranch
rootree -> lastbranch

if I'm going to move the 1stbranch to make it the last branch of the tree so that the new tree will be something like:

rootree -> midbranch
rootree -> lastbranch
rootree -> 1stbranch

Hopefully you may include a short discussion/topic about this in your upcoming book.

Reply
March 25, 2010

Bill Karwin

Hi @Arthur,

If you've studied graph theory in computer science classes you'll remember that the order of child nodes in a tree is irrelevant to the graph.

That is, (R (F) (M) (L)) is the same tree as (R (M) (L) (F)).

So keep in mind that display order data properly should be separate from the hierarchy data.

But since path enumeration is essentially a denormalized solution already, perhaps we can bend the rules.

Therefore you could just make sure to update the primary key values of tree nodes, so that the natural order of these values matches your desired display order.

This is admittedly a fragile solution, and pretty much a hack of coupling the sibling order to the primary key values (which should be arbitrary and independent of meaning).

This illustrates that each solution to represent trees in SQL has its strengths and weaknesses, and therefore which design you use should be based on the types of queries you need in a given application.

It would take a whole book to compare how to implement every scenario in all the designs of trees. In my book "SQL Antipatterns," I had to limit myself to 20 pages on hierarchical data, because there are other topics to cover.

Reply
March 25, 2010

Arthur Layese

Bill,

Thank you very much for a well detailed explanation. I took a look at your upcoming book and it's pretty interesting and tempting to have a copy soon.

Reply
May 8, 2010

info

This comment has been removed by the author.

Reply
May 8, 2010

info

This comment has been removed by the author.

Reply
May 18, 2010

apren

Hi Bill, thanks a lot for the presentation.

I have two question about polymorphic associations.

if i have 5 entities with comments, what solution you recommend?. I like the solution "exclusive arcs" but it is good with 5 foreign keys?

In "reverse relationship", when i delete a bug (cascade delete), their comments are orphans in comments table.

Reply
May 18, 2010

Bill Karwin

@apren: Thanks for reading my presentation! I think the last solution, to create a common super-type table, is almost always the best way to represent polymorphic relationships.

Reply
August 11, 2010

marco.markl

Hi Bill!

I have a question about Closure Table.

I would like to ask if there's a way I can find all roots in a query?

Example:
root1
– sub1.1
– sub1.2
root2
– sub2.1
— sub 2.1.1
– sub2.2
root3

Result:
root1
root2
root3

Thanks!

Reply
August 11, 2010

Bill Karwin

@marco.markl: Hi thanks for the question. You can get all root nodes by searching for the entries in TreePaths such that no path exists to that node as the descendant.

SELECT root.descendant
FROM TreePaths AS root
LEFT JOIN TreePaths AS parent
ON root.descendant = parent.descendant
AND parent.ancestor <> parent.descendant
WHERE parent.descendant IS NULL;

This will naturally find all the self-referencing (zero-length) paths of root nodes.

Reply
August 11, 2010

marco.markl

@Bill Karwin: Thanks for the Answer!

My Solution 😉

SELECT descendant FROM TreePaths
GROUP BY descendant
HAVING count(descendant) = 1

Greets from Vienna / Austria

Reply
August 11, 2010

Bill Karwin

@marco.markl: I suggest benchmarking both solutions.

I've adopted the habit of avoiding GROUP BY when I use MySQL, because it optimizes so poorly in many cases.

No matter what brand of database you use, you should use EXPLAIN to analyze the optimization plan, and perhaps some profiling to measure the final performance.

Anyway, good job for thinking of another solution!

Reply
August 16, 2010

Lennart

Hi Bill. Your presentation is a very nice summary of different ways to represent an hierarchy in a rdbms. I have some notes on an implementation of a closure table:

http://www.dustbite.se/tree

It is a slight variation of your closure table, where I have both a parent relation, and an ancestor relation. The ancestor relation is maintained via triggers on the parents table.

The tables/triggers code and some sample data can be downloaded at the end of the article in case someone is interested in testing it.

Reply
August 17, 2010

Bill Karwin

@Lennart: Thanks very much! Your solution looks interesting and very expressive.

It would take a while for me to analyze your article fully, but I think I can do similar tree operations with my solution of a single closure table.

It's always good to have multiple solution to choose from. The best solution for a given application depends on the operations you need to do in that app.

Reply
August 17, 2010

Lennart

Hi Bill, it is indeed possible to express all operations with just the closure relation (since we can derive parents from it). The benefit (IMO) is that a developer can focus on how to update the parents relation, and the triggers will maintain the closure.

To be honest I feel that some of the operations discussed are a bit weird (I can't for example imagine when one would like to "Find the Immediate Subordinates of a Node" including the node under investigation), but I wanted to mimic the operations from the NS article for comparison.

I definitely agree on your last remark and I find your presentation very valuable for anyone who must decide on how to represent a tree.

Reply
October 11, 2010

chunlinyao

@Bill Karwin said…

> Or are you trying to fill in the depth values for a populate TreePaths table? That's a bit tricker than providing the depth value for each node as you insert it.
Cannot found a good solution to recalculate depth when I relocate a subtree.

Reply
May 2, 2012

dasersoft

Bill you are just awesome. I made true with your presentation on slideshare and it has helped me alot. However i posted this question sometimes ago in stackoverflow i dont know how u can throw more light.

4 forms are distributed, each form brings 4 people and each 4 people bring another four people. The network grows downword until 7 generations. How can i find downliners and upliners assuming i decide to pick a node at any level?

Explanation:

A brings A B C D
E then brings F G H J
F brings WXYZ

and so on and so forth. At 7th generation we experience an halt. Meanwhile each node begins a lineage downwords.

Question 1: How can i move upward like 7 levels upward to calculate the upliners of a node. Cos what i have been seeing around is how to query children of a node. This time around i want to be able to calculate upliners.

Reply
July 21, 2014

Emmanuel Bouton

Hello Bill,

Thanks for sharing your knowledge 🙂

I have a question on the Closure Table design …
I wonder which request I can run to easily construct an object oriented tree.

This is my entity :
class Environment
{
protected $id;
protected $name;
protected $parent;
protected $children;
}

with the associated getters/setters.

getParent() and getChildren() are loaded lazily, but I'd like to load the full hierarchy on each request.

The problem with the following request (to get children) is that I cannot guess the ancestor of the environments at the second level …

SELECT e.*, p.length FROM environments e JOIN environments_paths AS p ON e.id = p.descendant_id WHERE p.ancestor_id = 7;

How would you do that (in php) ?

Reply
July 21, 2014

Bill Karwin

Hi Emmanuel,

You can get all descendants of 7 with their immediate parents:

SELECT p.ancestor_id AS parent_id, e.*
FROM environments e
JOIN environment_paths AS c ON e.id = c.descendant_id
JOIN environment_paths AS p ON c.descendant_id = p.descendant_id AND p.length = 1
WHERE c.ancestor_id = 7;

Then as you fetch the result, populate an array of objects indexed by the child id.

while ($row = $stmt->fetch()) {
if (!isset($nodes[$row["id"]]) {
$nodes[$row["id"]] = new Environment($row);
}
}

Your constructor for Environment may have logic in it to make an SQL query, but I like to code my object constructors to allow an optional argument for the initial data. That way I can avoid making many SQL queries when I already got all the data for many nodes by joining in the tree query.

Then pass through the array again, assigning objects for parent and children:

foreach ($nodes as $node) {
$nodes[$node->parent_id]->children[] = $node;
$node->parent = $nodes[$node->parent_id];
}

Reply
July 21, 2014

Emmanuel Bouton

Amazing ! Thanks a lot for your quick answer !

I'll do the following :

* Query for the getParent() :
SELECT e.* FROM environments e LEFT JOIN environments_paths AS p ON e.id = p.ancestor_id WHERE p.descendant_id = 7 and e.id != 7 order by p.length;
=> I exclude the row for id 7 because my entity is already « hydrated ».
I'll just have to loop on the result set to set the parents recursively.

* Query for the getChildren() (as you said) :
SELECT p.ancestor_id AS parent_id, e.* FROM environments e LEFT JOIN environments_paths AS c ON e.id = c.descendant_id LEFT JOIN environments_paths AS p ON c.descendant_id = p.descendant_id AND p.length = 1 WHERE c.ancestor_id = 7 AND id != 7;
=> I prefer to store the results by parent_id :

$children = [];
foreach ($rows as $row) {
$children[$row['parent_id']][] = $row;
}
setAllChildren($environment, $children);

function setAllChildren($environment, $allChildrenRows)
{
$childrenRows = $allChildrenRows[$environment->getId()];
if (isset($childrenRows)) {
foreach ($childrenRows as $row) {
$child = new Environment($row);
setAllChildren($child, $allChildrenRows);
$environment->addChild($child);
}
}
}

Haven't tested it yet but i think it could do the job.
Thanks again for your help !!

Reply
July 21, 2014

Emmanuel Bouton

Just another question …

In your slideshare models-for-hierarchical-data (page 63), how would you move the whole subtree #4 under #2 (in SQL) ?

Reply
July 24, 2014

Emmanuel Bouton

Ok I found my response in one of your post on mysqlperformanceblog 🙂

Thanks a lot !

Reply
October 15, 2014

Unknown

INSERT INTO TreePaths (ancestor, descendant, depth)
SELECT 8, 8, 0
UNION ALL
SELECT ancestor, 8, depth+1
FROM TreePaths 
WHERE descendant = 5;

That doesn't appear to work, at least not on my mySQL 5.6.16 build – the UNION ALL query provided actually gives two rows, one with a path depth of 0 and another with a path depth of 1, and as such causes a primary key error when it tries to insert the same ancestor/descendent twice.

Unless I'm misunderstanding something, which is entirely possible.

What would be helpful, if you had the time to providing it, would be a method of calculating the depth AFTER insert. You've said it's complicated, but having followed you around the Internet, I can't find an example of where you've done it, and this project I'm working on isn't necessarily able to guarantee inserting nodes in order.

Reply
October 15, 2014

Bill Karwin

Hi Unknown,

The idea is that 8 is just an example value, not a literal value you must use. It's the id of a new node, that is not in the TreePaths yet before you run the INSERT.

Since it's not in the tree, then "SELECT ancestor, 8" cannot generate the pair 8,8.

I think you already have an existing node 8 in your tree, which is one of the ancestors of 5.

Reply

SQL Antipatterns Strike Back! Slides

Like this:

Comments

43 responses to “SQL Antipatterns Strike Back! Slides”

Leave a Reply Cancel reply

More posts

The Scaffold Project

The Shed Porch Project

The Footbridge Project

Will Voyager 1 and 2 come back as V’Ger?

SQL Antipatterns Strike Back! Slides

Share this:

Like this:

Comments

43 responses to “SQL Antipatterns Strike Back! Slides”

Leave a Reply Cancel reply

More posts

The Scaffold Project

The Shed Porch Project

The Footbridge Project

Will Voyager 1 and 2 come back as V’Ger?