System and methodology for parallel query optimization using semantic-based partitioning

• US 8,126,870 B2
• Filed: 06/02/2005
• Issued: 02/28/2012
• Est. Priority Date: 03/28/2005
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Chowdhuri, Sudipto R., Andrei, Mihnea
• Primary Examiner(s): Chbouki, Tarek
• Application Number:
  US10/908,956
• Publication Number:
  US 20060218123A1
• Time in Patent Office: 2,462 Days
• Field of Search: 707/3, 707/2, 707/1, 707/100
• US Class Current: 707/713
• CPC Class Codes: G06F 16/24532 of parallel queries

Abstract

A system and methodology for parallel query optimization using semantic-based partitioning is described. In one embodiment, for example, in a database system comprising a database storing data in database tables, a method is described for improving query performance by dynamically partitioning the data, the method comprises steps of: receiving a query requesting data from the database; generating a plurality of subplans for executing the query, each subplan including one or more operators for performing relational operations; adding operators for partitioning data and performing a given relational operation in parallel to at least some of the plurality of subplans; and building a plan for execution of the query based, at least in part, upon selecting subplans having favorable execution costs.

Claims

1. In a database system comprising a database storing data in database tables, a method for improving query performance by dynamically partitioning said data, the method comprising:

generating, by at least one processor, a plurality of subplans for obtaining data requested by the query, each subplan including one or more operators for performing relational operations;

determining if partitioning of data is advantageous for performing a given relational operation, wherein said data includes unpartitioned data, and wherein determining if partitioning of data is advantageous for performing the given relational operation comprises determining whether an amount of data involved for the given relational operation satisfies a threshold;

performing the given relational operation serially with at least some of said plurality of subplans if partitioning of data is determined to be not advantageous;

adding operators for partitioning data and performing the given relational operation in parallel to at least some of said plurality of subplans if partitioning of data is determined to be advantageous;

building a plan for execution of the query based, at least in part, upon selecting subplans having favorable execution costs; and

executing the plan and returning results in response to the query.

2. The method of claim 1, wherein the query comprises a Structured Query Language (SQL) expression which includes at least one of a join, grouping, union, distinct, subquery and ordering operation.

3. The method of claim 1, wherein said adding step includes adding an operator to a subplan for splitting data into a plurality of partitions during processing of the query.

4. The method of claim 3, wherein said adding step includes cloning an operator for performing a given relational operation, so as to provide for performing the relational operation in parallel on said plurality of partitions.

5. The method of claim 3, wherein said plurality of partitions includes selected ones of data partitions and index partitions.

6. The method of claim 3, wherein said adding step includes determining partitions qualifying a predicate of the query.

7. The method of claim 6, further comprising:

eliminating partitions not qualifying a predicate of the query, so as to avoid processing eliminated partitions.

8. The method of claim 7, wherein said step of determining partitions qualifying a predicate of the query includes determining whether a particular partition qualifies a given predicate based on partitioning keys of the particular partition.

9. The method of claim 1, wherein said adding step includes cloning an operator in a subplan into a plurality of operators for processing data in parallel.

10. The method of claim 1, wherein said adding step includes adding an operator for pipelining of intermediate results from a first operator to a second operator.

11. The method of claim 1, wherein said adding step includes adding an operator for performing a selected one of a range partitioning, a list partitioning, a hash partitioning, a round-robin partitioning, and an “

any”

partitioning.

12. The method of claim 1, wherein said building step includes selecting a subplan providing a partitioning which is advantageous to include the plan for execution of the query.

13. In a database system, a method for optimization of a query requesting data from a database, the method comprising:

constructing, by at least one processor, a tree of relational operators based on the query, each relational operator for performing a given relational operation;

determining whether partitioning of data processed by a particular relational operator in said tree is advantageous for executing a relational operation in parallel, wherein said data includes unpartitioned data, and wherein determining whether partitioning of data processed by a particular relational operator in said tree is advantageous for executing the relational operation in parallel comprises determining whether an amount of data involved for the given relational operation satisfies a threshold;

if partitioning of data processed by a particular relational operation in said tree is determined to be not advantageous, executing the particular relational operation serially;

if partitioning of data processed by a particular relational operator in said tree is determined to be advantageous, creating a revised tree by adding operators to said tree for dividing data processed by the particular relational operator and executing the particular relational operator in parallel over the divided data;

generating a plan for execution of the query based on said revised tree; and

executing the plan and returning results in response to the query.

14. The method of claim 13, wherein the query comprises a Structured Query Language (SQL) expression which includes at least one of a join, grouping, union, distinct, subquery and ordering operation.

15. The method of claim 13, wherein said step of constructing a tree of relational operators includes generating nodes of the tree of relational operators as iterators for applying predefined behavior to data.

16. The method of claim 13, wherein said creating step includes creating a plurality of clones of the particular relational operator.

17. The method of claim 16, wherein said creating step includes inserting one or more operators into said tree for dividing data for processing in parallel by said plurality of clones.

18. The method of claim 17, wherein at least one of said one or more operators inserted into said tree implements a particular partitioning strategy.

19. The method of claim 18, wherein said particular partitioning strategy comprises a selected one of a range partitioning strategy, a list partitioning strategy, a hash partitioning strategy, a round-robin partitioning strategy, and an “

any”

partitioning strategy.

20. The method of claim 17, wherein said creating step further comprises inserting one or more operators into said tree for merging data after the data has been processed in parallel by said plurality of clones.

21. The method of claim 13, wherein said creating step is performed during generation of alternate plans for executing the query and said operators are added to at least some of said alternate plans.

22. The method of claim 21, wherein said step of generating alternate plans includes generating alternate subplans and said creating step includes adding operators for dividing data to at least some of said alternate subplans.

23. The method of claim 22, wherein said step of generating a plan for execution of the query includes selecting a particular subplan from a plurality of alternate subplans based, at least in part, upon whether the particular subplan has a division of data which is advantageous for purposes of query processing.

24. The method of claim 13, wherein said step of generating a plan for execution of the query includes determining data qualifying a predicate of the query.

25. A database system for dynamically partitioning data during query processing, the system comprising:

a computer having memory and at least one processor for running the database system;

a module operable to generate a plurality of plan fragments for obtaining data requested by a query from database tables of the database system;

wherein at least some of the data is unpartitioned;

a partitioning module operable to create additional plan fragments by adding operators for dynamically partitioning data and processing the partitioned data in parallel to at least some of said plan fragments;

a module operable to determine whether dynamically partitioning data is advantageous, based on whether an amount of data involved for a plan fragment satisfies a threshold; and

a module operable to construct a final plan for execution of the query based, at least in part, upon selecting plan fragments having operators for dynamically partitioning data and processing the partitioned data in parallel when dynamically partitioning data is determined to be advantageous and selecting plan fragments for processing the data serially when dynamically partitioning data is determined to be not advantageous.

26. The system of claim 25, wherein said module operable to generate groups said plan fragments into classes based on database tables covered by each plan fragment.

27. The system of claim 25, wherein said module operable to construct selects a given plan fragment from a given class based, at least in part, upon determining whether the given plan fragment has favorable execution costs.

28. The system of claim 25, wherein said module operable to generate generates plan fragments using iterators.

29. The system of claim 28, wherein a plan fragment comprises a tree of iterators for executing a portion of the query.

30. The system of claim 28, wherein said partitioning module creates an additional plan fragment by adding one or more iterators for partitioning data to a given plan fragment.

31. The system of claim 30, wherein said partitioning module creates the additional plan fragment by adding one or more iterators for executing a relational operation in parallel over the partitioned data to the given plan fragment.

32. The system of claim 25, wherein said module operable to construct prunes plan fragments having unfavorable execution costs and not providing a partitioning which is advantageous.

33. The system of claim 25, wherein said module operable to construct selects a particular plan fragment for inclusion in the final plan based on whether estimated execution costs of the particular plan fragment and whether the particular plan fragment provides a partitioning which is advantageous.

34. The system of claim 25, further comprising:

an execution module operable to execute the query based on the final plan.

35. In a database system comprising a database storing data in database tables, a method for improving query performance comprising:

receiving a query specifying a join of two or more database tables;

as data is retrieved from the database during processing of the query,

determining, by at least one processor, whether partitioning is advantageous for a given relational operation to be performed for returning data requested by the query based, at least in part, on determining whether a quantity of data to be processed during a given relational operation satisfies a threshold; and

if partitioning is determined to be not advantageous, processing said query serially;

if partitioning is determined to be advantageous, partitioning data to be processed during a given relational operation into separate memory;

wherein at least some of the data is unpartitioned when retrieved from the database and before being partitioned into separate memory buffers;

processing said query in parallel by concurrently processing said data in said memory buffers if partitioning is determined to be advantageous; and

returning results of processing said query in response to said query.

36. The method of claim 35, wherein said partitioning step includes dividing the data into a plurality of data streams during processing of the query.

37. The method of claim 35, wherein said partitioning step includes determining data qualifying a predicate of the query.

38. The method of claim 37, further comprising:

processing only the data determined to qualify a predicate of the database query.

39. The method of claim 35, wherein said processing step includes cloning a relational operator to be used in processing the query into a plurality of relational operators for processing data in said memory buffers in parallel.

40. The method of claim 39, wherein said processing step includes merging results of said plurality of relational operators for returning results of the query.

41. The method of claim 35, wherein said partitioning step includes adding one or more operators to a plan for executing the query, said one or more operators for splitting data into a plurality of separate memory buffers for executing a given relational operation in parallel.

42. The method of claim 41, wherein said processing step includes cloning a given relational operator in the plan for performing the given relational operation in parallel on the plurality of separate memory buffers.

43. The method of claim 42, wherein said processing step further comprises adding an operator to the plan for merging data after the data has been processed in parallel.

44. A computer readable medium encoded with a computer program, the program comprising instructions that when executed by one or more processors cause the one or more processors to perform operations comprising:

generating a plurality of subplans for obtaining data requested by a query, each subplan including one or more operators for performing relational operations;

determining if partitioning of data is advantageous for performing a given relational operation, wherein said data includes unpartitioned data, and wherein determining if partitioning of data is advantageous for performing the given relational operation comprises determining whether an amount of data involved for the given relational operation satisfies a threshold;

performing the given relational operation serially with at least some of said plurality of subplans if partitioning of data is determined to be not advantageous;

adding operators for partitioning data and performing the given relational operation in parallel to at least some of said plurality of subplans if partitioning of data is determined to be advantageous;

building a plan for execution of the query based, at least in part, upon selecting subplans having favorable execution costs; and

executing the plan and returning results in response to the query.

45. A computer readable medium encoded with a computer program, the program comprising instructions that when executed by one or more processors cause the one or more processors to perform operations comprising:

constructing a tree of relational operators based on a query, each relational operator for performing a given relational operation;

determining whether partitioning of data processed by a particular relational operator in said tree is advantageous for executing a relational operation in parallel, wherein said data includes unpartitioned data, and wherein determining whether partitioning of data processed by a particular relational operator in said tree is advantageous for executing the relational operation in parallel comprises determining whether an amount of data involved for the given relational operation satisfies a threshold;

if partitioning of data processed by a particular relational operation in said tree is determined to be not advantageous, executing the particular relational operation serially;

if partitioning of data processed by a particular relational operator in said tree is determined to be advantageous, creating a revised tree by adding operators to said tree for dividing data processed by the particular relational operator and executing the particular relational operator in parallel over the divided data;

generating a plan for execution of the query based on said revised tree; and

executing the plan and returning results in response to the query.

46. A computer readable medium encoded with a computer program, the program comprising instructions that when executed by one or more processors cause the one or more processors to perform operations comprising:

receiving a query specifying a join of two or more database tables;

as data is retrieved from the database during processing of the query,

determining whether partitioning is advantageous for a given relational operation to be performed for returning data requested by the query based, at least in part, on determining whether a quantity of data to be processed during a given relational operation satisfies a threshold; and

if partitioning is determined to be not advantageous, processing said query serially;

if partitioning is determined to be advantageous, partitioning data to be processed during a given relational operation into separate memory buffers;

wherein at least some of the data is unpartitioned when retrieved from the database and before being partitioned into separate memory buffers;

processing said query in parallel by concurrently processing said data in said memory buffers if partitioning is determined to be advantageous; and

returning results of processing said query in response to said query.