4 ms·

Recursion with SQL

56 points by thebillkidy 12y ago

r00fus 12y ago
So essentially this is Oracle SQL - does anyone know if there are analogous similar START WITH and CONNECT BY keywords for other platforms? (author mentions MSSQL has the them, but no mention of MySQL/MariaDB or PGSQL).
- spacemanmatt 12y ago
  They're nice to have but you can do some or all the same things using recursive CTE in PostgreSQL, for one.
- dragonwriter 12y ago
  Recursive CTEs are strictly more powerful than Oracle's START WITH/CONNECT BY and are supported by most databases (pretty much everything other than the MySQL/MariaDB family -- SQLServer, Oracle, Postgres, even SQlite.) To be fair to Oracle, START WITH/CONNECT BY has been available in Oracle a lot longer than CTEs as part of the SQL standard have existed.
- crorella 12y ago
  Teradata has the WITH RECURSIVE statement which is pretty easy to use.
- batbomb 12y ago
  No support in MySQL/MariaDB. There is support in Postgres, sqlite, MSSQL, HSQLDB, Oracle, etc... for CTEs. You can sort of emulate some recursive SQL properties using a temporary table: http://brianv0.github.io/blog/2013/6/recursive.html http://brianv0.github.io/blog/2013/6/recursive.html
smoyer 12y ago
Beware! If you're running one-off queries, you probably won't have issues using recursion, but there are a lot of instances where you really don't want to run a complex SQL statement for each of the 1M users reading data from your site. Selecting the proper database table structure can help dramatically! For example, take any data structured as a tree. If there are more writes than reads, it's pretty easy to put new data in place and your read becomes recursive. When you have vastly more reads than writes it's almost always better to "pre-order" the data. I've had good success with using the modified pre-ordered lists for tree structures but other table formats and processing can be used for other data types. Sometimes it's just careful but non-obvious indexing.
marktangotango 12y ago
I recommend this link to anyone contemplating storing/querying hierarchical data in sql/rdbms. The "LR Method" is the best solution I've found. Does not depend on vendor specific funcationality and/or keywords: http://kamfonas.com/id3.html http://kamfonas.com/id3.html
- platz 12y ago
  this is also called nested sets.. it's nice but has some tradeoffs as well
- gtaylor 12y ago
  We started writing a threaded discussion system using these, but it ended up being much easier to use Postgres's Recursive CTEs. Highly recommend!
sequence7 12y ago
This seems to be taking advantage of a specific Oracle feature whose performance I have no idea about, there are suggestions that Common Table Expressions could do the same sort of thing but since CTE performance is generally horrible I'd be concerned that you get nice syntax and horrible performance. Does anyone have a suggestion as to how you could do something similar across different DBs without basically killing performance or am I missing something here?
- dragonwriter 12y ago
  In the read-mostly case, you can use an adjacency list, use a query with a CTE to generate a heirarchy in a materialized view which is updated when you write to the main table, and query against the materialized view. You still pay the performance cost for the CTE, but only on writes, not every read. This doesn't help in a write-heavy use case.
- rosser 12y ago
  Recursive CTEs work quite well in PostgreSQL, and the performance isn't at all what I'd call "horrible".
- jeffdavis 12y ago
  I recommend actually trying it (e.g. PostgreSQL CTE) on a problem you are trying to solve, if you haven't already. People tend to report the bad cases, and stay silent for the good cases, which can contribute to a sense of fear of the feature. It could have started from a real issue, or it could just be someone trying to solve the traveling salesman problem with fake data and then blogging when it's slow.
encloser 12y ago
Nice. A few tricks with dual I haven't come across before. When you get into examples using tables it would be nice if you provided the table definitions and some sample data. PS: psoug's connect by page (http://psoug.org/reference/connectby.html http://psoug.org/reference/connectby.html) is my favorite reference.
rosser 12y ago
...and no mention at all of recursive CTEs. My favorite ridiculous use-case for them: https://wiki.postgresql.org/wiki/Mandelbrot_set https://wiki.postgresql.org/wiki/Mandelbrot_set (For reference, that ran in 252ms on my low-end Linode.)
- gtaylor 12y ago
  I didn't think Oracle SQL server has CTEs, but maybe that's changed. Postgres CTEs are amazing, though. Surprisingly efficient for our particular usage case (threaded discussions that don't ever get too deep).
  - thebillkidy 12y ago
    Oracle SQL Indeed has CTE's :) I mentioned those together with other special use cases in previous articles on my blog.
  - dragonwriter 12y ago
    Oracle has recursive CTEs since, I think, 11gR2, and non-recursive CTEs since 9.2.
jeffdavis 12y ago
For those who prefer standard syntax in an open-source system, see: http://www.postgresql.org/docs/9.4/static/queries-with.html http://www.postgresql.org/docs/9.4/static/queries-with.html
thebillkidy 12y ago
I have not included CTE's because I wanted to show pure recursion queries without the use of this. I think CTE's will be faster though but I have yet to verify this.
greggyb 12y ago
I prefer the syntax of recursive CTEs (as many others have mentioned). A simple use case that I have in my work is generating a date table, and a recursive CTE sits at the core of this script: TSQL Syntax: WITH dateCTE (FullDate) AS (SELECT '20100101' UNION ALL SELECT DATEADD(DAY, 1, FullDate) FROM dateCTE WHERE FullDate < 20101231 ) In the example above, we generate a table of all dates in 2010. I don't get much chance to play with Postgres, but from their documentation[0] it seems the concept transfers over readily by using WITH RECURSIVE. [0]http://www.postgresql.org/docs/9.4/static/queries-with.html http://www.postgresql.org/docs/9.4/static/queries-with.html
- JonnieCache 12y ago
  In postgres you would use generate_series for that. http://www.postgresql.org/docs/current/static/functions-srf.html http://www.postgresql.org/docs/current/static/functions-srf....
  - greggyb 12y ago
    Neat. It seems we can simulate this behavior in TSQL[0] by using recursive CTEs in a function. [0]https://developer42.wordpress.com/2014/09/17/t-sql-generate-series-getting-a-list-of-numbers-in-a-given-range/ https://developer42.wordpress.com/2014/09/17/t-sql-generate-...
jmadsen 12y ago
There are, of course, many very large databases that would need something like this. However, I've found that most small sites I've worked on, a simple "lineage" system in a completely flat single table is more than adequate. (The following is a link to my own website where I explain it using a Codeigniter library I built. It can be done in any type of code, however) http://codebyjeff.com/blog/2012/10/nested-data-with-mahana-hierarchy-library http://codebyjeff.com/blog/2012/10/nested-data-with-mahana-h...
thorin 12y ago
I like your final solution for a calendar. I've implemented a calendar like this in a jasper report (on Oracle), with hyperlinks to actions on that date . Your SQL is cleaner to read. However on my environment the week numbers don't line up correctly. I had to change the line , TO_CHAR(x +1, 'iw') weeknumber , TO_CHAR(x , 'iw') weeknumber I guess this might be environmental as some regions may consider the start/end of the week on different days.

56 points by thebillkidy 12y ago

So essentially this is Oracle SQL - does anyone know if there are analogous similar START WITH and CONNECT BY keywords for other platforms? (author mentions MSSQL has the them, but no mention of MySQL/MariaDB or PGSQL).

spacemanmatt 12y ago
They're nice to have but you can do some or all the same things using recursive CTE in PostgreSQL, for one.
dragonwriter 12y ago
Recursive CTEs are strictly more powerful than Oracle's START WITH/CONNECT BY and are supported by most databases (pretty much everything other than the MySQL/MariaDB family -- SQLServer, Oracle, Postgres, even SQlite.) To be fair to Oracle, START WITH/CONNECT BY has been available in Oracle a lot longer than CTEs as part of the SQL standard have existed.
crorella 12y ago
Teradata has the WITH RECURSIVE statement which is pretty easy to use.
batbomb 12y ago
No support in MySQL/MariaDB. There is support in Postgres, sqlite, MSSQL, HSQLDB, Oracle, etc... for CTEs. You can sort of emulate some recursive SQL properties using a temporary table: http://brianv0.github.io/blog/2013/6/recursive.html http://brianv0.github.io/blog/2013/6/recursive.html

smoyer 12y ago

Beware! If you're running one-off queries, you probably won't have issues using recursion, but there are a lot of instances where you really don't want to run a complex SQL statement for each of the 1M users reading data from your site. Selecting the proper database table structure can help dramatically! For example, take any data structured as a tree. If there are more writes than reads, it's pretty easy to put new data in place and your read becomes recursive. When you have vastly more reads than writes it's almost always better to "pre-order" the data. I've had good success with using the modified pre-ordered lists for tree structures but other table formats and processing can be used for other data types. Sometimes it's just careful but non-obvious indexing.

marktangotango 12y ago

I recommend this link to anyone contemplating storing/querying hierarchical data in sql/rdbms. The "LR Method" is the best solution I've found. Does not depend on vendor specific funcationality and/or keywords: http://kamfonas.com/id3.html http://kamfonas.com/id3.html

platz 12y ago
this is also called nested sets.. it's nice but has some tradeoffs as well
gtaylor 12y ago
We started writing a threaded discussion system using these, but it ended up being much easier to use Postgres's Recursive CTEs. Highly recommend!

sequence7 12y ago

This seems to be taking advantage of a specific Oracle feature whose performance I have no idea about, there are suggestions that Common Table Expressions could do the same sort of thing but since CTE performance is generally horrible I'd be concerned that you get nice syntax and horrible performance. Does anyone have a suggestion as to how you could do something similar across different DBs without basically killing performance or am I missing something here?

dragonwriter 12y ago
In the read-mostly case, you can use an adjacency list, use a query with a CTE to generate a heirarchy in a materialized view which is updated when you write to the main table, and query against the materialized view. You still pay the performance cost for the CTE, but only on writes, not every read. This doesn't help in a write-heavy use case.
rosser 12y ago
Recursive CTEs work quite well in PostgreSQL, and the performance isn't at all what I'd call "horrible".
jeffdavis 12y ago
I recommend actually trying it (e.g. PostgreSQL CTE) on a problem you are trying to solve, if you haven't already. People tend to report the bad cases, and stay silent for the good cases, which can contribute to a sense of fear of the feature. It could have started from a real issue, or it could just be someone trying to solve the traveling salesman problem with fake data and then blogging when it's slow.

encloser 12y ago

Nice. A few tricks with dual I haven't come across before. When you get into examples using tables it would be nice if you provided the table definitions and some sample data. PS: psoug's connect by page (http://psoug.org/reference/connectby.html http://psoug.org/reference/connectby.html) is my favorite reference.

rosser 12y ago

...and no mention at all of recursive CTEs. My favorite ridiculous use-case for them: https://wiki.postgresql.org/wiki/Mandelbrot_set https://wiki.postgresql.org/wiki/Mandelbrot_set (For reference, that ran in 252ms on my low-end Linode.)

gtaylor 12y ago
I didn't think Oracle SQL server has CTEs, but maybe that's changed. Postgres CTEs are amazing, though. Surprisingly efficient for our particular usage case (threaded discussions that don't ever get too deep).
- thebillkidy 12y ago
  Oracle SQL Indeed has CTE's :) I mentioned those together with other special use cases in previous articles on my blog.
- dragonwriter 12y ago
  Oracle has recursive CTEs since, I think, 11gR2, and non-recursive CTEs since 9.2.

jeffdavis 12y ago

For those who prefer standard syntax in an open-source system, see: http://www.postgresql.org/docs/9.4/static/queries-with.html http://www.postgresql.org/docs/9.4/static/queries-with.html

thebillkidy 12y ago

I have not included CTE's because I wanted to show pure recursion queries without the use of this. I think CTE's will be faster though but I have yet to verify this.

greggyb 12y ago

I prefer the syntax of recursive CTEs (as many others have mentioned). A simple use case that I have in my work is generating a date table, and a recursive CTE sits at the core of this script: TSQL Syntax: WITH dateCTE (FullDate) AS (SELECT '20100101' UNION ALL SELECT DATEADD(DAY, 1, FullDate) FROM dateCTE WHERE FullDate < 20101231 ) In the example above, we generate a table of all dates in 2010. I don't get much chance to play with Postgres, but from their documentation[0] it seems the concept transfers over readily by using WITH RECURSIVE. [0]http://www.postgresql.org/docs/9.4/static/queries-with.html http://www.postgresql.org/docs/9.4/static/queries-with.html

JonnieCache 12y ago
In postgres you would use generate_series for that. http://www.postgresql.org/docs/current/static/functions-srf.html http://www.postgresql.org/docs/current/static/functions-srf....
- greggyb 12y ago
  Neat. It seems we can simulate this behavior in TSQL[0] by using recursive CTEs in a function. [0]https://developer42.wordpress.com/2014/09/17/t-sql-generate-series-getting-a-list-of-numbers-in-a-given-range/ https://developer42.wordpress.com/2014/09/17/t-sql-generate-...

jmadsen 12y ago

There are, of course, many very large databases that would need something like this. However, I've found that most small sites I've worked on, a simple "lineage" system in a completely flat single table is more than adequate. (The following is a link to my own website where I explain it using a Codeigniter library I built. It can be done in any type of code, however) http://codebyjeff.com/blog/2012/10/nested-data-with-mahana-hierarchy-library http://codebyjeff.com/blog/2012/10/nested-data-with-mahana-h...

thorin 12y ago

I like your final solution for a calendar. I've implemented a calendar like this in a jasper report (on Oracle), with hyperlinks to actions on that date . Your SQL is cleaner to read. However on my environment the week numbers don't line up correctly. I had to change the line , TO_CHAR(x +1, 'iw') weeknumber , TO_CHAR(x , 'iw') weeknumber I guess this might be environmental as some regions may consider the start/end of the week on different days.