Recursive references in subqueries

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Recursive references in subqueries

Christian Duta
Hello,

when writing a recursive queries, I encountered the following error:

[...] recursive reference in a subquery: [...]

The following minimal example illustrates when this error occurs:

WITH RECURSIVE
   count_down(v) AS (
     SELECT 5
       UNION ALL
     SELECT cd.v - 1
     FROM (
       SELECT cd.v
       FROM count_down AS cd
     ) AS cd
     WHERE cd.v > 0
   )
SELECT * FROM count_down;

Error: near line 1: recursive reference in a subquery: count_down

I subsequently rewrote the query, but I started to wonder:

What is the reasoning behind this restriction?
And more importantly: Are there plans to allow recursive references
inside of a subquery in a future release of SQLite?

Best regards,
Christian Duta
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive references in subqueries

R Smith-2

On 2018/07/19 2:32 PM, Christian Duta wrote:

>
> WITH RECURSIVE
>   count_down(v) AS (
>     SELECT 5
>       UNION ALL
>     SELECT cd.v - 1
>     FROM (
>       SELECT cd.v
>       FROM count_down AS cd
>     ) AS cd
>     WHERE cd.v > 0
>   )
> SELECT * FROM count_down;
>
> Error: near line 1: recursive reference in a subquery: count_down
>
> What is the reasoning behind this restriction?
> And more importantly: Are there plans to allow recursive references
> inside of a subquery in a future release of SQLite?

The problem is that there can be only one "builder" of the recursive set.

In your example above, the full recursive set is not known at the time
of first encountering the sub-query.
i.e. do you expect it to have results on the first iteration? Because it
can't, since by the time it is reached (which must be before the first
row from the main select is produced, as is the nature of FROM/JOIN
clauses), there is no set built to choose any values from, and since it
has no values, it will produce no rows, and if it doesn't produce rows,
the entire recursive part of the query doesn't produce rows (since it
selects from the very sub-query in question, which has no rows yet on
the first iteration), and therefore there simply is no row added at all
on the first (or any next) iteration since there never occurs a first row.

And THAT would probably thorroughly confuse even more people than my
explanation of it does.

Or, let's say you envision the sub-query building its own recursive set
before we get to the main query - this seems like a solution, but it
would fill up to infinity because you did not specify a limit or WHERE
clause inside the sub-query.

But, let's assume for a moment you did add a WHERE or LIMIT to avoid
filling the sub-query-recursed-set of rows to infinity, where does the
main recursive set build from?
It clearly has to accommodate all rows added by the sub-query recursive
set, and in your case there is no main recursive set (because you did
not FROM or JOIN the count_down table, which by definition stops this
query from being "recursive").

But again, let's assume for a moment you did add the count_down table to
the FROM/JOIN in the second select (the recursive part) also, then you
have 2 recursive sets being built, one for the sub query, and the
correct main query one. What will happen now is either one of the sets
will not be what you wanted, OR, they will feed each other into an
exponential growing set (depending on the nature of the JOIN you apply).

None of this is what we want from the recursive queries.

I guess it's much like recursion in programming, you have to be very
careful not to run into infinite loops or nonsense results, and for that
you have to have some strict rules. SQL solves this by not allowing a
dream in a dream.

Please note that I've only discussed some of the theory here, but there
might be other unrelated physical design limits in the sqlite code which
may or may not prevent it, and which the devs may or may not  overcome
eventually.

That said, if this is something you seriously hope to employ as a
mechanic for finding a more complex result from a recursive query - note
that you can daisy-chain recursive queries together to form nicely
complex results.
This simple example shows the basic idea, but you can also use any join
on them, filter from one another in the recursive parts, etc. There
really is no conceptual limit, so long as any recursive part doesn't
self-reference in a sub-part of it.

   -- SQLite version 3.24.0  [ Release: 2018-06-04 ]

WITH a(x) AS (
   SELECT 1 UNION ALL SELECT x+2 FROM a WHERE x < 3
), b(fx) AS (
   SELECT 1 UNION ALL SELECT fx*x FROM b,a LIMIT 30
)
SELECT * FROM b;


   --  fx
   -- ---
   --  1
   --  1
   --  3
   --  1
   --  3
   --  3
   --  9
   --  1
   --  3
   --  3
   --  9
   --  3
   --  9
   --  9
   --  27
   --  1
   --  3
   --  3
   --  9
   --  3
   --  9
   --  9
   --  27
   --  3
   --  9
   --  9
   --  27
   --  9
   --  27
   --  27

PS: Apologies, I know the descriptions above lack some simplistic
clarity, but I couldn't find the vocabulary for reducing it to more
succinct, yet well-defined, ideas.

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive references in subqueries

Lifepillar
On 19/07/2018 15:53, R Smith wrote:

>
> On 2018/07/19 2:32 PM, Christian Duta wrote:
>>
>> WITH RECURSIVE
>>   count_down(v) AS (
>>     SELECT 5
>>       UNION ALL
>>     SELECT cd.v - 1
>>     FROM (
>>       SELECT cd.v
>>       FROM count_down AS cd
>>     ) AS cd
>>     WHERE cd.v > 0
>>   )
>> SELECT * FROM count_down;
>>
>> Error: near line 1: recursive reference in a subquery: count_down
>>
>> What is the reasoning behind this restriction?
>> And more importantly: Are there plans to allow recursive references
>> inside of a subquery in a future release of SQLite?
>
> The problem is that there can be only one "builder" of the recursive set.
>
> In your example above, the full recursive set is not known at the time
> of first encountering the sub-query.
> i.e. do you expect it to have results on the first iteration?

The query above is perfectly defined. In fact, it works in PostgreSQL.
PostgreSQL's manual also has a very nice explanation of how recursive
queries are evaluated. The first step is to evaluate the non-recursive
term. In the example above that is 'select 5', which builds a working
table with one record. When the recursive term is evaluated the first
time, the current working table is used. So, to answer your question:
yes, after the first iteration, the result (of the recursive term) is
a table with one record containing the value 4. SQL's recursion is
iteration in disguise.

That said, the query above can be simplified as follows:

   with recursive count_down(v) as (
     select 5
     union all
     select n - 1 from count_down where n > 0
   )
   select * from count_down;

which is what the OP has likely done.

Life.

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive references in subqueries

R Smith-2
On 2018/07/19 10:23 PM, Lifepillar wrote:
> On 19/07/2018 15:53, R Smith wrote:
>>
>> In your example above, the full recursive set is not known at the
>> time of first encountering the sub-query.
>> i.e. do you expect it to have results on the first iteration?
>
> The query above is perfectly defined. In fact, it works in PostgreSQL.
> PostgreSQL's manual also has a very nice explanation of how recursive
> queries are evaluated.

Thank you for pointing out the obvious that I still managed to miss. :)

I guess my explanation got carried away in why multiple references is a
problem and not so much a sub-query reference. The mechanism of
sub-querying within a recursive query still disallows a second reference
to the recursive set in any way I imagine, and if it is referenced in a
sub-query like that, I imagine it would throw an error if you then also
refer to it in the main FROM (or any other JOIN).

In theory anyway. I have not checked this in Postgres, but I'm willing
to bet this alteration of the same query cannot prepare without error.
It is still perfectly defined, and the join doesn't affect the
calculation or theoretical outcome (it's basically a no-op), but its
mere presence should confuse any recursing algorithm, at least so I
hope, else I'll be eating my words. :)

WITH count_down(v) AS (
     SELECT 5
       UNION ALL
     SELECT cd.v - 1
       FROM count_down AS cd
       LEFT JOIN (
              SELECT a.v FROM count_down AS a
            ) AS dd ON dd.v = 0
     WHERE cd.v > 0
   )
SELECT * FROM count_down;



> That said, the query above can be simplified as follows:
>
>   with recursive count_down(v) as (
>     select 5
>     union all
>     select n - 1 from count_down where n > 0
>   )
>   select * from count_down;
>
> which is what the OP has likely done.

I think the OP tried something a bit more complex, and then tried to
reduce it to a simple example to post here, perhaps deceptively simple. 
However, it's still possible that his actual complex query might be
refined into such a simpler form.


Cheers,
Ryan

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive references in subqueries

Christian Duta
This post was updated on .
R Smith-2 wrote
> The query above is perfectly defined. In fact, it works in PostgreSQL.
> PostgreSQL's manual also has a very nice explanation of how recursive
> queries are evaluated.

The way PostgreSQL handles recursive queries was one of my motivations to
post about this.
PostgreSQL allows for recursive references inside subqueries like the one I
posted.


R Smith-2 wrote
>> That said, the query above can be simplified as follows:
>>
>>   with recursive count_down(v) as (
>>     select 5
>>     union all
>>     select n - 1 from count_down where n > 0
>>   )
>>   select * from count_down;
>>
>> which is what the OP has likely done.
>
> I think the OP tried something a bit more complex, and then tried to
> reduce it to a simple example to post here, perhaps deceptively simple. 
> However, it's still possible that his actual complex query might be
> refined into such a simpler form.

You're right, the queries I have in mind are complex. And readability would
greatly improve with a feature like recursive references inside subqueries.
Recursive queries are often difficult to read anyway, so having a feature
which improves readability is a *big* plus in my book.

But: My questions have more of a technical background than a practical one.
I try to figure out *why* SQLite decided to forbid a recursive reference be
placed inside a subquery.
Is there a technical reason? Or did the developer explicitly decide against
recursive references inside subqueries because of the SQL standard?

And of course: are there plans to allow for recursive references inside
subqueries?

Best regards,
Christian Duta



--
Sent from: http://sqlite.1065341.n5.nabble.com/
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Web draft problem

R Smith-2
The Web-site seems to have a bit of an error on the draft pages (which
may only be because of the draft pages and not matter at all, but I
thought I'd post it just in case it is something needing attention).

The steps leading to the error:

1 - Navigate to http://sqlite.org/draft/
(This redirects to http://sqlite.org/index.html)

2 - Make the "Search" box appear, type "window functions"  (Or anything
else that will get results), then press "Enter".

3 - The below message appears:


  Wapp Application Error

attempt to write a readonly database
     while executing
"db2 eval {
     PRAGMA synchronous=OFF;
     PRAGMA journal_mode=OFF;
     BEGIN;
       CREATE TABLE IF NOT EXISTS log(
         ip,                  -- I..."
     (procedure "search_add_log_entry" line 7)
     invoked from within
"search_add_log_entry $nRes"
     (procedure "searchresults" line 49)
     invoked from within
"$cmd"
     ("uplevel" body line 1)
     invoked from within
"uplevel {$cmd}"
     invoked from within
"time [list uplevel $script]"
     (procedure "ttime" line 2)
     invoked from within
"ttime {$cmd}"
     invoked from within
"db transaction {
     set t [ttime {$cmd}]
   }"
     (procedure "wapp-default" line 46)
     invoked from within
"wapp-default"


_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Web draft problem

Richard Hipp-3
On 7/20/18, R Smith <[hidden email]> wrote:
> The Web-site seems to have a bit of an error on the draft pages

Thanks for the report.  It is a missing chown in the script that syncs
from development.  Fixed now.
--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

META: polite plea to the clueful [Was: Web draft problem]

Ian Zimmerman-2
In reply to this post by R Smith-2
On 2018-07-20 17:51, R Smith wrote:

> The Web-site seems to have a bit of an error on the draft pages (which
> may only be because of the draft pages and not matter at all, but I
> thought I'd post it just in case it is something needing attention).

This was wholly unrelated to the post you replied to.  Please keep the
threading tidy by starting a new _thread_ (not just a new Subject) when
appropriate.  Thanks!

--
Please don't Cc: me privately on mailing lists and Usenet,
if you also post the followup to the list or newsgroup.
To reply privately _only_ on Usenet and on broken lists
which rewrite From, fetch the TXT record for no-use.mooo.com.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive references in subqueries

John Gillespie-2
In reply to this post by Christian Duta
Just to nitpick :

SQLite version 3.16.0 2016-11-04 19:09:39
Enter ".help" for usage hints.
Connected to a transient in-memory database.

sqlite> with recursive count_down(v) as (
   ...>     select 5
   ...>     union all
   ...>     select n - 1 from count_down where n > 0
   ...>   )
   ...>   select * from count_down;
Error: no such column: n


should have been  (replacing 'n' with 'v'):


sqlite> with recursive count_down(v) as (select 5 union all select v - 1
from count_down where v  > 0)
   ...>  select * from count_down;
5
4
3
2
1
0

John Gillespie

On 20 July 2018 at 14:14, Christian Duta <[hidden email]>
wrote:

> R Smith-2 wrote
> > The query above is perfectly defined. In fact, it works in PostgreSQL.
> > PostgreSQL's manual also has a very nice explanation of how recursive
> > queries are evaluated.
>
> The way PostgreSQL handles recursive queries was one of my motivations to
> post about this.
> PostgreSQL allows for recursive references inside subqueries like the one I
> posted.
>
>
> R Smith-2 wrote
> >> That said, the query above can be simplified as follows:
> >>
> >>   with recursive count_down(v) as (
> >>     select 5
> >>     union all
> >>     select n - 1 from count_down where n > 0
> >>   )
> >>   select * from count_down;
> >>
> >> which is what the OP has likely done.
> >
> > I think the OP tried something a bit more complex, and then tried to
> > reduce it to a simple example to post here, perhaps deceptively simple.
> > However, it's still possible that his actual complex query might be
> > refined into such a simpler form.
>
> You're right, the queries I have in mind are complex. And readability would
> greatly improve
> with a feature like recursive references inside subqueries.
> Recursive queries are often difficult to read anyway, so having a feature
> which improves
> readability is a *big* plus in my book.
>
> But: My questions have more of a technical background than a practical one.
> I try to figure out *why* SQLite decided to forbid a recursive reference be
> placed inside a subquery.
> Is there a technical reason? Or did the developer explicitly decide against
> recursive references inside
> subqueries because of the SQL standard?
>
> And of course: are there plans to allow for recursive references inside
> subqueries?
>
> Best regards,
> Christian Duta
>
>
>
> --
> Sent from: http://sqlite.1065341.n5.nabble.com/
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users