[SOLVED] Extreme slow-down from ORDER BY clause

Extreme slow-down from ORDER BY clause

My query:

SELECT * FROM "mytable" where col1="foo"

resolves in around 0.5 seconds (~100 results of ~100,000 rows in a 700MB database file). As I add ORDER BY it takes 120 seconds:

SELECT * FROM "mytable" where col1="foo" ORDER BY col2

Even when I limit the result:

SELECT * FROM (SELECT * FROM "mytable" where col1="foo" LIMIT 1) ORDER BY col2

it takes 120 seconds although there's nothing to sort. The exception is if I ORDER BY rowid (instead of ORDER BY col2), or like this (0.5 seconds):

SELECT * FROM "mytable" WHERE rowid IN (SELECT rowid FROM "mytable"  WHERE col1="foo") ORDER BY col2

I VACUUM'ed and checked integrity but this problem persists. I use SQLite version: 3.7.7.1. The slowdowns appear both in phpLiteAdmin and my PHP code.

EXPLAIN QUERY PLAN SELECT * FROM "mytable" WHERE col1="foo"

selectid|order|from|detail
       0|    0|   0|SCAN TABLE mytable (~11345 rows)

EXPLAIN QUERY PLAN SELECT * FROM "mytable" WHERE col1="foo" ORDER BY col2

selectid|order|from|detail
       0|    0|   0|SEARCH TABLE mytable USING AUTOMATIC COVERING INDEX (col1=?) (~7 rows)
       0|    0|   0|USE TEMP B-TREE FOR ORDER BY

Solution

So it seems SQLite erroneously thinks it would be cheaper to build a temporary index (automatic covering index) to run your query instead of sorting in memory. Obviously building an index on 100,000 rows for every query isn't the most optimal query plan.

An obvious solution would be to add an index on the columns on which you want to perform querying/sorting.

CREATE INDEX col1_idx ON mytable (col1);
CREATE INDEX col2_idx ON mytable (col2);