[ZODB-Dev] Re: [Zope3-dev] Re: Community opinion about search+filter

[Dieter Maurer]

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).


-- 
Dieter