SQLite Forum

A crash bug in MULTI-INDEX OR
Login

A crash bug in MULTI-INDEX OR

(1.1) By Wang Ke (krking) on 2021-06-22 17:39:03 edited from 1.0 [source]

Hi,

We found a crash bug existing in SQLite 3.36.0, which may be triggered by:

CREATE TABLE IF NOT EXISTS t1(a int, b);
CREATE TABLE t2(e, d, f);
CREATE INDEX i1 ON t1(a);
INSERT INTO t2(f, d, e) VALUES (5, 2.0, 7);
SELECT e FROM t2 LEFT JOIN t1 INDEXED BY i1 ON likely(a=e) WHERE (b=5 AND e=12) OR (e=11 AND a=4) ORDER BY e; -- Segmentation fault (core dumped)

The query plan looks like this:

QUERY PLAN
|--SCAN t2
|--MULTI-INDEX OR
|  |--INDEX 1
|  |  `--SEARCH t1 USING INDEX i1 (a=?)
|  `--INDEX 2
|     `--SEARCH t1 USING INDEX i1 (a=?)
`--USE TEMP B-TREE FOR ORDER BY

Note that we use functions in order to adjust the cost so that the specific query solution is chosen, there may be other ways to do so.

Here are the bytecode for the query:

addr  opcode         p1    p2    p3    p4             p5  comment      
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     63    0                    0   Start at 63
1     SorterOpen     2     3     0     k(1,B)         0   
2     OpenRead       0     3     0     1              0   root=3 iDb=0; t2
3     OpenRead       1     2     0     2              0   root=2 iDb=0; t1
4     Rewind         0     56    0                    0   
5       Integer        0     1     0                    0   r[1]=0; init LEFT JOIN no-match flag
6       Null           0     3     0                    0   r[3]=NULL
7       Integer        34    2     0                    0   r[2]=34
8       Column         0     0     5                    0   r[5]=t2.e
9       Ne             6     21    5     BINARY-8       81  if r[5]!=r[6] goto 21
10      ReopenIdx      3     4     0     k(2,,)         2   root=4 iDb=0; i1
11      Column         0     0     7                    0   r[7]=t2.e
12      IsNull         7     21    0                    0   if r[7]==NULL goto 21
13      Affinity       7     1     0     C              0   affinity(r[7])
14      SeekGE         3     21    7     1              0   key=r[7]
15        IdxGT          3     21    7     1              0   key=r[7]
16        DeferredSeek   3     0     1     [1,0]          0   Move 1 to 3.rowid if needed
17        IdxRowid       3     4     0                    0   r[4]=rowid
18        RowSetTest     3     20    4     0              0   if r[4] in rowset(3) goto 20
19        Gosub          2     35    0                    0   
20      Next           3     15    1                    0   
21      Column         0     0     5                    0   r[5]=t2.e
22      Ne             8     34    5     BINARY-8       81  if r[5]!=r[8] goto 34
23      ReopenIdx      3     4     0     k(2,,)         2   root=4 iDb=0; i1
24      Column         0     0     9                    0   r[9]=t2.e
25      IsNull         9     34    0                    0   if r[9]==NULL goto 34
26      Affinity       9     1     0     C              0   affinity(r[9])
27      SeekGE         3     34    9     1              0   key=r[9]
28        IdxGT          3     34    9     1              0   key=r[9]
29        DeferredSeek   3     0     1     [1,0]          0   Move 1 to 3.rowid if needed
30        IdxRowid       3     4     0                    0   r[4]=rowid
31        RowSetTest     3     33    4     -1             0   if r[4] in rowset(3) goto 33
32        Gosub          2     35    0                    0   
33      Next           3     28    1                    0   
34      Goto           0     51    0                    0   
35      Column         3     0     5                    0   r[5]=t1.a
36      Column         0     0     10                   0   r[10]=t2.e
37      Ne             10    50    5     BINARY-8       83  if r[5]!=r[10] goto 50
38      Integer        1     1     0                    0   r[1]=1; record LEFT JOIN hit
39      Column         1     1     10                   0   r[10]=t1.b
40      Ne             11    43    10    BINARY-8       81  if r[10]!=r[11] goto 43
41      Column         0     0     10                   0   r[10]=t2.e
42      Eq             6     47    10    BINARY-8       65  if r[10]==r[6] goto 47
43      Column         0     0     10                   0   r[10]=t2.e
44      Ne             8     50    10    BINARY-8       81  if r[10]!=r[8] goto 50
45      Column         3     0     10                   0   r[10]=t1.a
46      Ne             12    50    10    BINARY-8       84  if r[10]!=r[12] goto 50
47      Column         0     0     13                   0   r[13]=t2.e
48      MakeRecord     13    1     15                   0   r[15]=mkrec(r[13])
49      SorterInsert   2     15    13    1              0   key=r[15]
50      Return         2     0     0                    0   
51      IfPos          1     55    0                    0   if r[1]>0 then r[1]-=0, goto 55
52      NullRow        1     0     0                    0   
53      NullRow        3     0     0                    0   
54      Gosub          2     38    0                    0   
55    Next           0     5     0                    1   
56    OpenPseudo     4     16    3                    0   3 columns in r[16]
57    SorterSort     2     62    0                    0   
58      SorterData     2     16    4                    0   r[16]=data
59      Column         4     0     14                   0   r[14]=e
60      ResultRow      14    1     0                    0   output=r[14]
61    SorterNext     2     58    0                    0   
62    Halt           0     0     0                    0   
63    Transaction    0     0     3     0              1   usesStmtJournal=0
64    Integer        12    6     0                    0   r[6]=12
65    Integer        11    8     0                    0   r[8]=11
66    Integer        5     11    0                    0   r[11]=5
67    Integer        4     12    0                    0   r[12]=4
68    Goto           0     1     0                    0   

It seems that it's caused by ReopenIdx an index without open an index first.

Besides, through bisecting, we find that the crash problem maybe first appear in check-in ce35e39c.

Hope these information will help you locate the cause of the bug more easily.

Looking forward to your reply :)

(2) By Richard Hipp (drh) on 2021-06-22 23:39:57 in reply to 1.1 [link] [source]

A very interesting problem. The query planner tries to use index i1 as a covering index, but because of the unusual INDEXED BY clause and the likely() function, it ends up not initializing the cursor to the index in time for the OP_NullRow opcode that occurs as part of LEFT JOIN processing. The problem is associated with the Multi-OR covering index optimization from 2012. But it is unclear whether or not the exact set of circumstances that trigger the problem could be reached until other more recent optimizations were also put in place.

Fixed on trunk. Two alternative fixes are shown on nearby branches

(3) By Wang Ke (krking) on 2021-06-23 00:43:44 in reply to 2 [link] [source]

Thanks for the fix.

We will continue to produce similar test cases to verify whether the fix is perfect.