Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Representing Trees in PostgreSQL

woss.name

Post reply on HN
Print view View original

41–50 of 60 posts

Re: Representing Trees in PostgreSQL

#41

Post by stephen_mcd »

Walkman wrote: post #35

I don't know if ActiveRecord is capable of doing this, but here is how to do it with Django ORM: in models.py: class Node(models.Model): parent = models.ForeignKey('self', related_name='children') in the view: nodes = Node.objects.prefetch_related('children') in template: {% for node in nodes %} {% for subnode in node.children.all %} ... {% endfor %} {% endfor %} This will make exactly two queries; one for all the pa…

You can easily render a tree many levels deep in O(n) time using a single DB query as an adjacency list with a lookup dictionary:

http://blog.jupo.org/2010/01/26/linear-traversal-of-adjacenc...

No need for mptt either.

Re: Representing Trees in PostgreSQL

#42

Post by batbomb »

First off: The first example is exactly what a relational database is for. It's a "tree" structure only because it's several 1:many joins. It is true that ORMs aren't that amenable to composition and lots of dynamic joins, but that's not the fault of the database, it's the fault of the ORMs.

That being said, I've tried all these methods before across a few different DBMS.

IMO a good way to go about this all is to actually just reimplement a file system; You have a caching virtual file system in your application, and store data as key:parentKey:name (equivalent-ish dentry:parentDentry:fileName) in every table which contains child nodes. It's fast, often more predictable, and definitely more portable (as you aren't relying on DMBS-specific constructs). It's also amenable to partitioning/sharding by parent key. You can drastically reduce the amount of queries that are being sent. Also, if you use a b+tree as an index for your paths, you can invalidate cache/subtrees pretty fast in your application.

Of course, you end up duplicating functionality of the database, and if there is a lot of latency between you and the DB, this might not be the best method (or it might, depending).

It would be nice if MySQL finally supported CTEs.

Re: Representing Trees in PostgreSQL

#44

Post by bojanz »

Someone wrote: post #33
barosl wrote: post #9

Does anyone remember how Drupal handles the hierarchical comments? It maintains a "sort key" field for each comment, which consists of multiple index numbers for all levels, much like the section numbers in Wikipedia. 1 1.1 1.2 2 2.1 2.1.1 2.1.2 2.1.2.1 In this way, displaying comments in a tree form is trivial. Just ORDER BY the sort key. I find it brilliant for applying to such an application.

But beware of what may happen when you get over 9: 1 1.1 1.2 10 2 2.1 To support that, you will have to be careful when picking collation order, and binary collation will not do it. It may be better to use fixed-width numbers with leading zeroes instead, but that, of course, may unnecessarily grow the space used by the table. And of course, that also is what RCS and SCCS use for numbering revisions.

I've done research on this and other problems, based on Drupal's solutions: https://bojanz.wordpress.com/2014/04/25/storing-hierarchical...

Re: Representing Trees in PostgreSQL

#45

Post by Retra »

Someone wrote: post #33
barosl wrote: post #9

Does anyone remember how Drupal handles the hierarchical comments? It maintains a "sort key" field for each comment, which consists of multiple index numbers for all levels, much like the section numbers in Wikipedia. 1 1.1 1.2 2 2.1 2.1.1 2.1.2 2.1.2.1 In this way, displaying comments in a tree form is trivial. Just ORDER BY the sort key. I find it brilliant for applying to such an application.

But beware of what may happen when you get over 9: 1 1.1 1.2 10 2 2.1 To support that, you will have to be careful when picking collation order, and binary collation will not do it. It may be better to use fixed-width numbers with leading zeroes instead, but that, of course, may unnecessarily grow the space used by the table. And of course, that also is what RCS and SCCS use for numbering revisions.

Or use your decimal as a place extension instead of a hierarchal separator. Your tree would look like this:

  1 
  11
  12
  1.0
  2
  21
Then you just ensure that '.' sorts after all digits. (Probably by using a different symbol.) Basically, the '.' means "insert after."

Re: Representing Trees in PostgreSQL

#46

Post by crescentfresh »

rosser wrote: post #8

Other comments have mentioned this as well, but recursive CTEs are a very effective technique for representing trees, and they work very well in PostgreSQL.

We are using CTEs in SQL Server (2008 pre R2), with a not too large object graph, and find the query performance inadequate for our realtime needs. We ended up flattening and caching graph representations in order to remove the bottleneck. The CTE query was the starting point to further queries throughout our applications so it benefitted all applications to introduce this layer.

Of course, then we had two problems on our hands. :)

Re: Representing Trees in PostgreSQL

#47

Post by ketralnis »

Someone wrote: post #33
barosl wrote: post #9

Does anyone remember how Drupal handles the hierarchical comments? It maintains a "sort key" field for each comment, which consists of multiple index numbers for all levels, much like the section numbers in Wikipedia. 1 1.1 1.2 2 2.1 2.1.1 2.1.2 2.1.2.1 In this way, displaying comments in a tree form is trivial. Just ORDER BY the sort key. I find it brilliant for applying to such an application.

But beware of what may happen when you get over 9: 1 1.1 1.2 10 2 2.1 To support that, you will have to be careful when picking collation order, and binary collation will not do it. It may be better to use fixed-width numbers with leading zeroes instead, but that, of course, may unnecessarily grow the space used by the table. And of course, that also is what RCS and SCCS use for numbering revisions.

In postgres specifically you can use an int array field rather than a string

Re: Representing Trees in PostgreSQL

#49

Post by mappu »

Random data point: I have a hierarchal authentication system under MySQL (no recursive query support). My schema does the most obvious thing of having user.parent as a user_id (adjacency model).

My most common query is to find whether user X is a child of user Y.

My solution was to use application-level triggers to maintain a separate lookup table, so i can simply do `user_id IN (SELECT child_id FROM lookup_table WHERE parent_id = Y)` as an additional search clause. With appropriate indexes it's very fast to query, and i can do partial updates to maintain the lookup table.

If my most common tree query was something else (e.g. enumerate children in sorted order) then i'd need some other data structure.

Re: Representing Trees in PostgreSQL

#50

Post by maaku »

> There’s also a twist on the Nested Sets model, called the nested interval model, where the nodes are given two numbers that represent the numerator and denominator of a fraction, but it doesn’t seem so popular, and was too complex to wrap my head around!

...and the author just wrote-off the best performing generic tree solution, because "it was too complex to wrap my head around!"

:facepalm:

Post reply on HN