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.