missing subquery flattening

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

missing subquery flattening

Mark Brand
Hi,

Shouldn't we expect subquery flattening to happen in V2 below?

Mark

CREATE TABLE X ( a PRIMARY KEY, b ) WITHOUT ROWID;
CREATE TABLE Y ( a PRIMARY KEY ) WITHOUT ROWID;
/*
WITH RECURSIVE Q AS (
     SELECT 1 a
     UNION ALL SELECT a + 1 FROM Q
     WHERE a < 100000
)
INSERT INTO X (a, b)
SELECT a, CHAR(a%255) FROM Q;
*/
-- flattening as expected
CREATE VIEW V1 AS
     SELECT * FROM X
     LEFT JOIN (
         SELECT X.* FROM X
     ) Z
     ON Z.a = X.a;

-- no flattening
CREATE VIEW V2 AS
     SELECT * FROM X
     LEFT JOIN (
         SELECT * FROM X
         LEFT JOIN Y ON Y.a = X.a
     ) Z
     ON Z.a = X.a;

-- manually flattened version of V2
CREATE VIEW V2_FLATTENED AS
     SELECT *
     FROM X
     LEFT JOIN X X2
        ON X2.a = X.a
     LEFT JOIN Y
        ON Y.a = X2.a;

SELECT sqlite_version();
EXPLAIN QUERY PLAN SELECT * FROM V1;
/*
0|0|0|SCAN TABLE X
0|1|1|SEARCH TABLE X USING PRIMARY KEY (a=?)
*/

EXPLAIN QUERY PLAN SELECT * FROM V2;
/*
1|0|0|SCAN TABLE X
1|1|1|SEARCH TABLE Y USING PRIMARY KEY (a=?)
0|0|0|SCAN TABLE X
0|1|1|SEARCH SUBQUERY 1 AS Z USING AUTOMATIC COVERING INDEX (a=?)
*/

EXPLAIN QUERY PLAN SELECT * FROM V2_FLATTENED;
/*
0|0|0|SCAN TABLE X
0|1|1|SEARCH TABLE X AS X2 USING PRIMARY KEY (a=?)
0|2|2|SEARCH TABLE Y USING PRIMARY KEY (a=?)
*/

_______________________________________________
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: missing subquery flattening

Clemens Ladisch
Mark Brand wrote:

> Shouldn't we expect subquery flattening to happen in V2 below?
>
> -- no flattening
> CREATE VIEW V2 AS
>     SELECT * FROM X
>     LEFT JOIN (
>         SELECT * FROM X
>         LEFT JOIN Y ON Y.a = X.a
>     ) Z
>     ON Z.a = X.a;
>
> -- manually flattened version of V2
> CREATE VIEW V2_FLATTENED AS
>     SELECT *
>     FROM X
>     LEFT JOIN X X2
>        ON X2.a = X.a
>     LEFT JOIN Y
>        ON Y.a = X2.a;

In the general case, left outer joins are not associative.  Apparently,
SQLite does not try to prove the opposite for special cases.


Regards,
Clemens
_______________________________________________
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: missing subquery flattening

Mark Brand


On 26/01/18 19:35, Clemens Ladisch wrote:

> Mark Brand wrote:
>> Shouldn't we expect subquery flattening to happen in V2 below?
>>
>> -- no flattening
>> CREATE VIEW V2 AS
>>      SELECT * FROM X
>>      LEFT JOIN (
>>          SELECT * FROM X
>>          LEFT JOIN Y ON Y.a = X.a
>>      ) Z
>>      ON Z.a = X.a;
>>
>> -- manually flattened version of V2
>> CREATE VIEW V2_FLATTENED AS
>>      SELECT *
>>      FROM X
>>      LEFT JOIN X X2
>>         ON X2.a = X.a
>>      LEFT JOIN Y
>>         ON Y.a = X2.a;
> In the general case, left outer joins are not associative.  Apparently,
> SQLite does not try to prove the opposite for special cases.
>

The simplified case above does not make obvious the usefulness of
flattening. A real world situation is where the right operand of a LEFT
JOIN is a handy reusable view with a LEFT JOIN whose left side provides
a useful index. For example:

    -- handy reusable view

         CREATE VIEW W AS
              SELECT X.*, X.cost + IFNULL(Y.fee, 0) price
              FROM X
              LEFT JOIN Y
                  ON Y.c = X.c;

         SELECT *
         FROM X
         LEFT JOIN W -- based on X
           ON W.a = X.a
         WHERE X.color = 'red';

W, by itself, might produce many more rows than the outer query and be
expensive. In cases like this, it's critical for performance that the
index of W be used for the LEFT JOIN in the outer query.

Without flattening, we have to go to some trouble to avoid using
otherwise handy logic-encapsulating views on the right side of a LEFT
JOIN. I've only recently realized this.

Would it make sense for sqlite to flatten this pattern? As far as I can
see, it satisfies all the conditions listed in
http://www.sqlite.org/optoverview.html#flattening.

Mark


_______________________________________________
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: missing subquery flattening

E.Pasma
Mark Brand wrote:

>
>
> On 26/01/18 19:35, Clemens Ladisch wrote:
>> Mark Brand wrote:
>>> Shouldn't we expect subquery flattening to happen in V2 below?
>>>
>>> -- no flattening
>>> CREATE VIEW V2 AS
>>>     SELECT * FROM X
>>>     LEFT JOIN (
>>>         SELECT * FROM X
>>>         LEFT JOIN Y ON Y.a = X.a
>>>     ) Z
>>>     ON Z.a = X.a;
>>>
>>> -- manually flattened version of V2
>>> CREATE VIEW V2_FLATTENED AS
>>>     SELECT *
>>>     FROM X
>>>     LEFT JOIN X X2
>>>        ON X2.a = X.a
>>>     LEFT JOIN Y
>>>        ON Y.a = X2.a;
>> In the general case, left outer joins are not associative.  
>> Apparently,
>> SQLite does not try to prove the opposite for special cases.
>>
>
> The simplified case above does not make obvious the usefulness of  
> flattening. A real world situation is where the right operand of a  
> LEFT JOIN is a handy reusable view with a LEFT JOIN whose left side  
> provides a useful index. For example:
>
>   -- handy reusable view
>
>         CREATE VIEW W AS
>              SELECT X.*, X.cost + IFNULL(Y.fee, 0) price
>              FROM X
>              LEFT JOIN Y
>                  ON Y.c = X.c;
>
>        SELECT *
>        FROM X
>        LEFT JOIN W -- based on X
>          ON W.a = X.a
>        WHERE X.color = 'red';
>
> W, by itself, might produce many more rows than the outer query and  
> be expensive. In cases like this, it's critical for performance that  
> the index of W be used for the LEFT JOIN in the outer query.
>
> Without flattening, we have to go to some trouble to avoid using  
> otherwise handy logic-encapsulating views on the right side of a  
> LEFT JOIN. I've only recently realized this.
>
> Would it make sense for sqlite to flatten this pattern? As far as I  
> can see, it satisfies all the conditions listed in http://www.sqlite.org/optoverview.html#flattening 
> .
>
> Mark
>

Hello, may be I'm wrong or the documentation is wrong:
If the subquery is not the right operand of a LEFT JOIN then
the subquery may not be a join, and
the FROM clause of the subquery may not contain a virtual table, and
the outer query may not be an aggregate.

The "not" in the first line does not belong there?
Thanks.



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