SQLite Forum

Query performance regression after v3.33.0 (OP_SeekScan?)
Login

Query performance regression after v3.33.0 (OP_SeekScan?)

(1) By mlin (dnamlin) on 2021-06-01 06:30:08 [link] [source]

My application hit a severe performance regression upgrading SQLite to v3.35.4 from v3.33.0, I think possibly due to the new OP_SeekScan feature. I've distilled a reproduction in this gist:

https://gist.github.com/mlin/a5e9ef7ca0d6583b8397a0fb324e4327

Briefly, our database stores a graph, with nodes, edges connecting them, and indexes thereof. Then we get a 1-column temporary table providing a certain subset of node IDs, and we wish to query for those edges touching only nodes included in the subset:

SELECT count(_rowid_)
FROM edge
WHERE node_from IN temp.sub_nodes AND node_to IN temp.sub_nodes

With the numerous constants in the Python script, SQLite v3.35.5 runs this query roughly 500X slower than v3.31.1. (My Rust application, on which the repro script is based, hit the problem after upgrading from v3.33.0 to v3.35.4)

The high-level "explain query plans" are identical between the two versions, but, the opcode-level "explain" results differ (shown in the gist), notably including the new SeekScan operation. I speculate perhaps the two "IN" clauses in our query lead to some kind of quadratic cost to the new scan attempt?

Thanks in advance for advice/attention.

(2) By mlin (dnamlin) on 2021-06-01 11:54:02 in reply to 1 [link] [source]

Brief PS: simply removing indexes from this example (deleting lines 40 & 41 from my repro script) makes the query hundreds of times faster using v3.35.5, and the plan doesn't use SeekScan in that case. It smells to me like the SeekScan scanning effort parameter (This.P1) might somehow be off by orders of magnitude in the circumstances I've created.

(3) By anonymous on 2021-06-01 13:54:47 in reply to 1 [link] [source]

Any reason not to use a three-way join?

    select count(*)
    from edge,
        temp.sub_nodes src on src.node_id=node_from,
        temp.sub_nodes dst on dst.node_id=node_to;

(4) By Richard Hipp (drh) on 2021-06-01 16:48:13 in reply to 1 [link] [source]

As a temporary work-around, please try modifying your query by putting a single "+" in from of the node_from in the WHERE clause:

SELECT count(_rowid_)
FROM edge
WHERE +node_from IN temp.sub_nodes AND node_to IN temp.sub_nodes;
  --  ^-- extra "+" here

(5) By mlin (dnamlin) on 2021-06-01 20:51:46 in reply to 3 [link] [source]

Any reason not to use a three-way join?

Thanks for this suggestion! It does solve the problem in SQLite v3.35, but makes it ~equally as fast as the original version in SQLite v3.31, which suggests the query planner is, impressively, supposed to run my original (more concise and readable?) version in effectively the same way.

Original plus Richard's workaround:

EXPLAIN QUERY PLAN SELECT count(_rowid_) FROM edge
WHERE +node_from IN temp.sub_nodes AND node_to IN temp.sub_nodes
SEARCH TABLE edge USING COVERING INDEX edge_to_from (node_to=?)
USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR
USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR

Three-way join:

EXPLAIN QUERY PLAN SELECT count(edge._rowid_) FROM edge,
     temp.sub_nodes sub_from ON sub_from.node_id = node_from,
     temp.sub_nodes sub_to ON sub_to.node_id = node_to
SCAN TABLE sub_nodes AS sub_from
SEARCH TABLE edge USING COVERING INDEX edge_from_to (node_from=?)
SEARCH TABLE sub_nodes AS sub_to USING INTEGER PRIMARY KEY (rowid=?)

The runtimes of these two queries remain roughly equivalent with increasing problem size.

(6) By mlin (dnamlin) on 2021-06-01 20:55:12 in reply to 4 [link] [source]

Yes, this worked like a charm, both in my repro script and in the full application. With the hint, the bytecode no longer uses SeekScan -- one more piece of evidence pointing in that direction. Thank you!!

(7) By Keith Medcalf (kmedcalf) on 2021-06-01 22:34:26 in reply to 1 [link] [source]

Should not that query be exactly equal to:

SELECT count(_rowid_)
  FROM edge
 WHERE EXISTS (SELECT * FROM sub_nodes WHERE node_id == node_from)
   AND EXISTS (SELECT * FROM sub_nodes WHERE node_id == node_to)
;

since value IN table means where exists a row in table where the primary key of table == value?

(8) By mlin (dnamlin) on 2021-06-01 23:30:31 in reply to 7 [link] [source]

I can agree that these queries should produce the same exact result sets, but the query planner certainly seems to distinguish them. All with v3.35.5 and problem size N=1000000:

  • Mike's version plus Richard's hint (WHERE...IN)
EXPLAIN QUERY PLAN SELECT count(_rowid_) FROM edge
WHERE +node_from IN temp.sub_nodes AND node_to IN temp.sub_nodes

SEARCH TABLE edge USING COVERING INDEX edge_to_from (node_to=?)
USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR
USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR
  • anonymous' three-way join
EXPLAIN QUERY PLAN SELECT count(edge._rowid_) FROM edge,
     temp.sub_nodes sub_from ON sub_from.node_id = node_from,
     temp.sub_nodes sub_to ON sub_to.node_id = node_to

SCAN TABLE sub_nodes AS sub_from
SEARCH TABLE edge USING COVERING INDEX edge_from_to (node_from=?)
SEARCH TABLE sub_nodes AS sub_to USING INTEGER PRIMARY KEY (rowid=?)
  • Keith's version plus Richard's hint (WHERE...EXISTS)
EXPLAIN QUERY PLAN SELECT count(_rowid_)
  FROM edge
 WHERE EXISTS (SELECT * FROM sub_nodes WHERE node_id == +node_from)
   AND EXISTS (SELECT * FROM sub_nodes WHERE node_id == node_to)

SEARCH TABLE edge USING COVERING INDEX edge_to_from (node_to=?)
USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR
CORRELATED SCALAR SUBQUERY 1
    SEARCH TABLE sub_nodes USING INTEGER PRIMARY KEY (rowid=?)
  • Mike's or Keith's version without Richard's hint (disastrously slow, using SeekScan)
SEARCH TABLE edge USING COVERING INDEX edge_to_from (node_to=? AND node_from=?)
USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR
USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR

Beauty is in the eye of the beholder, but my version is the most concise and most closely approximates what I'd say in English ("gimme the edges whose node_from and node_to are both in sub_nodes). And SQLite v3.33.0 did great with it even without the hint.

I'm certainly learning a ton from all this though, thanks!

(9) By Keith Medcalf (kmedcalf) on 2021-06-02 00:49:47 in reply to 8 [link] [source]

Using the current tip of trunk (my version of a8d921136f) I get the following results (this is after analyze being run).

Clearly the different spellings of the same request result in wildly different query plans and vdbe code being generated, the most efficient being the "direct join" where the planner has the most latitude to choose the nesting order.

The interesting thing is that the IN form should be no less efficient that the EXISTS form, but it is.

sqlite> SELECT count(_rowid_)
   ...>   FROM edge
   ...>  WHERE node_from IN sub_nodes
   ...>    AND node_to IN sub_nodes
   ...> ;
QUERY PLAN
|--SEARCH edge USING COVERING INDEX edge_to_from (node_to=? AND node_from=?) (~44 rows)
|--USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR
`--USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     31    0                    0   Start at 31
1     Null           0     1     2                    0   r[1..2]=NULL
2     OpenRead       3     8     0     k(3,,,)        0   root=8 iDb=0; edge_to_from
3     ColumnsUsed    3     0     0     3              0
4     Explain        4     0     0     SEARCH edge USING COVERING INDEX edge_to_from (node_to=? AND node_from=?) (~44 rows)  0
5     Noop           0     0     0                    0   Begin WHERE-loop0: edge
6     Once           0     8     0                    0
7     OpenRead       4     4     0     1              0   root=4 iDb=0; sub_nodes
8     Rewind         4     26    0                    0
9       Rowid          4     3     0                    0   r[3]=rowid
10      IsNull         3     25    0                    0   if r[3]==NULL goto 25
11      Once           0     13    0                    0
12      OpenRead       5     4     0     1              0   root=4 iDb=0; sub_nodes
13      Rewind         5     25    0                    0
14        Rowid          5     4     0                    0   r[4]=rowid
15        IsNull         4     24    0                    0   if r[4]==NULL goto 24
16        SeekScan       18    19    0                    0   Scan-ahead up to 18 rows
17        SeekGE         3     24    3     2              0   key=r[3..4]
18          IdxGT          3     24    3     2              0   key=r[3..4]
19          Noop           0     0     0                    0   Begin WHERE-core
20          IdxRowid       3     5     0                    0   r[5]=rowid
21          AggStep        0     5     1     count(1)       1   accum=r[1] step(r[5])
22          Noop           0     0     0                    0   End WHERE-core
23        Next           3     18    0                    0
24      Next           5     14    0                    0
25    Next           4     9     0                    0
26    Noop           0     0     0                    0   End WHERE-loop0: edge
27    AggFinal       1     1     0     count(1)       0   accum=r[1] N=1
28    Copy           1     6     0                    0   r[6]=r[1]
29    ResultRow      6     1     0                    0   output=r[6]
30    Halt           0     0     0                    0
31    Transaction    0     0     7     0              1   usesStmtJournal=0
32    Goto           0     1     0                    0
┌────────────────┐
│ count(_rowid_) │
├────────────────┤
│ 1929           │
└────────────────┘
Run Time: real 5.817 user 5.703125 sys 0.031250
sqlite> SELECT count(_rowid_)
   ...>   FROM edge
   ...>  WHERE +node_from IN sub_nodes
   ...>    AND node_to IN sub_nodes
   ...> ;
QUERY PLAN
|--SEARCH edge USING COVERING INDEX edge_to_from (node_to=?) (~44 rows)
|--USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR
`--USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     35    0                    0   Start at 35
1     Null           0     1     2                    0   r[1..2]=NULL
2     OpenRead       3     8     0     k(3,,,)        2   root=8 iDb=0; edge_to_from
3     ColumnsUsed    3     0     0     3              0
4     Explain        4     0     0     SEARCH edge USING COVERING INDEX edge_to_from (node_to=?) (~44 rows)  0
5     Noop           0     0     0                    0   Begin WHERE-loop0: edge
6     Once           0     8     0                    0
7     OpenRead       4     4     0     1              0   root=4 iDb=0; sub_nodes
8     Rewind         4     30    0                    0
9       Rowid          4     3     0                    0   r[3]=rowid
10      IsNull         3     29    0                    0   if r[3]==NULL goto 29
11      SeekGE         3     29    3     1              0   key=r[3]
12        IdxGT          3     29    3     1              0   key=r[3]
13        Noop           0     0     0                    0   begin IN expr
14        Once           0     16    0                    0
15        OpenRead       5     4     0     1              0   root=4 iDb=0; sub_nodes
16        Column         3     1     4                    0   r[4]=edge.node_from
17        SeekRowid      5     28    4                    0   intkey=r[4]
18        Goto           0     24    0                    0
19        Goto           0     28    0                    0
20        Rewind         5     28    0                    0
21        Column         5     0     5                    0   r[5]=
22        Ne             4     28    5     BINARY-8       0   if r[5]!=r[4] goto 28
23        Goto           0     28    0                    0   end IN expr
24        Noop           0     0     0                    0   Begin WHERE-core
25        IdxRowid       3     5     0                    0   r[5]=rowid
26        AggStep        0     5     1     count(1)       1   accum=r[1] step(r[5])
27        Noop           0     0     0                    0   End WHERE-core
28      Next           3     12    0                    0
29    Next           4     9     0                    0
30    Noop           0     0     0                    0   End WHERE-loop0: edge
31    AggFinal       1     1     0     count(1)       0   accum=r[1] N=1
32    Copy           1     6     0                    0   r[6]=r[1]
33    ResultRow      6     1     0                    0   output=r[6]
34    Halt           0     0     0                    0
35    Transaction    0     0     7     0              1   usesStmtJournal=0
36    Goto           0     1     0                    0
┌────────────────┐
│ count(_rowid_) │
├────────────────┤
│ 1929           │
└────────────────┘
Run Time: real 0.124 user 0.015625 sys 0.015625
sqlite> SELECT count(_rowid_)
   ...>   FROM edge
   ...>  WHERE +node_from IN sub_nodes
   ...>    AND +node_to IN sub_nodes
   ...> ;
QUERY PLAN
|--SCAN edge (~180224 rows)
|--USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR
`--USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     39    0                    0   Start at 39
1     Null           0     1     2                    0   r[1..2]=NULL
2     OpenRead       0     3     0     2              0   root=3 iDb=0; edge
3     ColumnsUsed    0     0     0     3              0
4     Explain        4     0     0     SCAN edge (~180224 rows)  0
5     Noop           0     0     0                    0   Begin WHERE-loop0: edge
6     Rewind         0     34    0                    0
7       Noop           0     0     0                    0   begin IN expr
8       Once           0     10    0                    0
9       OpenRead       3     4     0     1              0   root=4 iDb=0; sub_nodes
10      Column         0     0     3                    0   r[3]=edge.node_from
11      SeekRowid      3     33    3                    0   intkey=r[3]
12      Goto           0     18    0                    0
13      Goto           0     33    0                    0
14      Rewind         3     33    0                    0
15      Column         3     0     4                    0   r[4]=
16      Ne             3     33    4     BINARY-8       0   if r[4]!=r[3] goto 33
17      Goto           0     33    0                    0   end IN expr
18      Noop           0     0     0                    0   begin IN expr
19      Once           0     21    0                    0
20      OpenRead       4     4     0     1              0   root=4 iDb=0; sub_nodes
21      Column         0     1     4                    0   r[4]=edge.node_to
22      SeekRowid      4     33    4                    0   intkey=r[4]
23      Goto           0     29    0                    0
24      Goto           0     33    0                    0
25      Rewind         4     33    0                    0
26      Column         4     0     5                    0   r[5]=
27      Ne             4     33    5     BINARY-8       0   if r[5]!=r[4] goto 33
28      Goto           0     33    0                    0   end IN expr
29      Noop           0     0     0                    0   Begin WHERE-core
30      Rowid          0     5     0                    0   r[5]=rowid
31      AggStep        0     5     1     count(1)       1   accum=r[1] step(r[5])
32      Noop           0     0     0                    0   End WHERE-core
33    Next           0     7     0                    1
34    Noop           0     0     0                    0   End WHERE-loop0: edge
35    AggFinal       1     1     0     count(1)       0   accum=r[1] N=1
36    Copy           1     6     0                    0   r[6]=r[1]
37    ResultRow      6     1     0                    0   output=r[6]
38    Halt           0     0     0                    0
39    Transaction    0     0     7     0              1   usesStmtJournal=0
40    Goto           0     1     0                    0
┌────────────────┐
│ count(_rowid_) │
├────────────────┤
│ 1929           │
└────────────────┘
Run Time: real 0.151 user 0.031250 sys 0.046875
sqlite> SELECT count(_rowid_)
   ...>   FROM edge
   ...>  WHERE EXISTS (SELECT * FROM sub_nodes WHERE node_id == node_from)
   ...>    AND EXISTS (SELECT * FROM sub_nodes WHERE node_id == node_to)
   ...> ;
QUERY PLAN
|--SCAN edge (~180224 rows)
|--CORRELATED SCALAR SUBQUERY 1
|  `--SEARCH sub_nodes USING INTEGER PRIMARY KEY (rowid=?) (~1 row)
`--CORRELATED SCALAR SUBQUERY 2
   `--SEARCH sub_nodes USING INTEGER PRIMARY KEY (rowid=?) (~1 row)
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     49    0                    0   Start at 49
1     Null           0     1     2                    0   r[1..2]=NULL
2     OpenRead       0     3     0     2              0   root=3 iDb=0; edge
3     ColumnsUsed    0     0     0     3              0
4     Explain        4     0     0     SCAN edge (~180224 rows)  0
5     Noop           0     0     0                    0   Begin WHERE-loop0: edge
6     Rewind         0     44    0                    0
7       Integer        21    4     0                    0   r[4]=21; return address
8       Integer        0     5     0                    0   r[5]=0; Init EXISTS result
9       Integer        1     6     0                    0   r[6]=1; LIMIT counter
10      OpenRead       1     4     0     0              0   root=4 iDb=0; sub_nodes
11      ColumnsUsed    1     0     0     0              0
12      Explain        12    0     0     SEARCH sub_nodes USING INTEGER PRIMARY KEY (rowid=?) (~1 row)  0
13      Noop           0     0     0                    0   Begin WHERE-loop0: sub_nodes
14      Column         0     0     7                    0   r[7]=edge.node_from
15      SeekRowid      1     20    7                    0   intkey=r[7]
16      Noop           0     0     0                    0   Begin WHERE-core
17      Integer        1     5     0                    0   r[5]=1
18      DecrJumpZero   6     21    0                    0   if (--r[6])==0 goto 21
19      Noop           0     0     0                    0   End WHERE-core
20      Noop           0     0     0                    0   End WHERE-loop0: sub_nodes
21      Return         4     0     0                    0
22      IfNot          5     43    1                    0
23      Integer        37    9     0                    0   r[9]=37; return address
24      Integer        0     10    0                    0   r[10]=0; Init EXISTS result
25      Integer        1     11    0                    0   r[11]=1; LIMIT counter
26      OpenRead       2     4     0     0              0   root=4 iDb=0; sub_nodes
27      ColumnsUsed    2     0     0     0              0
28      Explain        28    0     0     SEARCH sub_nodes USING INTEGER PRIMARY KEY (rowid=?) (~1 row)  0
29      Noop           0     0     0                    0   Begin WHERE-loop0: sub_nodes
30      Column         0     1     12                   0   r[12]=edge.node_to
31      SeekRowid      2     36    12                   0   intkey=r[12]
32      Noop           0     0     0                    0   Begin WHERE-core
33      Integer        1     10    0                    0   r[10]=1
34      DecrJumpZero   11    37    0                    0   if (--r[11])==0 goto 37
35      Noop           0     0     0                    0   End WHERE-core
36      Noop           0     0     0                    0   End WHERE-loop0: sub_nodes
37      Return         9     0     0                    0
38      IfNot          10    43    1                    0
39      Noop           0     0     0                    0   Begin WHERE-core
40      Rowid          0     3     0                    0   r[3]=rowid
41      AggStep        0     3     1     count(1)       1   accum=r[1] step(r[3])
42      Noop           0     0     0                    0   End WHERE-core
43    Next           0     7     0                    1
44    Noop           0     0     0                    0   End WHERE-loop0: edge
45    AggFinal       1     1     0     count(1)       0   accum=r[1] N=1
46    Copy           1     14    0                    0   r[14]=r[1]
47    ResultRow      14    1     0                    0   output=r[14]
48    Halt           0     0     0                    0
49    Transaction    0     0     7     0              1   usesStmtJournal=0
50    Goto           0     1     0                    0
┌────────────────┐
│ count(_rowid_) │
├────────────────┤
│ 1929           │
└────────────────┘
Run Time: real 0.200 user 0.078125 sys 0.046875
sqlite> SELECT count(edge._rowid_)
   ...>  FROM edge
   ...>  JOIN sub_nodes as s1 ON s1.node_id == node_from
   ...>  JOIN sub_nodes as s2 ON s2.node_id == node_to
   ...> ;
QUERY PLAN
|--SCAN s1 (~9216 rows)
|--SEARCH edge USING COVERING INDEX edge_from_to (node_from=?) (~2 rows)
`--SEARCH s2 USING INTEGER PRIMARY KEY (rowid=?) (~1 row)
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     35    0                    0   Start at 35
1     Null           0     1     2                    0   r[1..2]=NULL
2     OpenRead       1     4     0     0              0   root=4 iDb=0; sub_nodes
3     ColumnsUsed    1     0     0     0              0
4     OpenRead       3     7     0     k(3,,,)        2   root=7 iDb=0; edge_from_to
5     ColumnsUsed    3     0     0     3              0
6     OpenRead       2     4     0     0              0   root=4 iDb=0; sub_nodes
7     ColumnsUsed    2     0     0     0              0
8     Explain        8     0     0     SCAN s1 (~9216 rows)  0
9     Noop           0     0     0                    0   Begin WHERE-loop0: sub_nodes
10    Rewind         1     30    0                    0
11      Explain        11    0     0     SEARCH edge USING COVERING INDEX edge_from_to (node_from=?) (~2 rows)  0
12      Noop           0     0     0                    0   Begin WHERE-loop1: edge
13      Rowid          1     3     0                    0   r[3]=rowid
14      CursorHint     3     0     0     EQ(r[3],c0)    0
15      Rowid          1     4     0                    0   r[4]=rowid
16      SeekGE         3     28    4     1              0   key=r[4]
17        IdxGT          3     28    4     1              0   key=r[4]
18        Explain        18    0     0     SEARCH s2 USING INTEGER PRIMARY KEY (rowid=?) (~1 row)  0
19        Noop           0     0     0                    0   Begin WHERE-loop2: sub_nodes
20        Column         3     1     5                    0   r[5]=edge.node_to
21        SeekRowid      2     26    5                    0   intkey=r[5]
22        Noop           0     0     0                    0   Begin WHERE-core
23        IdxRowid       3     6     0                    0   r[6]=rowid
24        AggStep        0     6     1     count(1)       1   accum=r[1] step(r[6])
25        Noop           0     0     0                    0   End WHERE-core
26        Noop           0     0     0                    0   End WHERE-loop2: sub_nodes
27      Next           3     17    0                    0
28      Noop           0     0     0                    0   End WHERE-loop1: edge
29    Next           1     11    0                    1
30    Noop           0     0     0                    0   End WHERE-loop0: sub_nodes
31    AggFinal       1     1     0     count(1)       0   accum=r[1] N=1
32    Copy           1     7     0                    0   r[7]=r[1]
33    ResultRow      7     1     0                    0   output=r[7]
34    Halt           0     0     0                    0
35    Transaction    0     0     7     0              1   usesStmtJournal=0
36    Goto           0     1     0                    0
┌─────────────────────┐
│ count(edge._rowid_) │
├─────────────────────┤
│ 1929                │
└─────────────────────┘
Run Time: real 0.114 user 0.015625 sys 0.000000
sqlite> SELECT count(edge._rowid_)
   ...>  FROM edge
   ...>  JOIN sub_nodes as s1 ON s1.node_id == +node_from
   ...>  JOIN sub_nodes as s2 ON s2.node_id == +node_to
   ...> ;
QUERY PLAN
|--SCAN edge (~196608 rows)
|--SEARCH s1 USING INTEGER PRIMARY KEY (rowid=?) (~1 row)
`--SEARCH s2 USING INTEGER PRIMARY KEY (rowid=?) (~1 row)
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     31    0                    0   Start at 31
1     Null           0     1     2                    0   r[1..2]=NULL
2     OpenRead       0     3     0     2              0   root=3 iDb=0; edge
3     ColumnsUsed    0     0     0     3              0
4     OpenRead       1     4     0     0              0   root=4 iDb=0; sub_nodes
5     ColumnsUsed    1     0     0     0              0
6     OpenRead       2     4     0     0              0   root=4 iDb=0; sub_nodes
7     ColumnsUsed    2     0     0     0              0
8     Explain        8     0     0     SCAN edge (~196608 rows)  0
9     Noop           0     0     0                    0   Begin WHERE-loop0: edge
10    Rewind         0     26    0                    0
11      Explain        11    0     0     SEARCH s1 USING INTEGER PRIMARY KEY (rowid=?) (~1 row)  0
12      Noop           0     0     0                    0   Begin WHERE-loop1: sub_nodes
13      Column         0     0     3                    0   r[3]=edge.node_from
14      SeekRowid      1     24    3                    0   intkey=r[3]
15      Explain        15    0     0     SEARCH s2 USING INTEGER PRIMARY KEY (rowid=?) (~1 row)  0
16      Noop           0     0     0                    0   Begin WHERE-loop2: sub_nodes
17      Column         0     1     4                    0   r[4]=edge.node_to
18      SeekRowid      2     23    4                    0   intkey=r[4]
19      Noop           0     0     0                    0   Begin WHERE-core
20      Rowid          0     5     0                    0   r[5]=rowid
21      AggStep        0     5     1     count(1)       1   accum=r[1] step(r[5])
22      Noop           0     0     0                    0   End WHERE-core
23      Noop           0     0     0                    0   End WHERE-loop2: sub_nodes
24      Noop           0     0     0                    0   End WHERE-loop1: sub_nodes
25    Next           0     11    0                    1
26    Noop           0     0     0                    0   End WHERE-loop0: edge
27    AggFinal       1     1     0     count(1)       0   accum=r[1] N=1
28    Copy           1     6     0                    0   r[6]=r[1]
29    ResultRow      6     1     0                    0   output=r[6]
30    Halt           0     0     0                    0
31    Transaction    0     0     7     0              1   usesStmtJournal=0
32    Goto           0     1     0                    0
┌─────────────────────┐
│ count(edge._rowid_) │
├─────────────────────┤
│ 1929                │
└─────────────────────┘
Run Time: real 0.138 user 0.046875 sys 0.031250
sqlite>

(10) By mlin (dnamlin) on 2021-06-02 02:25:19 in reply to 9 [source]

Keith: agreed. May I also suggest 10X'ing the problem size (N on line 8 of my script) from 100K to 1M. The result set size is ~20K instead of ~2K. I'm pretty sure I saw one or more of the query plans change in that case. Very interesting indeed! Mike

(11) By Richard Hipp (drh) on 2021-06-02 12:47:10 in reply to 1 [link] [source]

The following script demonstrates the problem. I am adding the script to this forum thread to save is as part of the historical record:

/* Adjust $N and $NSUB as necessary to increase/descrease the
** problem size.  $NSUB was $N/10 in the original problem */
.param set $N 10000
.param set $NSUB 1000
CREATE TABLE node(node_id INTEGER PRIMARY KEY);
CREATE TABLE edge(node_from INT, node_to INT);
CREATE TABLE sub_nodes(node_id INTEGER PRIMARY KEY);
WITH s(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<$N )
  INSERT INTO node(node_id) SELECT NULL FROM s;
WITH s(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<$N )
  INSERT INTO edge(node_from, node_to) SELECT i, i+1 FROM s;
WITH s(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<$N )
  INSERT INTO edge(node_from, node_to)
    SELECT i, abs((i*1103515245 + 12345) % $N) FROM s;
WITH s(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<$NSUB )
  REPLACE INTO sub_nodes(node_id) SELECT abs(i) FROM s;
CREATE INDEX edge_from_to ON edge(node_from,node_to);
CREATE INDEX edge_to_from ON edge(node_to,node_from);
ANALYZE;

.mode box
SELECT * FROM sqlite_stat1;
.stats vmstep
.eqp on
.echo on

SELECT count(*) FROM edge 
 WHERE node_from IN sub_nodes AND node_to IN sub_nodes;

SELECT count(*) FROM edge 
 WHERE +node_from IN sub_nodes AND node_to IN sub_nodes;

SELECT count(*) FROM edge NOT INDEXED
 WHERE node_from IN sub_nodes AND node_to IN sub_nodes;

(12) By Richard Hipp (drh) on 2021-06-04 18:29:07 in reply to 1 [link] [source]

I believe this issue is now resolved on trunk, check-in 9a2ab6092d644fc3 and later. Please confirm.

(13) By mlin (dnamlin) on 2021-06-05 12:46:12 in reply to 12 [link] [source]

Yes, tested this version with both the repro script and the real app -- looks good! Thanks! The patch's effect seems to be to avoid using OP_SeekScan in the cases I looked at the bytecode for -- so just the caveat, I didn't directly observe the query running fast and using OP_SeekScan.

(14) By Richard Hipp (drh) on 2021-06-05 14:40:00 in reply to 13 [link] [source]

One of our clients has real-world cases that run slowly if OP_SeekScan is turned off. In fact, OP_SeekScan was added specifically to support that client. We have cases in the TH3 test suite that run more slowly when OP_SeekScan is disabled.

If you don't want to ever use OP_SeekScan, you can now disable it at run-time using the SQLITE_TESTCTRL_OPTIMIZATIONS test-control with a mask of 0x20000:

 sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS, db, 0x20000);

In the CLI use this dot-command:

.testctrl optimizations 0x20000

If you discover a test case that runs faster with OP_SeekScan disabled, please bring it to our attention by posting it on this forum.