So, no way to make it O(N)? If the two indexes could be
Retrieving a single record from a BTree is an O(logN) operation. Doing so N times gives O(NlogN).
Oh, I thought it was also possible to step straight through an index,
You can step straight through the index in linear time. But for each index entry you encounter, you have to look up a record in the main table in order to get the data. It's the second step, the table lookup, that takes O(logN).
In some cases you can avoid the O(logN) lookup of the main table entry and just use the index. For example:
SELECT count(*) FROM table WHERE col1>'abc' AND col1<'xyz';
In this case, since you are never using any data from the table, just counting entries, it is sufficient to step through through the index and the operation runs in linear time. As recently as 2 weeks ago, SQLite would go ahead and look up the main table entry even though the data was needed. That extra lookup was optimized out with check-in [1165].
http://www.sqlite.org/cvstrac/chngview?cn=1165
After check-in [1165], queries such as the above are about 10x faster on large tables.
-- D. Richard Hipp -- [EMAIL PROTECTED] -- 704.948.4565
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
