Expression-index bug with OR query

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Expression-index bug with OR query

Jens Alfke-2
We’ve found a bug where creating indexes on expressions causes a query to give incorrect results. Our indexes use some complex custom functions, but the bug is easy to reproduce just using the ‘abs’ function:
        SELECT * FROM docs WHERE abs(a)=2 OR abs(b)=9
After indexing ‘abs(a)’ and ‘abs(b)’, this query no longer returns correct results.
This seems related to the OR — if we query only abs(a)=2, or only abs(b)=9, it works correctly.

The transcript below comes from the SQLite 3.24 shell.

### Populate database:
sqlite> create table docs (a int, b int);
sqlite> insert into docs (a, b) values (2, 4);
sqlite> insert into docs (a, b) values (3, 9);

### Simple OR query that correctly matches both docs:
sqlite> select * from docs where abs(a)=2 or abs(b)=9;
    a = 2
    b = 4

    a = 3
    b = 9
sqlite> explain query plan select * from docs where abs(a)=2 or abs(b)=9;
QUERY PLAN
`--SCAN TABLE docs

### Create indexes on the two expressions in the above query:
sqlite> create index ia on docs (abs(a));
sqlite> create index ib on docs (abs(b));

### Now repeat the query — it incorrectly finds only one doc, and the query plan looks bogus:
sqlite> select * from docs where abs(a)=2 or abs(b)=9;
    a = 3
    b = 9
sqlite> explain query plan select * from docs where abs(a)=2 or abs(b)=9;
QUERY PLAN
`--SEARCH TABLE docs USING INDEX ib (<expr>=?)

# And here’s the full explanation with bytecodes:
sqlite> explain select * from docs where abs(a)=2 or abs(b)=9;
addr  opcode         p1    p2    p3    p4             p5  comment      
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     23    0                    00  Start at 23  
1     OpenRead       0     2     0     2              00  root=2 iDb=0; docs
2     OpenRead       1     3     0     k(2,,)         02  root=3 iDb=0; ib
3     Once           0     11    0                    00              
4     OpenEphemeral  3     1     0     k(1,)          00  nColumn=1    
5     Integer        2     2     0                    00  r[2]=2      
6     MakeRecord     2     1     3     A              00  r[3]=mkrec(r[2])
7     IdxInsert      3     3     2     1              00  key=r[3]    
8     Integer        9     2     0                    00  r[2]=9      
9     MakeRecord     2     1     3     A              00  r[3]=mkrec(r[2])
10    IdxInsert      3     3     2     1              00  key=r[3]    
11    Rewind         3     22    0                    00              
12      Column         3     0     1                    00  r[1]=        
13      IsNull         1     21    0                    00  if r[1]==NULL goto 21
14      SeekGE         1     21    1     1              00  key=r[1]    
15        IdxGT          1     21    1     1              00  key=r[1]    
16        DeferredSeek   1     0     0                    00  Move 0 to 1.rowid if needed
17        Column         0     0     4                    00  r[4]=docs.a  
18        Column         0     1     5                    00  r[5]=docs.b  
19        ResultRow      4     2     0                    00  output=r[4..5]
20      Next           1     15    0                    00              
21    NextIfOpen     3     12    0                    00              
22    Halt           0     0     0                    00              
23    Transaction    0     0     7     0              01  usesStmtJournal=0
24    Goto           0     1     0                    00              

—Jens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Expression-index bug with OR query

Dan Kennedy-4
On 12/14/2018 07:22 AM, Jens Alfke wrote:
> We’ve found a bug where creating indexes on expressions causes a query to give incorrect results. Our indexes use some complex custom functions, but the bug is easy to reproduce just using the ‘abs’ function:
> SELECT * FROM docs WHERE abs(a)=2 OR abs(b)=9
> After indexing ‘abs(a)’ and ‘abs(b)’, this query no longer returns correct results.
> This seems related to the OR — if we query only abs(a)=2, or only abs(b)=9, it works correctly.

Thanks for reporting this. It was a bug:

   https://www.sqlite.org/src/info/d96eba87698a428c1ddd0790ea04
   https://www.sqlite.org/src/info/7e4ed8b5c2047b69

Dan.



>
> The transcript below comes from the SQLite 3.24 shell.
>
> ### Populate database:
> sqlite> create table docs (a int, b int);
> sqlite> insert into docs (a, b) values (2, 4);
> sqlite> insert into docs (a, b) values (3, 9);
>
> ### Simple OR query that correctly matches both docs:
> sqlite> select * from docs where abs(a)=2 or abs(b)=9;
>     a = 2
>     b = 4
>
>     a = 3
>     b = 9
> sqlite> explain query plan select * from docs where abs(a)=2 or abs(b)=9;
> QUERY PLAN
> `--SCAN TABLE docs
>
> ### Create indexes on the two expressions in the above query:
> sqlite> create index ia on docs (abs(a));
> sqlite> create index ib on docs (abs(b));
>
> ### Now repeat the query — it incorrectly finds only one doc, and the query plan looks bogus:
> sqlite> select * from docs where abs(a)=2 or abs(b)=9;
>     a = 3
>     b = 9
> sqlite> explain query plan select * from docs where abs(a)=2 or abs(b)=9;
> QUERY PLAN
> `--SEARCH TABLE docs USING INDEX ib (<expr>=?)
>
> # And here’s the full explanation with bytecodes:
> sqlite> explain select * from docs where abs(a)=2 or abs(b)=9;
> addr  opcode         p1    p2    p3    p4             p5  comment
> ----  -------------  ----  ----  ----  -------------  --  -------------
> 0     Init           0     23    0                    00  Start at 23
> 1     OpenRead       0     2     0     2              00  root=2 iDb=0; docs
> 2     OpenRead       1     3     0     k(2,,)         02  root=3 iDb=0; ib
> 3     Once           0     11    0                    00
> 4     OpenEphemeral  3     1     0     k(1,)          00  nColumn=1
> 5     Integer        2     2     0                    00  r[2]=2
> 6     MakeRecord     2     1     3     A              00  r[3]=mkrec(r[2])
> 7     IdxInsert      3     3     2     1              00  key=r[3]
> 8     Integer        9     2     0                    00  r[2]=9
> 9     MakeRecord     2     1     3     A              00  r[3]=mkrec(r[2])
> 10    IdxInsert      3     3     2     1              00  key=r[3]
> 11    Rewind         3     22    0                    00
> 12      Column         3     0     1                    00  r[1]=
> 13      IsNull         1     21    0                    00  if r[1]==NULL goto 21
> 14      SeekGE         1     21    1     1              00  key=r[1]
> 15        IdxGT          1     21    1     1              00  key=r[1]
> 16        DeferredSeek   1     0     0                    00  Move 0 to 1.rowid if needed
> 17        Column         0     0     4                    00  r[4]=docs.a
> 18        Column         0     1     5                    00  r[5]=docs.b
> 19        ResultRow      4     2     0                    00  output=r[4..5]
> 20      Next           1     15    0                    00
> 21    NextIfOpen     3     12    0                    00
> 22    Halt           0     0     0                    00
> 23    Transaction    0     0     7     0              01  usesStmtJournal=0
> 24    Goto           0     1     0                    00
>
> —Jens
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users