Odd query plan for without rowid table

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

Odd query plan for without rowid table

korablev
Consider the following example:

CREATE TABLE t1(a PRIMARY KEY, b, c) WITHOUT ROWID;
WITH RECURSIVE
    cnt(x) AS (VALUES(1000) UNION ALL SELECT x+1 FROM cnt WHERE x<2000)
INSERT INTO t1(a,b,c) SELECT x, x,x FROM cnt;
CREATE INDEX t1b ON t1(b);
ANALYZE;
EXPLAIN QUERY PLAN
SELECT * FROM t1 WHERE b BETWEEN 500 AND 2500;
EXPLAIN QUERY PLAN
SELECT * FROM t1 WHERE b BETWEEN 2900 AND 3000;

Output in both cases will be: 0|0|0|SEARCH TABLE t1 USING INDEX t1b (b>? AND
b<?)

However, if ordinary tables was created, results would be different:

DROP TABLE IF EXISTS t1;
CREATE TABLE t1(a, b, c);
WITH RECURSIVE
   cnt(x) AS (VALUES(1000) UNION ALL SELECT x+1 FROM cnt WHERE x<2000)
INSERT INTO t1(a,b,c) SELECT x, x,x FROM cnt;
CREATE INDEX t1b ON t1(b);
ANALYZE;
EXPLAIN QUERY PLAN
SELECT * FROM t1 WHERE b BETWEEN 500 AND 2500;
EXPLAIN QUERY PLAN
SELECT * FROM t1 WHERE b BETWEEN 2900 AND 3000;

In second case, it would be more efficient to use index search: 0|0|0|SEARCH
TABLE t1 USING INDEX t1b (b>? AND b<?)
And in the first case there is no need to use index due to the range of
query: 0|0|0|SCAN TABLE t1

Is this just a drawback of the optimizer, or things are not so simple and
there is hidden sense?

Moreover, if .selecttrace and .wheretrace options are enabled, we can
notice, that for without rowid tables planer doesn't even take into account
SCAN TABLE plan:

*** Optimizer Start *** (wctrlFlags: 0x0)
TERM-0   7FD9BF8203A0 ... left=-1      prob=1   op=0x000 wtFlags=0x0000
'-- BETWEEN
    |-- {0:1}  flags=0x820000
    |-- 500
    '-- 2500
TERM-1   7FD9BF8203E0 V.. left={0:1}   prob=1   op=0x020 wtFlags=0x0003
'-- GE
    |-- {0:1}  flags=0x820000
    '-- 500
TERM-2   7FD9BF820420 V.. left={0:1}   prob=1   op=0x008 wtFlags=0x0003
'-- LE
    |-- {0:1}  flags=0x820000
    '-- 2500
    add: * 0.01.00           t1.t1b               0 f 00200 N 0 cost
0,122,98
BEGIN addBtreeIdx(t1b), nEq=0
STAT4 range scan: 8..1001  est=98
Range scan lowers nOut from 99 to 98
subset cost adjustment 122,98 to 122,97
replace: * 0.01.00           t1.t1b               0 f 00200 N 0 cost
0,122,98
   with: * 0.01.00           t1.t1b               0 f 00222 N 1 cost
0,122,97
TERM-0   7FD9BF8203E0 V.. left={0:1}   prob=1   op=0x020 wtFlags=0x0003
'-- GE
    |-- {0:1}  flags=0x820000
    '-- 500
BEGIN addBtreeIdx(t1b), nEq=0
STAT4 range scan: 8..939  est=97
Range scan lowers nOut from 99 to 97
replace: * 0.01.00           t1.t1b               0 f 00222 N 1 cost
0,122,97
TERM-0   7FD9BF8203E0 V.. left={0:1}   prob=1   op=0x020 wtFlags=0x0003
'-- GE
    |-- {0:1}  flags=0x820000
    '-- 500
   with: * 0.01.00           t1.t1b               0 f 00232 N 2 cost
0,121,97
TERM-0   7FD9BF8203E0 V.. left={0:1}   prob=1   op=0x020 wtFlags=0x0003
'-- GE
    |-- {0:1}  flags=0x820000
    '-- 500
TERM-1   7FD9BF820420 V.. left={0:1}   prob=1   op=0x008 wtFlags=0x0003
'-- LE
    |-- {0:1}  flags=0x820000
    '-- 2500
END addBtreeIdx(t1b), nEq=0, rc=0
STAT4 range scan: 0..939  est=98
Range scan lowers nOut from 99 to 98
   skip: * 0.01.00           t1.t1b               0 f 00212 N 1 cost
0,122,98
TERM-0   7FD9BF820420 V.. left={0:1}   prob=1   op=0x008 wtFlags=0x0003
'-- LE
    |-- {0:1}  flags=0x820000
    '-- 2500
END addBtreeIdx(t1b), nEq=0, rc=0
subset cost adjustment 113,98 to 121,98
   skip: * 0.01.00           t1._1                0 f 00240 N 0 cost
0,121,98
BEGIN addBtreeIdx(sqlite_autoindex_t1_1), nEq=0
END addBtreeIdx(sqlite_autoindex_t1_1), nEq=0, rc=0
0 0.01.00           t1.t1b               0 f 00232 N 2 cost 0,121,97
TERM-0   7FD9BF8203E0 V.. left={0:1}   prob=1   op=0x020 wtFlags=0x0003
'-- GE
    |-- {0:1}  flags=0x820000
    '-- 500
TERM-1   7FD9BF820420 V.. left={0:1}   prob=1   op=0x008 wtFlags=0x0003
'-- LE
    |-- {0:1}  flags=0x820000
    '-- 2500
---- begin solver.  (nRowEst=0)
New    0 cost=121, 97,119 order=0
---- after round 0 ----
 0 cost=121 nrow=97  order=0
---- Solution nRow=97
0 0.01.00           t1.t1b               0 f 00232 N 2 cost 0,121,97
TERM-0   7FD9BF8203E0 V.. left={0:1}   prob=1   op=0x020 wtFlags=0x0003
'-- GE
    |-- {0:1}  flags=0x820000
    '-- 500
TERM-1   7FD9BF820420 V.. left={0:1}   prob=1   op=0x008 wtFlags=0x0003
'-- LE
    |-- {0:1}  flags=0x820000
    '-- 2500
*** Optimizer Finished ***




--
Sent from: http://sqlite.1065341.n5.nabble.com/
_______________________________________________
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: Odd query plan for without rowid table

Richard Hipp-3
On 10/15/17, korablev <[hidden email]> wrote:
>
> Moreover, if .selecttrace and .wheretrace options are enabled, we can
> notice, that for without rowid tables planer doesn't even take into account
> SCAN TABLE plan:

[...]

>    skip: * 0.01.00           t1._1                0 f 00240 N 0 cost
> 0,121,98

This is the SCAN TABLE plan for the WITHOUT ROWID example.  It is
considered, but is immediately rejected, since the estimated cost is
very slightly higher than the estimated cost of using the t1b index.

It might not be computing a good estimate for the cost of doing a full
table scan on a WITHOUT ROWID table.  I need to review that
computation.
--
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: Odd query plan for without rowid table

Richard Hipp-3
In reply to this post by korablev
On 10/15/17, korablev <[hidden email]> wrote:
>
> Is this just a drawback of the optimizer, or things are not so simple and
> there is hidden sense?
>

Fixed on trunk.  https://sqlite.org/src/info/ee31c043

Note that the upcoming 3.21.0 release will be off of a branch so
3.21.0 will not contain the fix this problem.  You'll have to wait for
3.22.0 if you want an official release.  If this problem is important
to you, build from trunk.

--
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: Odd query plan for without rowid table

korablev
Thanks, I really appreciate so fast responce. However, example above still
doesn't work: planner prefers index 'a' instead of TABLE SCAN for WITHOUT
ROWID table, when range of query covers full table.



--
Sent from: http://sqlite.1065341.n5.nabble.com/
_______________________________________________
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: Odd query plan for without rowid table

Richard Hipp-3
On 10/15/17, korablev <[hidden email]> wrote:
> Thanks, I really appreciate so fast responce. However, example above still
> doesn't work: planner prefers index 'a' instead of TABLE SCAN for WITHOUT
> ROWID table, when range of query covers full table.

My input is this:

CREATE TABLE t1(a PRIMARY KEY, b, c) WITHOUT ROWID;
WITH RECURSIVE
    cnt(x) AS (VALUES(1000) UNION ALL SELECT x+1 FROM cnt WHERE x<2000)
INSERT INTO t1(a,b,c) SELECT x, x,x FROM cnt;
CREATE INDEX t1b ON t1(b);
ANALYZE;
EXPLAIN QUERY PLAN
SELECT * FROM t1 WHERE b BETWEEN 500 AND 2500;
EXPLAIN QUERY PLAN
SELECT * FROM t1 WHERE b BETWEEN 2900 AND 3000;

I get this output:

0|0|0|SCAN TABLE t1
0|0|0|SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?)

Are you getting something different.  Are you saying the above is wrong?

--
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: Odd query plan for without rowid table

korablev
Hmm, I got this:

SQLite version 3.21.0 2017-10-15 22:16:25
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> .open test_db1
sqlite> CREATE TABLE t1(a PRIMARY KEY, b, c) WITHOUT ROWID;
sqlite> WITH RECURSIVE
   ...>     cnt(x) AS (VALUES(1000) UNION ALL SELECT x+1 FROM cnt WHERE
x<2000)  
   ...> INSERT INTO t1(a,b,c) SELECT x, x,x FROM cnt;
sqlite> CREATE INDEX t1b ON t1(b);
sqlite> ANALYZE;
sqlite> EXPLAIN QUERY PLAN
   ...> SELECT * FROM t1 WHERE b BETWEEN 500 AND 2500;
0|0|0|SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?)
sqlite> EXPLAIN QUERY PLAN
   ...> SELECT * FROM t1 WHERE b BETWEEN 2900 AND 3000;
0|0|0|SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?)

Am I doing something wrong?



--
Sent from: http://sqlite.1065341.n5.nabble.com/
_______________________________________________
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: Odd query plan for without rowid table

Richard Hipp-3
On 10/15/17, korablev <[hidden email]> wrote:
> Hmm, I got this:
>
> Am I doing something wrong?

Are you compiling with -DSQLITE_ENABLE_STAT4?  The STAT4 extension is
necessary in order for SQLite to distinguish between the two WHERE
clauses.

--
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: Odd query plan for without rowid table

Dominique Devienne
In reply to this post by Richard Hipp-3
On Mon, Oct 16, 2017 at 12:28 AM, Richard Hipp <[hidden email]> wrote:
>
> Fixed on trunk.  https://sqlite.org/src/info/ee31c043

FYI, small typo in that commit. --DD

line 1885 of where.c
** Return TRUE if all of the following are true:
**
**   (1)  X has the same or lower cost that Y
**   (2)  X users fewer WHERE clause terms than Y
**   (3)  Every WHERE clause term used by X is also used by Y
**   (4)  X skips at least as many columns as Y
**   (5)  If X is a covering index, than Y is too

-- **   (2)  X users fewer WHERE clause terms than Y
++ **   (2)  X uses fewer WHERE clause terms than Y
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users