Comment by nostrademons | Hacker News Reader

Comment by nostrademons | Hacker News Reader

Parent Full thread

The approach I took on Diffle (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.

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.

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.

You would find the full thread by searching for comments with the appropriate newsid.

To simplify the recursive function (using data in memory, not in the database), you could also have another field, called indent, that stores the level in the comments.

You could find all the comments with one SQL statement (where newsid = news.id), then go through each level of each comment, and sort it that way.

You could even make the parentid field a double, so you would store 123.4 where 123 would be the parent and 4 would be the indentation level.

I guess the difference is, do you want to store everything in one field or have different fields for everything?

I think this gives the original poster many options to think about. To me, a recursive function would be easier to write than coming up with ways to combine multiple fields into one using MySQL.

I think the order of optimization is: 1) Optimize so you can use a cached result if it exists 2) If the cache is out of the date, try to make just one SQL call 3) don't use table joins 4) reorder the data as needed in memory, then save it to a cache

As far as the single SQL call goes, I don't think it matters whether you have 5 fields or 30 in the actual table as long as you only request the fields you need, but I could be wrong.

By the way, do you have any other interesting examples?

i'm not sure why nobody has said this already... but why would you need an extra filed for keeping indentattion nuber when you can use <pre> in html for that.

Interesting examples of what?

Reply on news.ycombinator.com