Hi Folks,
I have a virtual table implementation currently based upon 3.6.18 sources. I
have found a bug in the way left outer joins are implemented in SQLITE3 that
causes bad results to occur. The short description of the problem is that the
temporary registers setup to fetch data from the virtual tables overwrite the
register used to store a value as part of the loop. By that I mean an inner
loop overwrites a value that is expected to be there when used by the outer
loop. As such, the result set is not as expected.
The virtual table setup can be emulated with the following SQL:
create table atab(id int, mask text) ;
create table btab(mask text, bid int) ;
create table ctab(bid int, desc text) ;
insert into atab values (1, '1234') ;
insert into atab values (2, '2345') ;
insert into btab values ('1234', 1) ;
insert into btab values ('1234', 2) ;
insert into btab values ('1234', 3) ;
insert into btab values ('1234', 7) ;
insert into ctab values ( 1, 'Text for 1') ;
insert into ctab values ( 2, 'Text for 2') ;
insert into ctab values ( 3, 'Text for 3') ;
select a.id, a.mask, b.mask, b.bid, c.bid, c.desc
from atab as a
left outer join btab as b
on a.mask = b.mask
left outer join ctab as c
on b.bid = c.bid
where
a.id = 1 ;
The following is the "explain" of the query as a virtual table implementation.
The names have been "corrected" to emulate the SQL above, and the column
numbers are obviously a bit different than those found above, but the problem
is demonstrated:
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- --------------------- -- -------------
0 Trace 0 0 0 00 (null)
1 Integer 3 1 0 00 (null)
2 Goto 0 50 0 00 (null)
3 VOpen 0 0 0 vtab:8224638:8101800 00 atab
4 VOpen 1 0 0 vtab:81F90E0:8101800 00 btab
5 VOpen 2 0 0 vtab:81E71C0:8101800 00 ctab
6 SCopy 1 4 0 00 (null)
7 Integer 1 2 0 00 (null)
8 Integer 1 3 0 00 (null)
9 VFilter 0 46 2 00 (null)
10 VColumn 0 0 6 00 atab.id
11 Ne 1 45 6 collseq(BINARY) 6c (null)
12 Integer 0 8 0 00 init LEFT
JOIN no-match flag
13 VColumn 0 3 4 00 atab.mask
14 Integer 1 2 0 00 (null)
15 Integer 1 3 0 00 (null)
16 VFilter 1 42 2 00 (null)
17 VColumn 1 0 7 00 btab.mask
18 Ne 7 41 4 collseq(BINARY) 6a (null)
19 Integer 1 8 0 00 record LEFT
JOIN hit
20 Integer 0 9 0 00 init LEFT
JOIN no-match flag
21 Integer 17 4 0 00 (null)
22 VColumn 1 1 5 00 btab.bid
23 Integer 2 2 0 00 (null)
24 Integer 2 3 0 00 (null)
25 VFilter 2 38 2 00 (null)
26 VColumn 2 0 7 00 ctab.bid
27 Integer 17 6 0 00 (null)
28 Ne 6 37 7 collseq(BINARY) 6c (null)
29 VColumn 2 1 6 00 ctab.bid
30 Ne 6 37 5 collseq(BINARY) 6b (null)
31 Integer 1 9 0 00 record LEFT
JOIN hit
32 VColumn 0 3 10 00 atab.mask
33 VColumn 1 1 11 00 btab.bid
34 VColumn 2 1 12 00 ctab.bid
35 VColumn 2 2 13 00 ctab.desc
36 ResultRow 10 4 0 00 (null)
37 VNext 2 26 0 00 (null)
38 IfPos 9 41 0 00 (null)
39 NullRow 2 0 0 00 (null)
40 Goto 0 31 0 00 (null)
41 VNext 1 17 0 00 (null)
42 IfPos 8 45 0 00 (null)
43 NullRow 1 0 0 00 (null)
44 Goto 0 19 0 00 (null)
45 VNext 0 10 0 00 (null)
46 Close 0 0 0 00 (null)
47 Close 1 0 0 00 (null)
48 Close 2 0 0 00 (null)
49 Halt 0 0 0 00 (null)
50 Transaction 0 0 0 00 (null)
51 VerifyCookie 0 151 0 00 (null)
52 Goto 0 3 0 00 (null)
Specifically, please note the VNext instruction at position 41. It jumps to
position 17 which fetches data into register 7 and (at position 18) performs a
comparison with register 4 which should be atab.mask loaded at position 13. The
first time through this condition is true. However, in processing the inner
loops (specifically, positions 22-25) register 4 is overwritten with a value
used to process the left outer join and is, from that point on, invalid when
the VNext instruction occurs at position 41.
This problem occurs using the 3.6.18 source tree as well as trunk (as of this
morning). I build from source (not amalgamation) and use various "OMIT"
symbols, so if that is important to debugging this I can supply more
information.
I can "fix" the problem by not releasing the temporary registers allocated in
the codeOneLoopStart() routine that handles the virtual table implementation.
That obviously uses more registers, but the expected results are then generated.
When comparing the above code to an explain plan using the above SQL I get:
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Trace 0 0 0 00
1 Integer 1 1 0 00
2 Goto 0 41 0 00
3 OpenRead 0 2 0 2 00 atab
4 OpenRead 1 3 0 2 00 btab
5 OpenRead 2 4 0 2 00 ctab
6 Rewind 0 37 0 00
7 Column 0 0 2 00 atab.id
8 Ne 1 36 2 collseq(BINARY) 6c
9 Integer 0 4 0 00 init LEFT JOIN
no-match flag
10 Rewind 1 33 0 00
11 Column 0 1 3 00 atab.mask
12 Column 1 0 5 00 btab.mask
13 Ne 5 32 3 collseq(BINARY) 6a
14 Integer 1 4 0 00 record LEFT JOIN hit
15 Integer 0 6 0 00 init LEFT JOIN
no-match flag
16 Rewind 2 29 0 00
17 Column 1 1 5 00 btab.bid
18 Column 2 0 3 00 ctab.bid
19 Ne 3 28 5 collseq(BINARY) 6b
20 Integer 1 6 0 00 record LEFT JOIN hit
21 Column 0 0 7 00 atab.id
22 Column 0 1 8 00 atab.mask
23 Column 1 0 9 00 btab.mask
24 Column 1 1 10 00 btab.bid
25 Column 2 0 11 00 ctab.bid
26 Column 2 1 12 00 ctab.desc
27 ResultRow 7 6 0 00
28 Next 2 17 0 01
29 IfPos 6 32 0 00
30 NullRow 2 0 0 00
31 Goto 0 20 0 00
32 Next 1 11 0 01
33 IfPos 4 36 0 00
34 NullRow 1 0 0 00
35 Goto 0 14 0 00
36 Next 0 7 0 01
37 Close 0 0 0 00
38 Close 1 0 0 00
39 Close 2 0 0 00
40 Halt 0 0 0 00
41 Transaction 0 0 0 00
42 VerifyCookie 0 3 0 00
43 Goto 0 3 0 00
The difference to note is that the Next instruction at position 32 which jumps
to position 11, jumps to a location where it re-fetches the data it requires to
perform the comparison. I suspect a comparable solution is desired, or that the
register used to store atab.mask is marked as cached so that result is
preserved over the temporary register allocation process. However, the caching
seems to be on table columns and not expressions, and the fetch of atab.mask is
the result of processing the right-hand side of the join expression. Is there a
caching mechanism for non-column values?
I'm not sure what is the better solution. Any ideas or pointers or solutions is
appreciated.
Regards,
-Allan
_______________________________________________
sqlite-users mailing list
[email protected]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
