Method for localizing execution or subqueries and determining collocation of execution of subqueries in a parallel database
First Claim
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
13 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (10)
-
-
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. - View Dependent Claims (12, 13)
-
Specification