[geeklog-devel] Comment Speed Improvement

Dwight Trumbower dwight at trumbower.com
Sun Mar 28 01:02:35 EST 2004

English version of the same method can be found here. 

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 
>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?).
>geeklog-devel mailing list
>geeklog-devel at lists.geeklog.net

More information about the geeklog-devel mailing list