Recursive Common Table Expressions in Postgres

https://www.citusdata.com/blog/2018/05/15/fun-with-sql-recursive-ctes/

by jesperht • 8 years ago

202 97 8 years ago

skissane2• 8 years ago

It annoys me they have made backward incompatible changes to this in Postgres 10, such that recursive CTEs that worked perfectly fine in 9.6 suddenly get rejected in 10. See in particular the function in this StackOverflow answer – https://stackoverflow.com/a/46761197/2147204 – it works fine on 9.6, 10 rejects it with an error.

trinitry3• 8 years ago

Nothing to do with CTEs. The queries were badly written to begin with and should have used LATERAL.

skissane2• 8 years ago

Yes, I forgot the actual issue was not CTEs directly.

I agree the query could have written better (I am still getting my head around how to use LATERAL), but it worked fine in 9.6 and stopped working in 10. From a backward compatibility viewpoint, code working in one version should still work in the next (even if it isn't the best code.) Or at least, start issuing deprecation warnings one version before making it not work.

Anyway, posting this to HN has triggered someone to go rewrite my code for me (thanks Ants Aasma, whoever you are), so now my Postgres 10 upgrade blocker is solved :)

whitten• 8 years ago

Common Table Expressions (CTEs) are sometimes referred to as WITH clauses. This article focuses on WITH RECURSIVE. They are useful ways to deal with tree oriented data.

shrikant2• 8 years ago

Fun fact: Recursive CTEs are one of those things where, if you come in relatively new to them, would make you go "who would ever want to use this, and why?!"

Funner fact: Once you come across a problem to which the solution is to use a recursive CTE (handling train movement graphs in an RDBMS? yes please!), you'll find yourself having to explain your reasoning for it in a manner that will let you truly grok recursive CTEs.

Funnest fact: Both the above will almost certainly happen more than once in your data-wrangling lifetime.

(Or maybe that was just me...)

ccozan2• 8 years ago

We are using this kind of CTEs for handling BoM trees.

Everyone thinks we habe some complicated software that generates this tree. Well, we just maintain the correct parent-child relation. Rest is trivial, with recursive CTE.

esaym• 8 years ago

BoM trees

Bill of material trees? Could you maybe elaborate more?

dliff• 8 years ago

Very cool, this was actually my first real-world use case for Postgres CTE's. (BOM part of homemade ERP software I built for my last company). Worked great!

spacemanmatt2• 8 years ago

I thought I was crazy for implementing a dependency resolver in CTE but eventually the performance and database-encapsulation were serious winners.

Amezarak5• 8 years ago

One common use case I've found for recursive CTEs is generating tables of dates.

Very frequently, I have a question along the lines of "how many x have occurred per day/week/month?", where x has a timestamp column, where the data could be sparse.

One neat way to do this is to create a recursive CTE that begins by selecting the first relevant date, then unions that with the period (day/week/month) plus one up to the last date you're interested in.

Once done, you can left join your date CTE against a COUNT aggregation grouped by the period you care about on your data table.

blattimwind2• 8 years ago

Why not just GROUP BY to_char(timestamp, some_format) / extract(something from timestamp)?

barrkel2• 8 years ago

One common use case I've found for recursive CTEs is generating tables of dates.

If you don't have table-valued functions, just create a table with all the dates for the next hundred years or so. The number of distinct dates is pretty manageable. This is the approach I use when calculating stats data via MySQL.

meritt2• 8 years ago

assuming you're on postgres, generate_series() is a far easier option to do exactly what you've described.

rosser6• 8 years ago

If you're using postgres, take a look at the generate_series() set-returning function for this purpose. It might be a lot cheaper.

EDIT: Looks like someone already suggested this, down-thread.

barrkel2• 8 years ago

My order of discovery was more like this:

1) Recursive CTEs: that's nifty; I'll remember that for when I need it.

2) Here's a problem that involves chasing a linked list of rows, I know, I'll use a recursive CTE.

3) Oh dear, that doesn't perform well at all, I'm much better off denormalizing my lists into a separate column and using LIKE expressions, or something similar instead.

nerdponx• 8 years ago

Do some database systems have support for optimizing recursive queries?

dspillett4• 8 years ago

Be careful of performance when using CTEs in Postgres: unlike in other DBMSs they are optimisation fences with regard to predicate pushdown so for some queries will result in extra scans for every level of call needed.

Doesn't affect all queries of course, and where is does the difference may not be significant compared to what else is going on (i.e. querying a small tree/graph structure to pull out some large/complex data), but it is something to watch out for when working with data of any appreciable size.

Dowwie• 8 years ago

What pattern ought one look for in the explained plan to identify this issue?

Is this something that can likely be improved, technically speaking?

ximeng• 8 years ago

Yes - most other DBMS don't do this. If you have a filter on a derived table that uses a CTE, Postgres will not be able to push it down to the CTE. If the CTE is expensive to calculate (a lot of rows, or joins, or complicated functions), but you don't need many rows from it in the final results, performance is likely to be very poor compared to rewriting as normal subqueries. You should be able to see this on the plan if you see an expensive CTE subquery with limited row results being used.

This is unfortunate as it can reduce readability significantly. There's resistance to fixing this as it is considered a breaking change apparently, which it may be for CTEs used for data manipulation (INSERT / UPDATE / DELETE can operate using CTEs), but it shouldn't be for plain SELECTs. however no obvious plans for this to change.

https://blog.2ndquadrant.com/postgresql-ctes-are-optimizatio... has more.

lr4444lr2• 8 years ago

Is this something that would be evident upon running EXPLAIN over a query?

dspillett4• 8 years ago

Excess index (or full table) scans on the recursively referenced tables, or "wrong" index choices otherwise on those objects, where your filtering/joining clauses would otherwise allow for more efficient options with the indexes that are available.

I'm not an expert on postgres (I spend most of my life in MS SQL Server's domain) so I'll not try be more detailed than that for fear of accidentally spreading/creating misinformation. Search for "postgress CTE optimisation fence explain" and you'll hopefully find some good examples as it is a commonly discussed topic once you know the right keywords to search for.

brlewis2• 8 years ago

It's possible that this note at the bottom of the article was not there when you made your comment:

As a note CTEs at this time are an optimization fence in PostgreSQL, though there are hopes of that changing in the future. Common Table Expressions are an incredibly useful tool for reporting. At times the readability of CTEs outweighs the performance impact, but consider the trade-offs when using them

dspillett4• 8 years ago

It is also possible that I skimmed over that part!

karmakaze2• 8 years ago

For the amount of data it processes it can be slow. I used it to render a category taxonomy of just maybe 100 nodes and it was a perceptible duration. The representation was so direct and clear that I kept it and just cached it server-side I validating went any category was changed. Also had to ensure there were no cycles in the data when saving changes.

agentultra2• 8 years ago

For some kinds of data, such as taxonomies, there is a datatype called an ltree available in Postgres that can be indexed. Not as general as a CTE but useful for avoiding the optimization barrier in specific cases.

rosser6• 8 years ago

You can also mitigate this by judiciously ordering your CTEs, when you have more than one, having earlier ones do more of the winnowing work, and being used as inputs to later ones.

An often unrecognized consequence of CTEs being optimization fences is that they're much easier to farm out to background workers when parallel query execution is a thing.

lr4444lr2• 8 years ago

I never cease to be amazed at how well Postgres maintains decades-old ACID SQL standards while churning out these innovative advances to the spec.

Amezarak5• 8 years ago

Postgres is great, but I don't think there is a serious rdms that doesn't have recursive ctes.

twic• 8 years ago

Does Oracle have them now? There was a time when it had some janky CONNECT BY syntax of its own.

marzell• 8 years ago

I'm kinda trying to figure out why this is on HN today. Usually articles, even reposts, contain some sort of novel content or ideas. Recursive CTEs in SQL databases are well known and have been for years.

emilsedgh2• 8 years ago

The only problem I have with them is that it takes my brain 30 minutes to digest the peace of SQL in front of me that uses WITH RECURSIVE clause.

I do whatever I'm supposed to do. 3 months later, a bugfix required, I find myself at this piece of SQL that I know works but I cannot digest it for another 30 minutes.

And my case is really simple.

But yeah they are amazing.

pc86• 8 years ago

I do think the biggest pro for CTEs is the increased readability, and using recursion inhibits the readability a bit (still better than the alternative). But I'm curious how complicated the SQL you're using is that it takes half an hour to understand what it's doing.

craigkerstiens2• 8 years ago

OP here, completely agreed. I have a separate post from some years back about CTEs specifically around readability. While they can make things a bit long and can be an optimization fence in Postgres the building blocks and readability in my eyes tends to win out over those things pretty often - http://www.craigkerstiens.com/2013/11/18/best-postgres-featu...

olavk2• 8 years ago

But can you solve the same task in a more straightforward way without CTE?

maxdemarzi• 8 years ago

Yeah, use a graph database. Most trees end up becoming graphs as changes happen over time and the CTEs won't help much anymore.

Klathmon2• 8 years ago

People need to comment SQL more!

We have a few ~200 line long queries in one of our applications. With comments one of them is 460 lines.

When things get hairy, don't be afraid to explain why you needed this CTE, what it's doing from a high level, point out that little gotcha that you ran into a few times while developing the query, why you needed to do X instead of the simpler Y, etc...

While there are downsides to excessive commenting (the big one is that the comments can get "out of sync" with the code and just cause confusion), when it comes to big/complicated SQL, I've found that more is better for the most part.

craigkerstiens2• 8 years ago

OP here, couldn't agree more regarding commenting[1]. Far too often people don't treat their SQL queries or database the same way they do code. Giving SQL the same attention as you do code with good formatting and comments can make life much easier the next time someone else or even yourself has to come back to some query years later.

[1]. http://www.craigkerstiens.com/2013/07/29/documenting-your-po...

segmondy• 8 years ago

You can say that again! I started a DB review team at my company. Not only queries, but Postgres allows for tables to be commented on, you can place a comment on table, columns, constraints, domain, triggers, view, pretty much anything.

Initially a few folks rolled their eyes at that, but now everyone loves it. When you have thousands of tables, comments help, likewise when you have massive amount of queries. I'm also in the camp of let the DB do the work if it can do it faster, and likewise have 100-400 line queries that will turn into 5x LOC programs which take 20x time to execute. Writing tons of comments is important. Usually the query is right and when it works, no one remembers it for a year or two till business rules change.

My approach to commenting such queries after modification is to delete every single comment and start afresh. From memory, when I'm done. If I can't then I have no idea what the query was doing which is very bad. Sometimes folks modify query and get a happy result. If I can document it without reference to old one, great! After that, I look at the old one to make sure that I'm not missing anything.

riku_iki• 8 years ago

We have a few ~200 line long queries in one of our applications. With comments one of them is 460 lines.

You can decompose large queries into smaller views/temp tables, and such queries will be much more readable..

ht85• 8 years ago

I feel like for queries that are hard to understand at a glance, a picture is worth a thousand words. For the majority of people, myself included, writing helpful, high quality comments is really hard.

Instead, for a CTE, I would rather add a sample of initial data, and how they are transformed by the first two or so iterations of the loop.

dspillett4• 8 years ago

comments can get "out of sync" with the code and just cause confusion

I generally find it a safe assumption that were the comments don't agree with the code both are wrong, or will be next time someone makes a related change (as sod's law says they'll chose to trust the one that is least correct). Even when all the actors involved are me at different times.

mistercow4• 8 years ago

This is my problem with SQL in general. The facilities for which SQL is an API are incredible, but that API has so many weird design choices behind it that it often feels like I'm being forced to play some kind of perverse minigame in order to get the database to do what I want efficiently. And then, once I've managed to bend the query planner to my will, I often have to load it down with an absurd number comments to explain to future folk what exactly is happening – ostensibly the sort of thing that a declarative language is supposed to prevent.

amelius3• 8 years ago

Perhaps someone should design a purely functional language that translates to SQL (?)

ris3• 8 years ago

My advice is to always use an ORM with SQL if you possibly can, or if not an ORM per se, at least an abstraction library like the sqlalchemy "core". It sounds ironic to say but "SQL" is the worst part of SQL. That shouldn't stop you loving SQL though.

jnordwick• 8 years ago

Dont worry. It takes the database 30 minutes to execute it too.

recursive• 8 years ago

There's no particular reason that a recursive CTE should be that slow. Some are, but it's not too hard to write any kind of query to go as slow as you want to make it go.

xpil2• 8 years ago

Why use the word RECURSIVE at all? The engine should recognize the "recursiveness" of the CTE automatically, at the compile stage. Some other DB engines have had this for years.

brlewis2• 8 years ago

I think it's for humans. Often humans looking through SQL code are doing so for performance reasons, and a recursive query is fundamentally different from a non-recursive query. It's something you might want to know while skimming, before diving deep.

xpil2• 8 years ago

I see where you are coming from but the idea does not resonate with me. A CTE is a CTE, recursive or not. Sometimes you do not care as long as it generates correct data.

I can see an analogue though: some languages differ Sub from Function although they are basically the same idea.

On the other hand, Postgres seems to be the only RDBMS that makes the RECURSIVE keyword mandatory for recursive CTEs.

amelius3• 8 years ago

How do you pass parameters to the recursive function?

kqr• 8 years ago

I wouldn't call it a function as much as a temporary table defined in terms of itself. It is parametrised the way all CTEs are, by giving arguments in parentheses postfix.

shiado• 8 years ago

I once built a Reddit clone and used recursive ctes for the comment trees. Imagine each comment has a parent comment foreign key which might be null if at top level. If you use a recursive cte you can simply start with top level comments with null parents and recursively get all of the subtrees and end up with a nice flat list of all your comments in the order you want. The other way to do this is to just fetch all the comments and assemble the tree in memory and then flatten it, which is what I believe many sites do.

btilly2• 8 years ago

A third way to do this is described in https://en.wikipedia.org/wiki/Nested_set_model. Its performance for the common case of heavy reads and few writes is better than either of the two that you describe.

Recursive Common Table Expressions in Postgres

Related Stories