Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Multiple Indexed Access Path in a Relational Database System

IP.com Disclosure Number: IPCOM000100270D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 5 page(s) / 209K

Publishing Venue

IBM

Related People

Cheng, JM: AUTHOR [+4]

Abstract

In a relational database management system (RDBMS), information is represented as tables containing multiple rows (records) and multiple columns (attributes). A RDBMS user specifies the information needed via a query which contains predicates to identify which rows are to be retrieved from a table.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 29% of the total text.

Multiple Indexed Access Path in a Relational Database System

       In a relational database management system (RDBMS),
information is represented as tables containing multiple rows
(records) and multiple columns (attributes).  A RDBMS user specifies
the information needed via a query which contains predicates to
identify which rows are to be retrieved from a table.

      For example, a SQL query to find those employees qualified for
retirement -- age older than 65 or having at least 30 years of
service, might be as follows:
SELECT EMP-NAME
FROM   EMPLOYEE
WHERE  AGE > 65 OR
        SERVICE > 30;

      One way to process this query is to scan every row of the
EMPLOYEE table and to check all the predicates on that row.  If there
exists an index on column AGE and another index on column SERVICE, it
is possible to use the first index to find those employees with AGE >
65, and then to use the second index to find those employees with
SERVICE > 30. The final result would be the union of these two
partial answer sets.

      This invention uses all the possible indexes on the table to
check as many of the query's predicates as possible, so that the
result of the query can be derived in the most efficient way.  When
the query contains many predicates, they are linked by the Boolean
(logical) operators AND and OR.  Those predicates which are linked by
ANDs are called "conjunctive" predicates.  Those predicates which are
linked by ORs are called "disjunctive" predicates.

      This invention uses index intersection for conjunctive
predicates, and index union for disjunctive predicates.  For queries
with both conjunctive predicates and disjunctive predicates, index
intersection and index union are both used.

      PART 1:   Index Intersection for Conjunctive Predicates: When a
query's predicate is on the key column(s) of an index, the locations
of the rows (also called Row Identifier or RID) which satisfy that
predicate are found through the index structure.  If the query has
other conjunctive (ANDed) predicates on the key column(s) of another
index, this invention intersects these two RID list and then accesses
the rows of this intersected RID list.  This is done as follows.
      1)   For each index, search among the simple conjunctive
predicates for the best predicates on index keys to derive the best
strategy of single index access.
      2)   For each conjunctive predicate which is made up of
disjuncts, use the method in PART 2 (below) to prepare a strategy of
index unions for disjunctive predicates.
      3)   Place the single-index strategies of step 1) and index
union strategies of step 2) in order by their selectivity, and choose
as a final strategy the strategy with the greatest selectivity and
least cost.
      4)   Choose a next strategy from among the remaining strategies
such that, when combined with the existing strategies, the next
strategy produces the most o...