Indexes created in relational database management systems (RDBMS) can be exploited by a query optimizer to access the index and reduce the number of data rows and pages processed. When all columns required by a query are contained within a single index, then the query optimizer can choose to access only that index and avoid accessing the data pages, commonly referred to as “index-only access”. When the required columns are not within a single index, but exist within multiple indexes, then the query optimizer may consider accessing these multiple indexes. In its cost formula, the query optimizer determines and accumulates the cost of each index scan, the record identifier (RID) sort and merge, and resultant data page access, and the accumulated cost is compared with those of other access path alternatives.
When multi-index access is processed, the query optimizer obtains the qualifying record identifiers (RIDs) from each index. The RIDs function as addresses, pointing to the location of its associated row in the underlying table or data page. The list of qualifying RIDs from each index are sorted or hashed and either intersected (if the predicates are Boolean terms) or unioned (if predicates are non-Boolean terms). For efficient multi-index processing, the original index key columns are discarded at this step and only the RIDs survive for merging the lists of qualifying RIDs. However, to retrieve the index columns again after the RID merge, the RDBMS accesses the data pages using the RIDs on the merged list, since the original index key columns have been discarded. When necessary columns are spread over multiple indexes, requiring the data rows to be accessed to resolve the query result can add overhead to the query processing.
USPTO Backgrounds
USPTO Backgrounds