9 ms·

Representing Trees in PostgreSQL

164 points by mathie 12y ago

dharbin 12y ago
There's also the ltree module which is built-in to postgres: http://www.postgresql.org/docs/9.1/static/ltree.html http://www.postgresql.org/docs/9.1/static/ltree.html
kpmah 12y ago
There is also ltree http://www.postgresql.org/docs/9.3/static/ltree.html http://www.postgresql.org/docs/9.3/static/ltree.html Adjacency lists also don't perform that badly with recursive queries in my experience.
- rickmode 12y ago
  This. The project I'm on used materialized paths, which lead to great pain. I investigated nested intervals ... and they could't achieve the tree depths we needed (we were modeling a file system tree). We are back to adjacency lists (using a parent ID) but redesigned to avoid the need for recursive ancestor and descendant queries. _But_ the RDBMS doesn't support recursive queries and I've been curious about PostgreSQL's recursive query support. I played with it, but not on a fully loaded database with deep trees of data. Does PostgreSQL recursive query support work well with deep trees (> 100 levels) on tables with tens of millions or more rows?
  - andrewflnr 12y ago
    Can you elaborate on how materialized path caused pain? Was it more performance or maintenance? I would have expected MP to be a good fit for modeling a file system.
    - rickmode 12y ago
      First, renames and moves require updating all descendants. Second, the materialized path's length exceeded the database's indexable length limit. (MySQL, the DB in question, has a default index limit of 767 bytes, so only first 767 bytes are indexed.) There are ways around these issues (like using "UPDATE ... WHERE" rather than using an ORM to walk the tree and update... sigh). We also had other app-specific / design-specific issues too that swamped these issues performance wise. I'm hopefully we won't need ancestor and descendant queries again in our re-design. But I'm keeping PostgreSQL with its Common Table Expression stuff--the thing that facilities recursive queries--in my back pocket. It's that or use a stored procedure to build the capability by hand.
- pjungwir 12y ago
  Here is a blog post I wrote about using a recursive query to pull out this kind of tree: http://illuminatedcomputing.com/posts/2014/09/postgres-cte-for-threaded-comments/ http://illuminatedcomputing.com/posts/2014/09/postgres-cte-f... The problem I was tackling was making the tree sorted like you see in threaded, scored comments.
techtalsky 12y ago
There's a great Ruby on Rails gem called acts_as_sane_tree (after the non-recursive acts_as_tree) that uses postgresql's recursive queries. I'm using it on a project and have found it useful with good performance: https://github.com/chrisroberts/acts_as_sane_tree https://github.com/chrisroberts/acts_as_sane_tree
- btown 12y ago
  Looks like the main fork hasn't been updated since 2012. Is there an updated version you recommend for Rails 4 compatibility?
  - techtalsky 12y ago
    Hm, I didn't realize that. I'm using it on a Rails 4 project and haven't had any problems.
- elliotec 12y ago
  I've used gem awesome_nested_set with lots of success in the past. https://github.com/collectiveidea/awesome_nested_set https://github.com/collectiveidea/awesome_nested_set. Updated quite often, Rails 4 supported
  - techtalsky 12y ago
    Yeah, the Nested Set model is cool but it does not use recursive postgresql queries under the hood: http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ http://mikehillyer.com/articles/managing-hierarchical-data-i...
joesmo 12y ago
> We could have retrieved all the appropriate data with a single query, but that means reconstructing the tree from a flat set of rows we got back from PostgreSQL. Doing that sort of thing in the view would be hienous. Implement a view helper to take the flat data and return a hierarchical structure that you can render.
- smoyer 12y ago
  And store the data in PostgreSQL as a modified-preordered list so that the data is already in the order you need to efficiently recreate the object graph (note that this implies many reads for each write, since tree modifications become the costly operation).
m0ppers 12y ago
with recursive is actually VERY quick in postgresql (adjacency model). currently using that and thoroughly tested it. simple, very quick and no hassle to update it (as the other options). Compared to a mysql with nested set postgres using with recursive is a life changer :D
netghost 12y ago
There are some more tricks you can do using postgres' arrays to efficiently query the data: http://monkeyandcrow.com/blog/hierarchies_with_rails/ http://monkeyandcrow.com/blog/hierarchies_with_rails/ Namely using the && operator let's you make use of indices on the materialized paths. We've been using it in production for years to great effect.
rosser 12y ago
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.
- gtaylor 12y ago
  We have used these for our discussion features on Pathwright. With ltree, you don't have as much flexibility when sorting by multiple values. With the Recursive CTE, you can go nuts and still end up very efficient. I believe Disqus uses this, as well: http://cramer.io/2010/05/30/scaling-threaded-comments-on-django-at-disqus/ http://cramer.io/2010/05/30/scaling-threaded-comments-on-dja...
- crescentfresh 12y ago
  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. :)
barosl 12y ago
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.
- twerquie 12y ago
  This pattern is commonly called "materialized path", if anyone is trying to search for it.
  - barosl 12y ago
    Thanks! I wanted to know what it is called.
  - vkjv 12y ago
    Thanks for the name! We do this internally to store various levels of product data in a single mongo collection (e.g., style, variant).
  - benjohnson 12y ago
    A similar system is also heavily used in the construction world in their "Work Breakdown Structure" - a borrowing on how they document airplane parts that are part of an assembly, that are part of a module, that part of a structure. http://en.wikipedia.org/wiki/Work_breakdown_structure http://en.wikipedia.org/wiki/Work_breakdown_structure
- Someone 12y ago
  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.
Todd 12y ago
A good book on the subject is Joe Celko's Trees and Hierarchies in SQL for Smarties. http://www.amazon.com/Hierarchies-Smarties-Edition-Kaufmann-Management/dp/0123877334 http://www.amazon.com/Hierarchies-Smarties-Edition-Kaufmann-... He spends a chapter on each of the models outlined in this post: adjacency, path, and nested set models.
- platz 12y ago
  I've done nested set before; it's interesting - very fast for queries, but requires a lengthy insert/update cost. Also, team members were absolutely clueless as to what was really going on. I'm not sure nested sets are really much faster than what modern rdbms's can provide today.
  - tempVariable 12y ago
    In addition to expensive insert/update, it is necessary to keep the left and right boundaries across ALL of your entries in perfect order. If the boundaries get out of whack, fixing the tree is a nightmare scenario. I worked on a multi-tenant application with distinct trees present in one table and with one tree per table and so on. Fun fun fun!
    - alistairbayley 12y ago
      I think the nested intervals model, a refinement of nested sets, solves this slow update problem: http://www.rampant-books.com/art_vadim_nested_sets_sql_trees.htm http://www.rampant-books.com/art_vadim_nested_sets_sql_trees... But I've never had to use it, so I am just guessing. Same article, different site: https://communities.bmc.com/docs/DOC-9902 https://communities.bmc.com/docs/DOC-9902 And a paper: http://www.sigmod.org/publications/sigmod-record/0506/p47-article-tropashko.pdf http://www.sigmod.org/publications/sigmod-record/0506/p47-ar... Here's a comparison of the different approaches in a matrix: http://vadimtropashko.wordpress.com/2008/08/09/one-more-nested-intervals-vs-adjacency-list-comparison/ http://vadimtropashko.wordpress.com/2008/08/09/one-more-nest...
  - rickmode 12y ago
mattdeboard 12y ago
What are the upsides to this vice using a graph database like Neo4j?
- mikesname 12y ago
  You get all the benefits of a mature and very full-featured RMDBS. Neo4j is a great database, and I use it myself for a project that involves lots of deep hierarchies. But it has a fairly sparse feature-set where schema enforcement and data integrity checking are concerned; you basically have to add all that stuff yourself at the application level which can amount to a lot of work.
  - btown 12y ago
    To second this, if you're using multiple languages to write to your database, you almost certainly want that schema enforcement at the DB level. We decided not to go with Neo as our canonical database for exactly that reason. Its main strength is probably as a follower or slave to a RDBMS or log file, which is how it seems to be used in enterprise - when you want to do graph-based analytics, you bulk-load a snapshot of your non-graph-stored DB into Neo, then run read-only workloads.
- threeseed 12y ago
  Another option is to add PostgreSQL support to Titan (http://thinkaurelius.github.io/titan/ http://thinkaurelius.github.io/titan/).
savagej 12y ago
I've used django-mptt to represent a tree of human phenotypes before. It was fast and quite an easy api to use. I was using PostgreSQL as the backend. https://www.djangopackages.com/packages/p/django-mptt/ https://www.djangopackages.com/packages/p/django-mptt/
- robertfw 12y ago
  I've also used django-mptt and just wanted to throw another vote behind it in case anyone is considering using it. Our data structure was a good fit for MPTT (many reads, few writes) so I can't comment on how it would behave in the opposite scenario. Nice API, very easy to use from a developer standpoint. We were using MySQL.
  - jhgg 12y ago
    Likewise. I've done some heavy modification ontop of django-mptt to support limiting tree depth when querying, calculating total children, querying siblings, etc... https://gist.github.com/jhgg/32a379e34c8a56303295 https://gist.github.com/jhgg/32a379e34c8a56303295
coleifer 12y ago
Another option for storing tree structures is the closure table [1]. It acts as a sort of "many-to-many" junction table between the tree nodes, storing the relationships between each. [1] https://coderwall.com/p/lixing/closure-tables-for-browsing-trees-in-sql https://coderwall.com/p/lixing/closure-tables-for-browsing-t...
- chdir 12y ago
  +1, Related reading (all from Bill Karwin of SQL Antipatterns fame): http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree/192462#192462 http://stackoverflow.com/questions/192220/what-is-the-most-e... http://www.slideshare.net/billkarwin/models-for-hierarchical-data http://www.slideshare.net/billkarwin/models-for-hierarchical... http://karwin.blogspot.in/2010/03/rendering-trees-with-closure-tables.html http://karwin.blogspot.in/2010/03/rendering-trees-with-closu...
jeremyevans 12y ago
Not sure about ActiveRecord, but Sequel has supported using recursive common table expressions for loading all descendants in a given branch (or branches) of a tree for over 4 years using the rcte_tree plugin: http://sequel.jeremyevans.net/rdoc-plugins/classes/Sequel/Plugins/RcteTree.html http://sequel.jeremyevans.net/rdoc-plugins/classes/Sequel/Pl...
jimbokun 12y ago
If it's a small tree, you could encode it as a single JSON object and query on it using PostgreSQL's JSON support. http://schinckel.net/2014/05/25/querying-json-in-postgres/ http://schinckel.net/2014/05/25/querying-json-in-postgres/
Walkman 12y ago
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 parent nodes, and one for the children nodes. Django will make the pairing automagically, so you don't have to do it in view code.
- caust1c 12y ago
  Unfortunately, this still only gets the children of the root. If you want to be able to recursively get all the children and grandchildren of a root, you're going to be doing (N - leaves) queries where N is the number of Nodes in the tree. However, there is of course a django package to help with this and gathers all the nodes you care about into one query: https://github.com/django-mptt/django-mptt https://github.com/django-mptt/django-mptt
- herge 12y ago
  If you ever need to deal with trees deeper than one level in django, I'd highly recommend looking at (as mentioned in another comment): https://www.djangopackages.com/packages/p/django-mptt/ https://www.djangopackages.com/packages/p/django-mptt/
- stephen_mcd 12y ago
  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-adjacency-list-trees/ http://blog.jupo.org/2010/01/26/linear-traversal-of-adjacenc... No need for mptt either.
chx 12y ago
Bojan Živanović and I have a writeup on this whole tree storage business https://bojanz.wordpress.com/2014/04/25/storing-hierarchical-data-materialized-path/ https://bojanz.wordpress.com/2014/04/25/storing-hierarchical... here.
batbomb 12y ago
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.
deleted 12y ago
[deleted]
glibgil 12y ago
Should be titled representing paths. Trees are easy: id, parent_id. Paths are tricky.
mappu 12y ago
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.
maaku 12y ago
> 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:
quipo 12y ago
Covered this and several other techniques here: http://www.slideshare.net/quipo/trees-in-the-database-advanced-data-structures http://www.slideshare.net/quipo/trees-in-the-database-advanc...
jaunkst 12y ago
A graph database comes to mind. It's a different design problem when dealing with deep relationships vs top level relationships. Sometimes you need more deep inherent relational mappings for alogithms to be effecient.
ashmud 12y ago
I used to use code based on Kendall Willets' code. His original site is offline. Archive here: https://web.archive.org/web/20110928135313/http://willets.org/sqlgraphs.html https://web.archive.org/web/20110928135313/http://willets.or... Line from the page: "I just picked up a copy and it looks great! You are right about the whole approach and my stuff stinks." - Joe Celko, author of SQL for Smarties.

164 points by mathie 12y ago

There's also the ltree module which is built-in to postgres: http://www.postgresql.org/docs/9.1/static/ltree.html http://www.postgresql.org/docs/9.1/static/ltree.html

kpmah 12y ago

There is also ltree http://www.postgresql.org/docs/9.3/static/ltree.html http://www.postgresql.org/docs/9.3/static/ltree.html Adjacency lists also don't perform that badly with recursive queries in my experience.

rickmode 12y ago
This. The project I'm on used materialized paths, which lead to great pain. I investigated nested intervals ... and they could't achieve the tree depths we needed (we were modeling a file system tree). We are back to adjacency lists (using a parent ID) but redesigned to avoid the need for recursive ancestor and descendant queries. _But_ the RDBMS doesn't support recursive queries and I've been curious about PostgreSQL's recursive query support. I played with it, but not on a fully loaded database with deep trees of data. Does PostgreSQL recursive query support work well with deep trees (> 100 levels) on tables with tens of millions or more rows?
- andrewflnr 12y ago
  Can you elaborate on how materialized path caused pain? Was it more performance or maintenance? I would have expected MP to be a good fit for modeling a file system.
  - rickmode 12y ago
    First, renames and moves require updating all descendants. Second, the materialized path's length exceeded the database's indexable length limit. (MySQL, the DB in question, has a default index limit of 767 bytes, so only first 767 bytes are indexed.) There are ways around these issues (like using "UPDATE ... WHERE" rather than using an ORM to walk the tree and update... sigh). We also had other app-specific / design-specific issues too that swamped these issues performance wise. I'm hopefully we won't need ancestor and descendant queries again in our re-design. But I'm keeping PostgreSQL with its Common Table Expression stuff--the thing that facilities recursive queries--in my back pocket. It's that or use a stored procedure to build the capability by hand.
pjungwir 12y ago
Here is a blog post I wrote about using a recursive query to pull out this kind of tree: http://illuminatedcomputing.com/posts/2014/09/postgres-cte-for-threaded-comments/ http://illuminatedcomputing.com/posts/2014/09/postgres-cte-f... The problem I was tackling was making the tree sorted like you see in threaded, scored comments.

techtalsky 12y ago

There's a great Ruby on Rails gem called acts_as_sane_tree (after the non-recursive acts_as_tree) that uses postgresql's recursive queries. I'm using it on a project and have found it useful with good performance: https://github.com/chrisroberts/acts_as_sane_tree https://github.com/chrisroberts/acts_as_sane_tree

btown 12y ago
Looks like the main fork hasn't been updated since 2012. Is there an updated version you recommend for Rails 4 compatibility?
- techtalsky 12y ago
  Hm, I didn't realize that. I'm using it on a Rails 4 project and haven't had any problems.
elliotec 12y ago
I've used gem awesome_nested_set with lots of success in the past. https://github.com/collectiveidea/awesome_nested_set https://github.com/collectiveidea/awesome_nested_set. Updated quite often, Rails 4 supported
- techtalsky 12y ago
  Yeah, the Nested Set model is cool but it does not use recursive postgresql queries under the hood: http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ http://mikehillyer.com/articles/managing-hierarchical-data-i...

joesmo 12y ago

> We could have retrieved all the appropriate data with a single query, but that means reconstructing the tree from a flat set of rows we got back from PostgreSQL. Doing that sort of thing in the view would be hienous. Implement a view helper to take the flat data and return a hierarchical structure that you can render.

smoyer 12y ago
And store the data in PostgreSQL as a modified-preordered list so that the data is already in the order you need to efficiently recreate the object graph (note that this implies many reads for each write, since tree modifications become the costly operation).

m0ppers 12y ago

with recursive is actually VERY quick in postgresql (adjacency model). currently using that and thoroughly tested it. simple, very quick and no hassle to update it (as the other options). Compared to a mysql with nested set postgres using with recursive is a life changer :D

netghost 12y ago

There are some more tricks you can do using postgres' arrays to efficiently query the data: http://monkeyandcrow.com/blog/hierarchies_with_rails/ http://monkeyandcrow.com/blog/hierarchies_with_rails/ Namely using the && operator let's you make use of indices on the materialized paths. We've been using it in production for years to great effect.

rosser 12y ago

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.

gtaylor 12y ago
We have used these for our discussion features on Pathwright. With ltree, you don't have as much flexibility when sorting by multiple values. With the Recursive CTE, you can go nuts and still end up very efficient. I believe Disqus uses this, as well: http://cramer.io/2010/05/30/scaling-threaded-comments-on-django-at-disqus/ http://cramer.io/2010/05/30/scaling-threaded-comments-on-dja...
crescentfresh 12y ago
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. :)

barosl 12y ago

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.

twerquie 12y ago
This pattern is commonly called "materialized path", if anyone is trying to search for it.
- barosl 12y ago
  Thanks! I wanted to know what it is called.
- vkjv 12y ago
  Thanks for the name! We do this internally to store various levels of product data in a single mongo collection (e.g., style, variant).
- benjohnson 12y ago
  A similar system is also heavily used in the construction world in their "Work Breakdown Structure" - a borrowing on how they document airplane parts that are part of an assembly, that are part of a module, that part of a structure. http://en.wikipedia.org/wiki/Work_breakdown_structure http://en.wikipedia.org/wiki/Work_breakdown_structure
Someone 12y ago
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.

Todd 12y ago

A good book on the subject is Joe Celko's Trees and Hierarchies in SQL for Smarties. http://www.amazon.com/Hierarchies-Smarties-Edition-Kaufmann-Management/dp/0123877334 http://www.amazon.com/Hierarchies-Smarties-Edition-Kaufmann-... He spends a chapter on each of the models outlined in this post: adjacency, path, and nested set models.

platz 12y ago
I've done nested set before; it's interesting - very fast for queries, but requires a lengthy insert/update cost. Also, team members were absolutely clueless as to what was really going on. I'm not sure nested sets are really much faster than what modern rdbms's can provide today.
- tempVariable 12y ago
  In addition to expensive insert/update, it is necessary to keep the left and right boundaries across ALL of your entries in perfect order. If the boundaries get out of whack, fixing the tree is a nightmare scenario. I worked on a multi-tenant application with distinct trees present in one table and with one tree per table and so on. Fun fun fun!
  - alistairbayley 12y ago
    I think the nested intervals model, a refinement of nested sets, solves this slow update problem: http://www.rampant-books.com/art_vadim_nested_sets_sql_trees.htm http://www.rampant-books.com/art_vadim_nested_sets_sql_trees... But I've never had to use it, so I am just guessing. Same article, different site: https://communities.bmc.com/docs/DOC-9902 https://communities.bmc.com/docs/DOC-9902 And a paper: http://www.sigmod.org/publications/sigmod-record/0506/p47-article-tropashko.pdf http://www.sigmod.org/publications/sigmod-record/0506/p47-ar... Here's a comparison of the different approaches in a matrix: http://vadimtropashko.wordpress.com/2008/08/09/one-more-nested-intervals-vs-adjacency-list-comparison/ http://vadimtropashko.wordpress.com/2008/08/09/one-more-nest...
- rickmode 12y ago

mattdeboard 12y ago

What are the upsides to this vice using a graph database like Neo4j?

mikesname 12y ago
You get all the benefits of a mature and very full-featured RMDBS. Neo4j is a great database, and I use it myself for a project that involves lots of deep hierarchies. But it has a fairly sparse feature-set where schema enforcement and data integrity checking are concerned; you basically have to add all that stuff yourself at the application level which can amount to a lot of work.
- btown 12y ago
  To second this, if you're using multiple languages to write to your database, you almost certainly want that schema enforcement at the DB level. We decided not to go with Neo as our canonical database for exactly that reason. Its main strength is probably as a follower or slave to a RDBMS or log file, which is how it seems to be used in enterprise - when you want to do graph-based analytics, you bulk-load a snapshot of your non-graph-stored DB into Neo, then run read-only workloads.
threeseed 12y ago
Another option is to add PostgreSQL support to Titan (http://thinkaurelius.github.io/titan/ http://thinkaurelius.github.io/titan/).

savagej 12y ago

I've used django-mptt to represent a tree of human phenotypes before. It was fast and quite an easy api to use. I was using PostgreSQL as the backend. https://www.djangopackages.com/packages/p/django-mptt/ https://www.djangopackages.com/packages/p/django-mptt/

robertfw 12y ago
I've also used django-mptt and just wanted to throw another vote behind it in case anyone is considering using it. Our data structure was a good fit for MPTT (many reads, few writes) so I can't comment on how it would behave in the opposite scenario. Nice API, very easy to use from a developer standpoint. We were using MySQL.
- jhgg 12y ago
  Likewise. I've done some heavy modification ontop of django-mptt to support limiting tree depth when querying, calculating total children, querying siblings, etc... https://gist.github.com/jhgg/32a379e34c8a56303295 https://gist.github.com/jhgg/32a379e34c8a56303295

coleifer 12y ago

Another option for storing tree structures is the closure table [1]. It acts as a sort of "many-to-many" junction table between the tree nodes, storing the relationships between each. [1] https://coderwall.com/p/lixing/closure-tables-for-browsing-trees-in-sql https://coderwall.com/p/lixing/closure-tables-for-browsing-t...

chdir 12y ago
+1, Related reading (all from Bill Karwin of SQL Antipatterns fame): http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree/192462#192462 http://stackoverflow.com/questions/192220/what-is-the-most-e... http://www.slideshare.net/billkarwin/models-for-hierarchical-data http://www.slideshare.net/billkarwin/models-for-hierarchical... http://karwin.blogspot.in/2010/03/rendering-trees-with-closure-tables.html http://karwin.blogspot.in/2010/03/rendering-trees-with-closu...

jeremyevans 12y ago

Not sure about ActiveRecord, but Sequel has supported using recursive common table expressions for loading all descendants in a given branch (or branches) of a tree for over 4 years using the rcte_tree plugin: http://sequel.jeremyevans.net/rdoc-plugins/classes/Sequel/Plugins/RcteTree.html http://sequel.jeremyevans.net/rdoc-plugins/classes/Sequel/Pl...

jimbokun 12y ago

If it's a small tree, you could encode it as a single JSON object and query on it using PostgreSQL's JSON support. http://schinckel.net/2014/05/25/querying-json-in-postgres/ http://schinckel.net/2014/05/25/querying-json-in-postgres/

Walkman 12y ago

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 parent nodes, and one for the children nodes. Django will make the pairing automagically, so you don't have to do it in view code.

caust1c 12y ago
Unfortunately, this still only gets the children of the root. If you want to be able to recursively get all the children and grandchildren of a root, you're going to be doing (N - leaves) queries where N is the number of Nodes in the tree. However, there is of course a django package to help with this and gathers all the nodes you care about into one query: https://github.com/django-mptt/django-mptt https://github.com/django-mptt/django-mptt
herge 12y ago
If you ever need to deal with trees deeper than one level in django, I'd highly recommend looking at (as mentioned in another comment): https://www.djangopackages.com/packages/p/django-mptt/ https://www.djangopackages.com/packages/p/django-mptt/
stephen_mcd 12y ago
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-adjacency-list-trees/ http://blog.jupo.org/2010/01/26/linear-traversal-of-adjacenc... No need for mptt either.

chx 12y ago

Bojan Živanović and I have a writeup on this whole tree storage business https://bojanz.wordpress.com/2014/04/25/storing-hierarchical-data-materialized-path/ https://bojanz.wordpress.com/2014/04/25/storing-hierarchical... here.

batbomb 12y ago

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.

deleted 12y ago

[deleted]

glibgil 12y ago

Should be titled representing paths. Trees are easy: id, parent_id. Paths are tricky.

mappu 12y ago

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.

maaku 12y ago

> 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:

quipo 12y ago

Covered this and several other techniques here: http://www.slideshare.net/quipo/trees-in-the-database-advanced-data-structures http://www.slideshare.net/quipo/trees-in-the-database-advanc...

jaunkst 12y ago

A graph database comes to mind. It's a different design problem when dealing with deep relationships vs top level relationships. Sometimes you need more deep inherent relational mappings for alogithms to be effecient.

ashmud 12y ago

I used to use code based on Kendall Willets' code. His original site is offline. Archive here: https://web.archive.org/web/20110928135313/http://willets.org/sqlgraphs.html https://web.archive.org/web/20110928135313/http://willets.or... Line from the page: "I just picked up a copy and it looks great! You are right about the whole approach and my stuff stinks." - Joe Celko, author of SQL for Smarties.