Subject: Retrieve question

From: [email-masked] (Suresh Srinivasan)
Date: Fri, 25 Mar 94 10:05:56 EST

Folks, here's a naive question on how the
query optimizer works.

It seems that if the query is qualified by
even a simple Boolean expression, the search
defaults to a sequential scan rather than
use the index.  For example,

Given:

  create Word (wd = text) \g
  define index WdInd on Word using btree (wd text_ops) \g

the query:

  retrieve (w.all) from w in Word, where w.wd = "foo"
    or w.wd = "bar" \g

does not use the index at all.  It is actually
much faster to do:

  retrieve into tmp1 (w.all) from w in Word, where w.wd = "foo" \g
  retrieve into tmp2 (w.all) from w in Word, where w.wd = "bar" \g
  append tmp1 (tmp2.all) \g

Can somebody confirm this?  Thanks,

--Suresh

---

From: [email-masked] (Paul M. Aoki)
Date: Fri, 25 Mar 94 11:04:12 -0800

[email-masked] (Suresh Srinivasan) writes:
> use the index.

you can have fairly complex AND/NOT expressions and use indices.
the key in your query is the OR.  OR is a classic hard spot for 
optimizers because you really have to look closely at how clauses 
partition the data and believe in your stats.

a lot of classic papers, such as the system r paper, don't 
consider OR because their estimates/stats are assumed to be 
so poor that it doesn't make sense to do so.  ours fall into
the same category -- we have *no* key value stats.  if you keep 
better stats (like histograms) on key values and are willing 
to code ten million corner cases (as do ask/ingres and rdb)
you can do better.

you may think, well, a=b OR a=c will *always* be better done
by an index scan.  what if the column has very few distinct
values?  then, even with equality clauses, using the index
may not make a lot of sense.  so even "no brainer" cases have
problems.

notice that this problem is much, much harder in an extensible 
system where many types have no ordering, selectivity functions
may be really bizarre (at least, intelligent ones) for new access
methods like r-trees, etc.  hard-coded assumptions about b-trees 
and key ordering make no sense.  what stats should you keep for
polygons and r-trees?
--
  Paul M. Aoki  |  CS Div., Dept. of EECS, UCB  |  [email-masked]
                |  Berkeley, CA 94720           |  ...!uunet!ucbvax!aoki