3 ms·

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

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.

breatheoften 6y ago
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?
- golergka 6y ago
  With ->> jsonb operator, writing a recursive query on such table to do a walk-through should be pretty straightforward, I think.
- barrkel 6y ago
  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.
ComputerGuru 6y 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.
- barrkel 6y ago
  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.)

breatheoften 6y ago

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?

golergka 6y ago
With ->> jsonb operator, writing a recursive query on such table to do a walk-through should be pretty straightforward, I think.
barrkel 6y ago
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.

ComputerGuru 6y 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.

barrkel 6y ago
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.)