Shared nothing parallel execution of procedural constructs in SQL

• US 6,081,801 A
• Filed: 06/30/1997
• Issued: 06/27/2000
• Est. Priority Date: 06/30/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Simmen, David Everett, Sidle, Richard Sefton, Pirahesh, Mir Hamid, Truong, Tuong Chanh, Lapis, George, Cochrane, Roberta Jo, Urata, Monica Sachiye
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): PARDO, THUY N
• Application Number:
  US08/885,479
• Time in Patent Office: 1,093 Days
• Field of Search: 395/675, 395/704, 395/0.29, 707/2, 707/3, 707/201, 707/202, 707/203, 707/8
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

An automated methodology, and an apparatus for practicing the methodology, which enables the power and flexibility inherent in shared nothing parallel database systems (MPP) to be utilized on complex queries which have, heretofore, contained query elements requiring local computation or local coordination of data computation performed across the nodes of the distributed system. The present invention provides these features and advantages by identifying and marking the subgraphs containing these types of query elements as "no TQ zones" in the preparation phase prior to optimization. When the optimizer sees the markings, it builds a plan that will force the computation of the marked subgraphs to be in the same section. This preparation phase also provides the partitioning information for all inputs to the "no TQ zones". This allows the bottom-up optimizer to correctly plan the partitioning for the "no TQ zones". These partitionings can force the operation to a single-node, the coordinator node, the catalog node, or to a particular partition class on multiple nodes, or nodegroups.

Claims

1. Data processor implemented method for specifying complex queries to a relational database management system implemented on a parallel network, the network including a plurality of nodes coordinated by a network protocol, each of the nodes including at least one of data processor, data storage device, and memory, wherein the data contained in the base tables of the relational database management system is retrievable by means of a query language query to the database management system, the query containing at least one of query elements which require local computation or local coordination of data computation performed across the nodes of the distributed system and query elements which are computable on the several nodes of the network, the method comprising the steps of:

identifying and marking those subgraphs of the query which must be executed on one of a given node and a nodegroup as "No TQ Zones", or NTQZs;

recognizing the marks written on those subgraphs of the query which must be executed on a given node or nodegroup by the identifying and marking step;

responsive to the recognizing step, generating a query plan which forces the computation of the marked subgraphs to be in the same section of the query plan;

responsive to the step of generating a query plan, partitioning that query plan into subplans including the NTQZs marked in the identifying and marking step, whereby the partitions formed by the partitioning step force the operation of subplans including a NTQZ to at least one of a single-node, the coordinator node, the catalog node, and to a particular partition class on multiple nodes; and

executing the query plan.

2. The method of claim 1 further applicable to queries containing common sub-expressions and, responsive to the step of generating the query plan, comprising the further step of generating threaded code for the common sub-expressions prior to the step of executing the query plan.

3. A system for processing complex queries, comprising:

a parallel network including a plurality of nodes coordinated by a network protocol, each of the nodes including at least one of data processor, data storage device, and memory;

a relational database management system having data contained in base tables, wherein the data is retrievable by means of a query language query to the database management system, and the query contains at least one of query elements which require local computation or local coordination of data computation performed across the nodes of the distributed system and query elements which are computable on the several nodes of the parallel network;

a data processor for specifying the query to the relational database management system, the data processor operative for;

identifying and marking those subgraphs of the query which must be executed on one of a given node and a nodegroup as "No TQ Zones", or NTQZs;

recognizing the marks written on those subgraphs of the query which must be executed on a given node or nodegroup by the identifying and marking step;

responsive to the recognizing step, generating a query plan which forces the computation of the marked subgraphs to be in the same section of the query plan;

responsive to the step of generating a query plan, partitioning that query plan into subplans including the NTQZs marked in the identifying and marking step, whereby the partitions formed by the partitioning step force the operation of subplans including a NTQZ to at least one of a single-node, the coordinator node, the catalog node, and to a particular partition class on multiple nodes; and

executing the query plan.

4. The system of claim 3 further applicable to queries containing common sub-expressions, and wherein the data processor is further operative for, responsive to the step of generating the query plan, generating threaded code for the common sub-expressions prior to the step of executing the query plan.

5. A database language compiler for specifying complex queries to a relational database management system implemented on a parallel network, the network including a plurality of nodes coordinated by a network protocol, each of the nodes including at least one of data processor, data storage device, and memory, wherein the data contained in the base tables of the relational database management system is retrievable by means of a query language query to the database management system, the query containing at least one of query elements which require local computation or local coordination of data computation performed across the nodes of the distributed system and query elements which are computable on the several nodes of the network, the database language compiler operative for:

identifying and marking those subgraphs of the query which must be executed on one of a given node and a nodegroup as "No TQ Zones", or NTQZs;

recognizing the marks written on those subgraphs of the query which must be executed on a given node or nodegroup by the identifying and marking step;

responsive to the recognizing step, generating a query plan which forces the computation of the marked subgraphs to be in the same section of the query plan;

responsive to the step of generating a query plan, partitioning that query plan into subplans including the NTQZs marked in the identifying and marking step, whereby the partitions formed by the partitioning step force the operation of subplans including a NTQZ to at least one of a single-node, the coordinator node, the catalog node, and to a particular partition class on multiple nodes; and

executing the query plan.

6. The database language compiler of claim 5 further applicable to queries containing common sub-expressions and, responsive to the step of generating the query plan, comprising the further step of generating threaded code for the common sub-expressions prior to the step of executing the query plan.

7. A computer program product for specifying complex queries to a relational database management system implemented on a parallel network, the network including a plurality of nodes coordinated by a network protocol, each of the nodes including at least one of data processor, data storage device, and memory, wherein the data contained in the base tables of the relational database management system is retrievable by means of a query language query to the database management system, the query containing at least one of query elements which require local computation or local coordination of data computation performed across the nodes of the distributed system and query elements which are computable on the several nodes of the network, the computer program product comprising:

a storage medium;

computer software stored on the storage medium and executable on a data processor for;

identifying and marking those subgraphs of the query which must be executed on one of a given node and a nodegroup as "No TQ Zones", or NTQZs;

recognizing the marks written on those subgraphs of the query which must be executed on a given node or nodegroup by the identifying and marking step;

responsive to the recognizing step, generating a query plan which forces the computation of the marked subgraphs to be in the same section of the query plan;

responsive to the step of generating a query plan, partitioning that query plan into subplans including the NTQZs marked in the identifying and marking step, whereby the partitions formed by the partitioning step force the operation of subplans including a NTQZ to at least one of a single-node, the coordinator node, the catalog node, and to a particular partition class on multiple nodes; and

executing the query plan.

8. The computer program product of claim 7 further applicable to queries containing common sub-expressions and, responsive to the step of generating the query plan, comprising the further step of generating threaded code for the common sub-expressions prior to the step of executing the query plan.