Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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?

share|improve this question
    
can you give some information about the distribution of values in the frequency column? –  Jack Douglas May 23 '12 at 8:59
add comment

1 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?

share|improve this answer
    
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. –  ypercube May 22 '12 at 21:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.