optimization request: ORDER BY with LIMIT clause

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

optimization request: ORDER BY with LIMIT clause

Sqlite 3.2.7 does not seem to perform a fairly straightforward database optimization for queries
involving an ORDER BY clause with a LIMIT clause.

Given a table or view with a large number of rows, such as View1 below:

  CREATE TABLE t1(a,b,c);
  INSERT INTO "t1" VALUES(4, 5, 6);
  INSERT INTO "t1" VALUES(9, 12, 10);
  INSERT INTO "t1" VALUES(900, -23.4, 8900);
  INSERT INTO "t1" VALUES(190, 3, -8.9003);
  INSERT INTO "t1" VALUES(400, 450, 550);
  INSERT INTO "t1" VALUES(5400, 1450, 3445);
  INSERT INTO "t1" VALUES(321, 345, -0.0342);
  INSERT INTO "t1" VALUES(34, 8888, 2382344);
  INSERT INTO "t1" VALUES(-900000.0, -3478000.0, 10);
  INSERT INTO "t1" VALUES(999, 888, 777);
  INSERT INTO "t1" VALUES(9, -888, 7.77);
  CREATE VIEW View1 as
   select (aa.a*bb.b-cc.c+dd.a*ee.b-ff.c*gg.a) as V
   from t1 aa, t1 bb, t1 cc, t1 dd, t1 ee, t1 ff, t1 gg;

the following query will take a great deal of time, exhaust all memory and crash on my modest
RAM-deprived machine:

 select V from View1 order by V LIMIT 5;

Whereas this very similar query runs in under a minute while using a small constant amount of RAM
(specifically 2,044 K):

  sqlite> select min(V) from View1;

Instead of storing and sorting all intermediate calculated rows in memory for the first query,
SQLite need only store the number of rows as specified in the LIMIT clause and compare each new
row against these rows as per the ORDER BY clause, replacing and reordering the intermediate
result rows as necessary.

Adding such an optimization would be a huge benefit to data-mining applications or any
SQLite-driven websites with complex views and large datasets.


(No need for advice to speed up this specific query under SQLite 3.2.x - it is a contrived example
for demonstration purposes only).

Yahoo! for Good - Make a difference this year.