Williams, Ken wrote:
CREATE INDEX whatever ON output(verb_id,tag);
That will make it O(NlogN) instead of O(N**2).
So, no way to make it O(N)? If the two indexes could be iterated together,
as in the following pseudocode, it would seem to be an O(N) operation.
Retrieving a single record from a BTree is an O(logN) operation.
Doing so N times gives O(NlogN).
O(N) would be possible if you were to step straight through
both tables in native order (INTEGER PRIMARY KEY order) without
having to do a search for each record using an index. But
that would only work, of course, if the join was on the
INTEGER PRIMARY KEY of both tables. And even then, SQLite
doesn't do that particular optimization.
--
D. Richard Hipp -- [EMAIL PROTECTED] -- 704.948.4565
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
