SQLite Forum

Query shape to get plan with SeekGE on a composite key
Login

Query shape to get plan with SeekGE on a composite key

(1) By David Matson (dmatson) on 2021-07-13 23:04:30 [link] [source]

I'm moving some data access logic from an ISAM-style DB to SQLite. The ISAM-style code did a single SeekGE on a composite key for a table that includes a BLOB column as part of the key. Is there a way to shape a SQL query such that the SQLite query planner will do a single SeekGE on the entire composite key? (In particular, in this case I just want to find the next key according to the table's primary key ordering, which in theory should be able to be done quite efficiently. Since this is a WITHOUT ROWID table, I'd hope it doesn't even need to touch the page with the actual row data and just use the b-tree pages with the primary key values.)

Here's the table, with some sample data:

sqlite> CREATE TABLE Test(KeyPart1 INTEGER, KeyPart2 BLOB, KeyPart3 INTEGER, KeyPart4 INTEGER, Value BLOB, PRIMARY KEY(KeyPart1, KeyPart2, KeyPart3, KeyPart4)) WITHOUT ROWID;
sqlite> INSERT INTO Test(KeyPart1, KeyPart2, KeyPart3, KeyPart4, Value) VALUES(1, x'abcdef', 2, 3, x'deadbeef');
sqlite> INSERT INTO Test(KeyPart1, KeyPart2, KeyPart3, KeyPart4, Value) VALUES(1, x'abcdef', 3, 4, x'baadc0de');
sqlite> INSERT INTO Test(KeyPart1, KeyPart2, KeyPart3, KeyPart4, Value) VALUES(1, x'abcdef0123', 0, 1, x'beadbead');
sqlite> INSERT INTO Test(KeyPart1, KeyPart2, KeyPart3, KeyPart4, Value) VALUES(2, x'012345', 2, 5, x'cadbed');
sqlite> INSERT INTO Test(KeyPart1, KeyPart2, KeyPart3, KeyPart4, Value) VALUES(3, x'01', 1, 6, x'beadcafe');

The query I started with gets a SeekGE only on the first column of the key. In the case where most values in the table have the same value for the first key, it has basically the same performance as a table scan (far worse than the old ISAM-style database in terms of CPU, File, and Disk I/O usage according to performance traces):

sqlite> SELECT KeyPart1, hex(KeyPart2), KeyPart3, KeyPart4 FROM Test WHERE KeyPart1 > 1 OR (KeyPart1 = 1 AND (KeyPart2 > x'abcdef' OR (KeyPart2 = x'abcdef' AND (KeyPart3 > 2 OR (KeyPart3 = 2 AND KeyPart4 > 3))))) ORDER BY KeyPart1, KeyPart2, KeyPart3, KeyPart4 LIMIT 1;
1|ABCDEF|3|4
sqlite> EXPLAIN QUERY PLAN SELECT KeyPart1, hex(KeyPart2), KeyPart3, KeyPart4 FROM Test WHERE KeyPart1 > 1 OR (KeyPart1 = 1 AND (KeyPart2 > x'abcdef' OR (KeyPart2 = x'abcdef' AND (KeyPart3 > 2 OR (KeyPart3 = 2 AND KeyPart4 > 3))))) ORDER BY KeyPart1, KeyPart2, KeyPart3, KeyPart4 LIMIT 1;
QUERY PLAN
`--SEARCH Test USING PRIMARY KEY (KeyPart1>?)
sqlite> EXPLAIN SELECT KeyPart1, hex(KeyPart2), KeyPart3, KeyPart4 FROM Test WHERE KeyPart1 > 1 OR (KeyPart1 = 1 AND (KeyPart2 > x'abcdef' OR (KeyPart2 = x'abcdef' AND (KeyPart3 > 2 OR (KeyPart3 = 2 AND KeyPart4 > 3))))) ORDER BY KeyPart1, KeyPart2, KeyPart3, KeyPart4 LIMIT 1;
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     29    0                    0   Start at 29
1     Noop           1     9     0                    0
2     Integer        1     1     0                    0   r[1]=1; LIMIT counter
3     OpenRead       2     2     0     k(4,,,,)       0   root=2 iDb=0; sqlite_autoindex_Test_1
4     Integer        1     2     0                    0   r[2]=1
5     SeekGE         2     28    2     1              0   key=r[2]
6       Column         2     0     3                    0   r[3]=Test.KeyPart1
7       Gt             4     20    3     BINARY-8       68  if r[3]>r[4] goto 20
8       Column         2     0     3                    0   r[3]=Test.KeyPart1
9       Ne             4     27    3     BINARY-8       84  if r[3]!=r[4] goto 27
10      Column         2     1     3                    0   r[3]=Test.KeyPart2
11      Gt             5     20    3     BINARY-8       65  if r[3]>r[5] goto 20
12      Column         2     1     3                    0   r[3]=Test.KeyPart2
13      Ne             5     27    3     BINARY-8       81  if r[3]!=r[5] goto 27
14      Column         2     2     3                    0   r[3]=Test.KeyPart3
15      Gt             6     20    3     BINARY-8       68  if r[3]>r[6] goto 20
16      Column         2     2     3                    0   r[3]=Test.KeyPart3
17      Ne             6     27    3     BINARY-8       84  if r[3]!=r[6] goto 27
18      Column         2     3     3                    0   r[3]=Test.KeyPart4
19      Le             7     27    3     BINARY-8       84  if r[3]<=r[7] goto 27
20      Column         2     0     8                    0   r[8]=Test.KeyPart1
21      Column         2     1     3                    0   r[3]=Test.KeyPart2
22      Function       0     3     9     hex(1)         0   r[9]=func(r[3])
23      Column         2     2     10                   0   r[10]=Test.KeyPart3
24      Column         2     3     11                   0   r[11]=Test.KeyPart4
25      ResultRow      8     4     0                    0   output=r[8..11]
26      DecrJumpZero   1     28    0                    0   if (--r[1])==0 goto 28
27    Next           2     6     0                    0
28    Halt           0     0     0                    0
29    Transaction    0     0     1     0              1   usesStmtJournal=0
30    Integer        1     4     0                    0   r[4]=1
31    Blob           3     5     0     ???             0   r[5]=??? (len=3)
32    Integer        2     6     0                    0   r[6]=2
33    Integer        3     7     0                    0   r[7]=3
34    Goto           0     1     0                    0

With a more flattened query shape, it's probably better but still not a single SeekGE and uses a temp b-tree:

sqlite> SELECT KeyPart1, hex(KeyPart2), KeyPart3, KeyPart4 FROM Test WHERE (KeyPart1 = 1 AND KeyPart2 = x'abcdef' AND KeyPart3 = 2 AND KeyPart4 > 3) OR (KeyPart1 = 1 AND KeyPart2 = x'abcdef' AND KeyPart3 > 2) OR (KeyPart1 = 1 AND KeyPart2 > x'abcdef') OR (KeyPart1 > 1) ORDER BY KeyPart1, KeyPart2, KeyPart3, KeyPart4 LIMIT 1;
1|ABCDEF|3|4
sqlite> EXPLAIN QUERY PLAN SELECT KeyPart1, hex(KeyPart2), KeyPart3, KeyPart4 FROM Test WHERE (KeyPart1 = 1 AND KeyPart2 = x'abcdef' AND KeyPart3 = 2 AND KeyPart4 > 3) OR (KeyPart1 = 1 AND KeyPart2 = x'abcdef' AND KeyPart3 > 2) OR (KeyPart1 = 1 AND KeyPart2 > x'abcdef') OR (KeyPart1 > 1) ORDER BY KeyPart1, KeyPart2, KeyPart3, KeyPart4 LIMIT 1;
QUERY PLAN
|--MULTI-INDEX OR
|  |--INDEX 1
|  |  `--SEARCH Test USING PRIMARY KEY (KeyPart1=? AND KeyPart2=? AND KeyPart3=? AND KeyPart4>?)
|  |--INDEX 2
|  |  `--SEARCH Test USING PRIMARY KEY (KeyPart1=? AND KeyPart2=? AND KeyPart3>?)
|  |--INDEX 3
|  |  `--SEARCH Test USING PRIMARY KEY (KeyPart1=? AND KeyPart2>?)
|  `--INDEX 4
|     `--SEARCH Test USING PRIMARY KEY (KeyPart1>?)
`--USE TEMP B-TREE FOR ORDER BY
sqlite> EXPLAIN SELECT KeyPart1, hex(KeyPart2), KeyPart3, KeyPart4 FROM Test WHERE (KeyPart1 = 1 AND KeyPart2 = x'abcdef' AND KeyPart3 = 2 AND KeyPart4 > 3) OR (KeyPart1 = 1 AND KeyPart2 = x'abcdef' AND KeyPart3 > 2) OR (KeyPart1 = 1 AND KeyPart2 > x'abcdef') OR (KeyPart1 > 1) ORDER BY KeyPart1, KeyPart2, KeyPart3, KeyPart4 LIMIT 1;
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     79    0                    0   Start at 79
1     OpenEphemeral  1     9     0     k(4,B,B,B,B)   0   nColumn=9
2     Integer        1     1     0                    0   r[1]=1; LIMIT counter
3     OpenRead       0     2     0     k(4,,,,)       0   root=2 iDb=0; Test
4     OpenEphemeral  3     4     0     k(4,,,,)       0   nColumn=4
5     Integer        56    2     0                    0   r[2]=56
6     Integer        1     4     0                    0   r[4]=1
7     Blob           3     5     0     ???             0   r[5]=??? (len=3)
8     Integer        2     6     0                    0   r[6]=2
9     Integer        3     7     0                    0   r[7]=3
10    SeekGT         0     20    4     4              0   key=r[4..7]
11      IdxGT          0     20    4     3              0   key=r[4..6]
12      Column         0     0     8                    0   r[8]=Test.KeyPart1
13      Column         0     1     9                    0   r[9]=Test.KeyPart2
14      Column         0     2     10                   0   r[10]=Test.KeyPart3
15      Column         0     3     11                   0   r[11]=Test.KeyPart4
16      MakeRecord     8     4     3                    0   r[3]=mkrec(r[8..11])
17      IdxInsert      3     3     8     4              0   key=r[3]
18      Gosub          2     57    0                    0
19    Next           0     11    0                    0
20    Integer        1     12    0                    0   r[12]=1
21    Blob           3     13    0     ???             0   r[13]=??? (len=3)
22    Integer        2     14    0                    0   r[14]=2
23    SeekGT         0     34    12    3              0   key=r[12..14]
24      IdxGT          0     34    12    2              0   key=r[12..13]
25      Column         0     0     8                    0   r[8]=Test.KeyPart1
26      Column         0     1     9                    0   r[9]=Test.KeyPart2
27      Column         0     2     10                   0   r[10]=Test.KeyPart3
28      Column         0     3     11                   0   r[11]=Test.KeyPart4
29      Found          3     33    8     4              0   key=r[8..11]
30      MakeRecord     8     4     3                    0   r[3]=mkrec(r[8..11])
31      IdxInsert      3     3     8     4              16  key=r[3]
32      Gosub          2     57    0                    0
33    Next           0     24    0                    0
34    Integer        1     15    0                    0   r[15]=1
35    Blob           3     16    0     ???             0   r[16]=??? (len=3)
36    SeekGT         0     47    15    2              0   key=r[15..16]
37      IdxGT          0     47    15    1              0   key=r[15]
38      Column         0     0     8                    0   r[8]=Test.KeyPart1
39      Column         0     1     9                    0   r[9]=Test.KeyPart2
40      Column         0     2     10                   0   r[10]=Test.KeyPart3
41      Column         0     3     11                   0   r[11]=Test.KeyPart4
42      Found          3     46    8     4              0   key=r[8..11]
43      MakeRecord     8     4     3                    0   r[3]=mkrec(r[8..11])
44      IdxInsert      3     3     8     4              16  key=r[3]
45      Gosub          2     57    0                    0
46    Next           0     37    0                    0
47    Integer        1     17    0                    0   r[17]=1
48    SeekGT         0     56    17    1              0   key=r[17]
49      Column         0     0     8                    0   r[8]=Test.KeyPart1
50      Column         0     1     9                    0   r[9]=Test.KeyPart2
51      Column         0     2     10                   0   r[10]=Test.KeyPart3
52      Column         0     3     11                   0   r[11]=Test.KeyPart4
53      Found          3     55    8     4              0   key=r[8..11]
54      Gosub          2     57    0                    0
55    Next           0     49    0                    0
56    Goto           0     71    0                    0
57    Column         0     0     18                   0   r[18]=Test.KeyPart1
58    Column         0     1     19                   0   r[19]=Test.KeyPart2
59    Column         0     2     20                   0   r[20]=Test.KeyPart3
60    Column         0     3     21                   0   r[21]=Test.KeyPart4
61    Sequence       1     22    0                    0   r[22]=cursor[1].ctr++
62    IfNotZero      1     66    0                    0   if r[1]!=0 then r[1]--, goto 66
63    Last           1     0     0                    0
64    IdxLE          1     70    18    4              0   key=r[18..21]
65    Delete         1     0     0                    0
66    Column         0     1     28                   0   r[28]=Test.KeyPart2
67    Function       0     28    23    hex(1)         0   r[23]=func(r[28])
68    MakeRecord     18    6     27                   0   r[27]=mkrec(r[18..23])
69    IdxInsert      1     27    18    6              0   key=r[27]
70    Return         2     0     0                    0
71    Sort           1     78    0                    0
72      Column         1     3     26                   0   r[26]=KeyPart4
73      Column         1     2     25                   0   r[25]=KeyPart3
74      Column         1     5     24                   0   r[24]=hex(KeyPart2)
75      Column         1     0     23                   0   r[23]=KeyPart1
76      ResultRow      23    4     0                    0   output=r[23..26]
77    Next           1     72    0                    0
78    Halt           0     0     0                    0
79    Transaction    0     0     1     0              1   usesStmtJournal=0
80    Goto           0     1     0                    0

Is there a different query shape I can use that makes it clearer I have the values to make up a whole composite key that I want to use for a Seek* operation?

Thanks,

David

(2) By Richard Hipp (drh) on 2021-07-14 00:02:41 in reply to 1 [link] [source]

Use a vector comparison in the WHERE clause:

SELECT KeyPart1, hex(KeyPart2), KeyPart3, KeyPart4 
  FROM Test 
 WHERE (KeyPart1,KeyPart2,KeyPart3,KeyPart4) > (1,x'abcdef',2,3)
 ORDER BY KeyPart1, KeyPart2, KeyPart3, KeyPart4
 LIMIT 1;

(3) By David Matson (dmatson) on 2021-07-14 00:13:19 in reply to 2 [source]

Excellent - that's just what I was looking for.

Thanks, Richard!

David

sqlite> SELECT KeyPart1, hex(KeyPart2), KeyPart3, KeyPart4 FROM Test WHERE (KeyPart1,KeyPart2,KeyPart3,KeyPart4) > (1,x'abcdef',2,3) ORDER BY KeyPart1, KeyPart2, KeyPart3, KeyPart4 LIMIT 1;
1|ABCDEF|3|4
sqlite> EXPLAIN QUERY PLAN SELECT KeyPart1, hex(KeyPart2), KeyPart3, KeyPart4 FROM Test WHERE (KeyPart1,KeyPart2,KeyPart3,KeyPart4) > (1,x'abcdef',2,3) ORDER BY KeyPart1, KeyPart2, KeyPart3, KeyPart4 LIMIT 1;
QUERY PLAN
`--SEARCH Test USING PRIMARY KEY ((KeyPart1,KeyPart2,KeyPart3,KeyPart4)>(?,?,?,?))
sqlite> EXPLAIN SELECT KeyPart1, hex(KeyPart2), KeyPart3, KeyPart4 FROM Test WHERE (KeyPart1,KeyPart2,KeyPart3,KeyPart4) > (1,x'abcdef',2,3) ORDER BY KeyPart1, KeyPart2, KeyPart3, KeyPart4 LIMIT 1;
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     39    0                    0   Start at 39
1     Noop           1     9     0                    0
2     Integer        1     1     0                    0   r[1]=1; LIMIT counter
3     OpenRead       2     2     0     k(4,,,,)       0   root=2 iDb=0; sqlite_autoindex_Test_1
4     Integer        1     2     0                    0   r[2]=1
5     Blob           3     3     0     ???             0   r[3]=??? (len=3)
6     Integer        2     4     0                    0   r[4]=2
7     Integer        3     5     0                    0   r[5]=3
8     IsNull         2     38    0                    0   if r[2]==NULL goto 38
9     SeekGE         2     38    2     4              0   key=r[2..5]
10      Integer        1     6     0                    0   r[6]=1
11      Column         2     0     7                    0   r[7]=Test.KeyPart1
12      Gt             8     29    7     BINARY-8       68  if r[7]>r[8] goto 29
13      ElseEq         0     16    0                    0
14      ZeroOrNull     7     6     8                    0   r[6] = 0 OR NULL
15      Goto           0     29    0                    0
16      Column         2     1     7                    0   r[7]=Test.KeyPart2
17      Gt             9     29    7     BINARY-8       65  if r[7]>r[9] goto 29
18      ElseEq         0     21    0                    0
19      ZeroOrNull     7     6     9                    0   r[6] = 0 OR NULL
20      Goto           0     29    0                    0
21      Column         2     2     7                    0   r[7]=Test.KeyPart3
22      Gt             10    29    7     BINARY-8       68  if r[7]>r[10] goto 29
23      ElseEq         0     26    0                    0
24      ZeroOrNull     7     6     10                   0   r[6] = 0 OR NULL
25      Goto           0     29    0                    0
26      Column         2     3     7                    0   r[7]=Test.KeyPart4
27      Gt             11    29    7     BINARY-8       68  if r[7]>r[11] goto 29
28      ZeroOrNull     7     6     11                   0   r[6] = 0 OR NULL
29      IfNot          6     37    1                    0
30      Column         2     0     12                   0   r[12]=Test.KeyPart1
31      Column         2     1     6                    0   r[6]=Test.KeyPart2
32      Function       0     6     13    hex(1)         0   r[13]=func(r[6])
33      Column         2     2     14                   0   r[14]=Test.KeyPart3
34      Column         2     3     15                   0   r[15]=Test.KeyPart4
35      ResultRow      12    4     0                    0   output=r[12..15]
36      DecrJumpZero   1     38    0                    0   if (--r[1])==0 goto 38
37    Next           2     10    0                    0
38    Halt           0     0     0                    0
39    Transaction    0     0     1     0              1   usesStmtJournal=0
40    Integer        1     8     0                    0   r[8]=1
41    Blob           3     9     0     ???             0   r[9]=??? (len=3)
42    Integer        2     10    0                    0   r[10]=2
43    Integer        3     11    0                    0   r[11]=3
44    Goto           0     1     0                    0
sqlite>