I once heard of a system for representing threaded comments in a relational database, wherein the ID of each comment was a slash-separated list of its ancestors, e.g.:
1 Initial comment
1/1 Re: Initial comment
1/2 Re: Initial comment
1/2/1 Re: Re: Initial comment
1/2/2 ...
These sorts of IDs have the wonderful property that you can efficiently select any subtree using a LIKE query, e.g. "SELECT * FROM comments WHERE path LIKE '1/%'". These queries are efficient because they use string btree indexes. And the results may even be sorted the right way, provided you have monotonically increasing IDs within each level.
I think I read about this technique being used on Slashdot a few years ago, but I can't remember the name or find any reference. Still, it seems like a way to achieve the same benefits that the OP cites for comments with PostgreSQL's ltree support on any database with reasonable string indexing.
That, or restrict the maximum number of comments at a given level to a large, but fixed number that you can express as a fixed size number, say two digits in base 62 (digits are 0-9a-zA-Z). Or, if you use postgres, make the index column a list of integers.
I used these for a commenting system as well, they're really quite amazing. There's basically three options when storing a tree in a relational database - adjacency lists which are slow to read, nested sets which are slow for writes, and materialized path, which is slow for moving around nodes.
It's good to have a fourth option which is straightforward to implement and has excellent performance.
Just wanted to throw an update over here. The examples in my post are specifically geared towards a basic threaded comment structure, which Disqus is not. Our usage is much more complex than this example, but we are able to handle sorting by dynamic data (which we use in our "Most Popular" sort algorithm).
In other words, recursion still works, and in our tests has proven faster than doing it at the application layer (no matter how you sugar coat it).
Turns out that the average discussion thread has few enough comments that they can be fetched from the db in one call (e.g. by the thread_id). This makes even deeply nested comments fairly simple to query for, and then it is quite easy to rebuild the tree in memory.
I believe the author's point is that using these recursive SQL queries is more efficient, as the DB engine is inherently faster than your (presumably) scripting language. So this solution is for when the in-memory method is failing to scale.
Not saying necessarily that the DB engine is less efficient, but rather that it is serves as a limiting factor and anything you can offload onto other servers is a good solution (for highly-visited websites).
Is the DB engine really inherently faster than the scripting language?
As for anything, the answer is "it depends". It depends on what you want to do. In this case that is grab all rows in a specific dataset.
If you in any case want to grab the dataset X, consisting of a given set of rows, asking the database to figure how to fetch all rows in one operation as efficiently as possible will (or at least should on any respectable database engine) be more efficient than having the scripting language sending multiple requests which can only be optimized one by one.
For reference, I've only tried recursive queries in Microsoft SQL Server, but they are pretty fucking neat from a geeky perspective.
Yeah, I was about to mention that MSSQL has had this 'feature' for years. I've used it a lot for retrieving organizational structures from the typical parent-child table structure.
The best part of it, is that it is MUCH simpler than either trying to roll your own through cursors or dealing with it in whatever language outside the database.
Threaded comments are surprisingly difficult to model in a relational database. I spent about a month on the problem when I rolled my own threaded comment system for newsley. Relational Databases really don't lend themselves to easily modeling tree structures.
He has two really good chapters that specifically building a comment system. It takes a bit of work, and you end up pre-computing the comment system on INSERT's instead of SELECT's. But, you can build a comment system that pulls your entire comment tree in order using a single SELECT ... FROM COMMENTS ... ORDER BY comment.node_left;
Personally I just sort everything in memory like reddit, since I need to traverse all branches to calculate weighed scores, which is a balance of vote counts and age. I think reddit/HN do something similar? I wonder how Disqus handles this.
1 Initial comment
1/1 Re: Initial comment
1/2 Re: Initial comment
1/2/1 Re: Re: Initial comment
1/2/2 ...
These sorts of IDs have the wonderful property that you can efficiently select any subtree using a LIKE query, e.g. "SELECT * FROM comments WHERE path LIKE '1/%'". These queries are efficient because they use string btree indexes. And the results may even be sorted the right way, provided you have monotonically increasing IDs within each level.
I think I read about this technique being used on Slashdot a few years ago, but I can't remember the name or find any reference. Still, it seems like a way to achieve the same benefits that the OP cites for comments with PostgreSQL's ltree support on any database with reasonable string indexing.
Anyone know the name of that technique?