Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!midway!clout!chinet!dhartung
From: dhartung@chinet.chi.il.us (Dan Hartung)
Newsgroups: comp.databases
Subject: Re: Rushmore Query Optimization in FoxPro 2.0
Message-ID: <1991Jun28.063614.12966@chinet.chi.il.us>
Date: 28 Jun 91 06:36:14 GMT
References: <91178.110048RMC100@psuvm.psu.edu> <1991Jun27.225122.26594@agate.berkeley.edu>
Organization: Chinet - Chicago Public Access UNIX
Lines: 60

mao@eden.Berkeley.EDU (Mike Olson) writes:
>
>i asked a similar question about a month ago.  a couple of people responded
>to me.  the concensus was that rushmore uses at least two techniques to
>speed up query processing.  one strategy is to index only certain ranges of
>values for a given attribute in a relation.  for certain query patterns,
>indexing ten percent of your table could speed up ninety percent of your
>queries.  the other strategy was to optimize data dictionary operations
>inside the planner and optimizer in the same way as normal queries.  many
>systems hard-code table accesses internal to the dbms engine.  if you optimize
>the table accesses done by a 'define index' command, you may be able to make
>it go faster.
>
>prior art exists for both of these techniques, so if this is correct, then
>there's nothing especially interesting about rushmore.  in fact, i would
>wager that the patent application is more for the benefit of the marketing
>department than to protect the developments of the engineering department.

Rushmore is new to the xBase world.  The basic ideas behind it are not new,
but this particular implementation is.  I don't know anything more specific.

The simplest way of explaining it from an xBase point of view is this:

If you do something like:

LOCATE ALL FOR "Smith"$name .AND. salary > 50000 .OR. INLIST (zip,z1,z2,zn)

and you have indexes on none of the above fields, no optimization is 
possible.  If you have an index on name, that part of the query will be
optimized; if on salary, 2/3 optimized; and if all three are indexed,
then full optimization is possible.

This is an advance over previous implementations of xBase.

The RushMore technology (actually algorithm) combined with Fox's new CDX
compound/compact indexes means dramatic increases in speed.

1.  Your indexes are compact, so more can be buffered in memory, speeding
    disk access;

2.  Your indexes can be compounded, so only one need be accessed, saving
    a) file handles, and b) memory and sppeed a la 1.  This allows you
    to *efficiently* keep indexes simultaneously open on all key fields
    without a performance penalty.
 
    This is claimed to be significantly faster than dbase's MDX implementation
    of roughly the same idea.

3.  By having many indexes open, you can achieve full RushMore optimization
    most of the time (almost always if you plan right).

All of the above were basically necessary in order to achieve a fast SQL
implementation.  Fox did not want to introduce it, then weather the same
disappointment with speed experienced by Ashton-Tate.

-- 
Daniel A. Hartung           |  Brendan Gill spent a sleepless night at the
dhartung@chinet.chi.il.us   |  Bush mansion in Kennebunkport.  The only
Birch Grove Software        |  book he could find to read was _The Fart Book_.
                            |           --- Alexander Cockburn