Having learned SQL on a need-to-know basis, recursion took me a while to grok. Would have been nice to have this article back then.
Quite powerful stuff, both in the results it can produce and in the resources it can drain from the server.
Besides the typical "linked-list" queries, I used this to split a comma-separated column value into separate rows, as our DB server did not have that as a built-in function. Not pretty, but it did the job.
In case anyone is curious, here's how I solved the CSV split thing. Again, my SQL skills are limited, but it did the job for me.
with recursive lst (subidx, elm, input_str) as (
( -- initial row
select nullif(charindex(',', input_str), 0) as subidx, coalesce(substr(input_str, 1, subidx-1), input_str) as elm, input_col as input_str
from (select 'abc, d, ef, ghj' as input_col) x -- replace subquery with something useful
)
union all
( -- recursive
select nullif(charindex(',', substr(input_str, subidx+1)), 0)+subidx as next_subidx, substr(input_str, subidx+1, coalesce(next_subidx-1-subidx, length(input_str))) as next_elm, input_str as next_input_str
from lst
where subidx < length(input_str)
)
)
select trim(elm) from lst
Always find it frustrating how tedious trees are in SQL. Like, relational db is in the name, so why is such a common pattern of relations so annoying to work with?
How about we don't, and think about queries as the algebraic relations that they are?
I always found this explanation of SQL (and SQL-like) recursion much more reasonable than efforts to shoehorn SQL into an iterative, functional box: https://core.ac.uk/download/pdf/11454271.pdf
For modelling trees, I much prefer using a list of ancestors compared to the parent-child adjacency list because it doesn't require recursion to answer basic questions. I had thought about how I would model threaded comments in SQL some time ago and wrote down an example of what I mean:
"This module implements a data type ltree for representing labels of data stored in a hierarchical tree-like structure. Extensive facilities for searching through label trees are provided."
One way of modelling trees in SQL is hierarchical intervals. It allows fast querying entire sub-branches, along branches, and so on. Updating hierarchical intervals is a real pain, so think of them as an index that is built like a materialised view.
Quickest explanation: each node has two numbers: left and right (or low/high). All children under the node have numbers between left and right. So, querying an entire sub-branch:
select child.* from Nodes as parent, Nodes as child where child.lft between parent.lft and parent.rgt;
11 comments
[ 32.2 ms ] story [ 450 ms ] threadQuite powerful stuff, both in the results it can produce and in the resources it can drain from the server.
Besides the typical "linked-list" queries, I used this to split a comma-separated column value into separate rows, as our DB server did not have that as a built-in function. Not pretty, but it did the job.
It is used to extract an explained query from a plan table.
It does seem to be much easier than a common table expression.
How about we don't, and think about queries as the algebraic relations that they are?
I always found this explanation of SQL (and SQL-like) recursion much more reasonable than efforts to shoehorn SQL into an iterative, functional box: https://core.ac.uk/download/pdf/11454271.pdf
https://gist.github.com/bokwoon95/4fd34a78e72b2935e78ec0f40e...
https://www.postgresql.org/docs/current/ltree.html
Quickest explanation: each node has two numbers: left and right (or low/high). All children under the node have numbers between left and right. So, querying an entire sub-branch:
select child.* from Nodes as parent, Nodes as child where child.lft between parent.lft and parent.rgt;