Understanding Recursive Queries in PostgreSQL | Hacker News Reader

Understanding Recursive Queries in PostgreSQL

cybertec-postgresql.com

168 pointsfdr43 comments

This post is only scratching the surface of what can be achieved with a.. fully armed, and operational battle station.. powered by recursive SQL in postgres. Simply adding a parent_id column to a table (and a few constraints) can facilitate all sorts of useful network topologies. I doubt that the recursive query against a DAG is going to give better performance than a query against a DAG within a graph database, but the relational query may be sufficient for your work and not require the cost of graph db investment.

I think that people need to move beyond simple recursive sql example blog posts and share the more challenging examples. Recursive queries can become challenging quickly.

In Postgres, there is a data type ltree[0] which can materialize the full path in a DAG and help do relatively complex searches. Tree coordinates are typically stable, so it's easier and faster to recalculate the path on writes vs reads. We use parent_id + ltree to do search hundreds of thousands of relationships in milliseconds.

ltree is no match in power to CTEs, but it is perfect for a simple domain like the one used in the article.

[0] https://www.postgresql.org/docs/current/ltree.html

I 2nd this recommendation. If nothing else, it helps to have fewer recursive queries which are still treated as optimization barriers when you need to do complex queries joining to your DAG. So using a nice indexable ltree is much better for performance when your queries get complicated.

Similarly SQL Server has hierarchyid (https://docs.microsoft.com/en-us/sql/t-sql/data-types/hierar...) if anyone is interested.

Do you know of any other resources for learning more?

Check out this slide deck, it's full of interesting stuff, including recursive CTE, arrays, LATERAL, and practically useful complex examples: https://www.slideshare.net/pgdayasia/how-to-teach-an-elephan...

How far do you really want to go? It's possible to do a metacircular lisp-in-lisp-in-sql. If Turing says there's no attractive Schelling endpoint to the challenging examples, might as well stop after factorial[1].

[1] see also Checking a large routine, 1949

I use recursive queries in SQL to search persistent suffix arrays (mainly when there is a LOT OF DATA). You can do string search hundreds of gigabytes of data within ~0.004s with SQLite on cheap SSD and pretty much no RAM - my goal is to be able to be able to search and align on all genetic information we have so far (about ~9 trillion base pairs in total)

If anyone knows how to increase INSERT speeds on Postgres, I would appreciate. I can get about 100K per second with COPY or putting the inserts in a transaction. Have tried some more mirrored NVME drives and more RAM with ZFS, as well as dropping some unimportant indexes, but I'm still a little limited. Any thoughts?

Why ZFS? I thought copy-on-write filesystems were discouraged for database workloads. I know it is possible but are you getting other benefits from ZFS?

For OLTP, COW is horrible. For OLAP it's usually fine. I've had good results with Postgres and ZFS with LZ4 compression.

I have a single physical server for running all my virtual machines. ZFS is nice for everything else, and it just so happens that my database virtual machine takes up most of the SSD space on that computer. I guess I should have a dedicated machine if I really need to improve insert speeds though.

Ah ok, pragmatic. Makes sense.

Have you done things like disable constraints and indexing during loading?

I've disabled all constraints, but I haven't removed indexing during loading. I'll look into doing that, with adding the indexing later

I don’t often work with Postgres itself but I do work with a derivative (Redshift) at $dayjob.

Indexes don’t exist. Constraints are present in the syntax and the planner relies on them but they are never enforced. Our ETL layer deals with checking constraints at load time. Load performance is good. I’ve never run a rows/minute metric because it’s never been a problem.

Coming back to this just to provide a datapoint. I just loaded 10m rows into a table in less than one minute using Redshift. The data is encoded (compressed) at insert time but is not sorted until a vacuum runs.

With inserts you’ll see great results from goosing the transaction array multiplexer. Just make sure you’re aware of piping the commit hash to the properly isolate the down range effects on the memcpy and you’ll avoid corruption issues. This has worked for me anyways.

This comment is entirely random gibberish, not sure why you're posting that. I initially suspected a GPT-3 bot or something like that, but the comment history didn't support that.

GPT doesn’t make the kind of blatant grammatical mistakes the commenter did.

To be fair, I typed this quickly on a phone.

Came across this upcoming webinar on the topic: https://www.timescale.com/webinar/5-ways-to-improve-yourpost...

Assuming you're doing bulk inserts, and can restart the insert on any failure, one tactic is to disable all consistency and durability storage features during the insert. This heavily reduces the IO operations needed and the need to wait for them to complete. That's assuming that iops are the resource that you are constrained on.

Steps:

- use ext2 or even tmpfs as the filesystem, this disables journaling and COW features of ZFS; mount options async,nobarrier

- set tables to be UNLOGGED to disable Postgres WAL

This got things fast enough for my last use-case. But next ideas, as at some point you then become CPU/memory bound

- you could try sharding by partitioning the table

- another trick is to use SQLite as a backing store for inserts (it is quite fast if you turn off all logging) and then query with Postgres via a FDW https://github.com/pgspider/sqlite_fdw

How fast did it go for your last use-case? Disabling all the consistency and durability storage features is dreadful, to say the least, but I'd definitely be open to trying it if it means I can get it done quicker.

The algorithm I'm working with uses single-cores but is linear-time and in my experience is at least 10x-100x faster than the IO. Memory is actually the biggest problem with the method, which is why I need to use a database to back it to disk.

It's relatively safe to do so for a one-time bulk load, especially if you have a way to verify consistency what you've loaded for integrity reasons (foreign keys, for example, might be a single query and a join). If it's not a one-time load, then you are right, it's dreadful.

If, for example, you get a 3-5x speedup without checks (not unheard of), you can do it twice, verify the copies are the same, and get a 2x speedup.

Is there a reason you don't wish to batch inserts into transaction(s)? Otherwise, you're asking the database to commit (fsync to disk) between each insert statement.

Other ideas:

- Have multiple processes inserting in parallel (this interacts with the commit_delay and commit_siblings settings in postgresql.conf)

- Use unlogged tables (but table is truncated on db startup)

- Put fsync=off and synchronous_commit=off in postgresql.conf (but db may be corrupted in a crash)

- switching to BRIN indexes might be an option, but depends on data

I do batch the inserts into a large transaction, and usually optimize for the transaction to commit in approximately ~10s. Not sure if it is optimal, but I like to monitor it like that.

BRIN indexes actually work for some of the data types I'm working with! Thank you for pointing those out!

COPY is the fastest method to insert data in Postgres. As another poster mentioned, setting table to UNLOGGED will help also.

Finally, you can drop ALL indexes and recreate them after import (been hit and miss in my testing but on occasion has helped).

How has dropping and recreating indexes been hit or miss? I've been thinking about doing exactly that

In some cases it did not appear to give me an improvement in data load time - I didn't do a rigorous test though which is why I said it might be 'hit and miss'.

I'm new to postgres and having trouble visualizing the recursive query you're describing. Would you be willing to share an example query (or something that illustrates the point on fake data)?

The query that I have working is an abomination (it works though, https://github.com/Koeng101/poly/blob/polyStore_v0.1/store/c...)

The basic idea is that I am using SQL to back a suffix array (https://en.wikipedia.org/wiki/Suffix_array). The suffix array has all suffixes of a string (for "bats", it would have ["bat", "at", "t"] sorted in alphabetical order ["at", "bat", "t"] except storing the index of the suffix [1, 0, 2].

To search for a string, you go halfway in the suffix array and check if the suffix is lexicographically equal to, larger than, or smaller than your input. If it is not equal to, halve in the right direction. If the string is there, eventually you'll hit it.

Without benchmarking it, my first instinct would still be to design the schema in a way to avoid recursive queries, if possible. I'm thinking of stuff like a simple tree, e.g. categories with subcategories arbitrarily nested. In that case I'd probably just store all the parents as well, not just the immediate category. That is more work in the insert/update case, but makes queries that include all children trivial.

> Without benchmarking it, my first instinct would still be to design the schema in a way to avoid recursive queries, if possible.

In my experience that's a good idea. The query planner has a really hard time with recursive queries.

Recursive queries are better mentally modelled as iterated queries building up a result set. If you think of recursion as tracing a tree, or in trivial cases, a linked list, recursive queries are a breadth-first traversal.

You better not traverse too deep (iterate too much), or you lose the data locality benefits that relational databases are tuned for, and all you end up saving is the cost of round trips to the database.

Many tree structures are better modelled as prefix pattern matching on string paths. Extracting a whole subtree with "path LIKE 'foo/bar/baz/%'" on an indexed path column is much faster than following a series of parent links with a recursive query, more and more so the deeper your subtree gets. This denormalizes the tree structure into the path column - you can no longer make structural edits with small updates - but it's much faster for queries.

I have some tree data represented in jsonb fields -- is it possible to build a materialized view on top of recursive traversal of a jsonb data structure -- to extract a view like this ...?

owner_id, element_path, element_id

where element_path would be something like an LTree -- to allow easily querying over the set of traversals defined in the jsonb?

Is it a reasonable way to represent the tree in convenient way for queryomg purposes while also allowing data updates to stay simple?

With ->> jsonb operator, writing a recursive query on such table to do a walk-through should be pretty straightforward, I think.

I did approximately that, but with actual columns, not jsonb, and with a normal view, not a materialized view. Performance sucked on the view because of all the lookups.

So you could create the materialized view which builds the path, and then use an index on the path for subtree selection. However you might find refreshing the materialized view slower than you'd like.

The only real answer here is to build it and load it out with a representative sample of data, or a set scaled down for a smaller test machine, and finding out what the latency and throughput are like for your case. Find out what the ground truth is for you, today, on today's hardware. My tests were from 4+ years ago.

> This denormalizes the tree structure into the path column - you can no longer make structural edits with small updates - but it's much faster for queries.

I think it would be perhaps more beneficial to point out that the bigger problem with this approach that typically leads people to try other avenues including recursive queries is when storage comes at a premium or the “path” makes up the bulk of the record and there is significant duplication of leading prefixes.

Sure. Though hybrids are possible, e.g. encoding a fixed number of levels of recursion, with common prefixes held in or near the root.

The main point I'm making is that you can grab a whole subtree on a prefix match right out of a single index, whereas recursive queries need new lookups at every step. Recursive queries look cool for someone with an object-oriented mental model - hey, look, you can make the database chase pointers - but chasing pointers is still slow, whether it happens in the database or in memory.

(This was past me. I thought recursive queries looked neat for fetching tree-shaped data. So I built the data model and loaded it up, and then discovered that performance was absolute rubbish.)

A well-written, simple introduction to something I've been curious about but never took the time to dig into. Thank you!

A few years ago the company I was working for ran an advanced SQL course for a few people who were interested. I was skeptical going in, but the chap who ran the course was the real deal.

One particularly memorable example he showed was a real world implementation of Dijkstra's shortest path algorithm using recursive CTEs. While it was very impressive I did spend most of the demo thinking "I'm so glad I don't have to maintain that"!

How does a Recursive CTE run, line by line?

https://stackoverflow.com/questions/3187850/how-does-a-recur...

Recursive SQL is fun: https://excessivelyadequate.com/posts/sierpinksy.html

Datalog is a recursive query language. One of the very few alternatives to SQL.

Reply on news.ycombinator.com