question about covering index

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

question about covering index

Mark Wagner
Given the following schema:

CREATE TABLE foo (_id integer primary key, x, y);
CREATE INDEX i on foo(_id, x, y);

And the following query

sqlite> EXPLAIN QUERY PLAN SELECT * FROM foo WHERE x=1 GROUP BY _id ORDER
BY y;

I would have expected it (hoped?) that it would use the covering index for
the order by.  Any clue why it doesn't or what I could do differently to
get it to use an index for the selection, the grouping, and the ordering?

selectid = 0
   order = 0
    from = 0
  detail = SCAN TABLE foo

selectid = 0
   order = 0
    from = 0
  detail = USE TEMP B-TREE FOR ORDER BY
_______________________________________________
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: question about covering index

Simon Slavin-3
On 7 Feb 2018, at 12:43am, Mark Wagner <[hidden email]> wrote:

> CREATE TABLE foo (_id integer primary key, x, y);
> CREATE INDEX i on foo(_id, x, y);
>
> And the following query
>
> sqlite> EXPLAIN QUERY PLAN SELECT * FROM foo WHERE x=1 GROUP BY _id ORDER
> BY y;

Why are you grouping on the primary key ?  Primary key values must be, by definition, unique.  Grouping by a unique value means every group has one entry.

There's a similar problem with the index you created.  Since the primary key is first, there's no point in having the x and y in the index.  Therefore there's no point in having the index since it just duplicates the primary key index for the table.

I suspect that SQLite is acting weird because you fed it with weird things.

Simon.
_______________________________________________
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: question about covering index

Mark Wagner
OK, I oversimplified trying to make it easier.

The real query has a join so I'm aggregating some of the columns.  But this
test case seemed to show the issue.  I could show something closer to what
I'm really doing if that explanation isn't sufficient.



On Tue, Feb 6, 2018 at 4:48 PM, Simon Slavin <[hidden email]> wrote:

> On 7 Feb 2018, at 12:43am, Mark Wagner <[hidden email]> wrote:
>
> > CREATE TABLE foo (_id integer primary key, x, y);
> > CREATE INDEX i on foo(_id, x, y);
> >
> > And the following query
> >
> > sqlite> EXPLAIN QUERY PLAN SELECT * FROM foo WHERE x=1 GROUP BY _id ORDER
> > BY y;
>
> Why are you grouping on the primary key ?  Primary key values must be, by
> definition, unique.  Grouping by a unique value means every group has one
> entry.
>
> There's a similar problem with the index you created.  Since the primary
> key is first, there's no point in having the x and y in the index.
> Therefore there's no point in having the index since it just duplicates the
> primary key index for the table.
>
> I suspect that SQLite is acting weird because you fed it with weird things.
>
> Simon.
> _______________________________________________
> 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: question about covering index

Keith Medcalf
In reply to this post by Mark Wagner

Because your fields are backwards?

x should come before _id (x is a row selector, _id is a grouping selector), and the y cannot be used to sort (obviously) but can be used to avoid the table lookup to feed the results into the temp b-tree sorter.

sqlite> CREATE TABLE foo (_id integer primary key, x, y);
sqlite> CREATE INDEX i on foo(_id, x, y);
sqlite> CREATE INDEX j on foo(x, _id, y);
sqlite> CREATE INDEX k on foo(y, x, _id);
sqlite> .eqp on
sqlite> SELECT * FROM foo WHERE x=1 GROUP BY _id ORDER BY y;
--EQP-- 0,0,0,SEARCH TABLE foo USING COVERING INDEX j (x=?)
--EQP-- 0,0,0,USE TEMP B-TREE FOR ORDER BY
sqlite> .eqp full
sqlite> SELECT * FROM foo WHERE x=1 GROUP BY _id ORDER BY y;
--EQP-- 0,0,0,SEARCH TABLE foo USING COVERING INDEX j (x=?)
--EQP-- 0,0,0,USE TEMP B-TREE FOR ORDER BY
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     50    0                    00  Start at 50
1     SorterOpen     1     5     0     k(1,B)         00
2     Noop           2     3     0                    00
3     Integer        0     5     0                    00  r[5]=0; clear abort flag
4     Integer        0     4     0                    00  r[4]=0; indicate accumulator empty
5     Null           0     8     8                    00  r[8..8]=NULL
6     Gosub          7     39    0                    00
7     OpenRead       3     4     0     k(4,,,,)       02  root=4 iDb=0; j
8     Noop           0     0     0                    00  Begin WHERE-loop0: foo
9     CursorHint     3     0     0     EQ(c0,1)       00
10    Integer        1     10    0                    00  r[10]=1
11    SeekGE         3     27    10    1              00  key=r[10]
12      IdxGT          3     27    10    1              00  key=r[10]
13      Noop           0     0     0                    00  Begin WHERE-core
14      IdxRowid       3     9     0                    00  r[9]=rowid
15      Compare        8     9     1     k(1,B)         00  r[8] <-> r[9]
16      Jump           17    21    17                   00
17      Move           9     8     1                    00  r[8]=r[9]
18      Gosub          6     32    0                    00  output one row
19      IfPos          5     41    0                    00  if r[5]>0 then r[5]-=0, goto 41; check abort flag
20      Gosub          7     39    0                    00  reset accumulator
21      IdxRowid       3     1     0                    00  r[1]=rowid
22      Column         3     0     2                    00  r[2]=foo.x
23      Column         3     2     3                    00  r[3]=foo.y
24      Integer        1     4     0                    00  r[4]=1; indicate data in accumulator
25      Noop           0     0     0                    00  End WHERE-core
26    Next           3     12    0                    00
27    Noop           0     0     0                    00  End WHERE-loop0: foo
28    Gosub          6     32    0                    00  output final row
29    Goto           0     41    0                    00
30    Integer        1     5     0                    00  r[5]=1; set abort flag
31    Return         6     0     0                    00
32    IfPos          4     34    0                    00  if r[4]>0 then r[4]-=0, goto 34; Groupby result generator entry point
33    Return         6     0     0                    00
34    Copy           1     12    1                    00  r[12..13]=r[1..2]
35    Copy           3     11    0                    00  r[11]=r[3]
36    MakeRecord     11    3     15                   00  r[15]=mkrec(r[11..13])
37    SorterInsert   1     15    11    3              00  key=r[15]
38    Return         6     0     0                    00  end groupby result generator
39    Null           0     1     3                    00  r[1..3]=NULL
40    Return         7     0     0                    00
41    OpenPseudo     4     16    5                    00  5 columns in r[16]
42    SorterSort     1     49    0                    00
43      SorterData     1     16    4                    00  r[16]=data
44      Column         4     0     14                   00  r[14]=y
45      Column         4     2     13                   00  r[13]=x
46      Column         4     1     12                   00  r[12]=_id
47      ResultRow      12    3     0                    00  output=r[12..14]
48    SorterNext     1     43    0                    00
49    Halt           0     0     0                    00
50    Transaction    0     0     4     0              01  usesStmtJournal=0
51    Goto           0     1     0                    00
s


---
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.


>-----Original Message-----
>From: sqlite-users [mailto:sqlite-users-
>[hidden email]] On Behalf Of Mark Wagner
>Sent: Tuesday, 6 February, 2018 17:44
>To: SQLite mailing list
>Subject: [sqlite] question about covering index
>
>Given the following schema:
>
>CREATE TABLE foo (_id integer primary key, x, y);
>CREATE INDEX i on foo(_id, x, y);
>
>And the following query
>
>sqlite> EXPLAIN QUERY PLAN SELECT * FROM foo WHERE x=1 GROUP BY _id
>ORDER
>BY y;
>
>I would have expected it (hoped?) that it would use the covering
>index for
>the order by.  Any clue why it doesn't or what I could do differently
>to
>get it to use an index for the selection, the grouping, and the
>ordering?
>
>selectid = 0
>   order = 0
>    from = 0
>  detail = SCAN TABLE foo
>
>selectid = 0
>   order = 0
>    from = 0
>  detail = USE TEMP B-TREE FOR ORDER BY
>_______________________________________________
>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: question about covering index

Keith Medcalf

That said, however, the performance increase will be proportional to the number of x values that are selected vs the number of rows in the table.  Unless the table is many orders of magnitude larger than the number of similar x values you are searching for, the table scan will likely be faster.  Of course, you will also "pay" the extra index maintenance and storage fee's, which may or may not outweigh the increase conferred.

---
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.


>-----Original Message-----
>From: sqlite-users [mailto:sqlite-users-
>[hidden email]] On Behalf Of Keith Medcalf
>Sent: Tuesday, 6 February, 2018 18:07
>To: SQLite mailing list
>Subject: Re: [sqlite] question about covering index
>
>
>Because your fields are backwards?
>
>x should come before _id (x is a row selector, _id is a grouping
>selector), and the y cannot be used to sort (obviously) but can be
>used to avoid the table lookup to feed the results into the temp b-
>tree sorter.
>
>sqlite> CREATE TABLE foo (_id integer primary key, x, y);
>sqlite> CREATE INDEX i on foo(_id, x, y);
>sqlite> CREATE INDEX j on foo(x, _id, y);
>sqlite> CREATE INDEX k on foo(y, x, _id);
>sqlite> .eqp on
>sqlite> SELECT * FROM foo WHERE x=1 GROUP BY _id ORDER BY y;
>--EQP-- 0,0,0,SEARCH TABLE foo USING COVERING INDEX j (x=?)
>--EQP-- 0,0,0,USE TEMP B-TREE FOR ORDER BY
>sqlite> .eqp full
>sqlite> SELECT * FROM foo WHERE x=1 GROUP BY _id ORDER BY y;
>--EQP-- 0,0,0,SEARCH TABLE foo USING COVERING INDEX j (x=?)
>--EQP-- 0,0,0,USE TEMP B-TREE FOR ORDER BY
>addr  opcode         p1    p2    p3    p4             p5  comment
>----  -------------  ----  ----  ----  -------------  --  -----------
>--
>0     Init           0     50    0                    00  Start at 50
>1     SorterOpen     1     5     0     k(1,B)         00
>2     Noop           2     3     0                    00
>3     Integer        0     5     0                    00  r[5]=0;
>clear abort flag
>4     Integer        0     4     0                    00  r[4]=0;
>indicate accumulator empty
>5     Null           0     8     8                    00
>r[8..8]=NULL
>6     Gosub          7     39    0                    00
>7     OpenRead       3     4     0     k(4,,,,)       02  root=4
>iDb=0; j
>8     Noop           0     0     0                    00  Begin
>WHERE-loop0: foo
>9     CursorHint     3     0     0     EQ(c0,1)       00
>10    Integer        1     10    0                    00  r[10]=1
>11    SeekGE         3     27    10    1              00  key=r[10]
>12      IdxGT          3     27    10    1              00  key=r[10]
>13      Noop           0     0     0                    00  Begin
>WHERE-core
>14      IdxRowid       3     9     0                    00
>r[9]=rowid
>15      Compare        8     9     1     k(1,B)         00  r[8] <->
>r[9]
>16      Jump           17    21    17                   00
>17      Move           9     8     1                    00  r[8]=r[9]
>18      Gosub          6     32    0                    00  output
>one row
>19      IfPos          5     41    0                    00  if r[5]>0
>then r[5]-=0, goto 41; check abort flag
>20      Gosub          7     39    0                    00  reset
>accumulator
>21      IdxRowid       3     1     0                    00
>r[1]=rowid
>22      Column         3     0     2                    00
>r[2]=foo.x
>23      Column         3     2     3                    00
>r[3]=foo.y
>24      Integer        1     4     0                    00  r[4]=1;
>indicate data in accumulator
>25      Noop           0     0     0                    00  End
>WHERE-core
>26    Next           3     12    0                    00
>27    Noop           0     0     0                    00  End WHERE-
>loop0: foo
>28    Gosub          6     32    0                    00  output
>final row
>29    Goto           0     41    0                    00
>30    Integer        1     5     0                    00  r[5]=1; set
>abort flag
>31    Return         6     0     0                    00
>32    IfPos          4     34    0                    00  if r[4]>0
>then r[4]-=0, goto 34; Groupby result generator entry point
>33    Return         6     0     0                    00
>34    Copy           1     12    1                    00
>r[12..13]=r[1..2]
>35    Copy           3     11    0                    00  r[11]=r[3]
>36    MakeRecord     11    3     15                   00
>r[15]=mkrec(r[11..13])
>37    SorterInsert   1     15    11    3              00  key=r[15]
>38    Return         6     0     0                    00  end groupby
>result generator
>39    Null           0     1     3                    00
>r[1..3]=NULL
>40    Return         7     0     0                    00
>41    OpenPseudo     4     16    5                    00  5 columns
>in r[16]
>42    SorterSort     1     49    0                    00
>43      SorterData     1     16    4                    00
>r[16]=data
>44      Column         4     0     14                   00  r[14]=y
>45      Column         4     2     13                   00  r[13]=x
>46      Column         4     1     12                   00  r[12]=_id
>47      ResultRow      12    3     0                    00
>output=r[12..14]
>48    SorterNext     1     43    0                    00
>49    Halt           0     0     0                    00
>50    Transaction    0     0     4     0              01
>usesStmtJournal=0
>51    Goto           0     1     0                    00
>s
>
>
>---
>The fact that there's a Highway to Hell but only a Stairway to Heaven
>says a lot about anticipated traffic volume.
>
>
>>-----Original Message-----
>>From: sqlite-users [mailto:sqlite-users-
>>[hidden email]] On Behalf Of Mark Wagner
>>Sent: Tuesday, 6 February, 2018 17:44
>>To: SQLite mailing list
>>Subject: [sqlite] question about covering index
>>
>>Given the following schema:
>>
>>CREATE TABLE foo (_id integer primary key, x, y);
>>CREATE INDEX i on foo(_id, x, y);
>>
>>And the following query
>>
>>sqlite> EXPLAIN QUERY PLAN SELECT * FROM foo WHERE x=1 GROUP BY _id
>>ORDER
>>BY y;
>>
>>I would have expected it (hoped?) that it would use the covering
>>index for
>>the order by.  Any clue why it doesn't or what I could do
>differently
>>to
>>get it to use an index for the selection, the grouping, and the
>>ordering?
>>
>>selectid = 0
>>   order = 0
>>    from = 0
>>  detail = SCAN TABLE foo
>>
>>selectid = 0
>>   order = 0
>>    from = 0
>>  detail = USE TEMP B-TREE FOR ORDER BY
>>_______________________________________________
>>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



_______________________________________________
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: question about covering index

Mark Wagner
Wow, I had no idea that the order of the columns in the index effects how
they're used.  Must. Study. More.

On Tue, Feb 6, 2018 at 5:15 PM, Keith Medcalf <[hidden email]> wrote:

>
> That said, however, the performance increase will be proportional to the
> number of x values that are selected vs the number of rows in the table.
> Unless the table is many orders of magnitude larger than the number of
> similar x values you are searching for, the table scan will likely be
> faster.  Of course, you will also "pay" the extra index maintenance and
> storage fee's, which may or may not outweigh the increase conferred.
>
> ---
> The fact that there's a Highway to Hell but only a Stairway to Heaven says
> a lot about anticipated traffic volume.
>
>
> >-----Original Message-----
> >From: sqlite-users [mailto:sqlite-users-
> >[hidden email]] On Behalf Of Keith Medcalf
> >Sent: Tuesday, 6 February, 2018 18:07
> >To: SQLite mailing list
> >Subject: Re: [sqlite] question about covering index
> >
> >
> >Because your fields are backwards?
> >
> >x should come before _id (x is a row selector, _id is a grouping
> >selector), and the y cannot be used to sort (obviously) but can be
> >used to avoid the table lookup to feed the results into the temp b-
> >tree sorter.
> >
> >sqlite> CREATE TABLE foo (_id integer primary key, x, y);
> >sqlite> CREATE INDEX i on foo(_id, x, y);
> >sqlite> CREATE INDEX j on foo(x, _id, y);
> >sqlite> CREATE INDEX k on foo(y, x, _id);
> >sqlite> .eqp on
> >sqlite> SELECT * FROM foo WHERE x=1 GROUP BY _id ORDER BY y;
> >--EQP-- 0,0,0,SEARCH TABLE foo USING COVERING INDEX j (x=?)
> >--EQP-- 0,0,0,USE TEMP B-TREE FOR ORDER BY
> >sqlite> .eqp full
> >sqlite> SELECT * FROM foo WHERE x=1 GROUP BY _id ORDER BY y;
> >--EQP-- 0,0,0,SEARCH TABLE foo USING COVERING INDEX j (x=?)
> >--EQP-- 0,0,0,USE TEMP B-TREE FOR ORDER BY
> >addr  opcode         p1    p2    p3    p4             p5  comment
> >----  -------------  ----  ----  ----  -------------  --  -----------
> >--
> >0     Init           0     50    0                    00  Start at 50
> >1     SorterOpen     1     5     0     k(1,B)         00
> >2     Noop           2     3     0                    00
> >3     Integer        0     5     0                    00  r[5]=0;
> >clear abort flag
> >4     Integer        0     4     0                    00  r[4]=0;
> >indicate accumulator empty
> >5     Null           0     8     8                    00
> >r[8..8]=NULL
> >6     Gosub          7     39    0                    00
> >7     OpenRead       3     4     0     k(4,,,,)       02  root=4
> >iDb=0; j
> >8     Noop           0     0     0                    00  Begin
> >WHERE-loop0: foo
> >9     CursorHint     3     0     0     EQ(c0,1)       00
> >10    Integer        1     10    0                    00  r[10]=1
> >11    SeekGE         3     27    10    1              00  key=r[10]
> >12      IdxGT          3     27    10    1              00  key=r[10]
> >13      Noop           0     0     0                    00  Begin
> >WHERE-core
> >14      IdxRowid       3     9     0                    00
> >r[9]=rowid
> >15      Compare        8     9     1     k(1,B)         00  r[8] <->
> >r[9]
> >16      Jump           17    21    17                   00
> >17      Move           9     8     1                    00  r[8]=r[9]
> >18      Gosub          6     32    0                    00  output
> >one row
> >19      IfPos          5     41    0                    00  if r[5]>0
> >then r[5]-=0, goto 41; check abort flag
> >20      Gosub          7     39    0                    00  reset
> >accumulator
> >21      IdxRowid       3     1     0                    00
> >r[1]=rowid
> >22      Column         3     0     2                    00
> >r[2]=foo.x
> >23      Column         3     2     3                    00
> >r[3]=foo.y
> >24      Integer        1     4     0                    00  r[4]=1;
> >indicate data in accumulator
> >25      Noop           0     0     0                    00  End
> >WHERE-core
> >26    Next           3     12    0                    00
> >27    Noop           0     0     0                    00  End WHERE-
> >loop0: foo
> >28    Gosub          6     32    0                    00  output
> >final row
> >29    Goto           0     41    0                    00
> >30    Integer        1     5     0                    00  r[5]=1; set
> >abort flag
> >31    Return         6     0     0                    00
> >32    IfPos          4     34    0                    00  if r[4]>0
> >then r[4]-=0, goto 34; Groupby result generator entry point
> >33    Return         6     0     0                    00
> >34    Copy           1     12    1                    00
> >r[12..13]=r[1..2]
> >35    Copy           3     11    0                    00  r[11]=r[3]
> >36    MakeRecord     11    3     15                   00
> >r[15]=mkrec(r[11..13])
> >37    SorterInsert   1     15    11    3              00  key=r[15]
> >38    Return         6     0     0                    00  end groupby
> >result generator
> >39    Null           0     1     3                    00
> >r[1..3]=NULL
> >40    Return         7     0     0                    00
> >41    OpenPseudo     4     16    5                    00  5 columns
> >in r[16]
> >42    SorterSort     1     49    0                    00
> >43      SorterData     1     16    4                    00
> >r[16]=data
> >44      Column         4     0     14                   00  r[14]=y
> >45      Column         4     2     13                   00  r[13]=x
> >46      Column         4     1     12                   00  r[12]=_id
> >47      ResultRow      12    3     0                    00
> >output=r[12..14]
> >48    SorterNext     1     43    0                    00
> >49    Halt           0     0     0                    00
> >50    Transaction    0     0     4     0              01
> >usesStmtJournal=0
> >51    Goto           0     1     0                    00
> >s
> >
> >
> >---
> >The fact that there's a Highway to Hell but only a Stairway to Heaven
> >says a lot about anticipated traffic volume.
> >
> >
> >>-----Original Message-----
> >>From: sqlite-users [mailto:sqlite-users-
> >>[hidden email]] On Behalf Of Mark Wagner
> >>Sent: Tuesday, 6 February, 2018 17:44
> >>To: SQLite mailing list
> >>Subject: [sqlite] question about covering index
> >>
> >>Given the following schema:
> >>
> >>CREATE TABLE foo (_id integer primary key, x, y);
> >>CREATE INDEX i on foo(_id, x, y);
> >>
> >>And the following query
> >>
> >>sqlite> EXPLAIN QUERY PLAN SELECT * FROM foo WHERE x=1 GROUP BY _id
> >>ORDER
> >>BY y;
> >>
> >>I would have expected it (hoped?) that it would use the covering
> >>index for
> >>the order by.  Any clue why it doesn't or what I could do
> >differently
> >>to
> >>get it to use an index for the selection, the grouping, and the
> >>ordering?
> >>
> >>selectid = 0
> >>   order = 0
> >>    from = 0
> >>  detail = SCAN TABLE foo
> >>
> >>selectid = 0
> >>   order = 0
> >>    from = 0
> >>  detail = USE TEMP B-TREE FOR ORDER BY
> >>_______________________________________________
> >>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
>
>
>
> _______________________________________________
> 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: question about covering index

Keith Medcalf

Note that if the _id column were not UNIQUE, then the SKIP-SCAN optimization might be used with index i if and only if you had (a) done an analyze and (b) the optimizer thought it might be worthwhile to do so.


---
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.


>-----Original Message-----
>From: sqlite-users [mailto:sqlite-users-
>[hidden email]] On Behalf Of Mark Wagner
>Sent: Tuesday, 6 February, 2018 18:32
>To: SQLite mailing list
>Subject: Re: [sqlite] question about covering index
>
>Wow, I had no idea that the order of the columns in the index effects
>how
>they're used.  Must. Study. More.
>
>On Tue, Feb 6, 2018 at 5:15 PM, Keith Medcalf <[hidden email]>
>wrote:
>
>>
>> That said, however, the performance increase will be proportional
>to the
>> number of x values that are selected vs the number of rows in the
>table.
>> Unless the table is many orders of magnitude larger than the number
>of
>> similar x values you are searching for, the table scan will likely
>be
>> faster.  Of course, you will also "pay" the extra index maintenance
>and
>> storage fee's, which may or may not outweigh the increase
>conferred.
>>
>> ---
>> The fact that there's a Highway to Hell but only a Stairway to
>Heaven says
>> a lot about anticipated traffic volume.
>>
>>
>> >-----Original Message-----
>> >From: sqlite-users [mailto:sqlite-users-
>> >[hidden email]] On Behalf Of Keith Medcalf
>> >Sent: Tuesday, 6 February, 2018 18:07
>> >To: SQLite mailing list
>> >Subject: Re: [sqlite] question about covering index
>> >
>> >
>> >Because your fields are backwards?
>> >
>> >x should come before _id (x is a row selector, _id is a grouping
>> >selector), and the y cannot be used to sort (obviously) but can be
>> >used to avoid the table lookup to feed the results into the temp
>b-
>> >tree sorter.
>> >
>> >sqlite> CREATE TABLE foo (_id integer primary key, x, y);
>> >sqlite> CREATE INDEX i on foo(_id, x, y);
>> >sqlite> CREATE INDEX j on foo(x, _id, y);
>> >sqlite> CREATE INDEX k on foo(y, x, _id);
>> >sqlite> .eqp on
>> >sqlite> SELECT * FROM foo WHERE x=1 GROUP BY _id ORDER BY y;
>> >--EQP-- 0,0,0,SEARCH TABLE foo USING COVERING INDEX j (x=?)
>> >--EQP-- 0,0,0,USE TEMP B-TREE FOR ORDER BY
>> >sqlite> .eqp full
>> >sqlite> SELECT * FROM foo WHERE x=1 GROUP BY _id ORDER BY y;
>> >--EQP-- 0,0,0,SEARCH TABLE foo USING COVERING INDEX j (x=?)
>> >--EQP-- 0,0,0,USE TEMP B-TREE FOR ORDER BY
>> >addr  opcode         p1    p2    p3    p4             p5  comment
>> >----  -------------  ----  ----  ----  -------------  --  --------
>---
>> >--
>> >0     Init           0     50    0                    00  Start at
>50
>> >1     SorterOpen     1     5     0     k(1,B)         00
>> >2     Noop           2     3     0                    00
>> >3     Integer        0     5     0                    00  r[5]=0;
>> >clear abort flag
>> >4     Integer        0     4     0                    00  r[4]=0;
>> >indicate accumulator empty
>> >5     Null           0     8     8                    00
>> >r[8..8]=NULL
>> >6     Gosub          7     39    0                    00
>> >7     OpenRead       3     4     0     k(4,,,,)       02  root=4
>> >iDb=0; j
>> >8     Noop           0     0     0                    00  Begin
>> >WHERE-loop0: foo
>> >9     CursorHint     3     0     0     EQ(c0,1)       00
>> >10    Integer        1     10    0                    00  r[10]=1
>> >11    SeekGE         3     27    10    1              00
>key=r[10]
>> >12      IdxGT          3     27    10    1              00
>key=r[10]
>> >13      Noop           0     0     0                    00  Begin
>> >WHERE-core
>> >14      IdxRowid       3     9     0                    00
>> >r[9]=rowid
>> >15      Compare        8     9     1     k(1,B)         00  r[8]
><->
>> >r[9]
>> >16      Jump           17    21    17                   00
>> >17      Move           9     8     1                    00
>r[8]=r[9]
>> >18      Gosub          6     32    0                    00  output
>> >one row
>> >19      IfPos          5     41    0                    00  if
>r[5]>0
>> >then r[5]-=0, goto 41; check abort flag
>> >20      Gosub          7     39    0                    00  reset
>> >accumulator
>> >21      IdxRowid       3     1     0                    00
>> >r[1]=rowid
>> >22      Column         3     0     2                    00
>> >r[2]=foo.x
>> >23      Column         3     2     3                    00
>> >r[3]=foo.y
>> >24      Integer        1     4     0                    00
>r[4]=1;
>> >indicate data in accumulator
>> >25      Noop           0     0     0                    00  End
>> >WHERE-core
>> >26    Next           3     12    0                    00
>> >27    Noop           0     0     0                    00  End
>WHERE-
>> >loop0: foo
>> >28    Gosub          6     32    0                    00  output
>> >final row
>> >29    Goto           0     41    0                    00
>> >30    Integer        1     5     0                    00  r[5]=1;
>set
>> >abort flag
>> >31    Return         6     0     0                    00
>> >32    IfPos          4     34    0                    00  if
>r[4]>0
>> >then r[4]-=0, goto 34; Groupby result generator entry point
>> >33    Return         6     0     0                    00
>> >34    Copy           1     12    1                    00
>> >r[12..13]=r[1..2]
>> >35    Copy           3     11    0                    00
>r[11]=r[3]
>> >36    MakeRecord     11    3     15                   00
>> >r[15]=mkrec(r[11..13])
>> >37    SorterInsert   1     15    11    3              00
>key=r[15]
>> >38    Return         6     0     0                    00  end
>groupby
>> >result generator
>> >39    Null           0     1     3                    00
>> >r[1..3]=NULL
>> >40    Return         7     0     0                    00
>> >41    OpenPseudo     4     16    5                    00  5
>columns
>> >in r[16]
>> >42    SorterSort     1     49    0                    00
>> >43      SorterData     1     16    4                    00
>> >r[16]=data
>> >44      Column         4     0     14                   00
>r[14]=y
>> >45      Column         4     2     13                   00
>r[13]=x
>> >46      Column         4     1     12                   00
>r[12]=_id
>> >47      ResultRow      12    3     0                    00
>> >output=r[12..14]
>> >48    SorterNext     1     43    0                    00
>> >49    Halt           0     0     0                    00
>> >50    Transaction    0     0     4     0              01
>> >usesStmtJournal=0
>> >51    Goto           0     1     0                    00
>> >s
>> >
>> >
>> >---
>> >The fact that there's a Highway to Hell but only a Stairway to
>Heaven
>> >says a lot about anticipated traffic volume.
>> >
>> >
>> >>-----Original Message-----
>> >>From: sqlite-users [mailto:sqlite-users-
>> >>[hidden email]] On Behalf Of Mark Wagner
>> >>Sent: Tuesday, 6 February, 2018 17:44
>> >>To: SQLite mailing list
>> >>Subject: [sqlite] question about covering index
>> >>
>> >>Given the following schema:
>> >>
>> >>CREATE TABLE foo (_id integer primary key, x, y);
>> >>CREATE INDEX i on foo(_id, x, y);
>> >>
>> >>And the following query
>> >>
>> >>sqlite> EXPLAIN QUERY PLAN SELECT * FROM foo WHERE x=1 GROUP BY
>_id
>> >>ORDER
>> >>BY y;
>> >>
>> >>I would have expected it (hoped?) that it would use the covering
>> >>index for
>> >>the order by.  Any clue why it doesn't or what I could do
>> >differently
>> >>to
>> >>get it to use an index for the selection, the grouping, and the
>> >>ordering?
>> >>
>> >>selectid = 0
>> >>   order = 0
>> >>    from = 0
>> >>  detail = SCAN TABLE foo
>> >>
>> >>selectid = 0
>> >>   order = 0
>> >>    from = 0
>> >>  detail = USE TEMP B-TREE FOR ORDER BY
>> >>_______________________________________________
>> >>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
>>
>>
>>
>> _______________________________________________
>> 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



_______________________________________________
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: question about covering index

Simon Slavin-3
In reply to this post by Mark Wagner
On 7 Feb 2018, at 1:31am, Mark Wagner <[hidden email]> wrote:

> Wow, I had no idea that the order of the columns in the index effects how
> they're used.  Must. Study. More.

Just like a phone directory.  If the order is (surname, firstname) then the first name in the directory is the one with the lowest surname, not the lowest firstname.  This is why your covering index doesn't make sense.

Simon.
_______________________________________________
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: [EXTERNAL] question about covering index

Hick Gunter
In reply to this post by Mark Wagner
SQLite can only use a covering index whose prefix satifies the WHERE and/or ORDER BY clause(es).

WHERE x=1
ORDER BY y

The WHERE constraint can be handled by an index that starts off with x.
The ORDER BY can be handled by an index that starts off with y.

SQLite *may* realise that an index on (x,y) satisfies both conditions (within the fixed x values, y values are already ordered). In that case you would require the _id field to make it a convering index (x,y,_id).

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Mark Wagner
Gesendet: Mittwoch, 07. Februar 2018 01:44
An: SQLite mailing list <[hidden email]>
Betreff: [EXTERNAL] [sqlite] question about covering index

Given the following schema:

CREATE TABLE foo (_id integer primary key, x, y); CREATE INDEX i on foo(_id, x, y);

And the following query

sqlite> EXPLAIN QUERY PLAN SELECT * FROM foo WHERE x=1 GROUP BY _id
sqlite> ORDER
BY y;

I would have expected it (hoped?) that it would use the covering index for the order by.  Any clue why it doesn't or what I could do differently to get it to use an index for the selection, the grouping, and the ordering?

selectid = 0
   order = 0
    from = 0
  detail = SCAN TABLE foo

selectid = 0
   order = 0
    from = 0
  detail = USE TEMP B-TREE FOR ORDER BY
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick | Software Engineer | Scientific Games International GmbH | Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43 1 80100 - 0

May be privileged. May be confidential. Please delete if not the addressee.
_______________________________________________
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: [EXTERNAL] question about covering index

Eduardo
On Wed, 7 Feb 2018 09:17:27 +0000
Hick Gunter <[hidden email]> escribió:

> SQLite can only use a covering index whose prefix satifies the WHERE and/or ORDER BY clause(es).
>
> WHERE x=1
> ORDER BY y
>
> The WHERE constraint can be handled by an index that starts off with x.
> The ORDER BY can be handled by an index that starts off with y.
>
> SQLite *may* realise that an index on (x,y) satisfies both conditions (within the fixed x values, y values are already ordered). In that case you would require the _id field to make it a convering index (x,y,_id).
>

_id field is always appened at the end of all indexes, it's integer primary
key. Your index internally will be (x, y, _id, _id)


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