Recursion in SQL Explained Visually (2020) | Hacker News Reader

Recursion in SQL Explained Visually (2020)

denis-lukichev.medium.com

108 pointsTomte11 comments

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:

https://gist.github.com/bokwoon95/4fd34a78e72b2935e78ec0f40e...

This data structure you used is covered by the native postgres data type "ltree" right?

https://www.postgresql.org/docs/current/ltree.html

  "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;

Oracle has a more succinct syntax for this known as the CONNECT BY clause for a select.

It is used to extract an explained query from a plan table.

It does seem to be much easier than a common table expression.

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?

relational as in mathematical relation: a subset of some carthesian product

"Let's think about queries as a function."

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

Article mention there would be an algebraic approach post to follow. I couldn't find it :(

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

A good recap for me. Thanks. Haven't used CTE in 3yrs. I used to use this to find parent child relationship between tables in Db2 z/OS

Reply on news.ycombinator.com