OPTIMIZING QUERIES OF PARALLEL DATABASES

• US 20140114952A1
• Filed: 10/23/2012
• Published: 04/24/2014
• Est. Priority Date: 10/23/2012
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Robinson, Eric R., Halverson, Alan Dale, Shankar, Srinath, Nehme, Rimma V.
• Application Number:
  US13/657,891
• Publication Number:
  US 20140114952A1
• Time in Patent Office: Days
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24532 of parallel queries

Abstract

The present invention extends to methods, systems, and computer program products for optimizing queries of parallel databases. Queries can be partially optimized at an optimizer that is unaware of its use to optimize queries for parallel processing. The optimizer can produce a data structure (e.g., a SQL Server MEMO) that encapsulates a logical serial plan search space. The logical serial plan search space may not incorporate any notion of parallelism into the plan space itself. A parallel-aware optimizer can parallelize the logical serial plan search space by augmenting the data structure (e.g., transforming the SQL Server MEMO into a parallel MEMO). Augmentation can be with data movement operations that move data associated one or more compute nodes in a distributed architecture. Cost estimates can be calculated for the operations contained in the parallelized data structure. The parallel plan with the lowest estimated cost can be selected for the query.

Claims

1. At a computer system, the computer system including one or more processors and system memory, the computer system connected to a plurality of compute nodes configured in a shared-nothing architecture, a database distributed across the plurality of compute nodes, each compute node in the plurality of compute nodes maintaining a portion of the database in a local database instance, a method for optimizing a query of the database, the method comprising:

accessing the query, the query expressing a logical intent to retrieve specified data from within the database;

sending the query to an optimizer that lacks awareness of the database being distributed;

receiving a data structure from the optimizer, the data structure encapsulating a serial query plan search space, the serial query plan search space including one more query plans for implementing the expressed logical intent of the query;

parallelizing the serial query plan search space into a parallel query plan search space for use with the distributed database, the parallel query plan search space including one or more parallel query plans for implementing the expressed logical intent of the query, parallelizing the serial query plan search space including;

augmenting the data structure to account for data-parallelism in the database;

generating cost estimates for operations contained in the augmented data structure;

identifying a parallel query plan within the parallel query plan search space having the lowest cost based on the generated cost estimates; and

selecting the identified parallel query plan for implementing the expressed logical intent of the query.

2. The method of claim 1, wherein sending the query to an optimizer that lacks awareness of the database being distributed comprises sending the query to a shell database optimizer.

3. The method of claim 2, wherein receiving a data structure from the optimizer comprises receiving a MEMO data structure from the shell database optimizer.

4. The method of claim 3, wherein receiving a MEMO data structure from the shell database comprises receiving a MEMO data structure containing the serial query plan search space, the serial query plan search space having been optimized based on schema and statistics for the database.

5. The method of claim 1, wherein receiving a data structure from the optimizer comprises receiving a MEMO data structure including one or more serial query plans that were used to seed the MEMO data structure based on extended properties of the database.

6. The method as recited in claim 1, wherein augmenting the data structure to account for data-parallelism in the database comprises augmenting an SQL Server MEMO to account for data-parallelism in the database.

7. The method as recited in claim 6, wherein augmenting a SQL Server MEMO to account for data-parallelism in the database comprises adding data movement operations to the SQL Server MEMO.

8. The method as recited in claim 7, wherein generating cost estimates for operations contained in augmented data structure comprises generating cost estimates for the data movement operations added to the SQL Server MEMO data structure.

9. The method as recited in claim 7, wherein generating cost estimates for operations contained in augmented data structure comprises generating cost estimates for one or more non-data movement operations in the SQL Server MEMO data structure.

10. The method as recited in claim 1, wherein generating cost estimates for operations contained in augmented data structure comprises generating cost estimates for one or more of:

a replicate operation, a shuffle operation, a broadcast operation, a partition move operation, and a master move operation.

11. At a computer system, the computer system including one or more processors and system memory, the computer system also including a parallel-aware query optimizer, the computer system connected to a plurality of compute nodes configured in a shared-nothing architecture, a database distributed across the plurality of compute nodes, each compute node in the plurality of compute nodes maintaining a portion of a database in a local database instance, a method for optimizing a query of the database, the method comprising:

accessing a SQL Server MEMO, the SQL Server MEMO encapsulating one or more serial query plans for implementing an express logical intent of the query, the express logical intent to retrieve specified data from within the database;

transforming the SQL Server MEMO into a parallel MEMO by augmenting the one or more serial query plans into one or more parallel query plans that, when executed, implement the express logical intent of the query and that account for data-parallelism in the database, augmenting including adding at least one data movement operation to each of the one or more serial query plans, added data movement operations configured to move database data associated with at least one compute node;

for each of the one or more parallel query plans, generating an estimated execution cost for the parallel query plan, the estimated execution cost based on the type of data movement operation added to the query plan and on statistics for the associated database data;

identifying a parallel query plan with the lowest estimated cost; and

selecting the identified parallel query plan to implement the expressed logical intent of the query.

12. The method claim 11, wherein accessing a SQL Server MEMO comprises accessing an SQL Server MEMO that includes at least one query plan used to seed generation of the SQL Server MEMO.

13. The method claim 11, wherein transforming the SQL Server MEMO into a parallel MEMO comprises adding a DSQL group expression to the SQL Server MEMO.

14. The method of claim 11, wherein using the identified augmented query plan for the query comprises:

extracting the identified augmented query plan from the parallel MEMO as a DSQL group expression tree;

sending the DSQL group expression tree to an SQL generator to generate a DSQL plan for execution.

15. The method of claim 11, wherein generating an estimated execution cost for the augmented query plan comprises generating an estimated execution cost for the augmented query plan based on one or more non-data movement operators.

16. The method of claim 11, wherein generating an estimated execution cost for the parallel query plan comprises generating an estimated execution cost for one or more of:

a replicate operation, a shuffle operation, a broadcast operation, a partition move operation, and a master move operation.

17. A distributed database system, the distributed database system comprising:

a distributed database, the distributed database distributed across a plurality of compute nodes;

the plurality of compute nodes configured and a control node configured in a shared-nothing architecture, each compute node including;

one or more processors;

system memory; and

one or more storage devices; and

each compute node maintaining a portion of the database in a local database instance at the one or more storage devices;

the control node including;

one or more processors;

system memory;

one or more computer storage devices having stored thereon computer executable instructions representing a parallel-aware optimizer and a plan selector, the control node configured to;

access a query, the query expressing a logical intent to retrieve specified data from within the database; and

send the query to a SQL server optimizer; and

wherein the parallel-aware optimizer is configured to;

receive a data structure from the SQL server optimizer, the data structure containing a serial query plan search space, the serial query plan search space including one more query plans for implementing the expressed logical intent of the query; and

parallelize the serial query plan search space into a parallel query plan search space for use with the distributed database, the parallel query plan search space including one or more parallel query plans for implementing the expressed logical intent of the query, parallelizing the serial query plan search space including;

augment the data structure to account for data-parallelism in the database;

generate cost estimates for operations contained in the augmented data structure;

wherein the plan selector is configured to;

identify a parallel query plan within the parallel query plan search space having the lowest cost based on the generated cost estimates; and

select the identified parallel query plan for implementing the expressed logical intent of the query; and

the SQL server optimizer including;

a shell database;

the SQL server optimizer configured to;

receive the query from the control node;

generate the data structure containing the serial query plan search space for the query by referring to statistics in the shell database; and

return the data structure containing the serial query plan search space to the control node.

18. The system as recited in claim 17, wherein the SQL server optimizer being configured to generate the data structure containing the serial query plan search space comprises the SQL server optimizer being configured to generate a SQL Server MEMO.

19. The system as recited in claim 18, wherein the control node being configured to parallelize the serial query plan search space into a parallel query plan search space comprises the e control node being configured to transform the SQL Server MEMO into a parallel MEMO.

20. The system as recited in claim 19, wherein the parallel-aware optimizer being configured to generate cost estimates for operations contained in the augmented data structure comprise the parallel-aware optimizer being configured to generate cost estimates for one or more of:

replicate operation, a shuffle operation, a broadcast operation, a partition move operation, and a master move operation, contained in the parallel MEMO.