Mechanism for optimizing parallel execution of queries on symmetric resources

• US 10,019,478 B2
• Filed: 09/04/2014
• Issued: 07/10/2018
• Est. Priority Date: 09/05/2013
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Liu, Yanchen, Mortazavi, Masood, Chen, Mengmeng, Cao, Fang
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US14/477,296
• Publication Number:
  US 20150066972A1
• Time in Patent Office: 1,405 Days
• Field of Search: 707713, 707719, 707737, 707600
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/24549 Run-time optimisation

Abstract

A method that comprises receiving a logical execution plan for a database query corresponding to a plurality of tables of the database, wherein the logical execution plan comprises one or more operators, receiving an operator cost for each of the operators in the logical execution plan, computing a first accumulated processing cost for a first of the tables based on the logical execution plan, operator selectivity, and operator costs corresponding to the first table, computing a second accumulated processing cost for a second of the tables based on the logical execution plan, operator selectivity, and operator costs corresponding to the second table, comparing the first accumulated processing cost and the second accumulated processing cost to determine a table with the highest accumulated processing cost, and responsive to comparing the accumulated processing costs, computing a physical execution plan that requires partitioning the table with the highest accumulated processing cost.

Claims

1. A method comprising:

receiving a logical execution plan for a database query corresponding to a plurality of tables of a database, wherein the logical execution plan comprises one or more operators;

receiving an operator cost for each of the operators in the logical execution plan;

computing a first accumulated processing cost for a first of the tables based on the logical execution plan and operator costs corresponding to the first table;

computing a second accumulated processing cost for a second of the tables based on the logical execution plan and operator costs corresponding to the second table;

comparing the first accumulated processing cost and the second accumulated processing cost to determine a table with a highest accumulated processing cost; and

responsive to comparing the accumulated processing costs, computing a physical execution plan that requires partitioning the table with the highest accumulated processing cost.

2. The method of claim 1, further comprising partitioning the table with the highest accumulated processing cost into a plurality of pieces.

3. The method of claim 2, wherein the table with the highest accumulated processing cost is partitioned into a number of pieces equal to a number of available symmetric computing resources.

4. The method of claim 3, further comprising partitioning the table with less than the highest accumulated processing cost into fewer pieces than the number of pieces into which the table with the highest accumulated processing cost is partitioned.

5. The method of claim 3, wherein partitioning is performed according to a cost-based piece-partitioning scheme for determining an accumulated processing cost for each table.

6. The method of claim 5, wherein the cost-based piece-partitioning scheme comprises a product of a number of records stored in the table multiplied by a sum of the operator costs corresponding with the table and multiplied by an accumulated effective selectivity value corresponding to the table.

7. The method of claim 1, wherein the operator cost comprises an amount of computing resources required to perform a database table operation associated with the operator.

8. The method of claim 1, wherein the physical execution plan describes a plan for performing operations of the database query in parallel.

9. A method comprising:

receiving instructions for querying data in a database comprising a plurality of tables;

receiving an accumulated operator selectivity related to a first table by execution of the instructions;

computing a first accumulated processing cost for the first table based on the operator selectivity of the first table;

receiving an accumulated operator selectivity related to a second table by execution of the instructions;

computing a second accumulated processing cost for the second table based on the operator selectivity of the second table;

comparing the first accumulated processing cost and the second accumulated processing cost; and

selecting a table for partitioning in response to the comparison such that the table selected for partitioning has a highest accumulated processing cost.

10. The method of claim 9, further comprising partitioning the table with the highest accumulated processing cost into a plurality of pieces.

11. The method of claim 10, wherein the table with the highest accumulated processing cost is partitioned into a number of pieces equal to a number of available symmetric computing resources.

12. The method of claim 9, further comprising asymmetrically partitioning the table with less than the highest accumulated processing cost into a plurality of pieces according to a cost differential between tables.

13. The method of claim 11, further comprising determining physical instructions for querying the database, wherein the instructions indicate operations to be performed in parallel on the plurality of pieces of the table with the highest accumulated processing cost.

14. The method of claim 9, wherein the instructions contain a first operator and a second operator, and wherein the accumulated operator selectivity comprises a probability of a record being found in the first or second table of the database by the first operator prior to execution of the second operator.

15. The method of claim 9, wherein the accumulated processing cost for the first or second table comprises a product of a number of records stored in the table multiplied by a sum of the operator costs corresponding with the table and multiplied by the accumulated operator selectivity corresponding to the table.

16. An apparatus comprising:

a port configured to receive;

a query tree associated with a query to be performed on a plurality of database tables by a plurality of threads;

a number of records stored in each table;

a plurality of operator costs, each corresponding to an operator identified by the query tree and one of the tables; and

a plurality of accumulated effective selectivity values, each corresponding to one of the operators identified by the query tree and one of the tables; and

a processor coupled to the port and configured to;

compute an accumulated processing cost for each table comprising a product of a number of records stored in the table multiplied by a sum of the operator costs corresponding with the table and multiplied by the accumulated effective selectivity value corresponding to the table; and

compute a query execution plan for the query in response to a comparison that comprises instructions for partitioning one of the database tables with a highest accumulated processing cost.

17. The apparatus of claim 16, wherein the query tree contains a first operator and a second operator, and wherein the accumulated operator selectivity comprises a probability of a record being found in one of the table of the database by the first operator prior to execution of the second operator.

18. The apparatus of claim 16, wherein computing the query execution plan further comprises partitioning the table with the highest accumulated processing cost into a number of pieces determined by a number of symmetric computing resources available in the apparatus.

19. The apparatus of claim 18, wherein computing the query execution plan comprises partitioning a second table having an accumulated processing cost that is less than the highest accumulated processing cost into fewer pieces than the number of pieces into which the table with the highest accumulated processing cost in partitioned.

20. The apparatus of claim 16, wherein computing the query execution plan further comprises determining a sequence of operators for execution in parallel to perform the query on the database.