> -----Original Message-----
> From: D. Richard Hipp [mailto:[EMAIL PROTECTED]
> Sent: Tuesday, January 13, 2004 6:17 PM
> To: [EMAIL PROTECTED]
> Subject: Re: [sqlite] Optimizing a query
>
>
> > Can anyone suggest a good way to optimize the following query?
> >
> > SELECT count(*) FROM propositions p, output o
> > WHERE p.verb_id=o.verb_id
> > AND p.tag=o.tag
> > AND (p.stop!=o.stop OR p.start!=o.start);
> >
>
> 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.
P_INDEX:
while ($p_entry = p_index.next) {
while ($o_entry = o_index.next) {
if ($o_entry == $p_entry) {
...do the rest of the query criteria...
} elsif ($o_entry > $p_entry {
next P_INDEX;
}
}
}
-Ken
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
