Method for localizing execution or subqueries and determining collocation of execution of subqueries in a parallel database

• US RE37,965 E1
• Filed: 06/02/2000
• Issued: 01/07/2003
• Est. Priority Date: 09/27/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Malkemus, Timothy R., Jhingran, Anant D., Kollar, Lubor J., Padmanabhan, Sriram K.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/585,927
• Time in Patent Office: 949 Days
• Field of Search: 707/2, 707/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries

Abstract

A method for localizing execution of subqueries and determining collocation of execution of subqueries in a shared-nothing database. The concept of compatible partitioning is used to localize database operations in order to eliminate excess processes and communication, and thereby improve response time and throughput for the database management system. The method reduces the number of process by reducing the number of nodes involved in processing a query and by combining multiple processes.

Claims

1. A method for determining locality for execution of subqueries for queries in a relational database management system, wherein said queries comprise an outer query and a subquery having a query-subquery operator and wherein partitioning columns for the query and subquery are provided, said method comprising the steps of:

(a) determining if said outer query and said subquery are compatibly partitioned;

(b) if said outer query and said subquery are compatibly partitioned then for each pair of partitioning columns in said outer query and said subquery determining an equivalence class for each of said columns in said pair;

(c) determining if the partitioning column for said subquery belongs to the same equivalence class as the partitioning column for said outer query;

(d) determining if said query-subquery operator comprises a selected operator; and

(e) if said steps (c) and (d) are true, determining locality for said subquery so that said subquery is locally executable with respect to said outer query by the relational database management.

2. The method as claimed in claim 1, wherein said step (d) comprises checking if said selected operator is the=operator and determining if a correlation value connecting said outer query to said subquery guarantees localized execution of the said subquery with respect to said outer query.

3. The method as claimed in claim 2, wherein said step (c) comprises determining if a column for said outer query will match on values of a column for said subquery and which come from a same node.

4. The method as claimed in claim 1, wherein said selected operator belongs to a group of operators comprising=ANY, ⋄

ALL, NOT IN or IN.

5. The method as claimed in claim 1, wherein said step (c) comprises determining if a partitioning key for said subquery is specified by a construct.

6. The method as claimed in claim 4, wherein said construct comprises a constant.

7. The method as claimed in claim 4, wherein said construct comprises a HOSTVAR.

8. A method for determining locality for execution of subqueries in queries in a relational database management system, wherein said queries comprise an outer query and a subquery having a query-subquery operator and wherein partitioning columns for the query and subquery are provided, said method comprising the steps of:

(a) determining if said outer query and said subquery are compatibly partitioned;

(b) if said outer query and said subquery are compatibly partitioned then for each pair of partitioning columns in said outer query and said subquery determining an equivalence class for each of said columns in said pair;

(c) determining if the partitioning column for said subquery belongs to the same equivalence class as the partitioning column for said outer query;

(d) determining if said query-subquery operator belongs to a group of operators comprising=ANY, ⋄

ALL, NOT IN or IN; and

(e) if said steps (c) and (d) are true, then concluding locality for execution of said subquery so that said subquery is executable locally with respect to said outer query by the relational database management system.

9. A relational database management system for use with a computer system wherein queries are entered for retrieving data from tables and wherein partitioning columns and partitioning keys are provided, said system comprising:

means for processing nested queries comprising an outer query and a subquery;

means for determining locality of execution of said subquery including,

(a) means for determining if said outer query and said subquery are compatibly partitioned;

(b) means for determining an equivalence class for each column forming a corresponding pair of partitioning columns for said outer query and said subquery;

(c) means for ascertaining if the partitioning column for said subquery belongs to the same equivalence class as the partitioning column for said outer query;

(d) means for determining if said query-subquery operator comprises a selected operator; and

(e) means responsive to said means for ascertaining and said means for determining said selected operator for determining locality of said subquery so that said subquery is locally executable with respect to said outer query by the relational database management system.

10. The system as claimed in claim 9, wherein said means for determining said query-subquery is responsive to a query-subquery operator belonging to a group of operators comprising=ANY, ⋄

ALL, NOT IN or IN.

11. A computer program product for use on a computer wherein queries are entered for retrieving data from tables, wherein said queries comprise an outer query and a subquery having a query-subquery operator and wherein partitioning columns for the query and subquery are provided, said computer program product comprising:

a recording medium;

means recorded on said medium for instructing said computer to perform the steps of,

(a) determining if said outer query and said subquery are compatibly partitioned;

(b) if said outer query and said subquery are compatibly partitioned then for each pair of partitioning columns in said outer query and said subquery determining an equivalence class for each of said columns in said pair;

(c) determining if the partitioning column for said subquery belongs to the same equivalence class as the partitioning column for said outer query;

(d) determining if said query-subquery operator comprises a selected operator; and

(e) if said steps (c) and (d) are true, then determining locality for said subquery so that said subquery is locally executable with respect to said outer query by the relational database management.

12. The computer program product as claimed in claim 11, wherein step (d) comprises determining if a correlation value connecting said outer query to said subquery guarantees localized execution of said subquery with respect to said outer query.

13. The computer program product as claimed in claim 11, wherein said selected operator belongs to a group of operators comprising=ANY, ⋄

ALL, NOT IN or IN.