4 ms·

Incidentally I came across this while trying to find information about how reddit stores threaded comments. I've read they use postgres and while I've also read

by brett 19y ago

Incidentally I came across this while trying to find information about how reddit stores threaded comments. I've read they use postgres and while I've also read about many workable techniques to force hierarchical (and frequently reordered) comments into a relational db these solutions all sort of make me cringe. I'd welcome anyone's ideas here as well.

aston 19y ago
I did a quick and dirty forum a couple years back that now serves up hundreds of new threads a day (having tens, sometimes hundreds of messages each). My solution was to store a comment thread in display order in the database with hinting as to how deep in the heirarchy the comment is. Optimizes for output, although with some cost every time something gets posted. Luckily, for most forums, views outnumber posts by hundreds of times. The one issue that system has is that if you're doing a lot of reordering, let's say from quality scores. In that case you'll basically have to remake the thread after every post and after vote that makes a difference. Not recommended...
twism 19y ago
i am in the process of making a news.yc clone... threaded comments are not as easy as it looks on news.yc. [edit] especially when the comments get reordered on votes.
- aston 19y ago
  If you're trying to mimic this forum with a database solution, it's going to be a pain. PG's keeping this stuff in memory, almost certainly as the tree that it is. edit on the edit: scratch that.
  - nostrademons 19y ago
    I mentioned a possible solution here: http://news.ycombinator.com/item?id=33902 http://news.ycombinator.com/item?id=33902, but I'm really commenting because there's a really cool connection between PG's approach of storing it as an in-memory tree and my approach of a 2048-bit index: Y'know how in a typical CS datastructures course you'll have to build a heap, and then reimplement with an array? A heap is conceptually a balanced binary tree where every leaf is filled, while there's nothing tree-like about an array. However, your CS profs were trying to get across that any binary tree can be stored as an array, with the root in position 0, its leaves in positions 1 and 2, their leaves in positions 3, 4, 5, 6, etc. If a node doesn't have a leaf, that position in the array is empty. Normally this is very inefficient - a totally-unbalanced (linked list) binary tree of length 20 would require a 1MB array to hold it. However, heaps are always perfectly balanced, so an array really is the most efficient implementation for them. By restricting users to a certain number of replies to each comment (65,536), I'm effectively constraining an arbitrary tree structure to a 65,536-ary tree. Which can then be represented by an array. If held in memory, it'd be a very sparse and inefficient array. But databases are excellent at storing sparse arrays. If I don't store a potential key, it doesn't take up any space in the DB. And with a good indexing system, I can reference any element in constant time (well, O(logN), but the log base for B-trees is so huge that it might as well be constants). So, I'm really just applying some of the meta-principles of CS coursework to basic data structures. (Actually, I got the idea off a Slashdot posting and had to figure very little of this out on my own, but it's still really cool.) Incidentally, there's apparently a deep connection between number systems and tree structures. You can read more about it in Chris Okasaki's Purely Functional Data Structures. Apparently, every number system corresponds to a data structure. For example, Peano arithmetic = linked lists, binary numbers = binary trees, fibonacci numbers = binomial heaps, etc. There's a short presentation on it here: http://www.informatik.uni-bonn.de/~ralf/talks/BCTCS.pdf http://www.informatik.uni-bonn.de/~ralf/talks/BCTCS.pdf, and I'd strongly recommend the book.
    - pg 19y ago
      You probably don't even need to be using the word "bit" unless you're writing something a lot more performance intensive than a forum.
      - earthboundkid 19y ago
        Optimized ob. quote: "Premature → evil."
    - Jd 19y ago
      Just thinking off the cuff here, but couldn't one store a lisp-style list as a string in a relational database. If I was using Ruby on Rails, I could simply build a simple lisp interpreter in Ruby to parse the string, then capture it as an in-memory tree. This way I would only have active items in memory and could use some of the advantages of the standard web development platforms for whatever else I was doing. Edit: See Ruby/Lisp for one such already built interpreter.
      - nostrademons 19y ago
        Sure you could. You could also select all comments on the item and rebuild the tree in-memory, as Vlad suggests elsewhere on this thread. The code isn't even as hard as I'd thought it'd be: comments = dbh.query('SELECT * FROM comments WHERE news_id = $newsid') response_tree = {} for comment in comments: comment.children = [] response_tree[comment.id] = comment for comment in comments: response_tree[comment.parent_id].children.append(comment) The nifty thing about storing it in the database is that you need no application-level post-processing, you can take advantage of the DB for ad-hoc queries (what if you want to show subtrees of all posts by a certain user, like the "threads" page here?), and it happens to map to a set of simple and fast operations provided by most databases.
        Jd 19y ago
        After some reflection, I suppose my only hesitation with this method is that it locks one into dealing with the comments in a particular way, whereas the lisp model I outlined is easily adaptable to a variety of schemas. However, I'm not sure how else one would want to model things. Must think more...
- euccastro 19y ago
  What's hard about threaded comments, exactly?
  - twism 19y ago
    how you store them, to how they are fetched, to how they are displayed and arranged according to popularity (i think thats how news.yc works) on every vote.
nostrademons 19y ago
The approach I took on Diffle (http://www.diffle.com/ http://www.diffle.com/ - unfortunately it hasn't been exercised as we haven't really got traction yet) was to store the comment ID as a varbinary(255). A child comment takes the ID of the parent and then appends a 2-byte sequential number. So, the first comment is 0x0001, the second is 0x0002, a reply to the second is 0x00020001, a second reply is 0x00020002, the third is 0x0003, a reply to the third is 0x00030001, etc. To find the children of a comment, you look for all comments where the parent's ID is a prefix. MySQL can use leftmost-prefixes as indexes, so this computes very quickly. Also, with the standard varbinary collating order, 0x01 sorts before 0x0101, 0x0102, 0x02, etc, so all I have to do is order by the ID and everything will come out in proper threaded order. And nesting depth is calculated easily by len(id) / 2. Reordering can be done just by looking at all records whose IDs contain the parent as a prefix and have a length 2 greater than the parent, and then renumbering them. This should be computationally feasible in most cases. This does limit users to 65,536 replies to a single comment, and a maximum comment nesting depth of 127. Based on my experience with some very active LiveJournal threads, I considered these to be acceptable limitations (LJ limits comments to 5000/post anyway). A nesting depth of 127 would be nearly 2400 pixels over, so it's not like it'd all fit on one screen anyway.
- vlad 19y ago
  Why not just store the parentid (can be another comment or the news topic), username (instead of userid so you don't have to access the users table), and votecount for each comment? Also, each comment should have a newsid field that points to the original newstopic. The left-most posts would have the parentid and newsid that were the same (or parentid can be zero, depending on how you do it). But any replies would have the parentid to the parent comment, but the newsid would still point to the newstopic. Then you just run an SQL query to find all comments with the newsid for that newstopic. You won't have to join any tables. After that, with everything in memory, you can just sort the way it has to be. Finally, you can cache the page in memory or a file in case the page doesn't change for the next set of visitors.
  - nostrademons 19y ago
    How do you get the full thread for a given parent? Selecting based on the parentid alone gives you only immediate descendants. Recursive queries are generally a no-no, as they drag your performance down fairly quickly. Selecting based on the newsid gives you every single comment on the item, and then you'll have to do a lot of work (basically building up the full tree structure in memory) to find out which are children. For a site with traffic like news.yc, it's probably acceptable, but it's still more complicated to code than a simple select.

by brett 19y ago

aston 19y ago

I did a quick and dirty forum a couple years back that now serves up hundreds of new threads a day (having tens, sometimes hundreds of messages each). My solution was to store a comment thread in display order in the database with hinting as to how deep in the heirarchy the comment is. Optimizes for output, although with some cost every time something gets posted. Luckily, for most forums, views outnumber posts by hundreds of times. The one issue that system has is that if you're doing a lot of reordering, let's say from quality scores. In that case you'll basically have to remake the thread after every post and after vote that makes a difference. Not recommended...

twism 19y ago

i am in the process of making a news.yc clone... threaded comments are not as easy as it looks on news.yc. [edit] especially when the comments get reordered on votes.

aston 19y ago
If you're trying to mimic this forum with a database solution, it's going to be a pain. PG's keeping this stuff in memory, almost certainly as the tree that it is. edit on the edit: scratch that.
- nostrademons 19y ago
  I mentioned a possible solution here: http://news.ycombinator.com/item?id=33902 http://news.ycombinator.com/item?id=33902, but I'm really commenting because there's a really cool connection between PG's approach of storing it as an in-memory tree and my approach of a 2048-bit index: Y'know how in a typical CS datastructures course you'll have to build a heap, and then reimplement with an array? A heap is conceptually a balanced binary tree where every leaf is filled, while there's nothing tree-like about an array. However, your CS profs were trying to get across that any binary tree can be stored as an array, with the root in position 0, its leaves in positions 1 and 2, their leaves in positions 3, 4, 5, 6, etc. If a node doesn't have a leaf, that position in the array is empty. Normally this is very inefficient - a totally-unbalanced (linked list) binary tree of length 20 would require a 1MB array to hold it. However, heaps are always perfectly balanced, so an array really is the most efficient implementation for them. By restricting users to a certain number of replies to each comment (65,536), I'm effectively constraining an arbitrary tree structure to a 65,536-ary tree. Which can then be represented by an array. If held in memory, it'd be a very sparse and inefficient array. But databases are excellent at storing sparse arrays. If I don't store a potential key, it doesn't take up any space in the DB. And with a good indexing system, I can reference any element in constant time (well, O(logN), but the log base for B-trees is so huge that it might as well be constants). So, I'm really just applying some of the meta-principles of CS coursework to basic data structures. (Actually, I got the idea off a Slashdot posting and had to figure very little of this out on my own, but it's still really cool.) Incidentally, there's apparently a deep connection between number systems and tree structures. You can read more about it in Chris Okasaki's Purely Functional Data Structures. Apparently, every number system corresponds to a data structure. For example, Peano arithmetic = linked lists, binary numbers = binary trees, fibonacci numbers = binomial heaps, etc. There's a short presentation on it here: http://www.informatik.uni-bonn.de/~ralf/talks/BCTCS.pdf http://www.informatik.uni-bonn.de/~ralf/talks/BCTCS.pdf, and I'd strongly recommend the book.
  - pg 19y ago
    You probably don't even need to be using the word "bit" unless you're writing something a lot more performance intensive than a forum.
    - earthboundkid 19y ago
      Optimized ob. quote: "Premature → evil."
  - Jd 19y ago
    Just thinking off the cuff here, but couldn't one store a lisp-style list as a string in a relational database. If I was using Ruby on Rails, I could simply build a simple lisp interpreter in Ruby to parse the string, then capture it as an in-memory tree. This way I would only have active items in memory and could use some of the advantages of the standard web development platforms for whatever else I was doing. Edit: See Ruby/Lisp for one such already built interpreter.
    - nostrademons 19y ago
      Sure you could. You could also select all comments on the item and rebuild the tree in-memory, as Vlad suggests elsewhere on this thread. The code isn't even as hard as I'd thought it'd be: comments = dbh.query('SELECT * FROM comments WHERE news_id = $newsid') response_tree = {} for comment in comments: comment.children = [] response_tree[comment.id] = comment for comment in comments: response_tree[comment.parent_id].children.append(comment) The nifty thing about storing it in the database is that you need no application-level post-processing, you can take advantage of the DB for ad-hoc queries (what if you want to show subtrees of all posts by a certain user, like the "threads" page here?), and it happens to map to a set of simple and fast operations provided by most databases.
      - Jd 19y ago
        After some reflection, I suppose my only hesitation with this method is that it locks one into dealing with the comments in a particular way, whereas the lisp model I outlined is easily adaptable to a variety of schemas. However, I'm not sure how else one would want to model things. Must think more...
euccastro 19y ago
What's hard about threaded comments, exactly?
- twism 19y ago
  how you store them, to how they are fetched, to how they are displayed and arranged according to popularity (i think thats how news.yc works) on every vote.

nostrademons 19y ago

The approach I took on Diffle (http://www.diffle.com/ http://www.diffle.com/ - unfortunately it hasn't been exercised as we haven't really got traction yet) was to store the comment ID as a varbinary(255). A child comment takes the ID of the parent and then appends a 2-byte sequential number. So, the first comment is 0x0001, the second is 0x0002, a reply to the second is 0x00020001, a second reply is 0x00020002, the third is 0x0003, a reply to the third is 0x00030001, etc. To find the children of a comment, you look for all comments where the parent's ID is a prefix. MySQL can use leftmost-prefixes as indexes, so this computes very quickly. Also, with the standard varbinary collating order, 0x01 sorts before 0x0101, 0x0102, 0x02, etc, so all I have to do is order by the ID and everything will come out in proper threaded order. And nesting depth is calculated easily by len(id) / 2. Reordering can be done just by looking at all records whose IDs contain the parent as a prefix and have a length 2 greater than the parent, and then renumbering them. This should be computationally feasible in most cases. This does limit users to 65,536 replies to a single comment, and a maximum comment nesting depth of 127. Based on my experience with some very active LiveJournal threads, I considered these to be acceptable limitations (LJ limits comments to 5000/post anyway). A nesting depth of 127 would be nearly 2400 pixels over, so it's not like it'd all fit on one screen anyway.

vlad 19y ago
Why not just store the parentid (can be another comment or the news topic), username (instead of userid so you don't have to access the users table), and votecount for each comment? Also, each comment should have a newsid field that points to the original newstopic. The left-most posts would have the parentid and newsid that were the same (or parentid can be zero, depending on how you do it). But any replies would have the parentid to the parent comment, but the newsid would still point to the newstopic. Then you just run an SQL query to find all comments with the newsid for that newstopic. You won't have to join any tables. After that, with everything in memory, you can just sort the way it has to be. Finally, you can cache the page in memory or a file in case the page doesn't change for the next set of visitors.
- nostrademons 19y ago
  How do you get the full thread for a given parent? Selecting based on the parentid alone gives you only immediate descendants. Recursive queries are generally a no-no, as they drag your performance down fairly quickly. Selecting based on the newsid gives you every single comment on the item, and then you'll have to do a lot of work (basically building up the full tree structure in memory) to find out which are children. For a site with traffic like news.yc, it's probably acceptable, but it's still more complicated to code than a simple select.