Re: Multiple Indexes

cyberkid_at_my-dejanews.com wrote:
[SNIP]
> performance is my key issue. Are there any good resources out there to find
> out exactly what methodology is used by Oracle, or other RDBMS's? Also, I've
> seen a product by DISC (Dynamic Information Systems Corp.) called Omnidex
> which uses "Inverted List Indexes" and "Dynamic Aggregation Indexes". Are
> these really better than typical B tree indexes? Surely there must be a
> trade off if they do perform better.

I'm just going to answer this last question. Inverted list indexes are indexes where there is one entry for each key value to which is attached a list of data rows that contain that key. These are used for non-unique keys. Actually inversion indexes do not preclude using a Btree or B+tree or other optimized search/index method for organizing the keys it is just that you will only find one leaf containing any key value rather than one leaf for each row that matches. Informix, for example, does just this for its non-unique indexes. The basic index structure is a Btree but instead of the leaf pointing to a data row as it does for a unique index the leaf points to a linked list of index data pages containing the row pointers for all rows containing that key value. Because of this structure many older databases would perform ORing and ANDing operations across multiple non-unique keys using inversion lists by beating the inversion lists from each index against each other to create a net list of successful matches before going after data rows. Modern RDBMSs like Oracle and Informix only use a single index and filter the resulting data rows for keys and other criteria not contained (or not usable) in the selected index.

Dynamic aggregation indexes sounds like a proprietary name for a technique that RDBMS vendors have played with in various forms over the years to improve performance when appropriate indexes are not available, ie create an index or hash table, perhaps of a partial result set, on the fly. This is sometimes successful and sometimes slower that the table scan it replaces, it depends on a lot of factors. In general if the optimizer reports that it is doing this kind of thing and the query is a common one it is best to add the missing index permanently. Sometimes this cannot be done as the engine has created a "joined" index containing data from multiple tables which, except for Informix IDS with Decision Support Option, most RDBMSs do not allow.

Art S. Kagel Received on Thu Sep 03 1998 - 09:26:10 CDT