Method and system for look ahead query evaluation planning based on interesting partition properties

• US 6,345,267 B1
• Filed: 03/02/2000
• Issued: 02/05/2002
• Est. Priority Date: 06/30/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Shekita, Eugene Jon, Simmen, David E., Lohman, Guy Maring, Urata, Monica Sachiye
• Primary Examiner(s): Choules, Jack
• Assistant Examiner(s): Channavajjala, Srirama
• Application Number:
  US09/517,355
• Time in Patent Office: 705 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A relational data base management system includes a query processor that uses a query operator partition property to perform QEP pruning and to ensure that data input to a query operator is partitioned appropriately for the operation. The partition property indicates the group of network nodes across which a table is distributed. The query processor also makes use of partition classes that are designated “interesting classes” to perform preoptimization planning and query pruning, and to perform look-ahead partitioning based on partition classes that are identified as being of interest to future operations, thereby more efficiently evaluating complex query statements in an MPP, shared-nothing environment.

Claims

1. A method of processing a query in a relational database management system that operates in a computer network to retrieve data from computer storage, the method comprising:

receiving a query for retrieving data stored in partitioned data tables, the query being associated with an operator and one or more subsequent operators for execution of the query;

generating a plurality of interesting partition requirements for the one or more subsequent operators of the query;

generating a set of possible partition requirements for the operator of the query;

for each possible partition requirement generated for the operator;

determining whether the possible partition requirement is the same as one of the interesting partition requirements generated previously for the one or more subsequent operators; and

creating an alternative evaluation plan having a partition property that satisfies the possible partition requirement if it is determined that the possible partition requirement is the same as one of the interesting partition requirements generated previously for the one or more subsequent operators.

2. The method according to claim 1 wherein, for each possible partition requirement, creating an alternative evaluation plan further comprises creating an alternative evaluation plan if and only if the possible partition requirement is the same as one of the interesting partition requirements generated for the one or more subsequent operators.

3. The method according to claim 1, further comprising:

if no alternative evaluation plans for the query exist after performing the determining for each possible partition requirement;

selecting one of the possible partition requirements; and

creating an alternative evaluation plan that satisfies the selected partition requirement.

4. The method according to claim 1, further comprising:

if no alternative evaluation plans for the query exist after performing the determining for each possible partition requirement;

randomly selecting one of the possible partition requirements; and

creating an alternative evaluation plan that satisfies the randomly selected partition requirement.

5. The method according to claim 1, wherein generating the plurality of interesting partition requirements comprises generating the plurality of interesting partition requirements during a preoptimization phase.

6. The method according to claim 1, wherein the query comprises a Structured Query Language (SQL) query.

7. A relational database management system comprising:

a central processing unit of a computer network; and

a query processor that operates in the computer network to evaluate queries and retrieve data from computer storage, wherein the query processor is operative to perform query evaluation by receiving a query for retrieving data stored in partitioned data tables, where the query is associated with an operator and one or more subsequent operators for execution of the query;

generating a plurality of interesting partition requirements for at least the one or more subsequent operators of the query;

generating a set of possible partition requirements for the operator of the query;

for each possible partition requirement generated for the operator;

determining whether the possible partition requirement is the same as one of the interesting partition requirements generated previously for the one or more subsequent operators; and

creating an alternative evaluation plan having a partition property that satisfies the possible partition requirement if it is determined that the possible partition requirement is the same as one of the interesting partition requirements generated previously for the one or more subsequent operators.

8. The relational database management system according to claim 7, wherein the query processor is further operative to perform query evaluation by creating an alternative evaluation plan if and only if the possible partition requirement is the same as one of the interesting partition requirements for the one or more subsequent operators.

9. The relational database management system according to claim 7, wherein the query processor is further operative to perform query evaluation by, if no alternative evaluation plans for the query exist after performing the determining for each possible partition requirement:

selecting one of the possible partition requirements; and

creating an alternative evaluation plan that satisfies the selected partition requirement.

10. The relational database management system according to claim 7, the query processor being further operative to perform query evaluation by generating the plurality of interesting partition requirements during a preoptimization phase.

11. The relational database management system according to claim 7, wherein the query processor is further operative to perform query evaluation in connection with Structured Query Language (SQL) queries.