Row Identifier List Processing Management

• US 20080082489A1
• Filed: 09/28/2006
• Published: 04/03/2008
• Est. Priority Date: 09/28/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zeng, Ying, CHEN, Ying-Lin, Lin, Fen-Ling, Purcell, Terence Patrick, Fuh, You-Chin
• Granted Patent: US 7,895,185 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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, the method comprising:

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, 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

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.

2. The method of claim 1, further comprising:

terminating 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 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 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.

6. The method of claim 1, further comprising:

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 the 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.

8. A computer program product comprising a computer readable medium, the computer readable medium including a computer readable program for managing row identifier (RID) list processing on an index, wherein the computer readable program when executed on a computer causes the computer to:

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

retrieve a plurality of row identifiers corresponding to the one or more key values from the index, 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

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.

9. The computer program product of claim 8, wherein the computer readable program when executed on the computer further causes the computer to:

terminate 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 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

switch execution of the query to a tablespace scan after termination of the RID list processing on the index 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 program product of claim 8, wherein the computer readable program when executed on the computer further causes the computer 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.

11. The computer program product of claim 8, wherein the computer readable program when executed on the computer further causes the computer 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.

12. The computer program product of claim 8, wherein the computer readable program when executed on the computer further causes the computer 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.

13. The computer 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:

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

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 from the index, 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

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.

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

terminate 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 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 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.