[geeklog-devtalk] geeklog-devel digest, Vol 1 #297 - 2 msgs

[geeklog-devel-request at lists.geeklog.net]

Send geeklog-devel mailing list submissions to
	geeklog-devel at lists.geeklog.net

To subscribe or unsubscribe via the World Wide Web, visit
	http://lists.geeklog.net/listinfo/geeklog-devel
or, via email, send a message with subject or body 'help' to
	geeklog-devel-request at lists.geeklog.net

You can reach the person managing the list at
	geeklog-devel-admin at lists.geeklog.net

When replying, please edit your Subject line so it is more specific
than "Re: Contents of geeklog-devel digest..."


Today's Topics:

   1. Comment Speed Improvement (Vincent Furia)
   2. Re: Comment Speed Improvement (Dwight Trumbower)

--__--__--

Message: 1
Date: Sat, 27 Mar 2004 14:54:13 -0500
From: Vincent Furia <vmf at abtech.org>
To: geeklog-devel at lists.geeklog.net
Subject: [geeklog-devel] Comment Speed Improvement
Reply-To: geeklog-devel at lists.geeklog.net

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

--__--__--

Message: 2
Date: Sun, 28 Mar 2004 00:02:35 -0600
To: geeklog-devel at lists.geeklog.net
From: Dwight Trumbower <dwight at trumbower.com>
Subject: Re: [geeklog-devel] Comment Speed Improvement
Reply-To: geeklog-devel at lists.geeklog.net

--=======A7D2E5D=======
Content-Type: text/plain; x-avg-checked=avg-ok-520A2C5C; charset=iso-8859-1; format=flowed
Content-Transfer-Encoding: quoted-printable

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

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

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


>I've been thinking hard about improving the speed of displaying comments=20

>by reducing the number of queries and potentially removing the need to use=

=20

>recursive functions.

>

>While Niels solution provides a quick fix for groklaw's specific problems,=

=20

>it is pretty inefficient when you are looking at a subset of comments for=

=20

>a story.  A more elegant solution must be possilbe..

>

>I think I've found that solution, but it will take some work (including a=

=20

>database change) to implement.  While I'm fully capable of implementing=20

>it, I wanted to get some feed-back before jumping in.

>

>The idea is to store the comments in the database using a modified=20

>preorder tree traversal method.  A brief description (along with a=20

>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=20

>(http://babel.altavista.com) works pretty well on the first half of the=20

>page.  Plus it has many useful graphics.

>

>The idea is a little confusing at first, but once you wrap your head=20

>around it you'll think:  "Wow, hey, that's pretty darn cool".  Or maybe=20

>you'll think: "Mein Gott, das ist wirklich k=FChl.". ;)

>

>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=

=20

>given comment)

>- 1 query to count the number of children a comment has

>

>Basically this will drastically improve the speed of comment displays of=20

>all types, especially for sites that have very large databases of comments=

=20

>(groklaw).  The only expense is adding two extra db queries when a comment=

=20

>gets added (including one that could potentially update almost every=20

>database row).

>

>The only change to the database will be the addition of two integer=20

>columns: left terminal (lft) and right terminal (rgt).  Optionally we=20

>could also remove the parent id (pid) column as it would no longer be=20

>technically necessary.  That being said, I think we should preserve it for=

=20

>convenience.

>

>I think the improvement will be worth it, though we'll have to write a=20

>slick upgrade script to take care of current comments.  A side effect of=20

>using this method is that we will be able to write a comment function that=

=20

>is iterative rather than recursive which will further improve performance.

>

>Another note is that this method is database independent.  There are some=

=20

>other pretty nice solutions that require stored procedures and I think=20

>Oracle has something built in.  Obviously those other solutions are really=

=20

>going to work well with MySQL.

>

>If the article above doesn't make sense, let me know and I can write a=20

>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=20

>input from a DB guy to make sure I'm not missing something obvious=20

>(Dwight, you still out there?).

>

>-Vinny

>_______________________________________________

>geeklog-devel mailing list

>geeklog-devel at lists.geeklog.net

>http://lists.geeklog.net/listinfo/geeklog-devel

>

>

>


--=======A7D2E5D=======--



--__--__--

_______________________________________________
geeklog-devel mailing list
geeklog-devel at lists.geeklog.net
http://lists.geeklog.net/listinfo/geeklog-devel


End of geeklog-devel Digest