Re: [sqlite] Performance degradation in query planner in SQLite 3.14.2 (vs SQLite 3.10.2)

[Paul]

Yes, fixed in pre-release snapshot 201610041220.


Thank you.

 
> On 10/5/16, Richard Hipp  wrote:
> > On 10/5/16, Clemens Ladisch  wrote:
> >>   stop
> >>
> >> This looks like a bug.
> >>
> >
> > I think it might be fixed on trunk.  I was just trying to bisect...
> 
> I think this may be a repeat of the problem described by ticket
> https://sqlite.org/src/info/0eab1ac759 and fixed on 2016-09-16 by
> check-in https://sqlite.org/src/info/a92aee5520cfaf85
> 
> -- 
> D. Richard Hipp
> d...@sqlite.org
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
 
 
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Performance degradation in query planner in SQLite 3.14.2 (vs SQLite 3.10.2)

[Richard Hipp]

On 10/5/16, Richard Hipp  wrote:
> On 10/5/16, Clemens Ladisch  wrote:
>>   stop
>>
>> This looks like a bug.
>>
>
> I think it might be fixed on trunk.  I was just trying to bisect...

I think this may be a repeat of the problem described by ticket
https://sqlite.org/src/info/0eab1ac759 and fixed on 2016-09-16 by
check-in https://sqlite.org/src/info/a92aee5520cfaf85

-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Performance degradation in query planner in SQLite 3.14.2 (vs SQLite 3.10.2)

[Richard Hipp]

On 10/5/16, Clemens Ladisch  wrote:
>   stop
>
> This looks like a bug.
>

I think it might be fixed on trunk.  I was just trying to bisect...

-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Performance degradation in query planner in SQLite 3.14.2 (vs SQLite 3.10.2)

[Paul]

> Paul wrote:
> > I've traced this issue down to the simplest test case:
> >
> > CREATE TABLE IF NOT EXISTS foo
> > (
> >  id  INTEGER,
> >  baz INTEGER,
> >  PRIMARY KEY(id)
> > );
> >
> > CREATE INDEX IF NOT EXISTS baz_foo_idx ON foo(baz, id);
> >
> > CREATE TABLE IF NOT EXISTS bar
> > (
> >  foo INTEGER,
> >  PRIMARY KEY(foo),
> >  FOREIGN KEY(foo) REFERENCES foo(id) ON DELETE CASCADE
> > );
> >
> > WITH RECURSIVE
> >  cnt(x, y) AS (VALUES(1, 1) UNION ALL SELECT x + 1, x + 1 FROM cnt WHERE x 
> > < 20)
> >  INSERT INTO foo(id, baz) SELECT x, y FROM cnt;
> >
> > WITH RECURSIVE
> >  cnt(x) AS (VALUES(1) UNION ALL SELECT x + 3 FROM cnt WHERE x < 5)
> >  INSERT INTO bar SELECT x FROM cnt;
> >
> > This query takes too much time:
> >
> >  SELECT id FROM foo WHERE baz = 1 AND id IN (SELECT foo FROM bar) LIMIT 
> > 1;
> 
> EXPLAIN SELECT id FROM foo WHERE baz = 1 AND id IN (SELECT foo FROM bar) 
> LIMIT 1;
> addr  opcode p1p2p3p4 p5  comment
>   -        -  --  -
> 0 Init   0 24000  Start at 24
> 1 Integer1 1 000  r[1]=1; LIMIT 
> counter
> 2 OpenRead   2 3 0 k(3,,,)02  root=3 iDb=0; 
> baz_foo_idx
> 3 Integer1  2 000  r[2]=1
> 4 Once   0 6 000
> 5 OpenRead   3 4 0 1  00  root=4 iDb=0; bar
> 6 Rewind 3 22000
> 7   Rowid  3 3 000  r[3]=rowid
> 8   IsNull 3 21000  if r[3]==NULL 
> goto 21
> 9   Once   1 11000
> 10  OpenRead   4 4 0 1  00  root=4 iDb=0; bar
> 11  Rewind 4 21000
> 12Rowid  4 4 000  r[4]=rowid
> 13IsNull 4 20000  if r[4]==NULL 
> goto 20
> 14SeekGE 2 202 3  00  key=r[2..4]
> 15  IdxGT  2 202 3  00  key=r[2..4]
> 16  IdxRowid   2 5 000  r[5]=rowid
> 17  ResultRow  5 1 000  output=r[5]
> 18  DecrJumpZero   1 22000  if 
> (--r[1])==0 goto 22
> 19Next   2 15000
> 20  NextIfOpen 4 12000
> 21NextIfOpen 3 7 000
> 22Close  2 0 000
> 23Halt   0 0 000
> 24Transaction0 0 3 0  01  usesStmtJournal=0
> 25TableLock  0 2 0 foo00  iDb=0 root=2 write=0
> 26TableLock  0 4 0 bar00  iDb=0 root=4 write=0
> 27Goto   0 1 000
> 
> If I've understood this correctly, it's the equivalent of this pseudocode:
> 
>   cursor c3 = scan bar
>   for each row in c3:
>   cursor c4 = scan bar
>   for each row in c4:
>   cursor c2 = search (1, c3.rowid, c4.rowid) in baz_foo_idx
>   for each row in c2:
>   output c2.rowid
>   stop
> 
> This looks like a bug.
> 
> As a workaround, drop "id" from the index (the rowid is always part of
> the index anyway).

Thank you for the information! 

We'll stick with the old version for now, until the bug is fixed, since it's 
hard to change database structure since there are millions of copies. Also we 
use 'ORDER BY baz DESC, id DESC' and I'm not sure how will it work out in case 
of index on the single baz field.
 
 
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Performance degradation in query planner in SQLite 3.14.2 (vs SQLite 3.10.2)

[Clemens Ladisch]

Paul wrote:
> I've traced this issue down to the simplest test case:
>
> CREATE TABLE IF NOT EXISTS foo
> (
>  id  INTEGER,
>  baz INTEGER,
>  PRIMARY KEY(id)
> );
>
> CREATE INDEX IF NOT EXISTS baz_foo_idx ON foo(baz, id);
>
> CREATE TABLE IF NOT EXISTS bar
> (
>  foo INTEGER,
>  PRIMARY KEY(foo),
>  FOREIGN KEY(foo) REFERENCES foo(id) ON DELETE CASCADE
> );
>
> WITH RECURSIVE
>  cnt(x, y) AS (VALUES(1, 1) UNION ALL SELECT x + 1, x + 1 FROM cnt WHERE x < 
> 20)
>  INSERT INTO foo(id, baz) SELECT x, y FROM cnt;
>
> WITH RECURSIVE
>  cnt(x) AS (VALUES(1) UNION ALL SELECT x + 3 FROM cnt WHERE x < 5)
>  INSERT INTO bar SELECT x FROM cnt;
>
> This query takes too much time:
>
>  SELECT id FROM foo WHERE baz = 1 AND id IN (SELECT foo FROM bar) LIMIT 1;

EXPLAIN SELECT id FROM foo WHERE baz = 1 AND id IN (SELECT foo FROM bar) 
LIMIT 1;
addr  opcode p1p2p3p4 p5  comment
  -        -  --  -
0 Init   0 24000  Start at 24
1 Integer1 1 000  r[1]=1; LIMIT counter
2 OpenRead   2 3 0 k(3,,,)02  root=3 iDb=0; 
baz_foo_idx
3 Integer1  2 000  r[2]=1
4 Once   0 6 000
5 OpenRead   3 4 0 1  00  root=4 iDb=0; bar
6 Rewind 3 22000
7   Rowid  3 3 000  r[3]=rowid
8   IsNull 3 21000  if r[3]==NULL goto 
21
9   Once   1 11000
10  OpenRead   4 4 0 1  00  root=4 iDb=0; bar
11  Rewind 4 21000
12Rowid  4 4 000  r[4]=rowid
13IsNull 4 20000  if r[4]==NULL 
goto 20
14SeekGE 2 202 3  00  key=r[2..4]
15  IdxGT  2 202 3  00  key=r[2..4]
16  IdxRowid   2 5 000  r[5]=rowid
17  ResultRow  5 1 000  output=r[5]
18  DecrJumpZero   1 22000  if (--r[1])==0 
goto 22
19Next   2 15000
20  NextIfOpen 4 12000
21NextIfOpen 3 7 000
22Close  2 0 000
23Halt   0 0 000
24Transaction0 0 3 0  01  usesStmtJournal=0
25TableLock  0 2 0 foo00  iDb=0 root=2 write=0
26TableLock  0 4 0 bar00  iDb=0 root=4 write=0
27Goto   0 1 000

If I've understood this correctly, it's the equivalent of this pseudocode:

  cursor c3 = scan bar
  for each row in c3:
  cursor c4 = scan bar
  for each row in c4:
  cursor c2 = search (1, c3.rowid, c4.rowid) in baz_foo_idx
  for each row in c2:
  output c2.rowid
  stop

This looks like a bug.

As a workaround, drop "id" from the index (the rowid is always part of
the index anyway).


Regards,
Clemens
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Performance degradation in query planner in SQLite 3.14.2 (vs SQLite 3.10.2)

[Paul]

To add to that, EXPLAIN QUERY PLAN shows that covering index will be used:

sqlite> EXPLAIN QUERY PLAN SELECT id FROM foo WHERE baz = 1 AND id IN 
(SELECT foo FROM bar) LIMIT 1;
selectidorder   fromdetail  
  
--  --  --  
--
0   0   0   SEARCH TABLE foo USING COVERING INDEX 
baz_foo_idx (baz=? AND id=? AND rowid=??)


It is not clear to me, what query algorithm is doing. It seems like it iterates 
through bar and for each row of bar it performs unindexed cross-search in the 
foo. 

However, according to EXPLAIN, it should iterate over the baz_foo_idx index and 
perform indexed cross-searches in the bar.


 
> I've traced this issue down to the simplest test case:
> 
> CREATE TABLE IF NOT EXISTS foo
> (
>  id  INTEGER,
>  baz INTEGER,
>  PRIMARY KEY(id)
> );
> 
> CREATE INDEX IF NOT EXISTS baz_foo_idx ON foo(baz, id);
> 
> CREATE TABLE IF NOT EXISTS bar
> (
>  foo INTEGER,
>  PRIMARY KEY(foo),
>  FOREIGN KEY(foo) REFERENCES foo(id) ON DELETE CASCADE
> );
> 
> WITH RECURSIVE
>  cnt(x, y) AS (VALUES(1, 1) UNION ALL SELECT x + 1, x + 1 FROM cnt WHERE x < 
> 20)
>  INSERT INTO foo(id, baz) SELECT x, y FROM cnt;
> 
> WITH RECURSIVE
>  cnt(x) AS (VALUES(1) UNION ALL SELECT x + 3 FROM cnt WHERE x < 5)
>  INSERT INTO bar SELECT x FROM cnt;
> 
> SELECT id FROM foo WHERE baz = 9 AND id IN (SELECT foo FROM bar) LIMIT 0, 
> 10;
> 
> 
> This query takes too much time:   
> 
>  SELECT id FROM foo WHERE baz = 1 AND id IN (SELECT foo FROM bar) LIMIT 
> 1; 
> 
> 
> It seems like execution time is a function of baz: 
> 
> sqlite> .timer on 
> sqlite> SELECT id FROM foo WHERE baz = 1 AND id IN (SELECT foo FROM bar) 
> LIMIT 1;
> id
> --
> 1 
> Run Time: real 14.839 user 14.836000 sys 0.00
> sqlite> SELECT id FROM foo WHERE baz = 1000 AND id IN (SELECT foo FROM bar) 
> LIMIT 1;
> id
> --
> 1000  
> Run Time: real 1.577 user 1.576000 sys 0.00
> sqlite> SELECT id FROM foo WHERE baz = 100 AND id IN (SELECT foo FROM bar) 
> LIMIT 1;
> id
> --
> 100   
> Run Time: real 0.232 user 0.232000 sys 0.00
> sqlite> SELECT id FROM foo WHERE baz = 10 AND id IN (SELECT foo FROM bar) 
> LIMIT 1;
> id
> --
> 10
> Run Time: real 0.036 user 0.036000 sys 0.00
> sqlite> SELECT id FROM foo WHERE baz = 1 AND id IN (SELECT foo FROM bar) 
> LIMIT 1;
> id
> --
> 1 
> Run Time: real 0.001 user 0.00 sys 0.00
>  
>  
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
 
 
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users