Slow query, with correlated sub-sub-query

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

Slow query, with correlated sub-sub-query

E.Pasma
Hello, below is a theoretical query that becomes slow when the number  
of rows increases. What it does is:
- scan input cases in table a
- for each input case:
-- determine the smallest value of attribute size of elements in table  
ab
-- count the number of elements having this smallest size
With 3 rows in table a and 3*1000 in ab this takes already several  
seconds.
I'm not so much interested in an alternative solution, though  
interesting, and merely want to show an inefficient construction. That  
is a sub-sub-query correlated directly to the main query.
Thanks, E. Pasma

.version
SQLite 3.19.3 2017-06-08 14:26:17 ...

create table a (a, primary key (a))
;
create table ab (a, b, size, primary key (a,b))
;
insert into a
with i as (select 1 as i union all select i+1 from i where i<3)
select i from i
;
insert into ab
with i as (select 1 as i union all select i+1 from i where i<1000)
select a, i as b, random()%10 as size from a, i
;
.eqp on
.timer on
select  a,
        (
            select  count(*)
            from    ab
            where   a=a.a
            and     size=(select min(size) from ab where a=a.a)
        )
from    a
;
--EQP-- 0,0,0,SCAN TABLE a
--EQP-- 0,0,0,EXECUTE CORRELATED SCALAR SUBQUERY 1
--EQP-- 1,0,0,SEARCH TABLE ab USING INDEX sqlite_autoindex_ab_1 (a=?)
--EQP-- 1,0,0,EXECUTE CORRELATED SCALAR SUBQUERY 2
--EQP-- 2,0,0,SEARCH TABLE ab USING INDEX sqlite_autoindex_ab_1 (a=?)
1|56
2|53
3|49
Run Time: real 2.678 user 2.597794 sys 0.008801

_______________________________________________
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: Slow query, with correlated sub-sub-query

David Raymond
I acknowledge you said you weren't so much interested in an alternative solution, but...

How about something like

select a, min(size) as minSize, recCount
from
  (select a, size, count(*) as recCount
  from a inner join ab
  using (a)
  group by a, size)
group by a;

The inner one will group by a and size, then the outer group by with the min() will pick the minimum and use that line to populate the bare column of recCount.

With 10,000 here's your original:

sqlite> select a, (select count(*) from ab where a = a.a and size = (select min(size) from ab where a = a.a)) from a;
--EQP-- 0,0,0,SCAN TABLE a
--EQP-- 0,0,0,EXECUTE CORRELATED SCALAR SUBQUERY 1
--EQP-- 1,0,0,SEARCH TABLE ab USING INDEX sqlite_autoindex_ab_1 (a=?)
--EQP-- 1,0,0,EXECUTE CORRELATED SCALAR SUBQUERY 2
--EQP-- 2,0,0,SEARCH TABLE ab USING INDEX sqlite_autoindex_ab_1 (a=?)
a|(select count(*) from ab where a = a.a and size = (select min(size) from ab where a = a.a))
1|522
2|486
3|500
Memory Used:                         975336 (max 1508448) bytes
Number of Outstanding Allocations:   270 (max 326)
Number of Pcache Overflow Bytes:     850880 (max 986272) bytes
Number of Scratch Overflow Bytes:    0 (max 12472) bytes
Largest Allocation:                  524288 bytes
Largest Pcache Allocation:           4256 bytes
Largest Scratch Allocation:          12472 bytes
Lookaside Slots Used:                35 (max 100)
Successful lookaside attempts:       71296
Lookaside failures due to size:      19
Lookaside failures due to OOM:       119
Pager Heap Usage:                    844920 bytes
Page cache hits:                     2030205
Page cache misses:                   0
Page cache writes:                   0
Schema Heap Usage:                   1472 bytes
Statement Heap/Lookaside Usage:      32400 bytes
Fullscan Steps:                      2
Sort Operations:                     0
Autoindex Inserts:                   0
Virtual Machine Steps:               1800501558
Run Time: real 39.031 user 38.906649 sys 0.015600


And the alternative:
sqlite> select a, min(size) as minSize, recCount from (select a, size, count(*) as recCount from a inner join ab using (a) group by a, size) group by a;
--EQP-- 1,0,0,SCAN TABLE a USING COVERING INDEX sqlite_autoindex_a_1
--EQP-- 1,1,1,SEARCH TABLE ab USING INDEX sqlite_autoindex_ab_1 (a=?)
--EQP-- 1,0,0,USE TEMP B-TREE FOR GROUP BY
--EQP-- 0,0,0,SCAN SUBQUERY 1
--EQP-- 0,0,0,USE TEMP B-TREE FOR GROUP BY
a|minSize|recCount
1|-9|522
2|-9|486
3|-9|500
Memory Used:                         984136 (max 1513008) bytes
Number of Outstanding Allocations:   280 (max 332)
Number of Pcache Overflow Bytes:     855136 (max 986272) bytes
Number of Scratch Overflow Bytes:    0 (max 12472) bytes
Largest Allocation:                  524288 bytes
Largest Pcache Allocation:           4256 bytes
Largest Scratch Allocation:          12472 bytes
Lookaside Slots Used:                55 (max 100)
Successful lookaside attempts:       102118
Lookaside failures due to size:      26
Lookaside failures due to OOM:       258
Pager Heap Usage:                    849164 bytes
Page cache hits:                     199
Page cache misses:                   0
Page cache writes:                   0
Schema Heap Usage:                   1736 bytes
Statement Heap/Lookaside Usage:      58280 bytes
Fullscan Steps:                      2
Sort Operations:                     2
Autoindex Inserts:                   0
Virtual Machine Steps:               511684
Run Time: real 0.063 user 0.015600 sys 0.000000


-----Original Message-----
From: sqlite-users [mailto:[hidden email]] On Behalf Of E.Pasma
Sent: Friday, July 07, 2017 9:47 AM
To: SQLite mailing list
Subject: [sqlite] Slow query, with correlated sub-sub-query

Hello, below is a theoretical query that becomes slow when the number  
of rows increases. What it does is:
- scan input cases in table a
- for each input case:
-- determine the smallest value of attribute size of elements in table  
ab
-- count the number of elements having this smallest size
With 3 rows in table a and 3*1000 in ab this takes already several  
seconds.
I'm not so much interested in an alternative solution, though  
interesting, and merely want to show an inefficient construction. That  
is a sub-sub-query correlated directly to the main query.
Thanks, E. Pasma

.version
SQLite 3.19.3 2017-06-08 14:26:17 ...

create table a (a, primary key (a))
;
create table ab (a, b, size, primary key (a,b))
;
insert into a
with i as (select 1 as i union all select i+1 from i where i<3)
select i from i
;
insert into ab
with i as (select 1 as i union all select i+1 from i where i<1000)
select a, i as b, random()%10 as size from a, i
;
.eqp on
.timer on
select  a,
        (
            select  count(*)
            from    ab
            where   a=a.a
            and     size=(select min(size) from ab where a=a.a)
        )
from    a
;
--EQP-- 0,0,0,SCAN TABLE a
--EQP-- 0,0,0,EXECUTE CORRELATED SCALAR SUBQUERY 1
--EQP-- 1,0,0,SEARCH TABLE ab USING INDEX sqlite_autoindex_ab_1 (a=?)
--EQP-- 1,0,0,EXECUTE CORRELATED SCALAR SUBQUERY 2
--EQP-- 2,0,0,SEARCH TABLE ab USING INDEX sqlite_autoindex_ab_1 (a=?)
1|56
2|53
3|49
Run Time: real 2.678 user 2.597794 sys 0.008801

_______________________________________________
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Slow query, with correlated sub-sub-query

Keith Medcalf
In reply to this post by E.Pasma

Well of course.  You are aware that a correlated subquery means "for each candidate result execute the query"?

So as you have formulated the query it means:

for each row in a
    compute the result count which
         for each ab candidate row
             calculate whether it is the minimum
   
which means that the you have requested that the same result be computed many times over.  You have requested exampination of count(a) * count(ab) * count(ab) rows.

Instead you should be computing the min(size) for each group of a once, and using that value in the correlated subquery

select a.a,
       (
           select count(*)
             from ab
            where a == a.a
              and size == b.size
       ) as acount
  from a,
       (
           select a,
                  min(size) as size
             from ab
         group by a
        ) as b
where a.a == b.a;

This will result in scanning count(ab) + count(a) * count(ab) rows.  Which is significantly less.  On my computer it reduces the execution time of the original query you posited from 400 ticks to less than 1 tick (ie, from 500 ms to <8 ms)

I do not know if any optimizer can flatten you original query to any significant degree.  Some optimizers may arrive at my fixed up query because they are capable of doing a hash table lookup on the result of the innermost correlate.  SQLite does not do that, and without that capability I do not think there is a relational database query optimizer on the planet that can help you.

--
˙uʍop-ǝpısdn sı ɹoʇıuoɯ ɹnoʎ 'sıɥʇ pɐǝɹ uɐɔ noʎ ɟı

> -----Original Message-----
> From: sqlite-users [mailto:[hidden email]]
> On Behalf Of E.Pasma
> Sent: Friday, 7 July, 2017 07:47
> To: SQLite mailing list
> Subject: [sqlite] Slow query, with correlated sub-sub-query
>
> Hello, below is a theoretical query that becomes slow when the number
> of rows increases. What it does is:
> - scan input cases in table a
> - for each input case:
> -- determine the smallest value of attribute size of elements in table
> ab
> -- count the number of elements having this smallest size
> With 3 rows in table a and 3*1000 in ab this takes already several
> seconds.
> I'm not so much interested in an alternative solution, though
> interesting, and merely want to show an inefficient construction. That
> is a sub-sub-query correlated directly to the main query.
> Thanks, E. Pasma
>
> .version
> SQLite 3.19.3 2017-06-08 14:26:17 ...
>
> create table a (a, primary key (a))
> ;
> create table ab (a, b, size, primary key (a,b))
> ;
> insert into a
> with i as (select 1 as i union all select i+1 from i where i<3)
> select i from i
> ;
> insert into ab
> with i as (select 1 as i union all select i+1 from i where i<1000)
> select a, i as b, random()%10 as size from a, i
> ;
> .eqp on
> .timer on
> select  a,
>         (
>             select  count(*)
>             from    ab
>             where   a=a.a
>             and     size=(select min(size) from ab where a=a.a)
>         )
> from    a
> ;
> --EQP-- 0,0,0,SCAN TABLE a
> --EQP-- 0,0,0,EXECUTE CORRELATED SCALAR SUBQUERY 1
> --EQP-- 1,0,0,SEARCH TABLE ab USING INDEX sqlite_autoindex_ab_1 (a=?)
> --EQP-- 1,0,0,EXECUTE CORRELATED SCALAR SUBQUERY 2
> --EQP-- 2,0,0,SEARCH TABLE ab USING INDEX sqlite_autoindex_ab_1 (a=?)
> 1|56
> 2|53
> 3|49
> Run Time: real 2.678 user 2.597794 sys 0.008801
>
> _______________________________________________
> 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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Slow query, with correlated sub-sub-query

E.Pasma
In reply to this post by E.Pasma

Keith, this definitely explains the observed time as it is relative to  
count(a)*count (ab)**2, thus non-linear.
And a correlated sub-query is generally recalculated for each row.
But I do not agree with everything.
In my example it is correlated to the outermost query, and not to the  
sub-query in which it occurs.
Theoretically the optimizer can take this into account and only  
recalculate for each row in the outermost query. And if I'm not  
mistaken Postgress does so. Below is a version modified for pgsql that  
runs fast no matter the number of rows.
Thanks for the suggested change, where the minimum size is computed is  
a sub-query (not sub-sub) and joined to the other sub-query. This is  
so elegant. I still need to compare the timing to David's version and  
use the fastest.

/* sudo -u postgres psql < issue2p.sql */
drop table if exists a
;
drop table if exists ab
;
create table a (a int, primary key (a))
;
create table ab (a int, b int, size int, primary key (a,b))
;
insert into a
with recursive i as (select 1 as i union all select i+1 from i where  
i<3)
select i from i
;
insert into ab
with recursive i as (select 1 as i union all select i+1 from i where  
i<10000)
select a, i as b, (a+i)%10 as size from a, i
;
select  a,
         (
             select  count(*)
             from    ab
             where   a=a.a
             and     size=(select min(size) from ab where a=a.a)
         )
from    a
;

Keith Medcalf wrote:

> Well of course.  You are aware that a correlated subquery means "for  
> each candidate result execute the query"?
>
> So as you have formulated the query it means:
>
> for each row in a
>     compute the result count which
>          for each ab candidate row
>              calculate whether it is the minimum
>
> which means that the you have requested that the same result be  
> computed many times over.  You have requested exampination of  
> count(a) * count(ab) * count(ab) rows.
>
> Instead you should be computing the min(size) for each group of a  
> once, and using that value in the correlated subquery
>
> select a.a,
>        (
>            select count(*)
>              from ab
>             where a == a.a
>               and size == b.size
>        ) as acount
>   from a,
>        (
>            select a,
>                   min(size) as size
>              from ab
>          group by a
>         ) as b
> where a.a == b.a;
>
> This will result in scanning count(ab) + count(a) * count(ab) rows.  
> Which is significantly less.  On my computer it reduces the  
> execution time of the original query you posited from 400 ticks to  
> less than 1 tick (ie, from 500 ms to <8 ms)
>
> I do not know if any optimizer can flatten you original query to any  
> significant degree.  Some optimizers may arrive at my fixed up query  
> because they are capable of doing a hash table lookup on the result  
> of the innermost correlate.  SQLite does not do that, and without  
> that capability I do not think there is a relational database query  
> optimizer on the planet that can help you.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Loading...