How can I optimize SQLite ORDER BY rowid?

Question

I want to query my sqlite db for all "level" values greater than 20, limit the result to 100 and order by rowid.

When ordering by rowid, the query is much slower. The database contains ~3 million records and the maximum value of level is 50. An index is created for level.

This statement takes ~20ms:

SELECT * FROM log WHERE level > 20 LIMIT 100

This statement takes ~100ms:

SELECT * FROM log WHERE level > 20 ORDER BY rowid LIMIT 100

This statement takes ~1000ms (no rows with level value greater than 50 exists):

SELECT * FROM log WHERE level > 50 ORDER BY rowid LIMIT 100

Is there a way to optimize this for faster ORDER BY query's?

This is the index used:

CREATE INDEX level_idx ON table (level)

Answer 1

There are two possible methods to execute this query:

1. Search the first entry with level>20 in the level_idx index, and then scan through all the following entries and fetch each corresponding row from the table. Because the index entries are not stored in rowid order, all the results must then be sorted. Then the first 100 of those can be returned.

2. Ignore the index. Scan through all rows of the table (which are already stored in rowid order), and return any where the level column matches.

The database estimates that the second method is faster.

If you estimate that the first method is faster, i.e., that so few rows match the level filter that fetching and sorting the remaining rows is faster than ignoring the non-matching rows while scanning through the table, then you can force the database to use the index with the INDEXED BY clause:

SELECT *
FROM log INDEXED BY level_idx
WHERE level > 20
ORDER BY rowid
LIMIT 100

However, forcing an index can lead to horrible slowdowns if your own estimate is wrong.