Space and Time Efficient Evaluation of Indexable Conjunctive Predicates
Original Publication Date: 1987-Aug-01
Included in the Prior Art Database: 2005-Feb-01
This invention relates to the evaluation of conjunctive (AND) predicates when several conjunctive terms on a single table can exploit indices on the table to restrict the set of tuples to consider in data base query execution. The current method most commonly employed by relational data base systems is to use one index to evaluate the most restrictive conjunctive term and then apply the remaining conjuncts to the tuples selected by the chosen index. This requires accessing possibly many tuples which do not satisfy the remaining conjuncts. Proposed solutions to the indexed conjuncts problem are based upon manipulating lists of tuple identifiers (TIDs). Sets of TIDs, produced by the indices for each conjunct, are intersected, the matching TIDs are retained, and the corresponding tuples are eventually accessed.