sqlite3 hangs on query

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

sqlite3 hangs on query

Jens-Heiner Rechtien
Hi SQLite team,

please consider the attached dump of a sqlite3 database and the
following - admittedly nonsensical, don't ask - query over a restored
version of the database:

*SELECT count(*) FROM spacefavorite, album_asset, albums,
assetProfileLinks, avatarCacheReferences, cacheReferences, comment,
conflicts, coreInfo, coreMD5, errors, flags, importSource,
missingBinariesOnOz, profileRegistration, quota_exceeded,
renditionRevisions, space, space_album LIMIT 1;**
*

On iOS, MacOS and Linux this query will busy hang and never return.
Happens with the command line tool and if used as a prepared statement
in our iOS app. Changing certain aspects of the query will resolve the
problem: leaving the table "spacefavorite" out of the query, or
replacing count(*) with a just an asterisk.

I tried the following versions:

3.14.0, 3.16.2 (MacOSX Sierra), 3.13.0, 3.17.0 (Linux Fedora 24), 3.14.0
(iOS 10), always the same behavior.

Many thanks for your consideration and especially for your great tool.

Heiner

--

Jens-Heiner Rechtien <[hidden email] <mailto:[hidden email]>>

Computer Scientist

Adobe Systems Engineering GmbH

Große Elbstraße 27

22767 Hamburg


Registergericht: Hamburg HRB 745 37

Geschäftsführer: Michael D. Jamrosy, Christian Keim, Thomas Mührke,
Keith San Felipe




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

Re: sqlite3 hangs on query

Simon Slavin-3

On 14 Feb 2017, at 12:33pm, Jens-Heiner Rechtien <[hidden email]> wrote:

> please consider the attached dump of a sqlite3 database and the following - admittedly nonsensical, don't ask - query over a restored version of the database

Jens,

You can’t send attachments to this list.  If your dump text is short, you should be able to just past it into a message.  If long, please put it on a server somewhere.

However, on reading your text I was wondering whether your database is corrupt.  Please execute

PRAGMA integrity_check;

on it and tell us whether it returns an error.

You might also try weeding extraneous tables out of your command and see if you can find a shorter version of your command which also hangs.  This could mean you could demonstrate the problem without creating so many tables.

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

Re: sqlite3 hangs on query

Clemens Ladisch
In reply to this post by Jens-Heiner Rechtien
Jens-Heiner Rechtien wrote:
> SELECT count(*)
> FROM spacefavorite, album_asset, albums, assetProfileLinks, avatarCacheReferences,
>      cacheReferences, comment, conflicts, coreInfo, coreMD5, errors, flags,
>      importSource, missingBinariesOnOz, profileRegistration, quota_exceeded,
>      renditionRevisions, space, space_album
> LIMIT 1;

The "LIMIT 1" does not have any effect because COUNT() returns only one row.

> this query will busy hang and never return.

It would return if you just waited long enough.

This is how your query would be implemented for five tables:

  sqlite> explain select count(*) from a, b, c, d, e;
  addr  opcode         p1    p2    p3    p4             p5  comment
  ----  -------------  ----  ----  ----  -------------  --  -------------
  0     Init           0     27    0                    00  Start at 27
  1     Null           0     1     1                    00  r[1..1]=NULL
  2     OpenRead       0     3     0     0              00  root=3 iDb=0; a
  3     OpenRead       1     2     0     0              00  root=2 iDb=0; b
  4     OpenRead       2     4     0     0              00  root=4 iDb=0; c
  5     OpenRead       3     5     0     0              00  root=5 iDb=0; d
  6     OpenRead       4     6     0     0              00  root=6 iDb=0; e
  7     Rewind         0     18    0                    00
  8       Rewind         1     17    0                    00
  9         Rewind         2     16    0                    00
  10          Rewind         3     15    0                    00
  11            Rewind         4     14    0                    00
  12              AggStep0       0     0     1     count(0)       00  accum=r[1] step(r[0])
  13            Next           4     12    0                    01
  14          Next           3     11    0                    01
  15        Next           2     10    0                    01
  16      Next           1     9     0                    01
  17    Next           0     8     0                    01
  18    Close          0     0     0                    00
  ...
  23    AggFinal       1     0     0     count(0)       00  accum=r[1] N=0
  24    Copy           1     2     0                    00  r[2]=r[1]
  25    ResultRow      2     1     0                    00  output=r[2]
  ...

Please note that "," is just the short form of "CROSS JOIN", so this
query is implemented as lots of nested loops.

> admittedly nonsensical

You could speed up this query by deleting the contents of all tables ...


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: sqlite3 hangs on query

Igor Tandetnik-2
In reply to this post by Jens-Heiner Rechtien
On 2/14/2017 7:33 AM, Jens-Heiner Rechtien wrote:

> please consider the attached dump of a sqlite3 database and the
> following - admittedly nonsensical, don't ask - query over a restored
> version of the database:
>
> *SELECT count(*) FROM spacefavorite, album_asset, albums,
> assetProfileLinks, avatarCacheReferences, cacheReferences, comment,
> conflicts, coreInfo, coreMD5, errors, flags, importSource,
> missingBinariesOnOz, profileRegistration, quota_exceeded,
> renditionRevisions, space, space_album LIMIT 1;**
> *

You are asking SQLite to count an enormous number of rows, so don't be
surprised if that takes an enormous amount of time.

You have a cross-join of 19 tables. Even if each one contains just 2
rows, that's 2^19 ~ 500K rows to work through. And it grows
exponentially from there.
--
Igor Tandetnik

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

Re: sqlite3 hangs on query

Richard Hipp-3
On 2/14/17, Igor Tandetnik <[hidden email]> wrote:

> On 2/14/2017 7:33 AM, Jens-Heiner Rechtien wrote:
>> please consider the attached dump of a sqlite3 database and the
>> following - admittedly nonsensical, don't ask - query over a restored
>> version of the database:
>>
>> *SELECT count(*) FROM spacefavorite, album_asset, albums,
>> assetProfileLinks, avatarCacheReferences, cacheReferences, comment,
>> conflicts, coreInfo, coreMD5, errors, flags, importSource,
>> missingBinariesOnOz, profileRegistration, quota_exceeded,
>> renditionRevisions, space, space_album LIMIT 1;**
>> *
>
> You are asking SQLite to count an enormous number of rows, so don't be
> surprised if that takes an enormous amount of time.
>
> You have a cross-join of 19 tables. Even if each one contains just 2
> rows, that's 2^19 ~ 500K rows to work through. And it grows
> exponentially from there.

I suppose a query planner optimization is possible here.  SQLite could
rewrite queries of the form:

    SELECT count(*) FROM t1,t2,t3,t4,...,tN;

Into something like this:

   SELECT (SELECT count(*) FROM t1)*(SELECT count(*) FROM
t2)*...*(SELECT count(*) FROM tN);

I say that it is possible to do this.  But it seems like a low-value
optimization - just something to complicate testing and increase the
library footprint without actually adding value.  So there is nothing
like this on the To-Do list.
--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: sqlite3 hangs on query

Hick Gunter
Maybe the original intent was to count all the rows in all the tables separately and return a vector of record counts, as a poor man's integrity check to make sure no rows got lost. Like

Select (select count() from t1) as t1,(select count() from t2) as t2, ...;

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Richard Hipp
Gesendet: Dienstag, 14. Februar 2017 17:04
An: SQLite mailing list <[hidden email]>
Betreff: Re: [sqlite] sqlite3 hangs on query

On 2/14/17, Igor Tandetnik <[hidden email]> wrote:

> On 2/14/2017 7:33 AM, Jens-Heiner Rechtien wrote:
>> please consider the attached dump of a sqlite3 database and the
>> following - admittedly nonsensical, don't ask - query over a restored
>> version of the database:
>>
>> *SELECT count(*) FROM spacefavorite, album_asset, albums,
>> assetProfileLinks, avatarCacheReferences, cacheReferences, comment,
>> conflicts, coreInfo, coreMD5, errors, flags, importSource,
>> missingBinariesOnOz, profileRegistration, quota_exceeded,
>> renditionRevisions, space, space_album LIMIT 1;**
>> *
>
> You are asking SQLite to count an enormous number of rows, so don't be
> surprised if that takes an enormous amount of time.
>
> You have a cross-join of 19 tables. Even if each one contains just 2
> rows, that's 2^19 ~ 500K rows to work through. And it grows
> exponentially from there.

I suppose a query planner optimization is possible here.  SQLite could rewrite queries of the form:

    SELECT count(*) FROM t1,t2,t3,t4,...,tN;

Into something like this:

   SELECT (SELECT count(*) FROM t1)*(SELECT count(*) FROM t2)*...*(SELECT count(*) FROM tN);

I say that it is possible to do this.  But it seems like a low-value optimization - just something to complicate testing and increase the library footprint without actually adding value.  So there is nothing like this on the To-Do list.
--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick
Software Engineer
Scientific Games International GmbH
FN 157284 a, HG Wien
Klitschgasse 2-4, A-1130 Vienna, Austria
Tel: +43 1 80100 0
E-Mail: [hidden email]

This communication (including any attachments) is intended for the use of the intended recipient(s) only and may contain information that is confidential, privileged or legally protected. Any unauthorized use or dissemination of this communication is strictly prohibited. If you have received this communication in error, please immediately notify the sender by return e-mail message and delete all copies of the original communication. Thank you for your cooperation.


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

Re: sqlite3 hangs on query

Jens-Heiner Rechtien
In reply to this post by Jens-Heiner Rechtien
Hi SQLite team,

sorry for replaying to my own email, the subscription to this list came
only just through (got eaten by my SPAM folder), so I had to read your
friendly replies via the list archive.

@Simon: thanks for pointing out that attachments do not work on the
list. I should have known this. The dumped database (~800kB) in question
can be found here:

https://dl.dropboxusercontent.com/u/92394185/db.dump.gz

I've checked the database for corruption with a PRAGMA integrity_check,
it found nothing. Anyway the problem persists a dump and restore cycle,
so I doubt that corruption plays a role here.

@Clemens, @Igor, @Richard and @Gunter: I know that the cross join with
19 tables in itself is utter nonsense. The purpose is to name all tables
in the database in one query - in the app there is special mechanism in
place which intercepts queries, parses for the statement for table names
and updates the tables from another data source upfront, before the
query is executed. Naming all tables would force this update for whole
database.

It turned out that the intercepting parser doesn't know about sql
comments, so a simple "SELECT current_date -- <long list of table
names>" works just as well.

But the problem I reported here is genuine. The query doesn't take that
long, the database isn't that sizeable. About 0.3s on my Mac if the
select statement is shortened by the *spacefavorite* table.

Please try the following with the restored database:

The query
*select * from albums, album_asset, cacheReferences, coreInfo, space
limit 1;*
will hang as well.

The query
*select * from albums, album_asset, cacheReferences, coreInfo, coreMD5
limit 1;*
on the other hand runs very fast as only the first rows of each table
are concatenated. Run Time: real 0.005 user 0.000317 sys 0.000248.

Note that the *space* table is empty, so the expected result of the
cross join in the first query would be an empty result set. With a
slightly different data set this is just what I get.

Thanks,
- Heiner



On 14/02/2017 13:33, Jens-Heiner Rechtien wrote:

>
> Hi SQLite team,
>
> please consider the attached dump of a sqlite3 database and the
> following - admittedly nonsensical, don't ask - query over a restored
> version of the database:
>
> *SELECT count(*) FROM spacefavorite, album_asset, albums,
> assetProfileLinks, avatarCacheReferences, cacheReferences, comment,
> conflicts, coreInfo, coreMD5, errors, flags, importSource,
> missingBinariesOnOz, profileRegistration, quota_exceeded,
> renditionRevisions, space, space_album LIMIT 1;**
> *
>
> On iOS, MacOS and Linux this query will busy hang and never return.
> Happens with the command line tool and if used as a prepared statement
> in our iOS app. Changing certain aspects of the query will resolve the
> problem: leaving the table "spacefavorite" out of the query, or
> replacing count(*) with a just an asterisk.
>
> I tried the following versions:
>
> 3.14.0, 3.16.2 (MacOSX Sierra), 3.13.0, 3.17.0 (Linux Fedora 24),
> 3.14.0 (iOS 10), always the same behavior.
>
> Many thanks for your consideration and especially for your great tool.
>
> Heiner
>
> --
>
> Jens-Heiner Rechtien <[hidden email] <mailto:[hidden email]>>
>
> Computer Scientist
>
> Adobe Systems Engineering GmbH
>
> Große Elbstraße 27
>
> 22767 Hamburg
>
>
> Registergericht: Hamburg HRB 745 37
>
> Geschäftsführer: Michael D. Jamrosy, Christian Keim, Thomas Mührke,
> Keith San Felipe
>
>
>
>

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

Re: sqlite3 hangs on query

Simon Slavin-3

On 15 Feb 2017, at 6:53pm, Jens-Heiner Rechtien <[hidden email]> wrote:

> Please try the following with the restored database:
>
> The query
> *select * from albums, album_asset, cacheReferences, coreInfo, space limit 1;*
> will hang as well.
>
> The query
> *select * from albums, album_asset, cacheReferences, coreInfo, coreMD5 limit 1;*
> on the other hand runs very fast as only the first rows of each table are concatenated. Run Time: real 0.005 user 0.000317 sys 0.000248.

Interesting.  I have verified that these all execute in the expected short times:

select * from albums, album_asset, cacheReferences, coreInfo limit 1;

select * from albums, album_asset, cacheReferences, coreInfo, coreMD5 limit 1;

select * from albums, album_asset, cacheReferences, space limit 1;

whereas this one appears to hang:

select * from albums, album_asset, cacheReferences, coreInfo, space limit 1;

It’s using 100% CPU time (on a multicore CPU).  Sampling suggests that the CLI is spending almost all its time doing paging and caching calls.

I’m using SQLite version 3.16.0 2016-11-04 19:09:39.

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

Re: sqlite3 hangs on query

Igor Tandetnik-2
In reply to this post by Jens-Heiner Rechtien
On 2/15/2017 1:53 PM, Jens-Heiner Rechtien wrote:
> Please try the following with the restored database:
>
> The query
> *select * from albums, album_asset, cacheReferences, coreInfo, space
> limit 1;*
> will hang as well.

Ah, interesting. space is empty, which is what makes the difference. In
the query plan, it ends up in the innermost loop. SQLite then goes
through the full cross join of all the other tables, only to get to the
inner loop and discover that there isn't going to be a row after all.
"LIMIT 1" doesn't help any as the query is never going to produce a row.
--
Igor Tandetnik

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

Re: sqlite3 hangs on query

Richard Hipp-3
In reply to this post by Simon Slavin-3
On 2/15/17, Simon Slavin <[hidden email]> wrote:
> select * from albums, album_asset, cacheReferences, coreInfo, space limit 1;
>
> It’s using 100% CPU time (on a multicore CPU).

It is still a 5-way join.  It will terminate after looking at all
20,318,172,864 possible combinations of albums, album_assets,
cacheReferences, and coreInfo and realizing that the space table will
be empty in every case.

It is an optimization opportunity, not a bug.

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: sqlite3 hangs on query

Richard Hipp-3
On 2/15/17, Richard Hipp <[hidden email]> wrote:
>
> It is an optimization opportunity, not a bug.
>

That optimization is now on trunk.

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: sqlite3 hangs on query

Jens-Heiner Rechtien
On 15/02/2017 23:36, Richard Hipp wrote:
> On 2/15/17, Richard Hipp <[hidden email]> wrote:
>> It is an optimization opportunity, not a bug.
>>
> That optimization is now on trunk.
Very cool!

Thanks,
- Heiner


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