[BUG; 3.7.13] ANALYZE leads to a wrong query plan for RTrees

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

[BUG; 3.7.13] ANALYZE leads to a wrong query plan for RTrees

mailing lists
This is an example that the ANALYZE command leads to a wrong query plan for RTrees:

CREATE TABLE A (ID INTEGER PRIMARY KEY, Latitude, Longitude, Altitude);
CREATE VIRTUAL TABLE B USING RTree (ID, FromLatitude, TillLatitude, FromLongitude,TillLongitude);
INSERT INTO A VALUES(1,0,0,0);
INSERT INTO A VALUES(2,1,1,1);
INSERT INTO B VALUES(1,0,0,0,0);
INSERT INTO B VALUES(2,1,1,1,1);

Without an analyze command the query plan seems to be OK:
EXPLAIN QUERY PLAN SELECT COUNT(*) FROM A,B WHERE (A.ID=B.ID) AND (B.FromLongitude > 5) AND (B.TillLongitude < 10);
0|0|1|SCAN TABLE B VIRTUAL TABLE INDEX 2:EcCd (~0 rows)
0|1|0|SEARCH TABLE A USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)

After running the ANALYZE command the query plan has changed and the result is a worse query plan than before:
ANALYZE;
EXPLAIN QUERY PLAN SELECT COUNT(*) FROM A,B WHERE (A.ID=B.ID) AND (B.FromLongitude > 5) AND (B.TillLongitude < 10);
0|0|0|SCAN TABLE A (~2 rows)
0|1|1|SCAN TABLE B VIRTUAL TABLE INDEX 1: (~0 rows)

Regards,
Hartwig

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

Re: [BUG; 3.7.13] ANALYZE leads to a wrong query plan for RTrees

Clemens Ladisch
skywind mailing lists wrote:

> This is an example that the ANALYZE command leads to a wrong query plan for RTrees:
>
> CREATE TABLE A (ID INTEGER PRIMARY KEY, Latitude, Longitude, Altitude);
> CREATE VIRTUAL TABLE B USING RTree (ID, FromLatitude, TillLatitude, FromLongitude,TillLongitude);
> INSERT INTO A VALUES(1,0,0,0);
> INSERT INTO A VALUES(2,1,1,1);
> INSERT INTO B VALUES(1,0,0,0,0);
> INSERT INTO B VALUES(2,1,1,1,1);
>
> Without an analyze command the query plan seems to be OK:
> EXPLAIN QUERY PLAN SELECT COUNT(*) FROM A,B WHERE (A.ID=B.ID) AND (B.FromLongitude > 5) AND (B.TillLongitude < 10);
> 0|0|1|SCAN TABLE B VIRTUAL TABLE INDEX 2:EcCd (~0 rows)
> 0|1|0|SEARCH TABLE A USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)
>
> After running the ANALYZE command the query plan has changed and the result is a worse query plan than before:
> ANALYZE;
> EXPLAIN QUERY PLAN SELECT COUNT(*) FROM A,B WHERE (A.ID=B.ID) AND (B.FromLongitude > 5) AND (B.TillLongitude < 10);
> 0|0|0|SCAN TABLE A (~2 rows)
> 0|1|1|SCAN TABLE B VIRTUAL TABLE INDEX 1: (~0 rows)

With such small tables, the join order does not matter.
With millions of records, SQLite uses the first query plan again.

The cost of lookups that use the index of a virtual table are not easy
to estimate; if you want SQLite to force using an FTS or R-tree index,
put the virtual table lookup into a subquery, like this:

EXPLAIN QUERY PLAN SELECT COUNT(*) FROM A WHERE ID IN (SELECT ID FROM B WHERE FromLongitude > 5 AND TillLongitude < 10);
0|0|0|SEARCH TABLE a USING INTEGER PRIMARY KEY (rowid=?)
0|0|0|EXECUTE LIST SUBQUERY 1
1|0|0|SCAN TABLE b VIRTUAL TABLE INDEX 2:EcCd


And SQLite 3.8.2 has an improvement in the query planner for R-trees;
you should try it.


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [BUG; 3.7.13] ANALYZE leads to a wrong query plan for RTrees

Dan Kennedy-4
In reply to this post by mailing lists
On 12/10/2013 02:44 PM, skywind mailing lists wrote:

> This is an example that the ANALYZE command leads to a wrong query plan for RTrees:
>
> CREATE TABLE A (ID INTEGER PRIMARY KEY, Latitude, Longitude, Altitude);
> CREATE VIRTUAL TABLE B USING RTree (ID, FromLatitude, TillLatitude, FromLongitude,TillLongitude);
> INSERT INTO A VALUES(1,0,0,0);
> INSERT INTO A VALUES(2,1,1,1);
> INSERT INTO B VALUES(1,0,0,0,0);
> INSERT INTO B VALUES(2,1,1,1,1);
>
> Without an analyze command the query plan seems to be OK:
> EXPLAIN QUERY PLAN SELECT COUNT(*) FROM A,B WHERE (A.ID=B.ID) AND (B.FromLongitude > 5) AND (B.TillLongitude < 10);
> 0|0|1|SCAN TABLE B VIRTUAL TABLE INDEX 2:EcCd (~0 rows)
> 0|1|0|SEARCH TABLE A USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)
>
> After running the ANALYZE command the query plan has changed and the result is a worse query plan than before:
> ANALYZE;
> EXPLAIN QUERY PLAN SELECT COUNT(*) FROM A,B WHERE (A.ID=B.ID) AND (B.FromLongitude > 5) AND (B.TillLongitude < 10);
> 0|0|0|SCAN TABLE A (~2 rows)
> 0|1|1|SCAN TABLE B VIRTUAL TABLE INDEX 1: (~0 rows)
>

If possible, please try with 3.8.2. 3.8.2 adds a way for virtual
table queries in general, and r-tree tables in particular, to take
advantage of ANALYZE data:

   http://www.sqlite.org/src/info/5a3cfd747a

As Clemens says in the other post, with such small tables the join
order is not very important. So a better test would be with the
original database - the one you used to spot the problem in the
first place.

Dan.


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

Re: [BUG; 3.7.13] ANALYZE leads to a wrong query plan for RTrees

mailing lists

Am 10.12.2013 um 10:59 schrieb Dan Kennedy <[hidden email]>:

> On 12/10/2013 02:44 PM, skywind mailing lists wrote:
>> This is an example that the ANALYZE command leads to a wrong query plan for RTrees:
>>
>> CREATE TABLE A (ID INTEGER PRIMARY KEY, Latitude, Longitude, Altitude);
>> CREATE VIRTUAL TABLE B USING RTree (ID, FromLatitude, TillLatitude, FromLongitude,TillLongitude);
>> INSERT INTO A VALUES(1,0,0,0);
>> INSERT INTO A VALUES(2,1,1,1);
>> INSERT INTO B VALUES(1,0,0,0,0);
>> INSERT INTO B VALUES(2,1,1,1,1);
>>
>> Without an analyze command the query plan seems to be OK:
>> EXPLAIN QUERY PLAN SELECT COUNT(*) FROM A,B WHERE (A.ID=B.ID) AND (B.FromLongitude > 5) AND (B.TillLongitude < 10);
>> 0|0|1|SCAN TABLE B VIRTUAL TABLE INDEX 2:EcCd (~0 rows)
>> 0|1|0|SEARCH TABLE A USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)
>>
>> After running the ANALYZE command the query plan has changed and the result is a worse query plan than before:
>> ANALYZE;
>> EXPLAIN QUERY PLAN SELECT COUNT(*) FROM A,B WHERE (A.ID=B.ID) AND (B.FromLongitude > 5) AND (B.TillLongitude < 10);
>> 0|0|0|SCAN TABLE A (~2 rows)
>> 0|1|1|SCAN TABLE B VIRTUAL TABLE INDEX 1: (~0 rows)
>>
>
> If possible, please try with 3.8.2. 3.8.2 adds a way for virtual
> table queries in general, and r-tree tables in particular, to take
> advantage of ANALYZE data:
>
>  http://www.sqlite.org/src/info/5a3cfd747a
>
> As Clemens says in the other post, with such small tables the join
> order is not very important. So a better test would be with the
> original database - the one you used to spot the problem in the
> first place.
>
> Dan.
>
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

I used my original database with slightly more than 70 000 datasets and I get the same result as in the small database. To make sure that the query works as expected I use a CROSS JOIN, now.

I will try 3.8.x at a later stage.

Regards,
Hartwig



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