Method and apparatus for dynamically associating different query execution strategies with selective portions of a database table

• US 20070016558A1
• Filed: 07/14/2005
• Published: 01/18/2007
• Est. Priority Date: 07/14/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kethireddy, Shantan, Tenner, Jeffrey, Bestgen, Robert
• Granted Patent: US 8,386,463 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

A query facility for database queries dynamically determines whether selective portions of a database table are likely to benefit from separate query execution strategies, and constructs an appropriate separate execution strategies accordingly. Preferably, the database contains at least one relatively large table comprising multiple partitions, each sharing the definitional structure of the table and containing a different respective discrete subset of the table records. The query facility compares metadata for different partitions to determine whether sufficiently large differences exist among the partitions, and in appropriate cases selects one or more partitions for separate execution strategies. Preferably, partitions are ranked for separate evaluation using a weighting formula which takes into account: (a) the number of indexes for the partition, (b) recency of change activity, and (c) the size of the partition.

Claims

1. A method for executing a database query in a computer system, comprising the computer-executed steps of:

automatically determining whether multiple separate query execution strategies should be used for evaluating said database query against different respective discrete subsets of a database table; and

responsive to determining that multiple separate query execution strategies should be used for evaluating said database query against different respective discrete subsets of a database table, automatically generating multiple separate query execution strategies for evaluating said database query against said different respective discrete subsets of said database table, and automatically generating a union of a respective results set of each said separate query execution strategy.

2. The method for executing a database query of claim 1,

wherein said database table comprises a plurality of discrete partitions, each partition having a common definitional structure and comprising a respective discrete subset of records of said database table;

and

wherein each said discrete subset of said database table comprises at least one said partition.

3. The method for executing a database query of claim 1, wherein said step of automatically determining whether multiple separate query execution strategies should be used comprises the computer-executed steps of:

automatically computing a respective weighted score for each of a plurality of said discrete subsets; and

comparing each said weighted score to a pre-determined threshold value.

4. The method for executing a database query of claim 3, wherein said step of automatically determining whether multiple separate query execution strategies should be used further comprises the computer-executed steps of:

if said weighted score for any said discrete subset exceeds said pre-determined threshold value, then automatically ranking said discrete subsets having respective weighted scores in excess of said pre-determined threshold value according to their respective weighted scores; and

selecting one or more said discrete subsets for generating respective separate query execution strategies according to rank established by said automatically ranking step.

5. The method for executing a database query of claim 1, wherein said step of automatically determining whether multiple separate query execution strategies should be used comprises the computer-executed steps of:

automatically constructing a common query execution strategy for evaluating said database query against all said discrete subsets of said database table;

automatically estimating an execution time for said common query execution strategy; and

automatically determining that multiple separate query execution strategies should be used only if the estimated execution time for said common query execution strategy exceeds a pre-determined threshold.

6. The method for executing a database query of claim 5, wherein said step of automatically determining whether multiple separate query execution strategies should be used further comprises computer-executed steps of:

if the estimated execution time for said common query execution strategy exceeds said pre-determined threshold, then automatically determining whether any of said discrete subsets of said database table are qualified as candidates for respective separate query execution strategies using at least one parameter of each respective said discrete subset.

7. The method for executing a database query of claim 6, wherein said step of automatically generating multiple separate query execution strategies for evaluating said database query against said different respective discrete subsets of said database table comprises computer-executed steps of:

if said step of determining whether any of said discrete subsets of said database table are qualified as candidates for respective separate query execution strategies determines that at least one said discrete subset of said database table is qualified as a candidate for a separate query execution strategy, then constructing a separate query execution strategy for at least one said discrete subset of said database table which is qualified as a candidate, and automatically constructing a revised common query execution strategy for evaluating said database query against all said discrete subsets of said database table for which no separate query execution strategy is constructed.

8. The method for executing a database query of claim 1, wherein said step of automatically determining whether multiple separate query execution strategies should be used comprises using at least one comparative criterion which compares a respective parameter of each said discrete subset with a composite of said respective parameters derived from all of said discrete subsets.

9. The method for executing a database query of claim 1, wherein said step of automatically determining whether multiple separate query execution strategies should be used comprises using at least one criterion from the set of criteria consisting of:

(a) at least one parameter indicating the existence of at least one local index for a portion of said database table;

(b) at least one parameter indicating volatility of a portion of said database table; and

(c) at least one parameter indicating a relative size of a portion of said database table.

10. The method for executing a database query of claim 1, further comprising the computer-executed steps of:

automatically executing said multiple separate query execution strategies and said union of results sets; and

saving said multiple separate query execution strategies and said union of results sets in a persistent query object for re-execution.

11. A computer program product for database query optimization comprising:

a plurality of computer-executable instructions recorded on signal-bearing media, wherein said instructions, when executed by at least one computer system, cause the at least one computer system to perform the steps of;

receiving a database query against information in a database table having multiple partitions;

determining whether multiple separate query execution strategies should be used for evaluating said database query against different respective partitions of said database table; and

responsive to determining that multiple separate query execution strategies should be used for evaluating said database query against different respective partitions of said database table, generating multiple separate query execution strategies for evaluating said database query against said different respective partitions of said database table, and generating a union of a respective results set of each said separate query execution strategy.

12. The computer program product of claim 11, wherein said step of determining whether multiple separate query execution strategies should be used comprises the steps of:

computing a respective weighted score for each of a plurality of said partitions; and

comparing each said weighted score to a pre-determined threshold value.

13. The computer program product of claim 12, wherein said step of determining whether multiple separate query execution strategies should be used further comprises the steps of:

if said weighted score for any said partition exceeds said pre-determined threshold value, then ranking said partitions having respective weighted scores in excess of said pre-determined threshold value according to their respective weighted scores; and

selecting one or more said partitions for generating respective separate query execution strategies according to rank established by said ranking step.

14. The computer program product of claim 11, wherein said step of determining whether multiple separate query execution strategies should be used comprises using at least one comparative criterion which compares a respective parameter of each said partition with a composite of said respective parameters derived from all of said partitions.

15. A computer system, comprising:

at least one processor;

a data storage for storing a database, said database containing a partitioned database table having a plurality of partitions;

a database management facility embodied as a plurality of instructions executable on said at least one processor, said database management facility including a query engine which executes logical queries against said database including logical queries against said partitioned database table and a query optimizer for generating execution strategies for executing logical queries against said database;

wherein said database management facility automatically determines, with respect to each of a plurality of said logical queries against said partitioned database table, whether multiple separate query execution strategies should be used for evaluating the respective said logical query against said partitioned database table; and

wherein, responsive to determining that multiple separate query execution strategies should be used for evaluating a respective logical query against said partitioned database table, said database management facility automatically generates multiple separate query execution strategies for evaluating the respective logical query, each of said multiple separate query execution strategies being used for evaluating the respective logical query against a different respective discrete non-empty set of partitions of said partitioned database table, and automatically generates a union of a respective results set of each said separate query execution strategy.

16. The computer system of claim 15, wherein said database management facility automatically determines whether multiple separate query execution strategies should be used by computing a respective weighted score for each of a plurality of said partitions, and comparing each said weighted score to a pre-determined threshold value.

17. The computer system of claim 16, wherein said database management facility automatically determines whether multiple separate query execution strategies should be used by ranking any said partitions having respective weighted scores in excess of said pre-determined threshold according to their respective weighted scores, and selecting one or more said partitions for generating respective separate query execution strategies according to the rank thereby established.

18. The computer system of claim 15, wherein said database management facility automatically determines whether multiple separate query execution strategies should be used by constructing a common query execution strategy for evaluating said database query against all said partitions of said partitioned database table, estimating an execution time for said common query execution strategy, and determining that multiple separate query execution strategies should be used only if the estimated execution time for said common query execution strategy exceeds a pre-determined threshold.

19. The computer system of claim 15, wherein said database management facility automatically determining whether multiple separate query execution strategies should be used by using at least one comparative criterion which compares a respective parameter of each said partition with a composite of said respective parameters derived from all of said partitions.

20. The computer system of claim 15, wherein said database management facility automatically determines whether multiple separate query execution strategies should be used by using at least one criterion from the set of criteria consisting of:

(a) at least one parameter indicating the existence of at least one local index for a partition of said database table;

(b) at least one parameter indicating volatility of a partition of said database table; and

(c) at least one parameter indicating a relative size of a partition of said database table.