Rushmore Technology by Sheila Kearney

Rushmore technology is a data access technique using indexes to optimize data access. Rushmore technology can be used with IDX (FoxPro version 1.x and compact indexes) and CDX (compound) Visual FoxPro indexes. Both IDX and CDX indexes use a compression technique that shrinks the indexes to one-sixth of their normal size if in uncompressed format. Since a compressed index requires less disk access, more of the index can be buffered in memory. If the user has extremely large tables and only the minimum amount of RAM, then Rushmore may not be able to operate.

Rushmore queries also work against native Jet data (MDB files) and dBASE data (DBF files). The Jet engine will be discussed later in this paper. Rushmore cannot be used against ODBC data sources because these queries must be sent to the ODBC data source for processing and are not processed locally by the Jet engine.

First, Rushmore technology as utilized by FoxPro will be discussed. The table below lists several Visual FoxPro commands that are potentially optimizable using Rushmore technology.

The nature of FoxPro's SQL - SELECT command it to automatically open any tables called in the FROM clause of the command. If any of these tables have an associated structural index, that index will also automatically be opened. If, however, there are any nonstructural index files associated with the tables in the projection list, then these indexes will have to be explicitly activated before Rushmore technology can use them. Since Rushmore requires indexes to operate, FoxPro will create an index if one does not exist. This will, of course, take additional time and will reduce the benefits of speed gained by Rushmore technology. To ensure the best performance possible, tables and their associated nonstructural indexes should be opened prior to the SELECT command being issued.

Rushmore cannot use an index created with a NOT condition. For example, INDEX ON DELETED() TAG DEL will be optimized by Rushmore while INDEX ON NOT DELETED() TAG NOTDEL will not be optimized by Rushmore. Another indexing issue Rushmore cannot handle is the use of FOR clauses in the index command. An example of this would be INDEX ON ORDNUM FOR DISCOUNT > 10 TAG ORDDISC. Rushmore also cannot use open indexes with filtered and UNIQUE indexes. In addition, the functions ISBLANK() and EMPTY() are not optimizable by Rushmore.

For optimal performance, the user should not set the order of the table since creating index or tags automatically sets the order. For a large data set that must be in a specific order, the SET ORDER TO command should be issued to turn off index control and then the SORT command can be used to order the data.

If using a scope clause in addition to an optimizable FOR clause expression, it should be set to ALL or REST for Rushmore technology to be utilized. The NEXT or RECORD scope clauses disables Rushmore. Since the default scope is ALL, Rushmore works when the scope clause is omitted.

To disable Rushmore for a single command, include the parameter NOOPTIMIZE in the command. To disable Rushmore globally, use the SET OPTIMIZE OFF command (and conversely SET OPTIMIZE ON to enable Rushmore optimization).

Visual FoxPro 5.0 has added a new SYS() function that allows the user to see the Rushmore optimization level of query. The level specified is either "full", "partial", or "none". This function will show what indexes are being used. When the level of Rushmore optimization is not full, the function will also suggest additional indexing in order to make the query fully Rushmore optimizable.

The Jet 2.0 Database Engine (used in MS Access) also includes support for the Rushmore query optimizer. Rushmore query optimization allows queries to run many times faster than previously possible. Rushmore query optimization involves the efficient use of indexes to quickly find a set of records. The design of the Jet Engine does not provide the user with a way to view the optimization schemes nor to specify how to optimize a query. However, the Database Documenter tool can be used to find out what indexes are present and the uniqueness of the indexes. In Microsoft Access 7.0 and Microsoft Access 97, the user is provided with a tool called the Performance Analyzer. This will analyze queries in the database and will suggest adding indexes only when those indexes will actually be used by the Jet engine to optimize the query. Rushmore query optimization is used on queries involving multicolumn, indexed restrictions of the following types:

•     Index Intersection - the two indexes are intersected. For example: "Where Company = 'Ford' and CarType = 'Sedan'. Rushmore would use the Company index and the CarType index to find the matching records. The resulting records from each of the indexes are then intersected to find the records matching both criteria.
• 
  
  
•     Index Union - the two indexes are unioned. For example: "Where CarType = 'Wagon' or Year = '1994'. Rushmore would use the CarType index and the Year index to find the matching records. The resulting records would then be unioned together to find the records matching either criteria.
• 
  
  
•     Index Minus - For example: column1 = AND column2 <> . Rushmore would use the index on column1 and column2 to find the matching records. The resulting records from the column2 index would then be subtracted from the column1 records to find the records that match the column1 criteria and that do not match the column2 criteria.
• 
  
  
•     Index Counts - queries that return record counts only. For example: "Select Count(*) from Autos Where Company = 'Dodge' and CarType = 'Truck'".

The Microsoft Jet database engine is comprised of several components:

•     Parser/binder - responsible for parsing the SQL statement that defines a query and for binding the names referenced in the query to columns in the underlying tables.
• 
  
  
•     Folder - responsible for moving expressions "up" in the query tree.
• 
  
  
•     Splitter - responsible for splitting query objects into discrete components.
• 
  
  
•     Flattener - responsible for taking the output of the splitter and combining joins whenever possible.
• 
  
  
•     Optimizer - responsible for using statistics to determine the most efficient way to execute a query. This optimizer assigns a cost to each task and then chooses the least expensive list of tasks to perform that will yield the desired result.
• 
  
  
•     Remote Post Processor - responsible for determining what can be sent to an ODBC back end processor.
• 
  
  
•     Join Processor - responsible for executing the compiled query.

The goal of using Rushmore Technology is to optimize queries. The join processor and the optimizer must work together to handle queries involving multiple tables efficiently. The Jet query engine has five available join strategies to choose from when executing multiple table queries. These join strategies are:

•     Nested Iteration Join
• 
  
•     Index Join
• 
  
•     Lookup Join
• 
  
•     Merge Join
• 
  
•     Index-Merge Join

The type of join chosen is based on base table statistics as well as statistics on non-base table inputs. Statistics for base tables include:

(1) the number of records in the base table,
(2) the number of data pages in the base table (the more data pages that need to be accessed, the more costly the query),
(3) the location of the table (ISAM format or ODBC database), and
(4) the indexes on the table.

When the optimizer is attempting to choose a join method from those listed above, it first selects a base table access strategy (this will be explained in more detail later in the paper). The optimizer will then store the estimated number of records returned and a cost associated with the expense that will be incurred to read the table. The optimizer will then generate all combinations or pairs of tables and assign a cost to each strategy. The optimizer continues to add tables to the joins and continues calculating statistics until the most cost effective strategy is found.

Three methods are available to choose a base table access plan. They are:

•      Table Scan - generally the slowest access method.
•      Index Range - a table is opened with a specific single-table index.
•      Rushmore Restriction - A Rushmore restriction is used when there are restrictions on multiple indexed columns. By using multiple indexes to perform the query, the number of base table pages needing to be accessed can be minimized.
• 
  
  

  Neal Black recommends indexing fields as much as possible in his paper, "Database Optimization Techniques: Designing Applications for Maximum Performance". His motto is "When in doubt, index!". Mr. Black recommends placing an index on all columns that are used in a join or in a restriction, especially for databases whose update frequency is low. Following this recommendation provides the ability to utilize the Rushmore query optimization in Access, since the Jet engine is able to take advantage of multiple indexes on a single table. Other tips for optimization using Rushmore include: (1) index the fields used in sorts and criteria, (2) index the fields used in joins in both tables, (3) use multiple-field indexes on fields where there are multiple-column joins between the tables, (4) if a table has a single-field primary key, do not add a separate index to the primary key field, (5) if a table has a multiple-field primary key, add a separate index on each field, and (6) use outer joins only when necessary since they limit the options for the query optimizer.

  Another paper by Mr. Black, "Rushmore Query Optimization in the Jet Database Engine Version 2.0", provides optimization measurements based on Set Query benchmarks. These benchmarks are an industry standard used to determine query speed against relational set operations on large sets of data. The following three benchmark results show the advantages of using Rushmore technology to speed up the processing of queries. These queries were performed using Jet 1.x engine and the Jet 2.0 engine. The Jet 2.0 engine utilized Rushmore technology, while the Jet 1.x engine only used one index to solve a query.

  Q2a - K1K:
  SELECT Count(*)
  FROM bench
  WHERE (bench.K2 = 2) AND (bench.K1K = 3)
  This query counted 46 records that matched the specified criteria out of the 100,000 records in the table. Using the Jet 1.x engine, the query took 1.59 seconds to execute. Using the Jet 2.0 engine, this query took just .55 seconds to execute. This produced approximately a 300% increase in performance.
  
  Q2a - K100:
  SELECT Count(*)
  FROM bench
  WHERE (bench.K2 = 2) AND (bench.K100 = 3)
  This query performed a count of 490 records that matched the specified criteria out of a total of 100,000 records in the table. Using the Jet 1.x engine, the query took 11.53 seconds to execute. Using the Jet 2.0 engine, this query took .77 seconds to execute. Rushmore technology produced roughly a 1500% increase in performance for this query.
  
  Q24 - 2-4:
  SELECT bench.KSEQ, bench.K500K
  FROM bench
  WHERE (bench.K100 > 80) AND (bench.K101K Between 2000 And 3000) AND (bench.K5=3)
  This query selected 379 records matching the specified criteria out of the total 100,000 records in the table. Using the Jet 1.x engine, the query took 223.93 seconds to execute. Using the Jet 2.0 engine, the query executed in 1.7 seconds. This resulted in roughly a 13100% increase in performance.
  
  As can be seen by these benchmarks, intelligent indexing of large tables can result in big performance wins when Rushmore query optimization is used.

  References
  Black, Neil W., Database Optimization Techniques, Microsoft Tech Ed 95, AC304, Microsoft Corporation, 1995.
  
  Black, Neil W., Database Optimization Techniques: Designing Applications for Maximum Performance, Microsoft Tech Ed 94, AC302, Microsoft Corporation, 1994.
  
  Black, Neil W., Rushmore Query Optimization in the Jet Database Engine Version 2.0, Microsoft Corporation, 1993.
  
  Litwin, Paul, Microsoft Jet Database Engine 2.0 A User's Overview, Microsoft Corporation, Pinnacle Publishing Inc., Kent, WA, 1994.
  
  ACC: How to Optimize Queries in MS Access v.2.0, 95, and 97, Microsoft Knowledge Base, http://support.microsoft.com/support/kb/articles/q112/1/12.as, Article ID Q112112, February 4, 1998.
  
  ACC95: Table and Query Questions and Answers (7.0), Microsoft Support, http://support.microsoft.com/support/kb/articles/q137/3/44.as, Article ID Q137344, June 25, 1998.
  
  How to Optimize SQL Using the FORCE Clause and SYS(3054), Microsoft Support, http://support.microsoft.com/support/kb/articles/q155/7/88.as, Article ID Q155788, January 20, 1997.
  
  HOWTO: Use SYS(3054) to Optimize a Query, Microsoft Support, http://support.microsoft.com/support/kb/articles/q145/5/51.as, Article ID Q156551, October 21, 1998.
  
  Rushmore Requires Open Indexes in Order to Operate, Microsoft Support, http://support.microsoft.com/support/kb/articles/q114/7/81.as, Article ID Q114781, April 30, 1996.
  
  Optimizing Applications (Chapter 15), Visual FoxPro Developer's Guide, Microsoft Visual FoxPro Version 5.0, Microsoft Corporation, 1996.