Xref: utzoo comp.object:104 comp.databases:3824
Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!swrinde!ucsd!ucbvax!pasteur!eden!mao
From: mao@eden (Mike Olson)
Newsgroups: comp.object,comp.databases
Subject: Re: Query optimization in OODB
Summary: optimization is tricky
Keywords: indices, comparison operators
Message-ID: <18122@pasteur.Berkeley.EDU>
Date: 9 Oct 89 17:07:20 GMT
References: <16958@watdragon.waterloo.edu> <1989Oct6.153505.24492@odi.com>
Sender: news@pasteur.Berkeley.EDU
Reply-To: mao@postgres.Berkeley.EDU (Mike Olson)
Followup-To: comp.databases
Distribution: comp
Organization: University of California, Berkeley
Lines: 42

In <1989Oct6.153505.24492@odi.com>, jack@odi.com (Jack Orenstein) writes

> As for a method appearing as an operator: this is less of a problem,
> as long as certain properties are guaranteed. For example, =, <, and >
> can be defined for rational numbers, and an index keyed by instances
> of a rational number class can be created. As long as the optimizer
> knows (because the class definer asserts it) that the functions
> implementing =, <, and > for rational numbers behave "as expected",
> optimization can proceed. See some of the early POSTGRES papers for
> more information along these lines.

mr. orenstein is correct, but he raises an interesting point that some
readers may have overlooked.  in order to optimize queries using <, the
optimizer has to understand what < means.  this isn't a problem for the
operators most vendors supply -- rationals have several well-defined partial
orderings, for example.

this isn't always true, though, and therefore it's not always easy to
optimize queries using methods (or comparison operators).  for example,
the initial postgres rtree index implementation provides operators for
"box contains", "box is contained by", "box is left {or right or above or
below} box," and so on.  making the optimizer smart enough to deal with
all this is a lot of trouble, and is actually a bad thing.  the idea is that
users can write their own access methods, and you don't want users hacking
your optimizer.

in general, the "certain properties" you need to guarantee for optimizablity
are:
	+  operator is a partial ordering on the relation;
	+  you're willing to build knowledge of the ordering into
	   your optimizer.

also, it helps a lot if your index has some useful adjacency properties, but
you can survive without them.

since you have to build all these smarts into your access method, it's a
lot of trouble to put them into the optimizer, as well.

					mike olson
					postgres research group
					uc berkeley
					mao@postgres.Berkeley.EDU