In my application, values v associated with metrics m and times t are
inserted into one big table d. Another process opens the same database
and looks in d for metrics with at least N entries, sorted by t. I'm
finding that the time to complete the query grows linearly with the
row count M of table d, even though, in the example here, the query
results are identical for any M >= 200.
I've made a self-contained example, where N = 20 and M = 200. Is
there a way to write the final select statement so that its completion
time does not grow with M?
-- demo.sql
-- create big table of data with M = 200
CREATE TABLE d (m INT NOT NULL, t INT NOT NULL, v REAL);
CREATE UNIQUE INDEX d_ind_1 ON d (m, t);
.timer on
INSERT INTO d (m, t, v)
WITH RECURSIVE
cnt(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM cnt WHERE x<200)
SELECT (x % 10) + 1 AS m, x+1 AS t, 1.0 AS v
FROM cnt;
.timer off
-- arrange for one rare value of m, which should not appear in results
DELETE FROM d WHERE m = 5;
INSERT INTO d (m, t, v)
WITH RECURSIVE
cnt(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM cnt WHERE x<10)
SELECT 5 AS m, x + 1230000 AS t, 1.0 AS v
FROM cnt;
-- now, for each value of m, look for exactly N rows, ordered by t
CREATE TEMP TABLE tt (m INT NOT NULL);
INSERT INTO tt (m) SELECT DISTINCT m from d;
.timer on
SELECT m, n_points, t_csv, v_csv, max_rowid FROM
(SELECT tt.m AS "m",
count(v) AS "n_points",
substr(group_concat(t), 1, 16) || '...' AS "t_csv",
substr(group_concat(round(v, 2)), 1, 16) || '...' AS "v_csv",
max(d.rowid) AS "max_rowid"
FROM tt, d
WHERE tt.m = d.m
AND d.t <= (SELECT MAX(d3.t) FROM (SELECT d2.t FROM d AS d2
WHERE d.m = d2.m ORDER BY d2.t LIMIT 20) AS d3)
GROUP BY tt.m ORDER BY tt.m, d.t)
WHERE n_points = 20;
-- end of demo.sql
The results are the following, on a Windows 7 64-bit platform:
$ sqlite3 -version
3.8.4.3 2014-04-03 16:53:12 a611fa96c4a848614efe899130359c9f6fb889c3
$ sqlite3 < demo.sql
Run Time: real 0.003 user 0.000000 sys 0.000000
1|20|1,11,21,31,41,51...|1.0,1.0,1.0,1.0,...|191
2|20|2,12,22,32,42,52...|1.0,1.0,1.0,1.0,...|192
3|20|3,13,23,33,43,53...|1.0,1.0,1.0,1.0,...|193
4|20|4,14,24,34,44,54...|1.0,1.0,1.0,1.0,...|194
6|20|6,16,26,36,46,56...|1.0,1.0,1.0,1.0,...|196
7|20|7,17,27,37,47,57...|1.0,1.0,1.0,1.0,...|197
8|20|8,18,28,38,48,58...|1.0,1.0,1.0,1.0,...|198
9|20|9,19,29,39,49,59...|1.0,1.0,1.0,1.0,...|199
10|20|10,20,30,40,50,6...|1.0,1.0,1.0,1.0,...|200
Run Time: real 0.012 user 0.000000 sys 0.000000
$ sed -e 's/200/200000/' < demo.sql | sqlite3
Run Time: real 0.608 user 0.592804 sys 0.000000
1|20|1,11,21,31,41,51...|1.0,1.0,1.0,1.0,...|191
2|20|2,12,22,32,42,52...|1.0,1.0,1.0,1.0,...|192
3|20|3,13,23,33,43,53...|1.0,1.0,1.0,1.0,...|193
4|20|4,14,24,34,44,54...|1.0,1.0,1.0,1.0,...|194
6|20|6,16,26,36,46,56...|1.0,1.0,1.0,1.0,...|196
7|20|7,17,27,37,47,57...|1.0,1.0,1.0,1.0,...|197
8|20|8,18,28,38,48,58...|1.0,1.0,1.0,1.0,...|198
9|20|9,19,29,39,49,59...|1.0,1.0,1.0,1.0,...|199
10|20|10,20,30,40,50,6...|1.0,1.0,1.0,1.0,...|200
Run Time: real 1.063 user 1.045207 sys 0.000000
$ sed -e 's/200/400000/' < demo.sql | sqlite3
Run Time: real 1.255 user 1.248008 sys 0.000000
1|20|1,11,21,31,41,51...|1.0,1.0,1.0,1.0,...|191
2|20|2,12,22,32,42,52...|1.0,1.0,1.0,1.0,...|192
3|20|3,13,23,33,43,53...|1.0,1.0,1.0,1.0,...|193
4|20|4,14,24,34,44,54...|1.0,1.0,1.0,1.0,...|194
6|20|6,16,26,36,46,56...|1.0,1.0,1.0,1.0,...|196
7|20|7,17,27,37,47,57...|1.0,1.0,1.0,1.0,...|197
8|20|8,18,28,38,48,58...|1.0,1.0,1.0,1.0,...|198
9|20|9,19,29,39,49,59...|1.0,1.0,1.0,1.0,...|199
10|20|10,20,30,40,50,6...|1.0,1.0,1.0,1.0,...|200
Run Time: real 2.090 user 2.074813 sys 0.000000
--
John Pitney
john at pitney.org
