System and Methodology for Parallel Query Optimization Using Semantic-Based Partitioning

• US 20060218123A1
• Filed: 06/02/2005
• Published: 09/28/2006
• Est. Priority Date: 03/28/2005
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Andrei, Mihnea, Chowdhuri, Sudipto R.
• Granted Patent: US 8,126,870 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 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 potentially useful for performing a given relational operation;

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 potentially useful; and

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

2. The method of claim 1, wherein the query comprises a Structured Query Language (SQL) expression.

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 useful partitioning.

13. A computer-readable medium having processor-executable instructions for performing the method of claim 1.

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

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

determining whether dividing data processed by a particular relational operator in said tree is useful for executing a relational operation in parallel;

if partitioning of a particular relational operator is determined to be useful, 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; and

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

15. The method of claim 14, wherein the query comprises a Structured Query Language (SQL) expression.

16. The method of claim 14, 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.

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

18. The method of claim 17, 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.

19. The method of claim 18, wherein said creating step further comprises determining a particular type of operator to be used for dividing data based on semantics of the query.

20. The method of claim 19, wherein said particular type of operator comprises 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.

21. The method of claim 18, 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.

22. The method of claim 14, 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.

23. The method of claim 22, 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.

24. The method of claim 23, 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 useful division of data.

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

26. A computer-readable medium having processor-executable instructions for performing the method of claim 14.

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

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

a partitioning module for creating 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; and

a module for constructing 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.

28. The system of claim 27, wherein said module for generating groups said plan fragments into classes based on database tables covered by each plan fragment.

29. The system of claim 27, wherein said module for constructing 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.

30. The system of claim 27, wherein said module for generating generates plan fragments using iterators.

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

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

33. The system of claim 32, 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.

34. The system of claim 27, wherein said module for constructing prunes plan fragments having unfavorable execution costs and not providing a potentially useful partitioning.

35. The system of claim 27, wherein said module for constructing 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 potentially useful partitioning.

36. The system of claim 27, further comprising:

an execution module for executing the query based on the final plan.

37. 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, partitioning said data into separate memory buffers; and

processing said query in parallel by concurrently processing said data in said memory buffers.

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

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

40. The method of claim 39, further comprising:

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

41. The method of claim 37, 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.

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

43. The method of claim 37, wherein said partitioning step includes substeps of:

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

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

44. The method of claim 37, 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.

45. The method of claim 44, 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.

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

47. A computer-readable medium having processor-executable instructions for performing the method of claim 37.