Recursive Postgres Queries

http://blog.timothyandrew.net/blog/2013/06/24/recursive-postgres-queries/

by tta • 13 years ago

67 44 13 years ago

blog.timothyandrew.net

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

tta3• 13 years ago

Good point! I've flipped the queries around.

The difference is lesser, but still fairly significant (30x).

Thanks for pointing this out.

sync• 13 years 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.

tta3• 13 years ago

I'm not familiar with JSON in Postgres, but thanks for the tip. Definitely something we can look into.

joevandyk5• 13 years 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• 13 years 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• 13 years 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

p0wl• 13 years ago

also: Nested Sets http://en.wikipedia.org/wiki/Nested_set_model

Saved me a couple of times.

joevandyk5• 13 years ago

How do you handle ordering of list elements? (say I have a "position" column that subcategories need to be sorted by)

RyanZAG• 13 years 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.

tta3• 13 years 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• 13 years 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• 13 years 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 :)

dragonwriter2• 13 years ago

Recursive CTEs are a portable solution; they are part of the SQL:1999 standard and are supported by current versions of Postgres, DB2, Oracle, SQL Server, Firebird, etc.

The only two widely used SQL-using relational databases I can think of off the top of my head that don't support them are SQLite and MySQL.

(PostgreSQL arrays aren't portable, though in other DBs I've seen strings used for similar purposes, though that is truly an abomination.)

nadaviv• 13 years ago

I make heavy use of SQL in my daily work. A lot of our business logic lives in the database as views, triggers and various functions.

I actually find that taking this logic away from the app code and into the database is one of the best architectural decisions we took.

I think the primary issue some people have with doing that is that they don't know working with databases well enough, and consider them a dumb place to store data, and nothing more. This is what makes it difficult to maintain.

One thing that I do agree with is that the SQL code isn't portable - but its the same as your Ruby/PHP/NodeJs/whatever code not being portable. I don't see that as an issue.

umsm• 13 years ago

In my experience: most people that don't know proper DB design and SQL will do two things:

- Over-utilize stored procedures, views, etc.

- Implement many obscure "hacks"

There is nothing wrong with using built-in database functionality, but it can be over done.

btilly10• 13 years ago

From a software engineering perspective, this is entirely backwards.

Databases offer a great way of looking at your data.

However they have very poor stories around version control, rollout, rollback, separating metadata from data, and creating multiple parallel environments for production, qa, and every dev engineer. Yes, I know that database vendors claim otherwise, but compared to what is standard for most programming environments these days, it is a major limitation.

But it doesn't stop there. If you are lucky enough to get a busy site, you will find that the database is the inevitable bottleneck that can't simply be scaled by putting machines in parallel. The more work you push down to that, the sooner you'll hit that bottleneck, and the harder it is to fix once you do. When you've experienced, as I have, the joys of periodic outages because the database choked at a million dynamic pages/day, you'll value moving logic out of the database, the ability to put caching in front of it, etc.

Now to all of this the database vendors have a trump card, what happens if multiple applications access the database? If your business logic is there, then you're fine, otherwise you're reimplementing that logic multiple times! The thing is that in the 15 years that I've seen people making that argument, I've not encountered a lot of organizations opening up a business critical transactional database for random applications. And in practice it is easier and saner to put an RPC layer on top of of your existing app, in which case you get the business logic that way.

I guess I should somewhere note that I spent several years of my life with my primary job being to write fancy SQL. I was also the go to person on the software development side for "get us to scale the database better". I do not criticize databases out of a lack of knowledge of how to use them. I criticize them based on a large amount of experience with how to make the most effective use of their capabilities.

bifel• 13 years ago

Common Table expressions are part of the SQL:1999 standard. Most RDBMS can handle them.

jeffdavis3• 13 years ago

"Programming like this in SQL is a maintainability nightmare."

How does it compare to the application code required to do the same thing?

nbouscal2• 13 years ago

I agree with you that in this particular instance, this is probably not the optimal solution to the problem at hand. I would argue, however, that you are significantly overreaching by implying that one should never take advantage of advanced features of your RDBMS. While the OP's problem was rather easy to solve in the application layer, there are many problems where that approach is absolutely unreasonable.

As an example, I'm currently working on a project that involves modeling a directed cyclic graph in the database. Trying to pull the logic out into the application layer is simply unfeasible. There is no performant way to do it, period. However, it's easy enough to work with it in the database, either by using a function that performs a recursive query, making a materialized view out of that same query, or using triggers to maintain the transitive closure in a table proper.

You also seem to have a pretty narrow perspective of the situations in which RDBMSs are used. As it happens, there are a lot more use cases than 'persistence layer for web apps', and in many of those use cases the idea of not using advanced features of your RDBMS would be absolutely ludicrous.

I do agree with one complaint made in another reply to your post, which is that version control, testing, etc. are much more difficult when your logic is residing in the database. There are a lot of solutions out there for that, though (migrations alone solve many of the headaches), so it's really not a knockdown argument. As for portability, the SQL itself is as portable as any SQL is. WITH RECURSIVE was added to the standard in '99.

masklinn• 13 years ago

The SQL itself is also non-portable

CTE is part of SQL:1999 and most RDBMS support it: http://en.wikipedia.org/wiki/Hierarchical_and_recursive_quer...

Or are you using some odd custom definition of the word "portable"?

dragonwriter2• 13 years ago

CTEs are portable, but the sorting piece of the solution relies on PostgreSQL's arrays, which are not portable. Even with CTEs, I think doing sort-by-path in a portable way is going to be ugly (arrays make it very nice.)

batbomb• 13 years 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.

btilly10• 13 years ago

This is basically a tree like data structure.

Did they look at http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html and see if it can be adapted to their problem?

ibotty• 13 years 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.

psychometry• 13 years 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• 13 years 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.h...

Recursive Postgres Queries

Related Stories