Bug due to left join strength reduction optimization?

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

Bug due to left join strength reduction optimization?

Danny
The result of the query described below changed (became incorrect, I
believe) with the addition of the left join strength reduction
optimization in revision dd568, and remains that way in trunk (2c876, at
the time of writing).

Consider the following statements:

```
CREATE TABLE tab (id INT);
INSERT INTO tab VALUES (1);
SELECT tab2.id IS NOT NULL AS c
  FROM tab LEFT JOIN tab AS tab2 ON 0
  WHERE c = 0;
```

As of revision a8dfe (parent of dd568), the SELECT outputs one row with
one column containing 0, as I would expect. At dd568 (and at trunk),
however, it outputs no rows.

This looks similar in spirit to an existing, fixed bug [1], but the
output for the test case there has gone back to its pre-LJSRO value at
some point since dd568, while this one has not.

Thanks,
Danny

[1] https://www.sqlite.org/src/tktview/1e39b966ae9ee7394334
_______________________________________________
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 due to left join strength reduction optimization?

Keith Medcalf

Fascinating.  From the same source table see also:

sqlite> select tab2.id is not null as c from tab left join tab as tab2 on 0 where c = 0;
QUERY PLAN
|--SCAN TABLE tab AS tab2 (~983040 rows)
`--SCAN TABLE tab (~1048576 rows)

sqlite> select tab2.id is not null as c from tab left join tab as tab2 on 0 where c is 0;
QUERY PLAN
|--SCAN TABLE tab (~1048576 rows)
`--SCAN TABLE tab AS tab2 (~917504 rows)
0

---
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.

>-----Original Message-----
>From: sqlite-users [mailto:sqlite-users-
>[hidden email]] On Behalf Of Danny
>Sent: Monday, 4 February, 2019 23:24
>To: [hidden email]
>Subject: [sqlite] Bug due to left join strength reduction
>optimization?
>
>The result of the query described below changed (became incorrect, I
>believe) with the addition of the left join strength reduction
>optimization in revision dd568, and remains that way in trunk (2c876,
>at
>the time of writing).
>
>Consider the following statements:
>
>```
>CREATE TABLE tab (id INT);
>INSERT INTO tab VALUES (1);
>SELECT tab2.id IS NOT NULL AS c
>  FROM tab LEFT JOIN tab AS tab2 ON 0
>  WHERE c = 0;
>```
>
>As of revision a8dfe (parent of dd568), the SELECT outputs one row
>with
>one column containing 0, as I would expect. At dd568 (and at trunk),
>however, it outputs no rows.
>
>This looks similar in spirit to an existing, fixed bug [1], but the
>output for the test case there has gone back to its pre-LJSRO value
>at
>some point since dd568, while this one has not.
>
>Thanks,
>Danny
>
>[1] https://www.sqlite.org/src/tktview/1e39b966ae9ee7394334
>_______________________________________________
>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 due to left join strength reduction optimization?

Dominique Devienne
On Tue, Feb 5, 2019 at 7:47 AM Keith Medcalf <[hidden email]> wrote:

> sqlite> select ... from tab left join tab as tab2 on 0 ...
>

Can someone please educate me on this {{ on 0 }} join "condition" ?

I'm not following what the intended meaning is... Must have one, since OP
"expects 1 row with one column containing 0", despite a table with a single
1 row.

Thanks, --DD
_______________________________________________
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 due to left join strength reduction optimization?

R Smith-2


On 2019/02/05 10:13 AM, Dominique Devienne wrote:
> On Tue, Feb 5, 2019 at 7:47 AM Keith Medcalf <[hidden email]> wrote:
>
>> sqlite> select ... from tab left join tab as tab2 on 0 ...
>>
> Can someone please educate me on this {{ on 0 }} join "condition" ?
>
> I'm not following what the intended meaning is... Must have one, since OP
> "expects 1 row with one column containing 0", despite a table with a single
> 1 row.

"on 0" is similar to "on FALSE" which simply means "don't join
anything... ever" but since it is a left-join, it will still produce any
rows forthcoming from the initial FROM table, /IF/ it clears the WHERE
clause, which in this case it should because the WHERE condition is one
that should always evaluate to TRUE.

If no rows are left-joined, the joined row-values can never have any
other value than NULL, so the "tab2.id IS NOT NULL" must by definition
always be FALSE (aka "0") - Which in turn means the WHERE condition of
"c = 0" must always evaluate to TRUE, which means the 1 row from the
base table MUST be output.

@OP:
As a matter of interest - what happens when the aliasing is taken out of
the loop and the query changes to:

CREATE TABLE tab (id INT);
INSERT INTO tab VALUES (1);
SELECT 1
   FROM tab LEFT JOIN tab AS tab2 ON 0
   WHERE (tab2.id IS NOT NULL) = 0
;

I don't have that broken version currently, so can't test on my side, but I'm assuming your example is minimal and it works if anything is changed, which means it's likely the fault of the logic that checks the aliased value (unless the above query still fails, in which case my assumption is wrong and the above is a better test case).


_______________________________________________
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: [EXTERNAL] Re: Bug due to left join strength reduction optimization?

Hick Gunter
In reply to this post by Dominique Devienne
We have an input table named tab with a single row whose sole column named id as a value of 1.
This table is joined to itself in a left join. The cartesian product would be

tab.id  tab2.id
1       1

The clause ON 0 evaluates to FALSE, so the row is eliminated from the result set.
LEFT JOIN processing requires that the result set be extended by a special row for each lhs row, giving

tab.id  tab2.id
1       NULL

From this the result expression evaluates to (NULL IS NOT NULL) which gives the number 0.
Then the WHERE clause is evaluated to (0 = 0) which gives TRUE.

This yields a single result row with a value 0

Changing the order of the tables gives

tab2.id tab.id
1       1

Which devolves into

tab2.id tab.id
1       NULL

Yielding c (1 IS NOT NULL) which gives the number 1
Which means the row is excluded by the WHERE clause

No output

Testing of R.Smiths changed query reveals that the difference is caused by different handling of the equality and the IS operator.

asql> explain query plan select 1 from tab left join tab as tab2 on 0 where (tab2.id IS NOT NULL) = 0;
id    parent         notu  deta
----  -------------  ----  ----
4     0              0     SCAN TABLE tab AS tab2
11    0              0     SCAN TABLE tab
asql> explain query plan select 1 from tab left join tab as tab2 on 0 where (tab2.id IS NOT NULL) is 0;
id    parent         notu  deta
----  -------------  ----  ----
3     0              0     SCAN TABLE tab
5     0              0     SCAN TABLE tab AS tab2


-----Urspr√ľngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Dominique Devienne
Gesendet: Dienstag, 05. Februar 2019 09:14
An: SQLite mailing list <[hidden email]>
Betreff: [EXTERNAL] Re: [sqlite] Bug due to left join strength reduction optimization?

On Tue, Feb 5, 2019 at 7:47 AM Keith Medcalf <[hidden email]> wrote:

> sqlite> select ... from tab left join tab as tab2 on 0 ...
>

Can someone please educate me on this {{ on 0 }} join "condition" ?

I'm not following what the intended meaning is... Must have one, since OP "expects 1 row with one column containing 0", despite a table with a single
1 row.

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


___________________________________________
 Gunter Hick | Software Engineer | Scientific Games International GmbH | Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43 1 80100 - 0

May be privileged. May be confidential. Please delete if not the addressee.
_______________________________________________
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 due to left join strength reduction optimization?

Danny
In reply to this post by R Smith-2
R Smith <[hidden email]> writes:

> As a matter of interest - what happens when the aliasing is taken out of
> the loop and the query changes to:
>
> CREATE TABLE tab (id INT);
> INSERT INTO tab VALUES (1);
> SELECT 1
>    FROM tab LEFT JOIN tab AS tab2 ON 0
>    WHERE (tab2.id IS NOT NULL) = 0
> ;
>
> I don't have that broken version currently, so can't test on my side, but I'm assuming your example is minimal and it works if anything is changed, which means it's likely the fault of the logic that checks the aliased value (unless the above query still fails, in which case my assumption is wrong and the above is a better test case).

In fact, that returns the incorrect empty result as well; I suppose I
didn't manage to minimize all the way. Good catch!

Replacing the end of the WHERE clause with "is 0" still returns one row,
as in Keith's example, while "= 0", "= false", and "is false" all give
no rows.

Danny
_______________________________________________
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 due to left join strength reduction optimization?

Danny
In reply to this post by Danny
This has been fixed by revision d840e. Thanks for the quick response, drh!

Danny
_______________________________________________
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 due to left join strength reduction optimization?

Richard Hipp-3
On 2/6/19, Danny <[hidden email]> wrote:
> This has been fixed by revision d840e. Thanks for the quick response, drh!

Just to be clear:  Dan found the fix.  I merely checked it in.

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