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

• US 8,386,463 B2
• Filed: 07/14/2005
• Issued: 02/26/2013
• Est. Priority Date: 07/14/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bestgen, Robert Joseph, Kethireddy, Shantan, Tenner, Jeffrey Wayne
• Primary Examiner(s): Leroux, Etienne
• Assistant Examiner(s): Rahman, Sabana
• Application Number:
  US11/181,713
• Publication Number:
  US 20070016558A1
• Time in Patent Office: 2,784 Days
• Field of Search: 707/3, 707/713, 707/719
• US Class Current: 707/713
• 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 selecting one or more candidate partitions of a partitioned database table for determining separate query execution strategies to be used for evaluating said database query, said partitioned database table having multiple previously defined partitions, each partition having a common definitional structure and comprising a respective disjoint subset of records of said partitioned database table, said candidate partitions comprising at least one and fewer than all previously defined partitions of said partitioned database table, said automatically selecting one or more candidate partitions step being performed without determining whether execution of said database query can benefit from using a separate query execution strategy for evaluating said database query against any said previously defined partition;

wherein said step of automatically selecting one or more candidate partitions of a partitioned database table 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 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; and

responsive to automatically selecting one or more candidate partitions of a partitioned database table, automatically generating a respective separate query execution strategy for evaluating said database query against each candidate partition of said candidate partitions of said partitioned database table, and automatically generating a union of a respective results set of each said separate query execution strategy, to execute more efficiently than a common query execution strategy for evaluating said database query against all partitions of said partitioned database table.

2. The method for executing a database query of claim 1, wherein said step of automatically selecting one or more candidate partitions of a partitioned database table comprises the computer-executed steps of:

automatically computing a respective weighted score for each of a plurality of said partitions, said weighted score being based on parameters of said database without reference to said database query; and

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

3. The method for executing a database query of claim 2, wherein said step of automatically selecting one or more candidate partitions of a partitioned database table further comprises the computer-executed steps of:

if said weighted score for any said partition 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 partitions as said candidate partitions according to rank established by said automatically ranking step.

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

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

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

automatically selecting candidate partitions only if the estimated execution time for said common query execution strategy exceeds a pre-determined threshold.

5. The method for executing a database query of claim 4, wherein said step of automatically generating a respective separate query execution strategy for evaluating said database query against each candidate partition of said candidate partitions of said partitioned database table further comprises computer-executed steps of:

automatically constructing a revised common query execution strategy for evaluating said database query against all said partitions of said partitioned database table for which no separate query execution strategy is constructed.

6. The method for executing a database query of claim 1, wherein said step of automatically selecting one or more candidate partitions of a partitioned database table 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.

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

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

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

receiving a database query against information in a partitioned database table having multiple previously defined partitions, each said partition having a common definitional structure and comprising a respective disjoint subset of records of said partitioned database table;

selecting one or more candidate partitions of said partitioned database table for determining separate query execution strategies to be used for evaluating said database query, said one or more candidate partitions comprising at least one and fewer than all said previously defined partitions of said partitioned database table, said selecting one or more candidate partitions of said partitioned database table being performed without determining a hypothetical query execution strategy for separately evaluating said database query against any said previously defined partition;

wherein said selecting one or more candidate partitions of said partitioned database table 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 partitioned database table;

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

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

responsive to selecting one or more candidate partitions of said partitioned database table, generating a respective separate query execution strategy for evaluating said database query against each candidate partition of said candidate partitions of said partitioned database table, and automatically generating a union of a respective results set of each said separate query execution strategy, to execute more efficiently than a common query execution strategy for evaluating said database query against all partitions of said partitioned database table.

9. The computer program product of claim 8, wherein said selecting one or more candidate partitions of said partitioned database table comprises:

computing a respective weighted score for each of a plurality of said partitions of said partitioned database table, said weighted score being based on parameters of said database without reference to said database query; and

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

10. The computer program product of claim 9, wherein said selecting one or more candidate partitions of said partitioned database table further comprises:

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.

11. The computer program product of claim 8, wherein said selecting one or more candidate partitions of said partitioned database table 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.

12. The computer program product of claim 8, wherein said instructions, when executed by said at least one computer system, cause the at least one computer system to perform:

responsive to receiving said database query, 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

performing said selecting one or more candidate partitions of said partitioned database table only if the estimated execution time for said common query execution strategy exceeds a pre-determined threshold.

13. The computer program product of claim 12, wherein said generating a respective separate query execution strategy for evaluating said database query against each candidate partition of said candidate partitions of said partitioned database table further comprises:

constructing a revised common query execution strategy for evaluating said database query against all said partitions of said partitioned database table for which no separate query execution strategy is constructed.

14. 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, each said partition having a common definitional structure and comprising a respective disjoint subset of records of said partitioned database table;

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 selects, with respect to each of a plurality of said logical queries against said partitioned database table, a respective one or more candidate partitions of said partitioned database table for determining separate query execution strategies to be used for evaluating the respective logical query, each said respective one or more candidate partitions comprising at least one and fewer than all partitions of said database table, each said respective one or more candidate partitions being selected without determining a hypothetical query execution strategy for separately evaluating the respective database query against any said partition;

wherein said database management facility automatically selects a respective one or more candidate partitions 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 partitioned database table;

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

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

wherein, responsive to selecting a respective one or more candidate partitions of 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 disjoint 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, to execute more efficiently than a common query execution strategy for evaluating said database query against all partitions of said partitioned database table.

15. The computer system of claim 14, wherein said database management facility automatically selects a respective one or more candidate partitions by computing a respective weighted score for each of a plurality of said partitions, each weighted scored being based on parameters of said database without reference to the respective logical query, and comparing each said weighted score to a pre-determined threshold value.

16. The computer system of claim 14, wherein said database management facility automatically selects a respective one or more candidate partitions 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.