7 ms·

Recursive Postgres Queries

67 points by tta 13y ago

btilly 13y ago
This is basically a tree like data structure. Did they look at http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html and see if it can be adapted to their problem?
- ibotty 13y ago
  nested sets are not generally faster. for anything which is not "get all direct and indirect children", they are slower than common table expressions (recursive queries). in databases supporting cte's, that is.
just_hobbyst 13y ago
I don't know Ruby, but does Benchmark.ms clear buffers and flush cache? If no, the second query has a large advantage, sometimes you can get similar performance improvements without changing query...
- tta 13y ago
  Good point! I've flipped the queries around. The difference is lesser, but still fairly significant (30x). Thanks for pointing this out.
sync 13y ago
Super cool, but it seems like this is throwing technology at a problem that could be solved in a much simpler way. Since you will rarely (if ever?) be looking up a single question in a survey, storing the whole set as a JSON array-of-arrays makes much more sense. Then you can look up the set of questions with a dead-simple SELECT.
- tta 13y ago
  I'm not familiar with JSON in Postgres, but thanks for the tip. Definitely something we can look into.
- joevandyk 13y ago
  I'm assuming you'd want to link an answer to a particular question. And have referential integrity. JSON is great if you don't need foreign keys to catch integrity problems.
- Erwin 13y ago
  I agree that recursive queries overcomplicate things greatly. Store the whole thing as a semi-typed JSON document, consider adding a thin caching layer to avoid re-parsing it on every hit (perhaps with some kind of sticky load balancing if you are running multiple processes -- I don't know how the app setup he uses work). Plus, depending on who your users, the amount of options you'll want your questions/answers to have will steadily increase, making it more suitable to a semi-typed JSON tree (I say that based on a decade's commercial experience in this field -- and at the very beginning I was doing it via Perl CGI scripts). Plus, if you really really wanted, with PG 9.3+ you an actually do queries within the JSON. One tip: make sure everything has a system-generated unique ID.
chrisfarms 13y ago
I've implemented similar designs in the past, but found ltree[1] to be much more useful/expressive when it comes to needing to fetch, order and manage lists of hierarchical data. [1] http://www.postgresql.org/docs/9.3/static/ltree.html http://www.postgresql.org/docs/9.3/static/ltree.html
- p0wl 13y ago
  also: Nested Sets http://en.wikipedia.org/wiki/Nested_set_model http://en.wikipedia.org/wiki/Nested_set_model Saved me a couple of times.
- joevandyk 13y ago
  How do you handle ordering of list elements? (say I have a "position" column that subcategories need to be sorted by)
RyanZAG 13y ago
Please, please, never do this. Programming like this in SQL is a maintainability nightmare. Can you even imagine how difficult it would be to modify this to add in new features? I've worked on projects where people have done 'clever' tricks like this, and it always ends in terrible awful terrible. The SQL itself is also non-portable which makes it even worse. Follow the advice of Justin in the comments there and rather denormalize - which basically means caching the results of deep tree queries at the top level where they can be easily and simply understood. EDIT: If you don't like the idea of denormalizing, another simple alternative is to create a separate lookup table/model which you can use to easily map back the items to the correct parent.
- bifel 13y ago
  Common Table expressions are part of the SQL:1999 standard. Most RDBMS can handle them.
- tta 13y ago
  Absolutely. We aren't using this code in production. It's sitting on a branch. I just thought recursive queries were really cool...and I had an example to illustrate it with. So hey, why not?
- lucian1900 13y ago
  There's a better way: create a view backed by the recursive query. This way if they ever wish to move away from Postgres (although why would they?), they can denormalise manually.
- aidos 13y ago
  Yep. For a portable solution there are a number of way of storing the hierarchy so that it's efficient to select a specific subtree. One way I've done it before is to have a field that contains the path (eg node1/sub_n/sub_n2 etc) and another field containing the ordering (in my case I did it across the whole tree). You can then use simple single selects to get ancestors / descendants / subtrees / siblings / all sorts of things you need (eg where path like '/path/to/subtree/%s'). Obviously not totally efficient but easy to work with and fine for small trees. The trade-off is that the operations to manipulate the tree are more fiddly - they make for a great little brain teaser though :)
batbomb 13y ago
I've dealt with recursive queries many many times. For legacy production systems I stick to Oracle's CONNECT BY statement and half joins to keep performance okay. Most of the tables I deal with typically have 80 million rows with a fanout of 1:2.5 and a average depth of ~3. A better solution is to create a temporary table to insert results in as you go if you can't afford extra DB results and perform additional inserts to that table in order to effectively take advantage of shared memory on the server side. The second better result is to effectively flatten out the rows as a closure table.
psychometry 13y ago
This is absurd. Is all this just to eliminate the n+1 queries problem? There are already solutions for this in any ORM. When loading a survey into an ActiveRecord object, why not just preload the associations? You can then iterate through the children and subchildren of survey in Ruby. Either Survey.includes(categories: { subcategories: questions }).find(1) (one query) or Survey.preload(categories: { subcategories: questions }).find(1) (four queries) would do the trick. No need for convoluted Postgres-only queries.
- nieve 13y ago
  This is a somewhat bad example of when to use recursive queries in PostgreSQL, but they're useful a lot of places Activerecord's preload can't hack it and trees. Examples: * Recursive queries can update, insert, or delete rows. This is a huge win over doing it in Activerecord with large data sets. I've done updates and inserts in under an hour that testing with Activerecord indicated would quite literally take days. It's not really black magic, but you have to actually learn SQL instead of simple selects to use this properly. * Pg's query optimizer with a recursive query & internal data handling is much higher performance than anything Activerecord can portably produce (or produce at all) even if you're lucky enough not to have to retrieve most of your results. Preloading is fine for small data sets, but by the time you hit a few hundred thousand rows you're going to start feeling it. This is one of those places where SQL as set handling and Activerecord as ORM diverge more than just conceptually. * Pulling up rows more than a few step away from the parents (especially through other tables) tends to move a lot of unnecessary data over the network with preloading and can produce ridiculous joins. * "WITH RECURSIVE" can do things Activerecord can't without multiple costly queries round-tripping their results to the client, getting processed there, and fed back into more queries. http://www.postgresql.org/docs/current/static/queries-with.html http://www.postgresql.org/docs/current/static/queries-with.h...

67 points by tta 13y ago

This is basically a tree like data structure. Did they look at http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html and see if it can be adapted to their problem?

ibotty 13y ago
nested sets are not generally faster. for anything which is not "get all direct and indirect children", they are slower than common table expressions (recursive queries). in databases supporting cte's, that is.

just_hobbyst 13y ago

I don't know Ruby, but does Benchmark.ms clear buffers and flush cache? If no, the second query has a large advantage, sometimes you can get similar performance improvements without changing query...

tta 13y ago
Good point! I've flipped the queries around. The difference is lesser, but still fairly significant (30x). Thanks for pointing this out.

sync 13y ago

Super cool, but it seems like this is throwing technology at a problem that could be solved in a much simpler way. Since you will rarely (if ever?) be looking up a single question in a survey, storing the whole set as a JSON array-of-arrays makes much more sense. Then you can look up the set of questions with a dead-simple SELECT.

tta 13y ago
I'm not familiar with JSON in Postgres, but thanks for the tip. Definitely something we can look into.
joevandyk 13y ago
I'm assuming you'd want to link an answer to a particular question. And have referential integrity. JSON is great if you don't need foreign keys to catch integrity problems.
Erwin 13y ago
I agree that recursive queries overcomplicate things greatly. Store the whole thing as a semi-typed JSON document, consider adding a thin caching layer to avoid re-parsing it on every hit (perhaps with some kind of sticky load balancing if you are running multiple processes -- I don't know how the app setup he uses work). Plus, depending on who your users, the amount of options you'll want your questions/answers to have will steadily increase, making it more suitable to a semi-typed JSON tree (I say that based on a decade's commercial experience in this field -- and at the very beginning I was doing it via Perl CGI scripts). Plus, if you really really wanted, with PG 9.3+ you an actually do queries within the JSON. One tip: make sure everything has a system-generated unique ID.

chrisfarms 13y ago

I've implemented similar designs in the past, but found ltree[1] to be much more useful/expressive when it comes to needing to fetch, order and manage lists of hierarchical data. [1] http://www.postgresql.org/docs/9.3/static/ltree.html http://www.postgresql.org/docs/9.3/static/ltree.html

p0wl 13y ago
also: Nested Sets http://en.wikipedia.org/wiki/Nested_set_model http://en.wikipedia.org/wiki/Nested_set_model Saved me a couple of times.
joevandyk 13y ago
How do you handle ordering of list elements? (say I have a "position" column that subcategories need to be sorted by)

RyanZAG 13y ago

Please, please, never do this. Programming like this in SQL is a maintainability nightmare. Can you even imagine how difficult it would be to modify this to add in new features? I've worked on projects where people have done 'clever' tricks like this, and it always ends in terrible awful terrible. The SQL itself is also non-portable which makes it even worse. Follow the advice of Justin in the comments there and rather denormalize - which basically means caching the results of deep tree queries at the top level where they can be easily and simply understood. EDIT: If you don't like the idea of denormalizing, another simple alternative is to create a separate lookup table/model which you can use to easily map back the items to the correct parent.

bifel 13y ago
Common Table expressions are part of the SQL:1999 standard. Most RDBMS can handle them.
tta 13y ago
Absolutely. We aren't using this code in production. It's sitting on a branch. I just thought recursive queries were really cool...and I had an example to illustrate it with. So hey, why not?
lucian1900 13y ago
There's a better way: create a view backed by the recursive query. This way if they ever wish to move away from Postgres (although why would they?), they can denormalise manually.
aidos 13y ago
Yep. For a portable solution there are a number of way of storing the hierarchy so that it's efficient to select a specific subtree. One way I've done it before is to have a field that contains the path (eg node1/sub_n/sub_n2 etc) and another field containing the ordering (in my case I did it across the whole tree). You can then use simple single selects to get ancestors / descendants / subtrees / siblings / all sorts of things you need (eg where path like '/path/to/subtree/%s'). Obviously not totally efficient but easy to work with and fine for small trees. The trade-off is that the operations to manipulate the tree are more fiddly - they make for a great little brain teaser though :)

batbomb 13y ago

I've dealt with recursive queries many many times. For legacy production systems I stick to Oracle's CONNECT BY statement and half joins to keep performance okay. Most of the tables I deal with typically have 80 million rows with a fanout of 1:2.5 and a average depth of ~3. A better solution is to create a temporary table to insert results in as you go if you can't afford extra DB results and perform additional inserts to that table in order to effectively take advantage of shared memory on the server side. The second better result is to effectively flatten out the rows as a closure table.

psychometry 13y ago

This is absurd. Is all this just to eliminate the n+1 queries problem? There are already solutions for this in any ORM. When loading a survey into an ActiveRecord object, why not just preload the associations? You can then iterate through the children and subchildren of survey in Ruby. Either Survey.includes(categories: { subcategories: questions }).find(1) (one query) or Survey.preload(categories: { subcategories: questions }).find(1) (four queries) would do the trick. No need for convoluted Postgres-only queries.

nieve 13y ago
This is a somewhat bad example of when to use recursive queries in PostgreSQL, but they're useful a lot of places Activerecord's preload can't hack it and trees. Examples: * Recursive queries can update, insert, or delete rows. This is a huge win over doing it in Activerecord with large data sets. I've done updates and inserts in under an hour that testing with Activerecord indicated would quite literally take days. It's not really black magic, but you have to actually learn SQL instead of simple selects to use this properly. * Pg's query optimizer with a recursive query & internal data handling is much higher performance than anything Activerecord can portably produce (or produce at all) even if you're lucky enough not to have to retrieve most of your results. Preloading is fine for small data sets, but by the time you hit a few hundred thousand rows you're going to start feeling it. This is one of those places where SQL as set handling and Activerecord as ORM diverge more than just conceptually. * Pulling up rows more than a few step away from the parents (especially through other tables) tends to move a lot of unnecessary data over the network with preloading and can produce ridiculous joins. * "WITH RECURSIVE" can do things Activerecord can't without multiple costly queries round-tripping their results to the client, getting processed there, and fed back into more queries. http://www.postgresql.org/docs/current/static/queries-with.html http://www.postgresql.org/docs/current/static/queries-with.h...