Row-identifier list processing management

• US 7,895,185 B2
• Filed: 09/28/2006
• Issued: 02/22/2011
• Est. Priority Date: 09/28/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lin, Fen-Ling, Chen, Ying-Lin, Purcell, Terence Patrick, Zeng, Ying, Fuh, You-Chin
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Nguyen; Kim T
• Application Number:
  US11/536,400
• Publication Number:
  US 20080082489A1
• Time in Patent Office: 1,608 Days
• Field of Search: 707/711, 707/742
• US Class Current: 707/711
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution

Abstract

A method, computer program product, and system for managing row identifier (RID) list processing on an index are provided. The method, computer program product, and system provide for accessing one or more key values in the index based on one or more keys specified in a query, retrieving a plurality of row identifiers corresponding to the one or more key values from the index, and predicting an actual number of row identifiers to be retrieved from the index based on the one or more key values accessed and the plurality of row identifiers retrieved.

Claims

1. A method for managing row identifier (RID) list processing on an index using an electronic computing device, the method comprising:

causing the electronic computing device to select RID list processing at a binding time to process a query;

causing the electronic computing to receive the query;

causing the electronic computing device to access one or more key values in the index based on one or more keys specified in the query;

causing the electronic computing device to retrieve a plurality of row identifiers corresponding to the one or more key values the index at a runtime, wherein

the plurality of row identifiers retrieved index is less than an estimated total number of row identifiers to be retrieved from the index, and wherein

the estimated total number of row identifiers is determined at the binding time;

causing the electronic computing device make a prediction of an actual number of row identifiers to be retrieved the index based on the one or more key values accessed and the plurality of row identifiers retrieved, wherein the prediction is made at the runtime; and

causing the electronic computing device to determine whether to continue processing the query by RID list processing based on the prediction, wherein the prediction is multiply made during the runtime.

2. The method of claim 1, further comprising:

terminating the RID list processing on the index during the runtime in response to the actual number of row identifiers predicted to be retrieved from the index being above a threshold or in response to termination of RID list processing on another index when the index and the other index are part of a multi-index logical OR operation.

3. The method of claim 2, further comprising:

switching execution of the query to a tablespace scan after termination of the RID list processing on the index during the runtime when the index is not a part of a multi-index operation or when the index is a part of a multi-index logical OR operation.

4. The method of claim 1, further comprising:

estimating an amount of time required to retrieve the actual number of row identifiers predicted to be retrieved from the index; and

terminating the RID list processing on the index in response to the amount of time estimated for retrieval of row identifiers from the index being greater than an amount of time estimated for retrieval of row identifiers from another index by a predetermined amount when the index and the other index are part of a multi-index logical AND operation.

5. The method of claim 1, further comprising:

pausing the RID list processing on the index in response to the plurality of row identifiers retrieved from the index reaching a limit, wherein the limit is an amount of memory allocated for the RID list processing on the index.

7. The method of claim 1, wherein prediction of the actual number of row identifiers is performed again in response to retrieval of additional row identifiers from the index.

6. The method of claim further comprising:

utilizing a work file for the RID list processing on the index in response to the actual number of row identifiers predicted to be retrieved from the index being above a limit or in response to the plurality of row identifiers retrieved from the index reaching the limit, wherein the limit is an amount of memory allocated for the RID list processing on the index.

8. A computer device program product for managing row identifier (RID) list processing on an index using a computing device, the computing device program product comprising:

a computer readable medium;

first programmatic instructions for selecting RID list processing at a binding time to process a query;

second programmatic instructions for receiving the query;

third programmatic instructions for accessing one or more key values in the index based on one or more keys specified in the query;

fourth programmatic instructions for retrieving a plurality of row identifiers corresponding to the one or more key values from the index at a runtime, wherein

the plurality of row identifiers retrieved from the index is less than an estimated total number of row identifiers to be retrieved from the index and wherein

the estimated total number of row identifiers is determined at the binding time;

fifth programmatic instructions for predicting an actual number of row identifiers to be retrieved from the index based on the one or more key values accessed and the plurality of row identifiers retrieved wherein the predicting is made at a runtime; and

sixth programmatic instructions for determining whether to continue processing the query by RID list processing based on the prediction, wherein the prediction is multiply made during the runtime.

9. The computer device program product of claim 8, further comprising:

seventh programmatic instructions for terminating the RID list processing on the index during the runtime in response to the actual number of row identifiers predicted to be retrieved from the index being above a threshold or in response to termination of RID list processing on another index when the index and the other index are part of a multi-index logical OR operation; and

eighth programmatic instructions for switching execution of the query to a tablespace scan after termination of the RID list processing on the index during the runtime when the index is not a part of a multi-index operation or when the index is a part of a multi-index logical OR operation.

10. The computer device program product of claim 8, further comprising:

ninth programmatic instructions for estimating an amount of time required to retrieve the actual number of row identifiers predicted to be retrieved from the index; and

tenth programmatic instructions for terminating the RID list processing on the index in response to the amount of time estimated for retrieval of row identifiers from the index being greater than an amount of time estimated for retrieval of row identifiers from another index by a predetermined amount when the index and the other index are part of a multi-index logical AND operation.

11. The computer device program product of claim 8, further comprising:

eleventh programmatic instructions for pausing the RID list processing on the index in response to the plurality of row identifiers retrieved from the index reaching a limit, wherein the limit is an amount of memory allocated for the RID list processing on the index.

12. The computer device program product of claim 8, further comprising:

twelfth programmatic instructions for utilizing a workfile for the RID list processing on the index in response to the actual number of row identifiers predicted to be retrieved from the index being above a limit or in response to the plurality of row identifiers retrieved from the index reaching a limit, wherein the limit is an amount of memory allocated for the RID list processing on the index.

13. The computer device program product of claim 8, wherein prediction of the actual number of row identifiers is performed again in response to retrieval of additional row identifiers from the index.

14. A system for managing row identifier (RID) list processing on an index, the system comprising:

an electronic computing device for processing the index;

a database comprising an index, the index including a plurality of key values, wherein each key value is associated with a plurality of row identifiers;

an optimizer in communication with the database, the optimizer being operable to estimate a total number of row identifiers to be retrieved from the index for a query; and

an execution engine in communication with the database and the optimizer, the execution engine being operable to;

select RID list processing at a binding time to process a query;

receive the query;

access one or more key values in the index based on one or more keys specified in the query,

retrieve a plurality of row identifiers corresponding to the one or more key values the index specified by the query, wherein the plurality of row identifiers retrieved from the index is less than the estimated total number of row identifiers to be retrieved from the index and wherein the estimated total number of row identifiers is determined at the binding time,

predict an actual number of row identifiers to be retrieved from the index based on the one or more key values accessed and the plurality of row identifiers retrieved wherein the prediction is made at he runtime, and

determine whether to continue processing the query by RID list processing based on the prediction, wherein the prediction is multiply made during the runtime.

15. The system of claim 14, wherein the execution engine is further operable to:

terminate the RID list processing on the index during the runtime in response to the actual number of row identifiers predicted to be retrieved from the index being above a threshold or in response to termination of RID list processing on another index when the index and the other index are part of a multi-index logical OR operation.

16. The system of claim 15, wherein the execution engine is further operable to:

switch execution of the query to a tablespace scan after termination of the RID list processing on the index during the runtime when the index is not a part of a multi-index operation or when the index is a part of a multi-index logical OR operation.

17. The system of claim 14, wherein the execution engine is further operable to:

estimate an amount of time required to retrieve the actual number of row identifiers predicted to be retrieved from the index, and

terminate the RID list processing on the index in response to the amount of time estimated for retrieval of row identifiers from the index being greater than an amount of time estimated for retrieval of row identifiers from another index by a predetermined amount when the index and the other index are part of a multi-index logical AND operation.

18. The system of claim 14, wherein the execution engine is further operable to:

pause the RID list processing on the index in response to the plurality of row identifiers retrieved from the index reaching a limit, wherein the limit is an amount of memory allocated for the RID list processing on the index,

19. The system of claim 14, wherein the execution engine is further operable to:

utilize a workfile for the RID list processing on the index in response to the actual number of row identifiers predicted to be retrieved from the index being above a limit or in response to the plurality of row identifiers retrieved from the index reaching a limit, wherein the limit is an amount of memory allocated for the RID list processing on the index.

20. The system of claim 14, wherein the execution engine is further operable to perform prediction of the actual number of row identifiers again in response to retrieval of additional row identifiers from the index by the execution engine.