[geeklog-devel] Comment Speed Improvement

[Dwight Trumbower]

English version of the same method can be found here. 
http://www.intelligententerprise.com/001020/celko.jhtml?_requestid=13769

It is by Joe Celko, one of the gurus in SQL programming. He has been 
promoting this method for years. I have used this method before and it 
works nice.

At 01:54 PM 3/27/2004, you wrote:

>I've been thinking hard about improving the speed of displaying comments 
>by reducing the number of queries and potentially removing the need to use 
>recursive functions.
>
>While Niels solution provides a quick fix for groklaw's specific problems, 
>it is pretty inefficient when you are looking at a subset of comments for 
>a story.  A more elegant solution must be possilbe..
>
>I think I've found that solution, but it will take some work (including a 
>database change) to implement.  While I'm fully capable of implementing 
>it, I wanted to get some feed-back before jumping in.
>
>The idea is to store the comments in the database using a modified 
>preorder tree traversal method.  A brief description (along with a 
>comparison to our current method) can be found in this article:
>
>         http://www.sitepoint.com/article/hierarchical-data-database
>
>A better description is this site:
>
>         http://membres.lycos.fr/sqlpro/Tree/SQL_tree.htm
>
>However it is in French (which I don't speak).  But babelfish 
>(http://babel.altavista.com) works pretty well on the first half of the 
>page.  Plus it has many useful graphics.
>
>The idea is a little confusing at first, but once you wrap your head 
>around it you'll think:  "Wow, hey, that's pretty darn cool".  Or maybe 
>you'll think: "Mein Gott, das ist wirklich kühl.". ;)
>
>The summary:
>
>- 1 query and 2 updates to insert a new comment
>- 1 query to get all the comments (in a logical order for display)
>- 1 query to get all the children of a given comment (with or without the 
>given comment)
>- 1 query to count the number of children a comment has
>
>Basically this will drastically improve the speed of comment displays of 
>all types, especially for sites that have very large databases of comments 
>(groklaw).  The only expense is adding two extra db queries when a comment 
>gets added (including one that could potentially update almost every 
>database row).
>
>The only change to the database will be the addition of two integer 
>columns: left terminal (lft) and right terminal (rgt).  Optionally we 
>could also remove the parent id (pid) column as it would no longer be 
>technically necessary.  That being said, I think we should preserve it for 
>convenience.
>
>I think the improvement will be worth it, though we'll have to write a 
>slick upgrade script to take care of current comments.  A side effect of 
>using this method is that we will be able to write a comment function that 
>is iterative rather than recursive which will further improve performance.
>
>Another note is that this method is database independent.  There are some 
>other pretty nice solutions that require stored procedures and I think 
>Oracle has something built in.  Obviously those other solutions are really 
>going to work well with MySQL.
>
>If the article above doesn't make sense, let me know and I can write a 
>brief summary of what is going on in "preorder tree traversal" method.
>
>Please everyone, let me know what you think.  I'd especially like some 
>input from a DB guy to make sure I'm not missing something obvious 
>(Dwight, you still out there?).
>
>-Vinny
>_______________________________________________
>geeklog-devel mailing list
>geeklog-devel at lists.geeklog.net
>http://lists.geeklog.net/listinfo/geeklog-devel
>
>
>