[ZODB-Dev] Re: [Zope3-dev] Re: Community opinion about
dieter at handshake.de
Thu Mar 29 16:11:32 EDT 2007
Lennart Regebro wrote at 2007-3-28 18:25 +0200:
>On 3/27/07, Dieter Maurer <dieter at handshake.de> wrote:
>> However, this approach is only efficient when the sort index size
>> is small compared to the result size.
>Sure. But with incremental searching, the result size is always one, right? ;-)
No. You want to have one (the best one) hit from a (potentially) large
set of hits. The size of this set is essential whether or not
a sort index is efficient.
The principle is like this:
Let "S" be the hit set.
Assume you sort index consists of values i1 < i2 < .... and
use "D(i)" for the set of documents indexed under i,
Then "D(i1) intersect S" preceeds "D(i2) intersects S" preceeds
"D(i3) intersects S", etc in the result ordered by the index i.
If the index size is small compared to "S" (and if we assume the
hits are uniformly distributed over the indexed values),
then each intersection can determine (on average) a significant
amount of sorted hits. You can efficiently determine the first hits.
Assume on the other hand that "S" contains a single element
and that the index is large, then almost all intersections are
a vaste of time (as the result is the empty set).
More information about the ZODB-Dev