At 11:12 AM 1/14/2004 -0500, D. Richard Hipp wrote:
SELECT count(*) FROM table WHERE col1>'abc' AND col1<'xyz';
In the original query, the result was indeed a count(*) so no access to the data we required there. But access to the data was required in order to evaluate the WHERE clause. So it is still O(NlogN).
What is different between his where clause and the one you cite as an example that only takes O(N)? Is it just that in your example col1 is (part of) the index? So, wouldn't Ken be able to do the same, except that he needs to step through two indices?
In the example above, both terms of the WHERE clause are satisfied by an index and are removed from the WHERE clause. In Ken's code, he had an additional term:
(p.stop!=o.stop OR pstart!=o.start)
That additional term cannot be satisfied by the index and must be evaluated by looking up the record in the main table.
Without that additional term, it would be possible, in theory, to run the join in O(N) time. But it would require a new join execution strategy which SQLite does not support at this time. -- D. Richard Hipp -- [EMAIL PROTECTED] -- 704.948.4565
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
