Method for Two-Stage Query Optimization in Massively Parallel Processing Database Clusters

• US 20140188841A1
• Filed: 12/29/2012
• Published: 07/03/2014
• Est. Priority Date: 12/29/2012
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Sun, Yang, Zhou, Qingqing, Singamshetty, Mohan
• Granted Patent: US 9,311,354 B2
• Time in Patent Office: Days
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24553 of query operations

Abstract

Queries may be processed more efficiently in an massively parallel processing (MPP) database by locally optimizing the global execution plan. The global execution plan and a semantic tree may be provided to MPP data nodes by an MPP coordinator. The MPP data nodes may then use the global execution plan and the semantic tree to generate a local execution plan. Thereafter, the MPP data nodes may select either the global execution plan or the local execution plan is accordance with a cost evaluation.

Claims

1. A method for processing queries in a massively parallel processing (MPP) database, the method comprising:

receiving, by an MPP data node, a global execution plan and a semantic tree from an MPP coordinator;

generating, by the MPP data node, a local execution plan in accordance with the semantic tree; and

selecting either the global execution plan or the local execution plan for execution by the MPP data node.

2. The method of claim 1, wherein the execution plan and the semantic tree correspond to a query made by a client.

3. The method of claim 1, wherein selecting either the global execution plan or the local execution plan for execution by the MPP data node comprises:

determining a cost for each of the local execution plan and the global execution plan in accordance with a defined cost model;

selecting the local execution plan when the local execution plan has a lower cost than the global execution plan; and

selecting the global execution plan when the local execution plan has an equal or greater cost than the global execution plan.

4. The method of claim 3, wherein the defined cost model accounts for local configuration information native to the MPP data node, and wherein the local configuration information native to the MPP data node is unavailable to the MPP coordinator when generating the global execution plan.

5. The method of claim 4, wherein the global execution plan is generated by the MPP coordinator under the assumption that data is uniformly distributed amongst a plurality of MPP data nodes in the MPP database.

6. The method of claim 1, wherein generating the local execution plan comprises:

generating the local execution plan in accordance with local configuration information native to the MPP data node, wherein the local configuration information is unavailable to the MPP coordinator when the MPP coordinator generates the global execution plan.

7. The method of claim 6, wherein the local configuration information specifies resource constraints of the MPP data node.

8. The method of claim 6, wherein the local configuration information specifies an amount of data stored by the MPP data node, wherein data is non-uniformly distributed in the MPP database such that the amount of data stored by the MPP data node differs from amounts of data stored in other MPP data nodes of the MPP database.

9. The method of claim 1, wherein generating the local execution plan comprises:

identifying a sub-tree of the semantic tree;

fortifying the sub-tree in accordance with a set of constraints enforced by the global execution plan; and

generating the local execution plan local plan in accordance with the fortified sub-tree.

10. The method of claim 9, wherein the set of constraints enforced by the global execution plan comprise at least one of an ordering of a result set, a distinctness of result set, and a number of rows contained in the result set.

11. A massively parallel processing (MPP) data node in an MPP database, the MPP data node comprising:

a processor; and

a computer readable storage medium storing programming for execution by the processor, the programming including instructions to;

receive a global execution plan and a semantic tree from an MPP coordinator;

generate a local execution plan in accordance with the semantic tree; and

select either the global execution plan or the local execution plan for execution by the MPP data node.

12. The MPP data node of claim 11, wherein the instructions to select either the global execution plan or the local execution plan for execution by the MPP data node includes instructions to:

determine a cost for each of the local execution plan and the global execution plan in accordance with a defined cost model;

select the local execution plan when the local execution plan has a lower cost than the global execution plan; and

select the global execution plan when the local execution plan has an equal or greater cost than the global execution plan.

13. The MPP data node of claim 12, wherein the defined cost model accounts for local configuration information native to the MPP data node, and wherein the local configuration information is unavailable to the MPP coordinator when the MPP coordinator generates the global execution plan.

14. The MPP data node of claim 13, wherein the global execution plan is generated by the MPP coordinator under the assumption that data is uniformly distributed amongst a plurality of MPP data nodes in the MPP database.

15. The MPP data node of claim 11, wherein generating the local execution plan comprises:

generating the local execution plan in accordance with local configuration information native to the MPP data node, wherein the local configuration information is unavailable to the MPP coordinator when the MPP coordinator generates the global execution plan.

16. The MPP data node of claim 15, wherein the local configuration information specifies resource constraints of the MPP data node.

17. The MPP data node of claim 15, wherein the local configuration information specifies an amount of data stored by the MPP data node, wherein data is non-uniformly distributed in the MPP database such that the amount of data stored by the MPP data node differs from amounts of data stored in other MPP data nodes of the MPP database.

18. The MPP data node of claim 11, wherein generating the local execution plan comprises:

identifying a sub-tree of the semantic tree;

fortifying the sub-tree in accordance with a set of constraints enforced by the global execution plan; and

generating the local execution plan in accordance with the fortified sub-tree.

19. A massively parallel processing (MPP) database system comprising:

one or more MPP coordinators configured to;

receive a query from a client;

generate a semantic tree;

develop a global execution plan for executing the query in accordance with the semantic tree; and

distribute the global execution plan to a plurality of MPP data nodes; and

a first one of the plurality of MPP data nodes configured to;

receive the global execution plan and the semantic tree from the one or more MPP coordinators;

obtain an optimized execution plan by optimizing the global execution plan using the semantic tree in accordance with local configuration information of the first MPP data node; and

execute the optimized execution plan.

20. The MPP database system of claim 19, wherein the local configuration information is unavailable to the one or more MPP coordinators during development of the global execution plan.