[ZODB-Dev] Indexing: Query Optimization

[Christian Robottom Reis]

On Mon, May 09, 2005 at 05:28:05PM +0200, Thomas Guettler wrote:
> > > Since btrees and btree ranges don't know their size, you need to do
> > > something like this:
> > > - do range searches at the end
> > > - if index "foo" is used, use it first, ...
> >
> > Hmmm. Can you elaborate on this? I don't quite grasp what you mean.
> 
> If you want the intersection (AND) of some sets, you can increase the speed
> if you take the the smallest set and check for each entry if it is a member of 
> the other sets. If you do take the large set first, you need to do more 
> checks for membership.
> 
> The applhe large set first, you need to do more 
> checks for membership.
> 
> The application developer might know that a search in index "foo" results in 
> small results. That's what I meant with "if index 'foo' is used, use it 
> first".

Ah, yes, this makes lots of sense. Hardcoding these heuristics isn't
very nice, though -- at least I don't know how to do it beyond using a
learning query optimizer, or telling the user to reorder his query: for
instance, in IC, it is faster to query through a small catalog and AND
that with a large catalog than the reverse. Having the user alter the
order of the query is a hack but it allows for situation-specific
optimization, which in many contexts is useful.

We do a little trick that avoids even touching the larger catalog (and
the largish sets that are stored in their keys) when doing ANDed joins:
if the number of items in the smaller catalog is below a certain magic
number, we synthesize a temporary index with just those values, querying
through there. This surprisingly gives great results.

However, then I question the general validity of the phrase:

> > > - do range searches at the end

Because in the case of our [business-oriented] applications,
double-bounded range searches (A < x < B) are among the fastest, thanks
to BTree index operations.

--
Christian Robottom Reis | http://async.com.br/~kiko/ | [+55 16] 3376 0125