6 ms·

SQLite: Outlandish Recursive Query Examples

201 points by Rendello 2y ago

westurner 2y ago
Firefox bookmarks have nested folders in an arbitrary depth tree, so a recursive CTE might be faster; https://www.google.com/search?q=Firefox+bookmarks+%22CTE%22 https://www.google.com/search?q=Firefox+bookmarks+%22CTE%22 (Edit) "Bug 1452376 - Replace GetDescendantFolders with a recursive subquery" https://hg.mozilla.org/integration/autoland/rev/827cc04dacce https://hg.mozilla.org/integration/autoland/rev/827cc04dacce "Recursive Queries Using Common Table Expressions" https://gist.github.com/jbrown123/b65004fd4e8327748b650c77383bf553 https://gist.github.com/jbrown123/b65004fd4e8327748b650c7738...
- leeoniya 2y ago
  storing the tree as an MPTT/NestedSet would massively simplify this, without any subquery shenanigans. https://en.m.wikipedia.org/wiki/Nested_set_model https://en.m.wikipedia.org/wiki/Nested_set_model https://imrannazar.com/articles/modified-preorder-tree-traversal https://imrannazar.com/articles/modified-preorder-tree-trave...
  - jitl 2y ago
    Well the read query has simpler syntax with MPTT but implementing the whole structure is more complicated and any re-organization like moving a folder around requires rewriting a lot of rows. Although it doesn’t apply to the Firefox use-case, I’ve never understood how this technique can be applied to anything but the most trivially sized, roughly immutable trees. What do you do in a production system when two people move two different node in the tree? It seems to need all kinds of complicated locks.
  - westurner 2y ago
    There are at least five ways to store a tree in PostgreSQL, for example: adjacency list, nested sets like MPTT Modified Preorder Tree Traversal, nested intervals, Materialized Paths, ltree, JSON E.g. django-mptt : https://github.com/django-mptt/django-mptt/blob/main/mptt/models.py https://github.com/django-mptt/django-mptt/blob/main/mptt/mo... : indexed_attrs = (mptt_meta.tree_id_attr,) field_names = ( mptt_meta.left_attr, mptt_meta.right_attr, mptt_meta.tree_id_attr, mptt_meta.level_attr, ) Nested set model: https://en.wikipedia.org/wiki/Nested_set_model https://en.wikipedia.org/wiki/Nested_set_model : > The nested interval model stores the position of the nodes as rational numbers expressed as quotients (n/d).
clumsysmurf 2y ago
Just curios: can CTE's be used to make time series range queries easier / more performant? Sqlite is the default option on Android and it's pretty common to have time series sensor data that needs to be captured, stored, and analyzed... But sqlite isn't really meant for a time series workload. There is also duckdb but I'm not sure about the status of the Android bindings.
- jitl 2y ago
  nothing really helps with potato slow Android device / storage media. CTE is not magic sauce that will make sqlite go faster. Depending on the recursion pattern and the overhead of your sqlite driver, it can be faster to do many ID lookups then try to cram it all into one mega CTE query. https://www.sqlite.org/np1queryprob.html https://www.sqlite.org/np1queryprob.html source: we have the CTE for loading page data in the notion Android app, and the network regularly beats disk on lower end Android devices using whichever query we pick.
- dspillett 2y ago
  > can CTE's be used to make time series range queries easier / more performant? On their own, I'd guess likely not a lot. If a view would help, a CTE will help similarly without needing the external structure, if a correlated subquery would help, then yes similarly, especially if the pattern is repeated in the overall query. In conjunction with other things (good indexing, materialised sequences ("numbers" tables), etc.), is guess yes. Though you need to be much more specific about your data and the queries in question before I can do better than these vague guesses.
- remram 2y ago
  No. They are a query syntax, they don't change the storage or retrieval performance.
jitl 2y ago
No matter how much time I spend contemplating recursive CTE examples, I just cannot “get it” enough to write my own without a lot of trial and error and head-scratching. I would love to take a 2 hour class on “thinking in SQL for hackers” or something, but I haven’t really found anything to improve my mental model from “broken” to “working” so far.
- daelon 2y ago
  I would also love to take that class!
- nbbaier 2y ago
  Sign me up for this class too!
- pawelduda 2y ago
  It's unusual and not a commonly needed tool in SQL. I always need a quick refresher on how to write these after a longer break
  - DemocracyFTW2 2y ago
    Not commonly needed presumably only because we've grown up to understand that SQL is not a language where you can easily express rescursively hierarchical relationships, such as the in the go-to example where you have a table of employees with a 'reports-to' field. In classical SQL there was no way to write a simple query that will resolve 'who is reporting to who' recursively with an arbitrary depth. Recursive CTEs can do that.
- CGamesPlay 2y ago
  A prerequisite to understanding is knowing the CTE syntax ("WITH"). That's just a group of SQL queries that can refer to one another. It's extremely useful for making modular SQL queries and has nothing to do with recursion. Then when you use "WITH RECURSIVE", the queries can now refer back to themselves. This is just a for loop over a queue of SQL results, conceptually. The part before the UNION ALL fills the queue to start, and the part after the UNION ALL runs once for each result in the queue, adding all results back into the queue. If you understand this, then you can understand the Sudoku or Mandelbrot examples (definitely don't start with trying to understand these two though). For example, the Sudoku example contains one recursive query, "x(s, ind)". As explained on the page, "s" is the puzzle (unsolved spaces shown as ".") and "ind" is the index of the first unsolved space (or 0 for a solved puzzle). It creates an unsolved puzzle in the initial setup. The for loop body finds all valid values for the first unsolved space, and the next index to solve; then puts all these results into the queue. The final (non-recursive) SELECT in the CTE looks over all results in the queue, and returns the one where the index is 0 (the solved puzzles).
magicalhippo 2y ago
I've mostly kept the usage to "sane" stuff like turning delimiter-separated text into rows, or walking a graph. As much as I enjoy the Mandelbrot set, I bought the Fractint book as a kid, anyone done any outlandish but useful recursive queries? PS: awesome explanation of how exactly the recursive query works. Wish I had read it when I first needed it in some other DB which help did not have such a clear explanation. Tore out a lot of hair before I got it working right.
- hobs 2y ago
  Last time it was useful I re-implemented XIRR(https://support.microsoft.com/en-us/office/xirr-function-de1242ec-6477-445b-b11b-a303ad9adc9d https://support.microsoft.com/en-us/office/xirr-function-de1...) using Excel's approach in pure SQL so it would be able to make the finance bros happy, it was something like 50,000x faster than the user defined function/loop approach.
- airstrike 2y ago
  12 years ago I wrote a recursive CTE which aggregated a bunch of accounting journal entries from pretty big SAP extracts with intermediate account also needing to be calculated in a way that rolled up to company-level values, with some tagging/indexing in the process. I remember only being able to finish the query after some kind anon helped me in an IRC channel at 4am on a weeknight... to this day I'm immensely grateful to them I made it into a neat little Django portal with configurable permissions, interactive charts for the data, filtering, etc. It became a ~10-min async celery task running in the background from what previously used to take the company weeks to create that report in an error prone way with macros written by someone long gone / in another department. I'm still pretty proud of that app even though it never got implemented. I got promoted, moved to a different department and don't think it ever saw the light of day, but I do have the code laying around somewhere
- JaggerFoo 2y ago
  Years ago I came across a Knapsack problem solution written in Oracle SQL, that I adapted to Daily Fantasy Golf. Here's the source: https://aprogrammerwrites.eu/?p=878 https://aprogrammerwrites.eu/?p=878 Cheers
rkwz 2y ago
Not SQLite, but recently used Postgres Recursive CTEs for graph retrieval - https://www.sheshbabu.com/posts/graph-retrieval-using-postgres-recursive-ctes/ https://www.sheshbabu.com/posts/graph-retrieval-using-postgr...
dspillett 2y ago
The Mandelbrot example had been around in various forms for quite some time, IIRC I first saw it in ~2006 for SQL Server which gained recursive CTE support in its 2005 release. Another example from around that time was using recursive CTEs to define dragon curves using spatial types that would then be drawn using SSMS's support for displaying data in those types.
jschrf 2y ago
CTEs are extremely useful mechanisms for writing modular and easily maintainable queries, particularly around anything to do with ETL, graphs, and timeseries data. Highly recommend.
otteromkram 2y ago
The SQL formatting on this website is atrocious. I can't find a good reason not to left-align everything vs trying to right-align keywords and keep everything else on one line until the next keyword.
- thissuchness 2y ago
  Can you give an example of a query you find offensive, and how you'd format it better?
owlninja 2y ago
I often have to generate ad-hoc recursive queries for bills of materials. Any one have good ideas to make something more self serve for end users? I guess just some sort of app where the user supplies the top level part works, but I wonder if it should be pre-exploded? Often I am given a list of many parts to explode.
- cryptonector 2y ago
  "Something more self-serve" is essentially what graph databases provide. If you don't have the time to use one of those or build your own (and you probably shouldn't) sort of thing on top of SQL, then you can instead define a bunch of VIEWs using recursive queries and GROUP BY and aggregation functions to provide something simple for your users to query. If you do want to build something more general purpose... If you begin by modeling your schema in something other than SQL DDLs (like with an AST) and then model FKs as bi-directional relationships (because they are), and if you add a way to group those relationships, and further provide a way to define a subset of like columns from all the tables in a graph defined by a group of those relationships, then suddenly you can also come up with a simple(ish) language for expressing [sub-]graphs that you want to fetch. And there's your ad-hoc query language for dealing with recursive graphs in your relational data.
  - owlninja 2y ago
    I appreciate this!
simonw 2y ago
I thought this might be a relatively new example - I remember having seen the fractal one but I didn't recall the Sudoku one. Turns out both of those examples have been in that documentation for over a decade now! https://web.archive.org/web/20140331191105/http://sqlite.org/lang_with.html https://web.archive.org/web/20140331191105/http://sqlite.org...
firer 2y ago
I love this stuff. If anybody wants another outlandish example here is an emulator I built: https://github.com/DanielFi/sqlite-vm/blob/main/emulator.sql https://github.com/DanielFi/sqlite-vm/blob/main/emulator.sql
hans_castorp 2y ago
With Postgres you can also generate fireworks http://explainextended.com/2009/12/31/happy-new-year/ http://explainextended.com/2009/12/31/happy-new-year/ or snowflakes: http://explainextended.com/2011/12/31/happy-new-year-3/ http://explainextended.com/2011/12/31/happy-new-year-3/ Or you can solve a Sudoku riddle in Oracle https://technology.amis.nl/2009/10/13/oracle-rdbms-11gr2-solving-a-sudoku-using-recursive-subquery-factoring/ https://technology.amis.nl/2009/10/13/oracle-rdbms-11gr2-sol...
- mike_hearn 2y ago
  Intriguing. The Sudoku puzzle in your last Oracle link from 2009 is exactly the same puzzle used in the SQLite example, doing the same thing.
deleted 2y ago
[deleted]
gzel 2y ago
I really like the way of how feldera implemented recursion in SQL: https://docs.feldera.com/sql/recursion https://docs.feldera.com/sql/recursion All you have to do is to add a forward declaration of the view and then you can reference it in a recursive query. Makes the syntax part much easier.

201 points by Rendello 2y ago

Firefox bookmarks have nested folders in an arbitrary depth tree, so a recursive CTE might be faster; https://www.google.com/search?q=Firefox+bookmarks+%22CTE%22 https://www.google.com/search?q=Firefox+bookmarks+%22CTE%22 (Edit) "Bug 1452376 - Replace GetDescendantFolders with a recursive subquery" https://hg.mozilla.org/integration/autoland/rev/827cc04dacce https://hg.mozilla.org/integration/autoland/rev/827cc04dacce "Recursive Queries Using Common Table Expressions" https://gist.github.com/jbrown123/b65004fd4e8327748b650c77383bf553 https://gist.github.com/jbrown123/b65004fd4e8327748b650c7738...

leeoniya 2y ago
storing the tree as an MPTT/NestedSet would massively simplify this, without any subquery shenanigans. https://en.m.wikipedia.org/wiki/Nested_set_model https://en.m.wikipedia.org/wiki/Nested_set_model https://imrannazar.com/articles/modified-preorder-tree-traversal https://imrannazar.com/articles/modified-preorder-tree-trave...
- jitl 2y ago
  Well the read query has simpler syntax with MPTT but implementing the whole structure is more complicated and any re-organization like moving a folder around requires rewriting a lot of rows. Although it doesn’t apply to the Firefox use-case, I’ve never understood how this technique can be applied to anything but the most trivially sized, roughly immutable trees. What do you do in a production system when two people move two different node in the tree? It seems to need all kinds of complicated locks.
- westurner 2y ago
  There are at least five ways to store a tree in PostgreSQL, for example: adjacency list, nested sets like MPTT Modified Preorder Tree Traversal, nested intervals, Materialized Paths, ltree, JSON E.g. django-mptt : https://github.com/django-mptt/django-mptt/blob/main/mptt/models.py https://github.com/django-mptt/django-mptt/blob/main/mptt/mo... : indexed_attrs = (mptt_meta.tree_id_attr,) field_names = ( mptt_meta.left_attr, mptt_meta.right_attr, mptt_meta.tree_id_attr, mptt_meta.level_attr, ) Nested set model: https://en.wikipedia.org/wiki/Nested_set_model https://en.wikipedia.org/wiki/Nested_set_model : > The nested interval model stores the position of the nodes as rational numbers expressed as quotients (n/d).

clumsysmurf 2y ago

Just curios: can CTE's be used to make time series range queries easier / more performant? Sqlite is the default option on Android and it's pretty common to have time series sensor data that needs to be captured, stored, and analyzed... But sqlite isn't really meant for a time series workload. There is also duckdb but I'm not sure about the status of the Android bindings.

jitl 2y ago
nothing really helps with potato slow Android device / storage media. CTE is not magic sauce that will make sqlite go faster. Depending on the recursion pattern and the overhead of your sqlite driver, it can be faster to do many ID lookups then try to cram it all into one mega CTE query. https://www.sqlite.org/np1queryprob.html https://www.sqlite.org/np1queryprob.html source: we have the CTE for loading page data in the notion Android app, and the network regularly beats disk on lower end Android devices using whichever query we pick.
dspillett 2y ago
> can CTE's be used to make time series range queries easier / more performant? On their own, I'd guess likely not a lot. If a view would help, a CTE will help similarly without needing the external structure, if a correlated subquery would help, then yes similarly, especially if the pattern is repeated in the overall query. In conjunction with other things (good indexing, materialised sequences ("numbers" tables), etc.), is guess yes. Though you need to be much more specific about your data and the queries in question before I can do better than these vague guesses.
remram 2y ago
No. They are a query syntax, they don't change the storage or retrieval performance.

jitl 2y ago

No matter how much time I spend contemplating recursive CTE examples, I just cannot “get it” enough to write my own without a lot of trial and error and head-scratching. I would love to take a 2 hour class on “thinking in SQL for hackers” or something, but I haven’t really found anything to improve my mental model from “broken” to “working” so far.

daelon 2y ago
I would also love to take that class!
nbbaier 2y ago
Sign me up for this class too!
pawelduda 2y ago
It's unusual and not a commonly needed tool in SQL. I always need a quick refresher on how to write these after a longer break
- DemocracyFTW2 2y ago
  Not commonly needed presumably only because we've grown up to understand that SQL is not a language where you can easily express rescursively hierarchical relationships, such as the in the go-to example where you have a table of employees with a 'reports-to' field. In classical SQL there was no way to write a simple query that will resolve 'who is reporting to who' recursively with an arbitrary depth. Recursive CTEs can do that.
CGamesPlay 2y ago
A prerequisite to understanding is knowing the CTE syntax ("WITH"). That's just a group of SQL queries that can refer to one another. It's extremely useful for making modular SQL queries and has nothing to do with recursion. Then when you use "WITH RECURSIVE", the queries can now refer back to themselves. This is just a for loop over a queue of SQL results, conceptually. The part before the UNION ALL fills the queue to start, and the part after the UNION ALL runs once for each result in the queue, adding all results back into the queue. If you understand this, then you can understand the Sudoku or Mandelbrot examples (definitely don't start with trying to understand these two though). For example, the Sudoku example contains one recursive query, "x(s, ind)". As explained on the page, "s" is the puzzle (unsolved spaces shown as ".") and "ind" is the index of the first unsolved space (or 0 for a solved puzzle). It creates an unsolved puzzle in the initial setup. The for loop body finds all valid values for the first unsolved space, and the next index to solve; then puts all these results into the queue. The final (non-recursive) SELECT in the CTE looks over all results in the queue, and returns the one where the index is 0 (the solved puzzles).

magicalhippo 2y ago

I've mostly kept the usage to "sane" stuff like turning delimiter-separated text into rows, or walking a graph. As much as I enjoy the Mandelbrot set, I bought the Fractint book as a kid, anyone done any outlandish but useful recursive queries? PS: awesome explanation of how exactly the recursive query works. Wish I had read it when I first needed it in some other DB which help did not have such a clear explanation. Tore out a lot of hair before I got it working right.

hobs 2y ago
Last time it was useful I re-implemented XIRR(https://support.microsoft.com/en-us/office/xirr-function-de1242ec-6477-445b-b11b-a303ad9adc9d https://support.microsoft.com/en-us/office/xirr-function-de1...) using Excel's approach in pure SQL so it would be able to make the finance bros happy, it was something like 50,000x faster than the user defined function/loop approach.
airstrike 2y ago
12 years ago I wrote a recursive CTE which aggregated a bunch of accounting journal entries from pretty big SAP extracts with intermediate account also needing to be calculated in a way that rolled up to company-level values, with some tagging/indexing in the process. I remember only being able to finish the query after some kind anon helped me in an IRC channel at 4am on a weeknight... to this day I'm immensely grateful to them I made it into a neat little Django portal with configurable permissions, interactive charts for the data, filtering, etc. It became a ~10-min async celery task running in the background from what previously used to take the company weeks to create that report in an error prone way with macros written by someone long gone / in another department. I'm still pretty proud of that app even though it never got implemented. I got promoted, moved to a different department and don't think it ever saw the light of day, but I do have the code laying around somewhere
JaggerFoo 2y ago
Years ago I came across a Knapsack problem solution written in Oracle SQL, that I adapted to Daily Fantasy Golf. Here's the source: https://aprogrammerwrites.eu/?p=878 https://aprogrammerwrites.eu/?p=878 Cheers

rkwz 2y ago

Not SQLite, but recently used Postgres Recursive CTEs for graph retrieval - https://www.sheshbabu.com/posts/graph-retrieval-using-postgres-recursive-ctes/ https://www.sheshbabu.com/posts/graph-retrieval-using-postgr...

dspillett 2y ago

The Mandelbrot example had been around in various forms for quite some time, IIRC I first saw it in ~2006 for SQL Server which gained recursive CTE support in its 2005 release. Another example from around that time was using recursive CTEs to define dragon curves using spatial types that would then be drawn using SSMS's support for displaying data in those types.

jschrf 2y ago

CTEs are extremely useful mechanisms for writing modular and easily maintainable queries, particularly around anything to do with ETL, graphs, and timeseries data. Highly recommend.

otteromkram 2y ago

The SQL formatting on this website is atrocious. I can't find a good reason not to left-align everything vs trying to right-align keywords and keep everything else on one line until the next keyword.

thissuchness 2y ago
Can you give an example of a query you find offensive, and how you'd format it better?

owlninja 2y ago

I often have to generate ad-hoc recursive queries for bills of materials. Any one have good ideas to make something more self serve for end users? I guess just some sort of app where the user supplies the top level part works, but I wonder if it should be pre-exploded? Often I am given a list of many parts to explode.

cryptonector 2y ago
"Something more self-serve" is essentially what graph databases provide. If you don't have the time to use one of those or build your own (and you probably shouldn't) sort of thing on top of SQL, then you can instead define a bunch of VIEWs using recursive queries and GROUP BY and aggregation functions to provide something simple for your users to query. If you do want to build something more general purpose... If you begin by modeling your schema in something other than SQL DDLs (like with an AST) and then model FKs as bi-directional relationships (because they are), and if you add a way to group those relationships, and further provide a way to define a subset of like columns from all the tables in a graph defined by a group of those relationships, then suddenly you can also come up with a simple(ish) language for expressing [sub-]graphs that you want to fetch. And there's your ad-hoc query language for dealing with recursive graphs in your relational data.
- owlninja 2y ago
  I appreciate this!

simonw 2y ago

I thought this might be a relatively new example - I remember having seen the fractal one but I didn't recall the Sudoku one. Turns out both of those examples have been in that documentation for over a decade now! https://web.archive.org/web/20140331191105/http://sqlite.org/lang_with.html https://web.archive.org/web/20140331191105/http://sqlite.org...

firer 2y ago

I love this stuff. If anybody wants another outlandish example here is an emulator I built: https://github.com/DanielFi/sqlite-vm/blob/main/emulator.sql https://github.com/DanielFi/sqlite-vm/blob/main/emulator.sql

hans_castorp 2y ago

With Postgres you can also generate fireworks http://explainextended.com/2009/12/31/happy-new-year/ http://explainextended.com/2009/12/31/happy-new-year/ or snowflakes: http://explainextended.com/2011/12/31/happy-new-year-3/ http://explainextended.com/2011/12/31/happy-new-year-3/ Or you can solve a Sudoku riddle in Oracle https://technology.amis.nl/2009/10/13/oracle-rdbms-11gr2-solving-a-sudoku-using-recursive-subquery-factoring/ https://technology.amis.nl/2009/10/13/oracle-rdbms-11gr2-sol...

mike_hearn 2y ago
Intriguing. The Sudoku puzzle in your last Oracle link from 2009 is exactly the same puzzle used in the SQLite example, doing the same thing.

deleted 2y ago

[deleted]

gzel 2y ago

I really like the way of how feldera implemented recursion in SQL: https://docs.feldera.com/sql/recursion https://docs.feldera.com/sql/recursion All you have to do is to add a forward declaration of the view and then you can reference it in a recursive query. Makes the syntax part much easier.