12 ms·
Understanding Recursive Queries in PostgreSQL
- koeng 6y agoI 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?
- mulmen 6y agoWhy 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?
- noctune 6y agoFor OLTP, COW is horrible. For OLAP it's usually fine. I've had good results with Postgres and ZFS with LZ4 compression.
- koeng 6y agoI 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.
- mulmen 6y agoAh ok, pragmatic. Makes sense. Have you done things like disable constraints and indexing during loading?
- koeng 6y agoI've disabled all constraints, but I haven't removed indexing during loading. I'll look into doing that, with adding the indexing later
- mulmen 6y agoI 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.
- mulmen 6y agoComing 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.
- site-packages1 6y agoWith 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.
- fabian2k 6y agoThis 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.
- ComputerGuru 6y agoGPT doesn’t make the kind of blatant grammatical mistakes the commenter did.
- site-packages1 6y agoTo be fair, I typed this quickly on a phone.
- liminal 6y agoCame across this upcoming webinar on the topic: https://www.timescale.com/webinar/5-ways-to-improve-yourpostgresql-insert-performance https://www.timescale.com/webinar/5-ways-to-improve-yourpost...
- vii 6y agoAssuming 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 https://github.com/pgspider/sqlite_fdw
- koeng 6y agoHow 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.
- prpl 6y agoIt'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.
- rarrrrrr 6y agoIs 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
- koeng 6y agoI 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!
- jarym 6y agoCOPY 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).
- chrisshroba 6y agoI'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)?
- koeng 6y agoThe query that I have working is an abomination (it works though, https://github.com/Koeng101/poly/blob/polyStore_v0.1/store/construct.go#L244-L332 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 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.
- Dowwie 6y agoThis 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.
- e1g 6y agoIn 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 https://www.postgresql.org/docs/current/ltree.html
- Tostino 6y agoI 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.
- Guillaume86 6y agoSimilarly SQL Server has hierarchyid (https://docs.microsoft.com/en-us/sql/t-sql/data-types/hierarchyid-data-type-method-reference?view=sql-server-ver15 https://docs.microsoft.com/en-us/sql/t-sql/data-types/hierar...) if anyone is interested.
- timClicks 6y agoDo you know of any other resources for learning more?
- barrkel 6y agoRecursive 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.
- breatheoften 6y agoI 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?
- golergka 6y agoWith ->> jsonb operator, writing a recursive query on such table to do a walk-through should be pretty straightforward, I think.
- barrkel 6y agoI 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.
- fabian2k 6y agoWithout 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.
- hansvm 6y ago> 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.
- doersino 6y agoRecursive SQL is fun: https://excessivelyadequate.com/posts/sierpinksy.html https://excessivelyadequate.com/posts/sierpinksy.html
- elchief 6y agoHow does a Recursive CTE run, line by line? https://stackoverflow.com/questions/3187850/how-does-a-recursive-cte-run-line-by-line https://stackoverflow.com/questions/3187850/how-does-a-recur...
- yeswecatan 6y agoA well-written, simple introduction to something I've been curious about but never took the time to dig into. Thank you!
- remus 6y agoA 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"!
- snicker7 6y agoDatalog is a recursive query language. One of the very few alternatives to SQL.