RMC100@psuvm.psu.edu (Randy Carraghan) (06/27/91)
I'm not a FoxPro user, but I was interested in finding out more about the Rushmore Query Optimization they plan to use in release 2.0 of their product. The advertisement I read said that a patent had been applied for - does this mean that other databases would have to license the technology from FoxBase? The claim was that many queries could be performed one to two orders of magnitude faster with the Rushmore algorithms. Are these algorithms available in publication? I'd like to see some of the techniques used to fulfill the SQL queries. Thanks in advance for any information... Randy
onder@ISI.EDU (Bruce Onder) (06/28/91)
In article <91178.110048RMC100@psuvm.psu.edu> RMC100@psuvm.psu.edu (Randy Carraghan) writes: >I'm not a FoxPro user, but I was interested in finding out more about the >Rushmore Query Optimization they plan to use in release 2.0 of their product. >The advertisement I read said that a patent had been applied for - does this >mean that other databases would have to license the technology from FoxBase? Depends on if they use Rushmore. You can do things the old ways in FoxPro 2.0, with standard .IDX index files. No one will be forced (except by the customers) to develop a dbms with Rushmore. >The claim was that many queries could be performed one to two orders of >magnitude faster with the Rushmore algorithms. Are these algorithms >available in publication? I'd like to see some of the techniques used to >fulfill the SQL queries. Good luck. :) >Thanks in advance for any information... > >Randy Bruce -- Bruce W. Onder onder@isi.edu Joel Wallach transmits cosmic energies that dissolve blockages within you, boosting your inner power and radiance. Ten years experience.
mao@eden.Berkeley.EDU (Mike Olson) (06/28/91)
In <91178.110048RMC100@psuvm.psu.edu>, RMC100@psuvm.psu.edu (Randy Carraghan) writes > I'm not a FoxPro user, but I was interested in finding out more about the > Rushmore Query Optimization they plan to use in release 2.0 of their product. > The advertisement I read said that a patent had been applied for [ ... ] > Are these algorithms > available in publication? I'd like to see some of the techniques used to > fulfill the SQL queries. 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. i should emphasize that i have no connection with foxpro, and that none of my correspondents was willing to state that his or her information was authoritative. this may or may not be an accurate description of some part of rushmore. given that a patent application is outstanding, however, this is probably the most authoritative answer you'll get for a while. if anyone with solid information can share it, publically or privately, i would be happy to see it. mike olson postgres research group uc berkeley mao@postgres.berkeley.edu
dhartung@chinet.chi.il.us (Dan Hartung) (06/28/91)
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
jrg@doc.ic.ac.uk (James Robert Grinter) (06/28/91)
In article <91178.110048RMC100@psuvm.psu.edu> RMC100@psuvm.psu.edu (Randy Carraghan) writes: >I'm not a FoxPro user, but I was interested in finding out more about the >Rushmore Query Optimization they plan to use in release 2.0 of their product. >The advertisement I read said that a patent had been applied for - does this Surely, when a patent is applied for, they have to submit details so that ANYONE can see how it is done. Just wander along to the patent office and have a look. At least that is the way it works in the UK. >mean that other databases would have to license the technology from FoxBase? >The claim was that many queries could be performed one to two orders of >magnitude faster with the Rushmore algorithms. Are these algorithms >available in publication? I'd like to see some of the techniques used to >fulfill the SQL queries. > >Thanks in advance for any information... > >Randy James disclaimer: I'm not a patent lawyer, and I'm not entirely sure of the US patent processes (is anybody? :-)) -- James Grinter, Dept of Computing, Imperial College JANET: jrg@uk.ac.ic.doc 180, Queen's Gate, LONDON SW7 2BZ DARPA: jrg@doc.ic.ac.uk UUCP: jrg@icdoc.UUCP, ..!ukc!icdoc!jrg "If it works, leave it alone!"