Query optimizer and recursive common table expressions

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Query optimizer and recursive common table expressions

Shane Dev
Hi,

This simple recursive common table expression returns all integers from 1
to 3 as expected -

sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt
limit 3) select * from cnt where x;
x
1
2
3
sqlite>

If the LIMIT constraint is moved from the compound SELECT to the subsequent
SELECT, it works the same -

sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt)
select * from cnt where x limit 3;
x
1
2
3
sqlite>

If the LIMIT constraint is replaced with a WHERE constraint in the compound
SELECT, it still works the same -

sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt
where x < 3) select * from cnt;
x
1
2
3
sqlite>

However if the WHERE constraint is moved from the compound SELECT to the
subsequent SELECT and adjusted slightly, it selects correct results but
then hangs indefinitely -

sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt)
select * from cnt where x <= 3;
x
1
2
3
[no sqlite> prompt, CPU utilization 25%]

I assume sqlite is recursively adding rows to the queue without considering
that the subsequent SELECT only needs the first 3 of them.

Can we conclude the query planner is unable to optimize the compound
SELECT (the part in brackets) based on the WHERE constraint of the
subsequent SELECT statement?
_______________________________________________
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: Query optimizer and recursive common table expressions

Shane Dev
I have just spotted a couple of typos in my email below. The first two
common table expressions should have been as follows -

with recursive cnt(x) as (select 1 union all select x+1 from cnt limit 3)
select * from cnt;
with recursive cnt(x) as (select 1 union all select x+1 from cnt) select *
from cnt limit 3;

On 3 January 2018 at 23:24, Shane Dev <[hidden email]> wrote:

> Hi,
>
> This simple recursive common table expression returns all integers from 1
> to 3 as expected -
>
> sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt
> limit 3) select * from cnt where x;
> x
> 1
> 2
> 3
> sqlite>
>
> If the LIMIT constraint is moved from the compound SELECT to the
> subsequent SELECT, it works the same -
>
> sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt)
> select * from cnt where x limit 3;
> x
> 1
> 2
> 3
> sqlite>
>
> If the LIMIT constraint is replaced with a WHERE constraint in the
> compound SELECT, it still works the same -
>
> sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt
> where x < 3) select * from cnt;
> x
> 1
> 2
> 3
> sqlite>
>
> However if the WHERE constraint is moved from the compound SELECT to the
> subsequent SELECT and adjusted slightly, it selects correct results but
> then hangs indefinitely -
>
> sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt)
> select * from cnt where x <= 3;
> x
> 1
> 2
> 3
> [no sqlite> prompt, CPU utilization 25%]
>
> I assume sqlite is recursively adding rows to the queue without
> considering that the subsequent SELECT only needs the first 3 of them.
>
> Can we conclude the query planner is unable to optimize the compound
> SELECT (the part in brackets) based on the WHERE constraint of the
> subsequent SELECT statement?
>
_______________________________________________
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: Query optimizer and recursive common table expressions

Richard Hipp-3
In reply to this post by Shane Dev
On 1/3/18, Shane Dev <[hidden email]> wrote:
>
> sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt)
> select * from cnt where x <= 3;
> [no sqlite> prompt, CPU utilization 25%]
>
> I assume sqlite is recursively adding rows to the queue without considering
> that the subsequent SELECT only needs the first 3 of them.

No, it is continuing to search for rows for which x<=3.  The query
planner does not know enough algebra to figure out that that will
never happen again after the first three rows.
--
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
|

Re: Query optimizer and recursive common table expressions

R Smith-2
On 2018/01/04 12:36 AM, Richard Hipp wrote:

> On 1/3/18, Shane Dev <[hidden email]> wrote:
>> sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt)
>> select * from cnt where x <= 3;
>> [no sqlite> prompt, CPU utilization 25%]
>>
>> I assume sqlite is recursively adding rows to the queue without considering
>> that the subsequent SELECT only needs the first 3 of them.
> No, it is continuing to search for rows for which x<=3.  The query
> planner does not know enough algebra to figure out that that will
> never happen again after the first three rows.

Not to mention that if you wait several years, depending on your
processor/compiler, the integer 64 value might wrap around and x<=3
might become true once more, producing rows again....  :)


_______________________________________________
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: Query optimizer and recursive common table expressions

Cezary H. Noweta
Hello,

On 2018-01-04 01:53, R Smith wrote:
> Not to mention that if you wait several years, depending on your
> processor/compiler, the integer 64 value might wrap around and x<=3
> might become true once more, producing rows again....  :)
Unfortunately, it will be stuck when int becomes double (at
9223372036854775808 -- still much time :-).

``We are programmers and responsible for programming. -O999999 is
responsible for thinking. Who in the hell implemented -O when there had
not been -O?'' :-)

-- best regards

Cezary H. Noweta
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users