Greetings, We are having an issue with the sqlite query plan for one of our queries, which seems to be sub-optimal both in time and in space complexity.
In short, we have two tables that are already sorted on a combination of two fields (which are their primary keys) and we want to union them and apply group by on both the aforementioned fields, like so: select c1, c2, myagg(*) from ( select * from tableA union all select * from tableB ) group by c1, c2; where tableA, tableB have primary key (c1, c2) and their schema comprises 3 integers: c1, c2, and prop. The sqlite query plan creates a temporary B-tree to hold all the records of both tables to execute the group by. This incurs too much time and space complexity compared to the better plan of sequentially iterating over both tables using their B-tree indices on the primary key (since they contain the records already sorted in the group by fields). Like what one would do on the sort step of mergesort to sort two already sorted lists. When we manually implemented the idea of the sequential scan of the two tables and manually gathering the groups and applying the aggregate function, we had a 2X speedup compared to the sqlite plan of creating a temp B-tree. Of course, this speedup would be even greater if we could push the agg function inside the sqlite engine and having it do the sequential scanning plan on the indices directly. Note: In the general case, tableA and tableB have a non empty intersection and neither one is a subset of the other. At the end of the email we provide extensive details for the tables we use and the query we want to run, plus a rundown on the complexity of the sqlite plan and our proposed solution. We are at your disposal for any further clarifications and we are looking forward to your reaction on this. Kind Regards, Manos Karvounis -------------------------------------------------------------------------------------- SQLite version: 3.8.8.1 (latest) pragma table_info(tableA); 0|c1|int(11)|0||1 1|c2|int(11)|0||2 2|prop|int(11)|0||0 pragma table_info(tableB); 0|c1|int(11)|0||1 1|c2|int(11)|0||2 2|prop|int(11)|0||0 select count(*) from tableA; 11095298 select count(*) from tableB; 1000000 pragma index_list(tableA); 0|sqlite_autoindex_tableA_1|1 pragma index_info(sqlite_autoindex_tableA_1); 0|0|c1 1|1|c2 pragma index_list(tableB); 0|sqlite_autoindex_tableB_1|1 pragma index_info(sqlite_autoindex_tableB_1); 0|0|c1 1|1|c2 explain query plan select c1, c2, myagg(*) from ( select * from tableA union all select * from tableB ) group by c1, c2; 2|0|0|SCAN TABLE tableA 3|0|0|SCAN TABLE tableB 1|0|0|COMPOUND SUBQUERIES 2 AND 3 (UNION ALL) 0|0|0|SCAN SUBQUERY 1 0|0|0|USE TEMP B-TREE FOR GROUP BY Note that we get the same query plan even if we explicitly ask for ordering tableA, tableB on c1, c2 prior to group by. explain query plan select c1, c2, myagg(*) from ( select * from tableA union all select * from tableB order by c1, c2 ) group by c1, c2; 2|0|0|SCAN TABLE tableA USING INDEX sqlite_autoindex_tableA_1 3|0|0|SCAN TABLE tableB USING INDEX sqlite_autoindex_tableB_1 1|0|0|COMPOUND SUBQUERIES 2 AND 3 (UNION ALL) 0|0|0|SCAN SUBQUERY 1 0|0|0|USE TEMP B-TREE FOR GROUP BY SQLite Query Plan: (1) Add every record of tableA and tableB on a new B-tree Time complexity: O((|tableA| + |tableB|)log(|tableA|+|tableB|)). Space overhead: O(|tableA|+|tableB|). (2) Run through the B-tree to get groups Time complexity: O(|tableA| + |tableB|). Alternative Query Plan: (1) Iterate over both B-trees in synch since they are already sorted (i.e., the way we would merge two already sorted lists using two running pointers, or the behavior you indicate in 3.2 here https://www.sqlite.org/queryplanner.html). Time complexity: O(|tableA|+|tableB|) Space overhead: O(1) Yet in the following queries the plan (seems to) correctly use the primary key index to speed up the order by. explain query plan select c1, c2, prop from ( select * from tableA union all select * from tableB ) order by c1, c2; 1|0|0|SCAN TABLE tableA USING INDEX sqlite_autoindex_tableA_1 2|0|0|SCAN TABLE tableB USING INDEX sqlite_autoindex_tableB_1 0|0|0|COMPOUND SUBQUERIES 1 AND 2 (UNION ALL) explain query plan select c1, c2, prop from table A order by c1, c2; 0|0|0|SCAN TABLE tableA USING INDEX sqlite_autoindex_tableA_1 Even if one of the tables did not have an index, again the better plan would be to create a temp B-tree for that table and then iterate in synch. Yet sqlite again creates a temp B-tree as shown below. pragma table_info(tableC); 0|c1|int(11)|0||0 1|c2|int(11)|0||0 2|prop|int(11)|0||0 select count(*) from tableC; 1000000 pragma index_list(tableC); explain query plan select c1, c2, myagg(*) from ( select * from tableA union all select * from tableC ) group by c1, c2; 2|0|0|SCAN TABLE tableA 3|0|0|SCAN TABLE tableC 1|0|0|COMPOUND SUBQUERIES 2 AND 3 (UNION ALL) 0|0|0|SCAN SUBQUERY 1 0|0|0|USE TEMP B-TREE FOR GROUP BY explain query plan select c1, c2, myagg(*) from ( select * from tableA union all select * from tableC order by c1, c2 ) group by c1, c2; 2|0|0|SCAN TABLE tableA USING INDEX sqlite_autoindex_tableA_1 3|0|0|SCAN TABLE tableC 3|0|0|USE TEMP B-TREE FOR ORDER BY 1|0|0|COMPOUND SUBQUERIES 2 AND 3 (UNION ALL) 0|0|0|SCAN SUBQUERY 1 0|0|0|USE TEMP B-TREE FOR GROUP BY explain query plan select c1, c2, prop from ( select * from tableA union all select * from tableC ) order by c1, c2; 1|0|0|SCAN TABLE tableA USING INDEX sqlite_autoindex_tableA_1 2|0|0|SCAN TABLE tableC 2|0|0|USE TEMP B-TREE FOR ORDER BY 0|0|0|COMPOUND SUBQUERIES 1 AND 2 (UNION ALL) _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
