[ZODB-Dev] Indexing: Query Optimization

[Dieter Maurer]

Thomas Guettler wrote at 2005-5-3 14:44 +0200:
> ...
>I developed a simple index using ZODB. Searching for single values is
>very fast. Searching big ranges is slow.
>
>Example: 
>Search: 
>
>customer_id=0815
>date_start=2001-01-01
>date_end=2004-12-31
>....
>The index holds a btree which maps values to docids. The search
>for customer_id is very fast (Maybe 500 results) . But the range search from 
>date_start to date_end is slow (Maybe 100.000 results).
>
>Up to now I use the intersection method of the BTree package to
>join the result with a logical AND.
>
>It would be better if the index would do the search for customer_id
>first, and then filter the result by deleting entries which are not in
>the given time period.

"IncrementalSearch" does it quite intelligently (although not
in your suggested way).

Unfortunately, it is not yet implemented in "C"
and therefore cannot yet beat "multiunion" (which you should use for unions
of more than a few sets). However, for highly specific "and"
queries, it is already faster than traditional search
even when a large "or" query is involved (which uses "multiunion";
it is several orders of magnitude faster, if the "or" uses
iterated "union"s rather than "multiunion").

You find "IncrementalSearch" at

  <http://www.dieter.handshake.de/pyprojects/zope>

I work on a C implementation. But, this is a lot of work
and therefore will take time...

-- 
Dieter