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:sqlite-users-boun...@mailinglists.sqlite.org] > 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 > 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