Does SQLITE ever optimize index creation based on another index?

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

Does SQLITE ever optimize index creation based on another index?

Deon Brewis
Given the SQL below, FooX is a covered index for x on Foo.

I want to create FooXB as a second index on x in Foo. Since 'x' is covered on FooX it should be cheaper to build FooXB from index FooX, than from table Foo. However, as far as I can tell from the from the opcodes of the index creation it doesn't do this (OpenRead uses rootpage=2 instead of 3). Is my understanding correct?

And if my understanding is correct, is there any scenarios in which I can coerce SQLITE to build a new index based on data in an existing index?


drop table Foo;
create table Foo(x text, y text, z text);

insert into Foo(x) values("elephant");
insert into Foo(x) values("cat");
insert into Foo(x) values("giraffe");
insert into Foo(x) values("dog");
insert into Foo(x) values("zebra");
insert into Foo(x) values("lion");
insert into Foo(x) values("panther");

create index FooX on Foo(x);
create index FooXB on Foo(substr(x,2,1)) where substr(x,2,1) > 'e';




select * from sqlite_master;
RecNo type  name tbl_name rootpage sql
----- ----- ---- -------- -------- ----------------------------------------
    1 table Foo  Foo             2 CREATE TABLE Foo(x text, y text, z text)
    2 index FooX Foo             3 CREATE INDEX FooX on Foo(x)

explain create index FooXB on Foo(substr(x,2,1)) where substr(x,2,1) > 'e';
RecNo addr opcode       p1 p2 p3 p4                                                                           p5 comment
----- ---- ------------ -- -- -- ---------------------------------------------------------------------------- -- -------
    1 0    Init         0  37 0                                                                               00 (null)
    2 1    Noop         0  36 0                                                                               00 (null)
    3 2    CreateBtree  0  1  2                                                                               00 (null)
    4 3    OpenWrite    0  1  0  5                                                                            00 (null)
    5 4    NewRowid     0  2  0                                                                               00 (null)
    6 5    String8      0  3  0  index                                                                        00 (null)
    7 6    String8      0  4  0  FooXB                                                                        00 (null)
    8 7    String8      0  5  0  Foo                                                                          00 (null)
    9 8    Copy         1  6  0                                                                               00 (null)
   10 9    String8      0  7  0  CREATE INDEX FooXB on Foo(substr(x,2,1)) where substr(x,2,1) > 'e' (more...) 00 (null)
   11 10   MakeRecord   3  5  8  BBBDB                                                                        00 (null)
   12 11   Insert       0  8  2                                                                               18 (null)
   13 12   SorterOpen   3  0  1  k(2,,)                                                                       00 (null)
   14 13   OpenRead     1  2  0  3                                                                            00 (null)
   15 14   Rewind       1  24 0                                                                               00 (null)
   16 15   Column       1  0  11                                                                              00 (null)
   17 16   PureFunc0    6  11 10 substr(3)                                                                    03 (null)
   18 17   Le           14 23 10                                                                              51 (null)
   19 18   Column       1  0  17                                                                              00 (null)
   20 19   PureFunc0    6  17 15 substr(3)                                                                    03 (null)
   21 20   Rowid        1  16 0                                                                               00 (null)
   22 21   MakeRecord   15 2  9                                                                               00 (null)
   23 22   SorterInsert 3  9  0                                                                               00 (null)
   24 23   Next         1  15 0                                                                               00 (null)
   25 24   OpenWrite    2  1  0  k(2,,)                                                                       11 (null)
   26 25   SorterSort   3  30 0                                                                               00 (null)
   27 26   SorterData   3  9  2                                                                               00 (null)
   28 27   SeekEnd      2  0  0                                                                               00 (null)
   29 28   IdxInsert    2  9  0                                                                               10 (null)
   30 29   SorterNext   3  26 0                                                                               00 (null)
   31 30   Close        1  0  0                                                                               00 (null)
   32 31   Close        2  0  0                                                                               00 (null)
   33 32   Close        3  0  0                                                                               00 (null)
   34 33   SetCookie    0  1  43                                                                              00 (null)
   35 34   ParseSchema  0  0  0  name='FooXB' AND type='index'                                                00 (null)
   36 35   Expire       0  1  0                                                                               00 (null)
   37 36   Halt         0  0  0                                                                               00 (null)
   38 37   Transaction  0  1  42 0                                                                            01 (null)
   39 38   Integer      2  12 0                                                                               00 (null)
   40 39   Integer      1  13 0                                                                               00 (null)
   41 40   String8      0  14 0  e                                                                            00 (null)
   42 41   Integer      2  18 0                                                                               00 (null)
   43 42   Integer      1  19 0                                                                               00 (null)
   44 43   Goto         0  1  0                                                                               00 (null)


_______________________________________________
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: Does SQLITE ever optimize index creation based on another index?

R Smith-2
On 2019/04/30 2:10 AM, Deon Brewis wrote:
> Given the SQL below, FooX is a covered index for x on Foo.
>
> I want to create FooXB as a second index on x in Foo. Since 'x' is covered on FooX it should be cheaper to build FooXB from index FooX, than from table Foo. However, as far as I can tell from the from the opcodes of the index creation it doesn't do this (OpenRead uses rootpage=2 instead of 3). Is my understanding correct?

Not quite. This is a good example of something that "feels" like it
should be better, just isn't.

Unless Foo(x) is a partial Index and the new index can somehow indicate
that it has the same partiality as the original index (which it can't
unless it's exactly equal, in which case, it's useless), there can be no
advantage.

Keep in mind that, in SQLite, a table is nothing less than a covering
Index itself with the row_id as the indexer (or the actual PK in the
case of WITHOUT ROWID tables). There is no reason why it itself (being
an Index) should be any slower to "walk" than any other Index, in fact a
lookup via any other index will include an extra step (the lookup
itself) that you don't have when walking the table index itself (aka
doing a "table scan"). It's just better for anything where you access
any field that are not in the existing index, and not worse for those
that are.

There might be a small but real advantage if the field (that was indexed
on) appeared at the end of very long list of fields or very large
fields, i.e. hidden at the back end of the column list with really large
(long-to-read) columns preceding it - meaning the existing Index would
already have singled out that bit of data - but it's a very small
likelihood and use-case though. (Meaning that it's unlikely for people
to make multiple Indexes on the same field(s), so investing the effort
and code-bloat in catering for the optimization it, which would only
ever benefit it in the case where the column IS at the back of big other
columns, would be of dubious benefit).


> And if my understanding is correct, is there any scenarios in which I can coerce SQLITE to build a new index based on data in an existing index?
>
>
> drop table Foo;
> create table Foo(x text, y text, z text);
>
> insert into Foo(x) values("elephant");
> insert into Foo(x) values("cat");
> insert into Foo(x) values("giraffe");
> insert into Foo(x) values("dog");
> insert into Foo(x) values("zebra");
> insert into Foo(x) values("lion");
> insert into Foo(x) values("panther");
>
> create index FooX on Foo(x);
> create index FooXB on Foo(substr(x,2,1)) where substr(x,2,1) > 'e';


As an aside - if your INSERTs above was a "find the odd one out" puzzle,
I vote that the answer would be "panther". :)


Cheers,

Ryan


_______________________________________________
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] Re: Does SQLITE ever optimize index creation based on another index?

Hick Gunter
AFAIK it is considered good practice to group fields used in indices at the beginning of the table definition (because they tend to get referenced most) and BLOB fields at the end (because acessing fields behind a BLOB - which is "large" by definition - tends to take more effort).

So the optimization would not benefit a "properly designed" schema anyway.

-----Urspr√ľngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von R Smith
Gesendet: Dienstag, 30. April 2019 13:54
An: [hidden email]
Betreff: [EXTERNAL] Re: [sqlite] Does SQLITE ever optimize index creation based on another index?

On 2019/04/30 2:10 AM, Deon Brewis wrote:
> Given the SQL below, FooX is a covered index for x on Foo.
>
> I want to create FooXB as a second index on x in Foo. Since 'x' is covered on FooX it should be cheaper to build FooXB from index FooX, than from table Foo. However, as far as I can tell from the from the opcodes of the index creation it doesn't do this (OpenRead uses rootpage=2 instead of 3). Is my understanding correct?

Not quite. This is a good example of something that "feels" like it should be better, just isn't.

Unless Foo(x) is a partial Index and the new index can somehow indicate that it has the same partiality as the original index (which it can't unless it's exactly equal, in which case, it's useless), there can be no advantage.

Keep in mind that, in SQLite, a table is nothing less than a covering Index itself with the row_id as the indexer (or the actual PK in the case of WITHOUT ROWID tables). There is no reason why it itself (being an Index) should be any slower to "walk" than any other Index, in fact a lookup via any other index will include an extra step (the lookup
itself) that you don't have when walking the table index itself (aka doing a "table scan"). It's just better for anything where you access any field that are not in the existing index, and not worse for those that are.

There might be a small but real advantage if the field (that was indexed
on) appeared at the end of very long list of fields or very large fields, i.e. hidden at the back end of the column list with really large
(long-to-read) columns preceding it - meaning the existing Index would already have singled out that bit of data - but it's a very small likelihood and use-case though. (Meaning that it's unlikely for people to make multiple Indexes on the same field(s), so investing the effort and code-bloat in catering for the optimization it, which would only ever benefit it in the case where the column IS at the back of big other columns, would be of dubious benefit).


> And if my understanding is correct, is there any scenarios in which I can coerce SQLITE to build a new index based on data in an existing index?
>
>
> drop table Foo;
> create table Foo(x text, y text, z text);
>
> insert into Foo(x) values("elephant"); insert into Foo(x)
> values("cat"); insert into Foo(x) values("giraffe"); insert into
> Foo(x) values("dog"); insert into Foo(x) values("zebra"); insert into
> Foo(x) values("lion"); insert into Foo(x) values("panther");
>
> create index FooX on Foo(x);
> create index FooXB on Foo(substr(x,2,1)) where substr(x,2,1) > 'e';


As an aside - if your INSERTs above was a "find the odd one out" puzzle, I vote that the answer would be "panther". :)


Cheers,

Ryan


_______________________________________________
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