5 ms·

I see. Cool. I'm building an HN clone now. Hierarchical comments are a fun challenge. Any tips?

• orf 11y ago
  Postgres recursive queries make them pretty simple to deal with. This[1] is the query I used to pull a list of all a stories children recursively. 1. https://gist.github.com/orf/5565a572c6ddda039d6f https://gist.github.com/orf/5565a572c6ddda039d6f
  • Kinnard 11y ago
    Hmmm, I'm trying to decide between this recursive query or something using ltrees. Can't make up my mind . . . [1] https://truongtx.me/2014/02/28/tree-structure-query-with-postgresql/ https://truongtx.me/2014/02/28/tree-structure-query-with-pos... [2] http://stackoverflow.com/questions/603894/is-postgresqls-ltree-module-a-good-fit-for-threaded-comments http://stackoverflow.com/questions/603894/is-postgresqls-ltr...
• Kenji 11y ago
  Yeah. If you store them in a relational database you will grow a couple of grey hairs because you're essentially forcing a tree structure into a table structure. The concepts clash and it's kind of a pain, but possible since every post has 1 unique parent, so you can make upwards references and rebuild a tree from that.
  • martin-adams 11y ago
    A great technique I've used for many years to store hierarchical data is by using a Nested Set Model (https://en.wikipedia.org/wiki/Nested_set_model https://en.wikipedia.org/wiki/Nested_set_model) It works a treat as you can query the whole tree in one SQL statement but preserve the nesting for formatting.
    • Kenji 11y ago
      Thank you sir for pointing that out. This looks very interesting and I might even implement that in my own blog at some point in time. I thought about doing something similar to that (without actually knowing this technique) but I shyed away precisely because of the price you pay at insertion time. EDIT: I've been thinking some more about this. Another possibility would be to limit the depth of the tree to, say, 8 (which should be reasonable) and then make 8 fields, one for each ancestor (parent, grandparent, and so on). Changing the tree will become a nightmare but all queries for subtrees will be blazingly fast.
      • MichaelGG 11y ago
        Since individual comment threads are never that big, just store the root parent ID and query on that. Then reconstruct in code.
        • Kenji 11y ago
          Yeah that's how I currently implemented it on my site, but it can't harm to overthink the solution of performance problems I don't (yet?) have ;)
          • krapp 11y ago
            You could probably solve more nonexistent problems with caching than by limiting thread depth.
            • deleted 11y ago
              [deleted]
            • krapp 11y ago
              To clarify - more users are going to read and refresh pages than actually post, so making certain not every GET request results in a new database query would probably improve performance more than trying to limit the number of rows in each query. Query performance obviously matters, but with a HN like site, it's probably not going to be so critical that limiting the depth of threads is even worth the effort.
• toupeira 11y ago
  The "closure table" approach works best if you have frequent reads and writes, see e.g. https://coderwall.com/p/lixing/closure-tables-for-browsing-trees-in-sql https://coderwall.com/p/lixing/closure-tables-for-browsing-t...
• Kinnard 11y ago
  Hmmm, toooo many options. How do I decide between them. Sort of a DB noob.
• krapp 11y ago
  A simple method (a modified adjacency list) I've used just stores the root id, parent id and id of each post together. You can get the entire tree from any root post easily (everything shares the same root id) but getting the whole subtree beyond immediate children takes recursion. I find that you don't even have to worry about treating the data as a tree in most cases until the very end. What you want to actually deal with is a flat array with the ids (root,parent,id) arranged in rendering order, and to have the tree built in the HTML. The data set from the DB doesn't even have to represent the tree structure directly, as long as you can sort it elsewhere. You can even have two arrays - one (say, an associative array) with the data, and another basic array with the ids. Sort just the array with the ids, then use those as keys to iterate the data array when building the html, so you can avoid ever having to sort the larger array (which as luck has it just happens to be optimized for non-linear access anyway.) I should probably mention, I thought this was terribly clever when I did it in PHP, before I was aware that all arrays in PHP are basically the same, so it was mostly pointless overoptimization. Building something like an unordered list in HTML from that array then becomes a matter of adding or removing <UL> elements based on the relative change in depth for each subsequent id. Depth is easy to find by checking if an item's parent is (or isn't) the same as the id of the previous element. The actual tree never exists in code until the unordered list is rendered in the browser. Also here's a good reference on Stack Overflow of different methods to do the same thing: https://stackoverflow.com/questions/2175882/how-to-represent-a-data-tree-in-sql https://stackoverflow.com/questions/2175882/how-to-represent... If you actually know what you're doing beforehand, probably ignore everything I just said and go with nested sets. My method is, admittedly, naive and better programmers are probably chuckling at it over the beverage of their choice, but it does work and it seems to be decently fast.