Quantcast

Optimization opportunity

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Optimization opportunity

Wolfgang Enzinger
Hello,

given the following:

------------------------

CREATE TABLE x(
  pk INTEGER PRIMARY KEY,
  description TEXT
);

CREATE TABLE y(
  fk INTEGER REFERENCES x(pk),
  flags INTEGER
);

CREATE INDEX yy ON y(fk);

CREATE VIEW z AS SELECT
  fk,
  (flags&1) AS odd,
  (flags&2)>>1 AS even,
  (flags&4)>>2 AS prime
  FROM y;

INSERT INTO x(pk,description) VALUES
  (1,'one'),(2,'two'),(3,'three'),(4,'four');

INSERT INTO y(fk,flags) VALUES (1,1|0|0),(2,0|2|4),(3,1|0|4),(4,0|2|0);

------------------------

Now using the VIEW z in a JOIN results in a full table scan on TABLE y
despite a WHERE clause and an appropriate INDEX:

EXPLAIN QUERY PLAN SELECT x.pk,z.odd,z.even,z.prime
FROM x LEFT JOIN z ON x.pk=z.fk WHERE x.pk=2;
1|0|0|SCAN TABLE y
0|0|0|SEARCH TABLE x USING INTEGER PRIMARY KEY (rowid=?)
0|1|1|SCAN SUBQUERY 1

Bypassing the VIEW however uses INDEX yy:

EXPLAIN QUERY PLAN
SELECT x.pk,(y.flags&1) AS odd,(y.flags&2)>>1 AS even,(y.flags&4)>>2 AS
prime FROM x LEFT JOIN y ON x.pk=y.fk WHERE x.pk=2;
0|0|0|SEARCH TABLE x USING INTEGER PRIMARY KEY (rowid=?)
0|1|1|SEARCH TABLE y USING INDEX yy (fk=?)

Unless I'm missing something, I think there is a potential optimization
opportunity.

Identical results with SQLite versions 3.13, 3.17 and 3.18.

Cheers, Wolfgang

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

Re: Optimization opportunity

Domingo Alvarez Duarte
Hello !

Maybe this problem would be the reason of getting bad query plans when
joining views too.

Cheers !


On 14/04/17 08:03, Wolfgang Enzinger wrote:

> Hello,
>
> given the following:
>
> ------------------------
>
> CREATE TABLE x(
>    pk INTEGER PRIMARY KEY,
>    description TEXT
> );
>
> CREATE TABLE y(
>    fk INTEGER REFERENCES x(pk),
>    flags INTEGER
> );
>
> CREATE INDEX yy ON y(fk);
>
> CREATE VIEW z AS SELECT
>    fk,
>    (flags&1) AS odd,
>    (flags&2)>>1 AS even,
>    (flags&4)>>2 AS prime
>    FROM y;
>
> INSERT INTO x(pk,description) VALUES
>    (1,'one'),(2,'two'),(3,'three'),(4,'four');
>
> INSERT INTO y(fk,flags) VALUES (1,1|0|0),(2,0|2|4),(3,1|0|4),(4,0|2|0);
>
> ------------------------
>
> Now using the VIEW z in a JOIN results in a full table scan on TABLE y
> despite a WHERE clause and an appropriate INDEX:
>
> EXPLAIN QUERY PLAN SELECT x.pk,z.odd,z.even,z.prime
> FROM x LEFT JOIN z ON x.pk=z.fk WHERE x.pk=2;
> 1|0|0|SCAN TABLE y
> 0|0|0|SEARCH TABLE x USING INTEGER PRIMARY KEY (rowid=?)
> 0|1|1|SCAN SUBQUERY 1
>
> Bypassing the VIEW however uses INDEX yy:
>
> EXPLAIN QUERY PLAN
> SELECT x.pk,(y.flags&1) AS odd,(y.flags&2)>>1 AS even,(y.flags&4)>>2 AS
> prime FROM x LEFT JOIN y ON x.pk=y.fk WHERE x.pk=2;
> 0|0|0|SEARCH TABLE x USING INTEGER PRIMARY KEY (rowid=?)
> 0|1|1|SEARCH TABLE y USING INDEX yy (fk=?)
>
> Unless I'm missing something, I think there is a potential optimization
> opportunity.
>
> Identical results with SQLite versions 3.13, 3.17 and 3.18.
>
> Cheers, Wolfgang
>
> _______________________________________________
> 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
|  
Report Content as Inappropriate

Re: Optimization opportunity

Richard Hipp-3
In reply to this post by Wolfgang Enzinger
On 4/14/17, Wolfgang Enzinger <[hidden email]> wrote:

>
> CREATE VIEW z AS SELECT
>   fk,
>   (flags&1) AS odd,
>   (flags&2)>>1 AS even,
>   (flags&4)>>2 AS prime
>   FROM y;
>
> Now using the VIEW z in a JOIN results in a full table scan on TABLE y
> despite a WHERE clause and an appropriate INDEX:
>
> EXPLAIN QUERY PLAN SELECT x.pk,z.odd,z.even,z.prime
> FROM x LEFT JOIN z ON x.pk=z.fk WHERE x.pk=2;
>
> Bypassing the VIEW however uses INDEX yy:
>
> EXPLAIN QUERY PLAN
> SELECT x.pk,(y.flags&1) AS odd,(y.flags&2)>>1 AS even,(y.flags&4)>>2 AS
> prime FROM x LEFT JOIN y ON x.pk=y.fk WHERE x.pk=2;
>

Performing this rewrite of a view into a simple LEFT JOIN is trickier
than it seems at first glance.  The rewrite works for the example you
provide.  But subtle changes to the view can make the rewrite invalid.
For example:

CREATE VIEW z AS SELECT
   fk,
  coalesce(flags&1,0) AS odd,  -- Added coalesce()
  (flags&2)>>1 AS even,
  (flags&4)>>2 AS prime
  FROM y;

The addition of the coalesce() function on one of the result columns
of the view means that a transformation such as you suggest will give
a different (and incorrect) answer.  This is just one of many examples
of the subtle pitfalls involved in trying to convert a LEFT JOIN into
a form that can make better use of indexes.

--
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
|  
Report Content as Inappropriate

Re: Optimization opportunity

Wolfgang Enzinger
Am Fri, 14 Apr 2017 10:59:25 -0400 schrieb Richard Hipp:

> Performing this rewrite of a view into a simple LEFT JOIN is trickier
> than it seems at first glance.  The rewrite works for the example you
> provide.  But subtle changes to the view can make the rewrite invalid.
> For example:
>
> CREATE VIEW z AS SELECT
>    fk,
>   coalesce(flags&1,0) AS odd,  -- Added coalesce()
>   (flags&2)>>1 AS even,
>   (flags&4)>>2 AS prime
>   FROM y;
>
> The addition of the coalesce() function on one of the result columns
> of the view means that a transformation such as you suggest will give
> a different (and incorrect) answer.  This is just one of many examples
> of the subtle pitfalls involved in trying to convert a LEFT JOIN into
> a form that can make better use of indexes.

Thank you Richard. I have to admit that it took me quite a while and also
reading the comment for check-in [1838a59c] several times to really
understand your explanation. Duh, that's tricky indeed!

Wolfgang

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

Re: Optimization opportunity

Richard Hipp-3
On 4/14/17, Wolfgang Enzinger <[hidden email]> wrote:
>
> Thank you Richard. I have to admit that it took me quite a while and also
> reading the comment for check-in [1838a59c] several times to really
> understand your explanation. Duh, that's tricky indeed!
>

But I've spent Good Friday working around it.  Please try using the
tip of the left-join-view branch
(https://www.sqlite.org/src/timeline?c=left-join-view) and let me know
if that version works better for you.  After some additional testing,
this optimization will likely be merge to trunk and appear in the next
release.  Your beta-testing is important - Thanks.

--
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
|  
Report Content as Inappropriate

Re: Optimization opportunity

Wolfgang Enzinger
Am Fri, 14 Apr 2017 15:14:12 -0400 schrieb Richard Hipp:

> But I've spent Good Friday working around it.

A thousand thanks! :-)

> Please try using the tip of the left-join-view branch
> (https://www.sqlite.org/src/timeline?c=left-join-view) and let me know
> if that version works better for you.  After some additional testing,
> this optimization will likely be merge to trunk and appear in the next
> release.  Your beta-testing is important - Thanks.

Sadly my C skills are just good enough to compile the amalgamation. But as
soon as the beta amalgamation will be available, I'll test it intensely,
promised.

Thanks again & happy Easter! :-)

Wolfgang

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

Re: Optimization opportunity

Wolfgang Enzinger
In reply to this post by Richard Hipp-3
Am Fri, 14 Apr 2017 15:14:12 -0400 schrieb Richard Hipp:

> On 4/14/17, Wolfgang Enzinger <[hidden email]> wrote:
>>
>> Thank you Richard. I have to admit that it took me quite a while and also
>> reading the comment for check-in [1838a59c] several times to really
>> understand your explanation. Duh, that's tricky indeed!
>>
>
> But I've spent Good Friday working around it.  Please try using the
> tip of the left-join-view branch
> (https://www.sqlite.org/src/timeline?c=left-join-view) and let me know
> if that version works better for you.  After some additional testing,
> this optimization will likely be merge to trunk and appear in the next
> release.  Your beta-testing is important - Thanks.

Tested now with sqlite-snapshot-201705020130. Excellent! The query plan no
longer shows any full table scan, and a specific query in my project runs ~
1 ms. now - vs. 11-12 sec. using version 3.18. Great enhancement, thank
you!

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