Another Partial Index optimization opportunity (INSERT)

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

Another Partial Index optimization opportunity (INSERT)

Deon Brewis
Hi, I previously reported that an UPDATE of a table containing an Expression and/or Partial Index will unnecessarily touch the expression and/or partial index. I see both are now fixed in the 3.26.0 2018-09-19 codebase. Thank you so much - it works great!

However, while testing it, I also noticed there is an opportunity for this INSERT optimization:

CREATE TABLE Foo(x, z);
CREATE INDEX FooPartialZ on Foo(z) WHERE z > 42;

explain INSERT INTO foo(x) VALUES(5);
explain INSERT INTO foo(z) VALUES(10);

Neither of these statements should affect FooPartialZ, the first is an unused column, the second is out of range. But currently they both will access FooPartialZ.

These are probably trickier to implement though (especially the second one), and not nearly as important to us as the UPDATE optimizations, but it may be useful for someone out there.

- Deon

_______________________________________________
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: Another Partial Index optimization opportunity (INSERT)

David Raymond
Could you show us the plans for the version you're looking at? When I'm looking at it with 3.25.0 the index inserts are guarded by conditionals such that that index is opened, but never actually accessed when run with the values in your examples.

They query plan is a *generic one* that gets used for both of your inserts, so may look a little weird for a single row. But it's got to consider the default for non-provided fields, etc.

Starting at line 6 it sets register 4 to null, then on line 7 checks z against 42 to see if it needs to make a record to put into the index, skipping the index record creation if it doesn't qualify. Line 11 says hey, if there isn't a record to insert, then skip past the index insert and go on to dealing with the main table.



sqlite> explain insert into foo(x) values (5);
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     16    0                    00  Start at 16
1     OpenWrite      0     2     0     2              00  root=2 iDb=0; Foo
2     OpenWrite      1     3     0     k(2,,)         00  root=3 iDb=0; FooPartialZ
3     NewRowid       0     1     0                    00  r[1]=rowid
4     Integer        5     2     0                    00  r[2]=5
5     Noop           0     0     0                    00  uniqueness check for FooPartialZ
6     Null           0     4     0                    00  r[4]=NULL
7     Le             8     11    3     (BINARY)       51  if r[3]<=r[8] goto 11
8     SCopy          3     5     0                    00  r[5]=r[3]; z
9     IntCopy        1     6     0                    00  r[6]=r[1]; rowid
10    MakeRecord     5     2     4                    00  r[4]=mkrec(r[5..6]); for FooPartialZ
11    IsNull         4     13    0                    00  if r[4]==NULL goto 13
12    IdxInsert      1     4     5     2              10  key=r[4]
13    MakeRecord     2     2     7                    00  r[7]=mkrec(r[2..3])
14    Insert         0     7     1     Foo            39  intkey=r[1] data=r[7]
15    Halt           0     0     0                    00
16    Transaction    0     1     2     0              01  usesStmtJournal=0
17    Null           0     3     0                    00  r[3]=NULL
18    Integer        42    8     0                    00  r[8]=42
19    Goto           0     1     0                    00


sqlite> explain insert into foo(z) values (10);
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     16    0                    00  Start at 16
1     OpenWrite      0     2     0     2              00  root=2 iDb=0; Foo
2     OpenWrite      1     3     0     k(2,,)         00  root=3 iDb=0; FooPartialZ
3     NewRowid       0     1     0                    00  r[1]=rowid
4     Integer        10    3     0                    00  r[3]=10
5     Noop           0     0     0                    00  uniqueness check for FooPartialZ
6     Null           0     4     0                    00  r[4]=NULL
7     Le             8     11    3     (BINARY)       51  if r[3]<=r[8] goto 11
8     SCopy          3     5     0                    00  r[5]=r[3]; z
9     IntCopy        1     6     0                    00  r[6]=r[1]; rowid
10    MakeRecord     5     2     4                    00  r[4]=mkrec(r[5..6]); for FooPartialZ
11    IsNull         4     13    0                    00  if r[4]==NULL goto 13
12    IdxInsert      1     4     5     2              10  key=r[4]
13    MakeRecord     2     2     7                    00  r[7]=mkrec(r[2..3])
14    Insert         0     7     1     Foo            39  intkey=r[1] data=r[7]
15    Halt           0     0     0                    00
16    Transaction    0     1     2     0              01  usesStmtJournal=0
17    Null           0     2     0                    00  r[2]=NULL
18    Integer        42    8     0                    00  r[8]=42
19    Goto           0     1     0                    00

-----Original Message-----
From: sqlite-users [mailto:[hidden email]] On Behalf Of Deon Brewis
Sent: Thursday, September 20, 2018 11:30 AM
To: SQLite mailing list
Subject: [sqlite] Another Partial Index optimization opportunity (INSERT)

Hi, I previously reported that an UPDATE of a table containing an Expression and/or Partial Index will unnecessarily touch the expression and/or partial index. I see both are now fixed in the 3.26.0 2018-09-19 codebase. Thank you so much - it works great!

However, while testing it, I also noticed there is an opportunity for this INSERT optimization:

CREATE TABLE Foo(x, z);
CREATE INDEX FooPartialZ on Foo(z) WHERE z > 42;

explain INSERT INTO foo(x) VALUES(5);
explain INSERT INTO foo(z) VALUES(10);

Neither of these statements should affect FooPartialZ, the first is an unused column, the second is out of range. But currently they both will access FooPartialZ.

These are probably trickier to implement though (especially the second one), and not nearly as important to us as the UPDATE optimizations, but it may be useful for someone out there.

- Deon

_______________________________________________
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: Another Partial Index optimization opportunity (INSERT)

Deon Brewis
You are of course very right. (The UPDATE loaded the existing column value from the row before it did the 'Le', which is why it was performing an index delete+insert later on. INSERT doesn't do that.).

I was expecting it to be kicked out of the query plan completely with an unused column, but as is I'm sure it will be fine with just the runtime checks.

Thanks!
- Deon

-----Original Message-----
From: sqlite-users <[hidden email]> On Behalf Of David Raymond
Sent: Thursday, September 20, 2018 9:07 AM
To: SQLite mailing list <[hidden email]>
Subject: Re: [sqlite] Another Partial Index optimization opportunity (INSERT)

Could you show us the plans for the version you're looking at? When I'm looking at it with 3.25.0 the index inserts are guarded by conditionals such that that index is opened, but never actually accessed when run with the values in your examples.

They query plan is a *generic one* that gets used for both of your inserts, so may look a little weird for a single row. But it's got to consider the default for non-provided fields, etc.

Starting at line 6 it sets register 4 to null, then on line 7 checks z against 42 to see if it needs to make a record to put into the index, skipping the index record creation if it doesn't qualify. Line 11 says hey, if there isn't a record to insert, then skip past the index insert and go on to dealing with the main table.



sqlite> explain insert into foo(x) values (5);
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     16    0                    00  Start at 16
1     OpenWrite      0     2     0     2              00  root=2 iDb=0; Foo
2     OpenWrite      1     3     0     k(2,,)         00  root=3 iDb=0; FooPartialZ
3     NewRowid       0     1     0                    00  r[1]=rowid
4     Integer        5     2     0                    00  r[2]=5
5     Noop           0     0     0                    00  uniqueness check for FooPartialZ
6     Null           0     4     0                    00  r[4]=NULL
7     Le             8     11    3     (BINARY)       51  if r[3]<=r[8] goto 11
8     SCopy          3     5     0                    00  r[5]=r[3]; z
9     IntCopy        1     6     0                    00  r[6]=r[1]; rowid
10    MakeRecord     5     2     4                    00  r[4]=mkrec(r[5..6]); for FooPartialZ
11    IsNull         4     13    0                    00  if r[4]==NULL goto 13
12    IdxInsert      1     4     5     2              10  key=r[4]
13    MakeRecord     2     2     7                    00  r[7]=mkrec(r[2..3])
14    Insert         0     7     1     Foo            39  intkey=r[1] data=r[7]
15    Halt           0     0     0                    00
16    Transaction    0     1     2     0              01  usesStmtJournal=0
17    Null           0     3     0                    00  r[3]=NULL
18    Integer        42    8     0                    00  r[8]=42
19    Goto           0     1     0                    00


sqlite> explain insert into foo(z) values (10);
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     16    0                    00  Start at 16
1     OpenWrite      0     2     0     2              00  root=2 iDb=0; Foo
2     OpenWrite      1     3     0     k(2,,)         00  root=3 iDb=0; FooPartialZ
3     NewRowid       0     1     0                    00  r[1]=rowid
4     Integer        10    3     0                    00  r[3]=10
5     Noop           0     0     0                    00  uniqueness check for FooPartialZ
6     Null           0     4     0                    00  r[4]=NULL
7     Le             8     11    3     (BINARY)       51  if r[3]<=r[8] goto 11
8     SCopy          3     5     0                    00  r[5]=r[3]; z
9     IntCopy        1     6     0                    00  r[6]=r[1]; rowid
10    MakeRecord     5     2     4                    00  r[4]=mkrec(r[5..6]); for FooPartialZ
11    IsNull         4     13    0                    00  if r[4]==NULL goto 13
12    IdxInsert      1     4     5     2              10  key=r[4]
13    MakeRecord     2     2     7                    00  r[7]=mkrec(r[2..3])
14    Insert         0     7     1     Foo            39  intkey=r[1] data=r[7]
15    Halt           0     0     0                    00
16    Transaction    0     1     2     0              01  usesStmtJournal=0
17    Null           0     2     0                    00  r[2]=NULL
18    Integer        42    8     0                    00  r[8]=42
19    Goto           0     1     0                    00

-----Original Message-----
From: sqlite-users [mailto:[hidden email]] On Behalf Of Deon Brewis
Sent: Thursday, September 20, 2018 11:30 AM
To: SQLite mailing list
Subject: [sqlite] Another Partial Index optimization opportunity (INSERT)

Hi, I previously reported that an UPDATE of a table containing an Expression and/or Partial Index will unnecessarily touch the expression and/or partial index. I see both are now fixed in the 3.26.0 2018-09-19 codebase. Thank you so much - it works great!

However, while testing it, I also noticed there is an opportunity for this INSERT optimization:

CREATE TABLE Foo(x, z);
CREATE INDEX FooPartialZ on Foo(z) WHERE z > 42;

explain INSERT INTO foo(x) VALUES(5);
explain INSERT INTO foo(z) VALUES(10);

Neither of these statements should affect FooPartialZ, the first is an unused column, the second is out of range. But currently they both will access FooPartialZ.

These are probably trickier to implement though (especially the second one), and not nearly as important to us as the UPDATE optimizations, but it may be useful for someone out there.

- Deon

_______________________________________________
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