Bug in 3.25.2 (RECURSIVE CTE + window function)

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

Bug in 3.25.2 (RECURSIVE CTE + window function)

Щекин Ярослав
Hello.

Here's the self-contained test case:

WITH t(id, parent) AS (
SELECT CAST(1 AS INT), CAST(NULL AS INT)
UNION ALL
SELECT 2, NULL
UNION ALL
SELECT 3, 1
UNION ALL
SELECT 4, 1
UNION ALL
SELECT 5, 2
UNION ALL
SELECT 6, 2
), q AS (
SELECT t.*, ROW_NUMBER() OVER (ORDER BY t.id) AS rn
  FROM t
 WHERE parent IS NULL
 UNION ALL
SELECT t.*, ROW_NUMBER() OVER (ORDER BY t.id) AS rn
  FROM q
  JOIN t
    ON t.parent = q.id
)
SELECT *
  FROM q;

Results in segmentation fault.
(I also wanted to thank [Arfrever] (in #sqlite IRC) for testing / confirmation.)

-- 
WBR, Yaroslav Schekin.

_______________________________________________
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: Bug in 3.25.2 (RECURSIVE CTE + window function)

Richard Hipp-3
Thanks for the report and test case.  Now fixed on trunk and on branch-3.25.

On 9/25/18, Щекин Ярослав <[hidden email]> wrote:

> Hello.
>
> Here's the self-contained test case:
>
> WITH t(id, parent) AS (
> SELECT CAST(1 AS INT), CAST(NULL AS INT)
> UNION ALL
> SELECT 2, NULL
> UNION ALL
> SELECT 3, 1
> UNION ALL
> SELECT 4, 1
> UNION ALL
> SELECT 5, 2
> UNION ALL
> SELECT 6, 2
> ), q AS (
> SELECT t.*, ROW_NUMBER() OVER (ORDER BY t.id) AS rn
>   FROM t
>  WHERE parent IS NULL
>  UNION ALL
> SELECT t.*, ROW_NUMBER() OVER (ORDER BY t.id) AS rn
>   FROM q
>   JOIN t
>     ON t.parent = q.id
> )
> SELECT *
>   FROM q;
>
> Results in segmentation fault.
> (I also wanted to thank [Arfrever] (in #sqlite IRC) for testing /
> confirmation.)
>
> --
> WBR, Yaroslav Schekin.
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>


--
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: Bug in 3.25.2 (RECURSIVE CTE + window function)

Nicolas Roy-Renaud
I've been dealing with occasional segfaults on one of my applications when running a similar query, except even on SQLite 3.26, the safeguard wouldn't trigger.

Running the SQL query specified in the bug report description from the tracker (https://www.sqlite.org/src/tktview?name=e8275b415a)
now yields either "Error: cannot use window functions in recursive queries" or "Error: recursive reference in a subquery: q" if I try to nest it.

Below is the query in question, modified to work as a self-contained test case, but I have not managed to figure out how to reduce it further. The query comes from a Markov chain project.
With the data contained in the CTE for chain, this query should print "hello" and "world" 10 times, but crashes after 3.
Alternatively, it could also not run at all and simply return an error, as seems to be the expected behavior for thee queries since SQLite 3.25.

> WITH RECURSIVE chain(link1, link2, n) AS (VALUES ('hello', 'world',
> 1), ('world', 'hello', 1)), markov(last_word, current_word,
> random_const) AS ( VALUES('hello', 'world', ABS(random()) /
> CAST(0x7FFFFFFFFFFFFFFF AS real)) UNION ALL SELECT
> markov.current_word, ( SELECT link2 FROM ( SELECT link1, link2, n,
> SUM(n) OVER (PARTITION BY link1 ROWS UNBOUNDED PRECEDING) AS rank,
> SUM(n) OVER (PARTITION BY link1) * markov.random_const AS roll FROM
> chain WHERE link1 = markov.current_word ) t WHERE roll <= rank LIMIT 1
> ) AS next_word, ABS(random()) / CAST(0x7FFFFFFFFFFFFFFF AS real) AS
> random_const FROM markov WHERE current_word <> ' ' ) SELECT last_word
> FROM markov LIMIT 10;

I've had no issue running that same query on PostgreSQL, and I have in fact had it run to completion multiple times on SQLite 3.26 as well, with very large datasets.

--
Nicolas Roy-Renaud


Richard Hipp Thu, 27 Sep 2018 06:13:36 -0700

> Thanks for the report and test case.  Now fixed on trunk and on branch-3.25.
> On 9/25/18, Щекин Ярослав <[hidden email]> wrote:
> > Hello.
> >
> > Here's the self-contained test case:
> >
> > WITH t(id, parent) AS (
> > SELECT CAST(1 AS INT), CAST(NULL AS INT)
> > UNION ALL
> > SELECT 2, NULL
> > UNION ALL
> > SELECT 3, 1
> > UNION ALL
> > SELECT 4, 1
> > UNION ALL
> > SELECT 5, 2
> > UNION ALL
> > SELECT 6, 2
> > ), q AS (
> > SELECT t.*, ROW_NUMBER() OVER (ORDER BY t.id) AS rn
> >   FROM t
> >  WHERE parent IS NULL
> >  UNION ALL
> > SELECT t.*, ROW_NUMBER() OVER (ORDER BY t.id) AS rn
> >   FROM q
> >   JOIN t
> >     ON t.parent = q.id
> > )
> > SELECT *
> >   FROM q;
> >
> > Results in segmentation fault.
> > (I also wanted to thank [Arfrever] (in #sqlite IRC) for testing /
> > confirmation.)
> >
> > --
> > WBR, Yaroslav Schekin.
> >
> > _______________________________________________
> > sqlite-users mailing list
> > [hidden email]
> > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> >
>
>
> --
> D. Richard Hipp
> [hidden email]
> _______________________________________________
> 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
Reply | Threaded
Open this post in threaded view
|

Re: Bug in 3.25.2 (RECURSIVE CTE + window function)

Dan Kennedy-4
On 12/30/2018 02:41 PM, Nicolas Roy-Renaud wrote:

> I've been dealing with occasional segfaults on one of my applications
> when running a similar query, except even on SQLite 3.26, the safeguard
> wouldn't trigger.
>
> Running the SQL query specified in the bug report description from the
> tracker (https://www.sqlite.org/src/tktview?name=e8275b415a)
> now yields either "Error: cannot use window functions in recursive
> queries" or "Error: recursive reference in a subquery: q" if I try to
> nest it.
>
> Below is the query in question, modified to work as a self-contained
> test case, but I have not managed to figure out how to reduce it
> further. The query comes from a Markov chain project.
> With the data contained in the CTE for chain, this query should print
> "hello" and "world" 10 times, but crashes after 3.
> Alternatively, it could also not run at all and simply return an error,
> as seems to be the expected behavior for thee queries since SQLite 3.25.



Thanks for reporting this. No fix yet, but a further reduction here:

   https://sqlite.org/src/tktview/d0866b26f83e9c55e30d

I think this probably should work (not return the error message).
Although technically there are window functions within a recursive
sub-query, they don't operate on the recursively generated dataset
(they're in a subquery) so I don't think the restriction applies.

Dan.



>
>> WITH RECURSIVE chain(link1, link2, n) AS (VALUES ('hello', 'world',
>> 1), ('world', 'hello', 1)), markov(last_word, current_word,
>> random_const) AS ( VALUES('hello', 'world', ABS(random()) /
>> CAST(0x7FFFFFFFFFFFFFFF AS real)) UNION ALL SELECT
>> markov.current_word, ( SELECT link2 FROM ( SELECT link1, link2, n,
>> SUM(n) OVER (PARTITION BY link1 ROWS UNBOUNDED PRECEDING) AS rank,
>> SUM(n) OVER (PARTITION BY link1) * markov.random_const AS roll FROM
>> chain WHERE link1 = markov.current_word ) t WHERE roll <= rank LIMIT 1
>> ) AS next_word, ABS(random()) / CAST(0x7FFFFFFFFFFFFFFF AS real) AS
>> random_const FROM markov WHERE current_word <> ' ' ) SELECT last_word
>> FROM markov LIMIT 10;
>
> I've had no issue running that same query on PostgreSQL, and I have in
> fact had it run to completion multiple times on SQLite 3.26 as well,
> with very large datasets.
>
> --
> Nicolas Roy-Renaud
>
>
> Richard Hipp Thu, 27 Sep 2018 06:13:36 -0700
>> Thanks for the report and test case.  Now fixed on trunk and on
>> branch-3.25.
>> On 9/25/18, Щекин Ярослав <[hidden email]> wrote:
>> > Hello.
>> >
>> > Here's the self-contained test case:
>> >
>> > WITH t(id, parent) AS (
>> > SELECT CAST(1 AS INT), CAST(NULL AS INT)
>> > UNION ALL
>> > SELECT 2, NULL
>> > UNION ALL
>> > SELECT 3, 1
>> > UNION ALL
>> > SELECT 4, 1
>> > UNION ALL
>> > SELECT 5, 2
>> > UNION ALL
>> > SELECT 6, 2
>> > ), q AS (
>> > SELECT t.*, ROW_NUMBER() OVER (ORDER BY t.id) AS rn
>> >   FROM t
>> >  WHERE parent IS NULL
>> >  UNION ALL
>> > SELECT t.*, ROW_NUMBER() OVER (ORDER BY t.id) AS rn
>> >   FROM q
>> >   JOIN t
>> >     ON t.parent = q.id
>> > )
>> > SELECT *
>> >   FROM q;
>> >
>> > Results in segmentation fault.
>> > (I also wanted to thank [Arfrever] (in #sqlite IRC) for testing /
>> > confirmation.)
>> >
>> > --
>> > WBR, Yaroslav Schekin.
>> >
>> > _______________________________________________
>> > sqlite-users mailing list
>> > [hidden email]
>> > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>> >
>>
>>
>> --
>> D. Richard Hipp
>> [hidden email]
>> _______________________________________________
>> 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

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