Bump. One bump limit met :-) Didn't know if this got lost in the holiday rush, but the bug remains. I have a work-around (see below) that does work, but didn't know if there was a better solution.
Regards, -Allan > -----Original Message----- > From: sqlite-users-boun...@sqlite.org [mailto:sqlite-users- > boun...@sqlite.org] On Behalf Of Schrum, Allan > Sent: Monday, November 23, 2009 11:29 AM > To: General Discussion of SQLite Database > Subject: [sqlite] Bug: Problem with left-outer join and virtual tables. > Version 3.6.18 and trunk > > 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 > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
