SQLite does not use opportunity to optimise COUNT() queries using partial indexes

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

SQLite does not use opportunity to optimise COUNT() queries using partial indexes

Paul
I am not very familiar with the SQLite internals, but I believe that index structure is similar
to that of a table, ie it's a B-TREE with a root containing a node count value. If so, then queries
like SELECT COUNT() FROM FOO WHERE <...>;  can be optimised the same way that
queries like SELECT COUNT() FROM FOO; given that condition is equivalent tho the
condition of the partial index.

Example:

sqlite> CREATE TABLE foo(
   ...>   id INTEGER PRIMARY KEY,
   ...>   ref_count INTEGER NOT NULL
   ...> );
sqlite>
sqlite> CREATE INDEX foo_ref_count_idx ON foo(ref_count) WHERE ref_count = 0;
sqlite>
sqlite> EXPLAIN SELECT COUNT() FROM foo;
addr        opcode      p1          p2          p3          p4          p5          comment  
----------  ----------  ----------  ----------  ----------  ----------  ----------  ----------
0           Init        0           7           0                       00                    
1           OpenRead    1           2           0           1           00                    
2           Count       1           1           0                       00                    
3           Close       1           0           0                       00                    
4           Copy        1           2           0                       00                    
5           ResultRow   2           1           0                       00                    
6           Halt        0           0           0                       00                    
7           Transactio  0           0           2           0           01                    
8           TableLock   0           2           0           foo         00                    
9           Goto        0           1           0                       00                    
sqlite>
sqlite> EXPLAIN SELECT COUNT() FROM foo WHERE ref_count = 0;
addr        opcode      p1          p2          p3          p4          p5          comment  
----------  ----------  ----------  ----------  ----------  ----------  ----------  ----------
0           Init        0           13          0                       00                    
1           Null        0           1           1                       00                    
2           OpenRead    1           3           0           k(2,nil,ni  00                    
3           Integer     0           2           0                       00                    
4           SeekGE      1           8           2           1           00                    
5           IdxGT       1           8           2           1           00                    
6           AggStep     0           0           1           count(0)    00                    
7           Next        1           5           1                       00                    
8           Close       1           0           0                       00                    
9           AggFinal    1           0           0           count(0)    00                    
10          Copy        1           3           0                       00                    
11          ResultRow   3           1           0                       00                    
12          Halt        0           0           0                       00                    
13          Transactio  0           0           2           0           01                    
14          TableLock   0           2           0           foo         00                    
15          Goto        0           1           0                       00                    
sqlite>
sqlite> EXPLAIN SELECT COUNT() FROM foo WHERE ref_count != 0;
addr        opcode      p1          p2          p3          p4          p5          comment  
----------  ----------  ----------  ----------  ----------  ----------  ----------  ----------
0           Init        0           13          0                       00                    
1           Null        0           1           1                       00                    
2           OpenRead    0           2           0           2           00                    
3           Rewind      0           8           0                       00                    
4           Column      0           1           2                       00                    
5           Eq          3           7           2           (BINARY)    54                    
6           AggStep     0           0           1           count(0)    00                    
7           Next        0           4           0                       01                    
8           Close       0           0           0                       00                    
9           AggFinal    1           0           0           count(0)    00                    
10          Copy        1           4           0                       00                    
11          ResultRow   4           1           0                       00                    
12          Halt        0           0           0                       00                    
13          Transactio  0           0           2           0           01                    
14          TableLock   0           2           0           foo         00                    
15          Integer     0           3           0                       00                    
16          Goto        0           1           0                       00

As we can see 'SELECT COUNT() FROM foo;' query does not scan the table.

But 'SELECT COUNT() FROM foo WHERE ref_count = 0;'  query does and is no
different from 'SELECT COUNT() FROM foo WHERE ref_count != 0;'  query that
obviously cannot be optimised.
 
 
_______________________________________________
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: SQLite does not use opportunity to optimise COUNT() queries using partial indexes

David Raymond
Gonna take a stab and answering this.
http://www.sqlite.org/opcode.html

The explain output for select count() from foo; uses the "Count" opcode. The description for that is
"Store the number of entries (an integer value) in the table or index opened by cursor P1 in register P2"
So that is indeed going to scan through the whole table, as the OpenRead was pointed to the table B-tree and not the index B-tree.

In the second case "select count() from foo where ref_count = 0" the OpenRead opens up the index (p4 isn't an integer) so that is indeed going through the index.

Remember also that you can get a more succinct explain by using "explain query plan".

Here's the output of me running this in a CLI I compiled with the pretty explain comments. Using .eqp full it outputs the "explain query plan" results, then the "explain" results, then the query results.

(Hmm, random note: It looks like ".eqp full" makes it disregard ".header on" when it gets down to outputting the results. Downgrading to only ".eqp on" respects the ".header on" though.)

SQLite version 3.15.1 2016-11-04 12:08:49
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.

sqlite> create table foo (id integer primary key, ref_count integer not null);

sqlite> create index foo_ref_count_idx on foo (ref_count) where ref_count = 0;

sqlite> .eqp full

sqlite> select count() from foo;
--EQP-- 0,0,0,SCAN TABLE foo
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     7     0                    00  Start at 7
1     OpenRead       1     2     0     1              00  root=2 iDb=0
2     Count          1     1     0                    00  r[1]=count()
3     Close          1     0     0                    00
4     Copy           1     2     0                    00  r[2]=r[1]
5     ResultRow      2     1     0                    00  output=r[2]
6     Halt           0     0     0                    00
7     Transaction    0     0     2     0              01  usesStmtJournal=0
8     Goto           0     1     0                    00
0

sqlite> select count() from foo where ref_count = 0;
--EQP-- 0,0,0,SEARCH TABLE foo USING COVERING INDEX foo_ref_count_idx (ref_count=?)
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     13    0                    00  Start at 13
1     Null           0     1     1                    00  r[1..1]=NULL
2     OpenRead       1     3     0     k(2,,)         02  root=3 iDb=0; foo_ref_count_idx
3     Integer        0     2     0                    00  r[2]=0
4     SeekGE         1     8     2     1              00  key=r[2]
5       IdxGT          1     8     2     1              00  key=r[2]
6       AggStep0       0     0     1     count(0)       00  accum=r[1] step(r[0])
7     Next           1     5     1                    00
8     Close          1     0     0                    00
9     AggFinal       1     0     0     count(0)       00  accum=r[1] N=0
10    Copy           1     3     0                    00  r[3]=r[1]
11    ResultRow      3     1     0                    00  output=r[3]
12    Halt           0     0     0                    00
13    Transaction    0     0     2     0              01  usesStmtJournal=0
14    Goto           0     1     0                    00
0

sqlite> select count() from foo where ref_count != 0;
--EQP-- 0,0,0,SCAN TABLE foo
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     13    0                    00  Start at 13
1     Null           0     1     1                    00  r[1..1]=NULL
2     OpenRead       0     2     0     2              00  root=2 iDb=0; foo
3     Rewind         0     8     0                    00
4       Column         0     1     2                    00  r[2]=foo.ref_count
5       Eq             3     7     2     (BINARY)       54  if r[2]==r[3] goto 7
6       AggStep0       0     0     1     count(0)       00  accum=r[1] step(r[0])
7     Next           0     4     0                    01
8     Close          0     0     0                    00
9     AggFinal       1     0     0     count(0)       00  accum=r[1] N=0
10    Copy           1     4     0                    00  r[4]=r[1]
11    ResultRow      4     1     0                    00  output=r[4]
12    Halt           0     0     0                    00
13    Transaction    0     0     2     0              01  usesStmtJournal=0
14    Integer        0     3     0                    00  r[3]=0
15    Goto           0     1     0                    00
0


-----Original Message-----
From: sqlite-users [mailto:[hidden email]] On Behalf Of Paul
Sent: Thursday, December 01, 2016 2:22 AM
To: General Discussion of SQLite Database
Subject: [sqlite] SQLite does not use opportunity to optimise COUNT() queries using partial indexes

I am not very familiar with the SQLite internals, but I believe that index structure is similar
to that of a table, ie it's a B-TREE with a root containing a node count value. If so, then queries
like SELECT COUNT() FROM FOO WHERE <...>;  can be optimised the same way that
queries like SELECT COUNT() FROM FOO; given that condition is equivalent tho the
condition of the partial index.

Example:

sqlite> CREATE TABLE foo(
   ...>   id INTEGER PRIMARY KEY,
   ...>   ref_count INTEGER NOT NULL
   ...> );
sqlite>
sqlite> CREATE INDEX foo_ref_count_idx ON foo(ref_count) WHERE ref_count = 0;
sqlite>
sqlite> EXPLAIN SELECT COUNT() FROM foo;
addr        opcode      p1          p2          p3          p4          p5          comment  
----------  ----------  ----------  ----------  ----------  ----------  ----------  ----------
0           Init        0           7           0                       00                    
1           OpenRead    1           2           0           1           00                    
2           Count       1           1           0                       00                    
3           Close       1           0           0                       00                    
4           Copy        1           2           0                       00                    
5           ResultRow   2           1           0                       00                    
6           Halt        0           0           0                       00                    
7           Transactio  0           0           2           0           01                    
8           TableLock   0           2           0           foo         00                    
9           Goto        0           1           0                       00                    
sqlite>
sqlite> EXPLAIN SELECT COUNT() FROM foo WHERE ref_count = 0;
addr        opcode      p1          p2          p3          p4          p5          comment  
----------  ----------  ----------  ----------  ----------  ----------  ----------  ----------
0           Init        0           13          0                       00                    
1           Null        0           1           1                       00                    
2           OpenRead    1           3           0           k(2,nil,ni  00                    
3           Integer     0           2           0                       00                    
4           SeekGE      1           8           2           1           00                    
5           IdxGT       1           8           2           1           00                    
6           AggStep     0           0           1           count(0)    00                    
7           Next        1           5           1                       00                    
8           Close       1           0           0                       00                    
9           AggFinal    1           0           0           count(0)    00                    
10          Copy        1           3           0                       00                    
11          ResultRow   3           1           0                       00                    
12          Halt        0           0           0                       00                    
13          Transactio  0           0           2           0           01                    
14          TableLock   0           2           0           foo         00                    
15          Goto        0           1           0                       00                    
sqlite>
sqlite> EXPLAIN SELECT COUNT() FROM foo WHERE ref_count != 0;
addr        opcode      p1          p2          p3          p4          p5          comment  
----------  ----------  ----------  ----------  ----------  ----------  ----------  ----------
0           Init        0           13          0                       00                    
1           Null        0           1           1                       00                    
2           OpenRead    0           2           0           2           00                    
3           Rewind      0           8           0                       00                    
4           Column      0           1           2                       00                    
5           Eq          3           7           2           (BINARY)    54                    
6           AggStep     0           0           1           count(0)    00                    
7           Next        0           4           0                       01                    
8           Close       0           0           0                       00                    
9           AggFinal    1           0           0           count(0)    00                    
10          Copy        1           4           0                       00                    
11          ResultRow   4           1           0                       00                    
12          Halt        0           0           0                       00                    
13          Transactio  0           0           2           0           01                    
14          TableLock   0           2           0           foo         00                    
15          Integer     0           3           0                       00                    
16          Goto        0           1           0                       00

As we can see 'SELECT COUNT() FROM foo;' query does not scan the table.

But 'SELECT COUNT() FROM foo WHERE ref_count = 0;'  query does and is no
different from 'SELECT COUNT() FROM foo WHERE ref_count != 0;'  query that
obviously cannot be optimised.
 
 
_______________________________________________
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: SQLite does not use opportunity to optimise COUNT() queries using partial indexes

Paul
Thanks!

That explains a lot. For some reason I thought that 'SELECT COUNT() FROM <table>' is optimised.

 

> Gonna take a stab and answering this.
> http://www.sqlite.org/opcode.html
>
> The explain output for select count() from foo; uses the "Count" opcode. The description for that is
> "Store the number of entries (an integer value) in the table or index opened by cursor P1 in register P2"
> So that is indeed going to scan through the whole table, as the OpenRead was pointed to the table B-tree and not the index B-tree.
>
> In the second case "select count() from foo where ref_count = 0" the OpenRead opens up the index (p4 isn't an integer) so that is indeed going through the index.
>
> Remember also that you can get a more succinct explain by using "explain query plan".
>
> Here's the output of me running this in a CLI I compiled with the pretty explain comments. Using .eqp full it outputs the "explain query plan" results, then the "explain" results, then the query results.
>
> (Hmm, random note: It looks like ".eqp full" makes it disregard ".header on" when it gets down to outputting the results. Downgrading to only ".eqp on" respects the ".header on" though.)
>
> SQLite version 3.15.1 2016-11-04 12:08:49
> Enter ".help" for usage hints.
> Connected to a transient in-memory database.
> Use ".open FILENAME" to reopen on a persistent database.
>
> sqlite> create table foo (id integer primary key, ref_count integer not null);
>
> sqlite> create index foo_ref_count_idx on foo (ref_count) where ref_count = 0;
>
> sqlite> .eqp full
>
> sqlite> select count() from foo;
> --EQP-- 0,0,0,SCAN TABLE foo
> addr  opcode         p1    p2    p3    p4             p5  comment
> ----  -------------  ----  ----  ----  -------------  --  -------------
> 0     Init           0     7     0                    00  Start at 7
> 1     OpenRead       1     2     0     1              00  root=2 iDb=0
> 2     Count          1     1     0                    00  r[1]=count()
> 3     Close          1     0     0                    00
> 4     Copy           1     2     0                    00  r[2]=r[1]
> 5     ResultRow      2     1     0                    00  output=r[2]
> 6     Halt           0     0     0                    00
> 7     Transaction    0     0     2     0              01  usesStmtJournal=0
> 8     Goto           0     1     0                    00
> 0
>
> sqlite> select count() from foo where ref_count = 0;
> --EQP-- 0,0,0,SEARCH TABLE foo USING COVERING INDEX foo_ref_count_idx (ref_count=?)
> addr  opcode         p1    p2    p3    p4             p5  comment
> ----  -------------  ----  ----  ----  -------------  --  -------------
> 0     Init           0     13    0                    00  Start at 13
> 1     Null           0     1     1                    00  r[1..1]=NULL
> 2     OpenRead       1     3     0     k(2,,)         02  root=3 iDb=0; foo_ref_count_idx
> 3     Integer        0     2     0                    00  r[2]=0
> 4     SeekGE         1     8     2     1              00  key=r[2]
> 5       IdxGT          1     8     2     1              00  key=r[2]
> 6       AggStep0       0     0     1     count(0)       00  accum=r[1] step(r[0])
> 7     Next           1     5     1                    00
> 8     Close          1     0     0                    00
> 9     AggFinal       1     0     0     count(0)       00  accum=r[1] N=0
> 10    Copy           1     3     0                    00  r[3]=r[1]
> 11    ResultRow      3     1     0                    00  output=r[3]
> 12    Halt           0     0     0                    00
> 13    Transaction    0     0     2     0              01  usesStmtJournal=0
> 14    Goto           0     1     0                    00
> 0
>
> sqlite> select count() from foo where ref_count != 0;
> --EQP-- 0,0,0,SCAN TABLE foo
> addr  opcode         p1    p2    p3    p4             p5  comment
> ----  -------------  ----  ----  ----  -------------  --  -------------
> 0     Init           0     13    0                    00  Start at 13
> 1     Null           0     1     1                    00  r[1..1]=NULL
> 2     OpenRead       0     2     0     2              00  root=2 iDb=0; foo
> 3     Rewind         0     8     0                    00
> 4       Column         0     1     2                    00  r[2]=foo.ref_count
> 5       Eq             3     7     2     (BINARY)       54  if r[2]==r[3] goto 7
> 6       AggStep0       0     0     1     count(0)       00  accum=r[1] step(r[0])
> 7     Next           0     4     0                    01
> 8     Close          0     0     0                    00
> 9     AggFinal       1     0     0     count(0)       00  accum=r[1] N=0
> 10    Copy           1     4     0                    00  r[4]=r[1]
> 11    ResultRow      4     1     0                    00  output=r[4]
> 12    Halt           0     0     0                    00
> 13    Transaction    0     0     2     0              01  usesStmtJournal=0
> 14    Integer        0     3     0                    00  r[3]=0
> 15    Goto           0     1     0                    00
> 0
>
 
 
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users