Performance of query with a range condition and order by

Question

We have the following table (in SQLite on Android) which a tree structure (Nested Set model) of words and their frequencies:

lexikon
-------
_id integer PRIMARY KEY
word text
frequency integer
lset integer UNIQUE KEY
rset integer UNIQUE KEY

And the query:

SELECT word
FROM lexikon
WHERE lset BETWEEN @Low AND @High
ORDER BY frequency DESC
LIMIT @N

I suppose a covering index on (lset, frequency, word) would be useful but I feel it may not perform well if there are too many lset values in the (@High, @Low) range.

A simple index on (frequency DESC) may also be sufficient sometimes, when a search using that index yields early the @N rows that match the range condition.

But it seems that performance depends a lot on the parameter values.

Is there a way to make it perform fast, regardless of whether the range (@Low, @High) is wide or narrow and regardless of whether the top frequency words are luckily in the (narrow) selected range?

• Jack Douglas: can you give some information about the distribution of values in the frequency column?

Answer 1

I would say give that covering index a try (lset, frequency, word), but you did not give much information. Please post how many rows does your table have, how large in bytes it is, how many maximum rows are you expecting to get back from your query, what's the cardinality of your data?

• ypercubeᵀᴹ: Table has about 100K rows. The query without the LIMIT would return a few thousand rows in some cases and less than 10 rows in other cases.