On 4/24/15, John Pitney <john at pitney.org> wrote: > > 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? > > 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;
I cannot think of an algorithm that would solve that in O(M) time. But if you know of one, describe it here and maybe I'll add it to SQLite's query planner. -- D. Richard Hipp drh at sqlite.org
