Database System with Methodology for Parallel Schedule Generation in a Query Optimizer

• US 20060080285A1
• Filed: 10/13/2004
• Published: 04/13/2006
• Est. Priority Date: 10/13/2004
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Chowdhuri, Sudipto R.
• Granted Patent: US 7,574,424 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A database system with methodology for parallel schedule generation in a query optimizer is described. In one embodiment, for example, in a database system, a method is described for parallel optimization of a query, the method comprises steps of: generating a plurality of parallel plans for obtaining data requested by the query, the parallel plans including parallel operators for executing portions of the query in parallel; adjusting parallel operators of each parallel plan if necessary based on resources available for executing the query; creating a schedule for each parallel plan indicating a sequence for execution of operators of each parallel plan; determining execution cost of each parallel plan based on its schedule; and selecting a particular parallel plan having lowest execution cost for obtaining data requested by the query.

Claims

1. In a database system, a method for parallel optimization of a query, the method comprising:

generating a plurality of parallel plans for obtaining data requested by the query, the parallel plans including parallel operators for executing portions of the query in parallel;

adjusting parallel operators of each parallel plan if necessary based on resources available for executing the query;

creating a schedule for each parallel plan indicating a sequence for execution of operators of each parallel plan;

determining execution cost of each parallel plan based on its schedule; and

selecting a particular parallel plan having lowest execution cost for obtaining data requested by the query.

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

3. The method of claim 1, wherein said generating step includes generating an operator tree for each parallel plan based on the query.

4. The method of claim 3, wherein said step of generating an operator tree includes generating nodes of the operator tree as iterators for applying predefined behavior to data.

5. The method of claim 3, wherein said step of generating an operator tree includes inserting a parallel operator in the operator tree.

6. The method of claim 5, wherein said step of generating an operator tree includes dividing a query operation into sub-tasks and said parallel operator provides for executing said sub-tasks in parallel.

7. The method of claim 6, wherein said step of executing said sub-tasks in parallel includes executing said sub-tasks in parallel across a plurality of storage units.

8. The method of claim 6, wherein said step of executing said sub-tasks in parallel includes executing said sub-tasks in parallel across a plurality of CPUs.

9. The method of claim 1, wherein said parallel operator provides for pipelining of intermediate results from a first set of operators to a second set of operators.

10. The method of claim 1, wherein said generating step includes generating a parallel plan using a partitioning property so as to efficiently partition data among operators of the parallel plan.

11. The method of claim 1, wherein said generating step includes generating a cost vector for each parallel plan.

12. The method of claim 11, wherein said cost vector includes as components a selected one or more of work done by a processor in a given time, execution time of an operator in the parallel plan, and resource usage of an operator in the parallel plan for a certain time period.

13. The method of claim 11, wherein said generating step further comprises:

pruning a first parallel plan having a cost vector less favorable in each vector dimension than a second parallel plan.

14. The method of claim 1, wherein said generating step includes generating a plurality of parallel plans based at least in part on partitioning and multi-dimensional costing.

15. The method of claim 1, wherein said adjusting step includes adjusting a parallel plan for available worker processes at compile time.

16. The method of claim 15, wherein the parallel plan comprises an operator tree and an adjustment is made to at least some parallel operators of the operator tree if the operator tree exceeds maximum configured worker processes.

17. The method of claim 1, wherein said step of adjusting parallel operators of each parallel plan if necessary based on resources available for executing the query includes adjusting parallel operators based on available memory resources.

18. The method of claim 1, wherein said creating step includes separating a resource intensive operator into a plurality of operators.

19. The method of claim 1, wherein said creating step includes identifying pipelines in each parallel plan.

20. The method of claim 19, wherein said creating step includes constructing a pipeline dependency tree based on dependencies among operators of each parallel plan.

21. The method of claim 20, wherein said creating step includes determining order of execution of pipelines based on the pipeline dependency tree and available resources.

22. The method of claim 19, further comprising:

if resource usage of a particular pipeline is greater than resources available for the particular pipeline, splitting the particular pipeline into a plurality of pipelines.

23. The method of claim 22, wherein said step of splitting the particular pipeline includes adding operators for materializing the particular pipeline into a plurality of pipelines at intervals such that resource usage is evenly distributed over the plurality of pipelines.

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

25. A downloadable set of processor-executable instructions for performing the method of claim 1.

26. A system for parallel optimization of a database query, the system comprising:

a search engine for generating a plurality of parallel plans which can be used for obtaining data requested by the query, the parallel plans including parallel operators for executing portions of the query in parallel;

a parallel scheduler for adjusting parallel operators of each parallel plan if necessary based on resources available for executing the query and creating a schedule for the parallel plan indicating a sequence for execution of operators of the parallel plan; and

a module for determining execution cost of each parallel plan based on its schedule and selecting a particular parallel plan having lowest execution cost for obtaining data requested by the query.

27. The system of claim 26, wherein the query comprises a Structured Query Language (SQL) expression.

28. The system of claim 26, wherein the search engine generates an operator tree for each parallel plan based on the query.

29. The system of claim 28, wherein the search engine generates nodes of the operator tree as iterators for applying predefined behavior to data.

30. The system of claim 28, wherein the search engine inserts a parallel operator in the operator tree.

31. The system of claim 30, wherein the search engine divides a query operation into sub-tasks and said parallel operator provides for executing said sub-tasks in parallel.

32. The system of claim 31, wherein said parallel operator provides for executing said sub-tasks in parallel across a plurality of storage units.

33. The system of claim 31, wherein said parallel operator provides for executing said sub-tasks in parallel across a plurality of CPUs.

34. The system of claim 26, wherein said parallel operator provides for pipelining of intermediate results from a first set of operators to a second set of operators.

35. The system of claim 26, wherein the search engine generates a parallel plan using a partitioning property so as to efficiently partition data among operators of the parallel plan.

36. The system of claim 26, wherein the search engine generates a cost vector for each parallel plan.

37. The system of claim 36, wherein said cost vector includes as components a selected one or more of work done by a processor in a given time, execution time of an operator in the parallel plan, and resource usage of an operator in the parallel plan for a certain time period.

38. The system of claim 36, wherein the search engine prunes a first parallel plan having a cost vector less favorable in each vector dimension than a second parallel plan.

39. The system of claim 26, wherein the search engine generates a plurality of parallel plans based at least in part on partitioning and multi-dimensional costing.

40. The system of claim 26, wherein the parallel scheduler adjusts a parallel plan for available worker processes at compile time.

41. The system of claim 26, wherein a parallel plan comprises an operator tree and the parallel scheduler adjusts at least some parallel operators of the operator tree based on available threads.

42. The system of claim 26, wherein the parallel scheduler separates a resource intensive operator into a plurality of operators.

43. The system of claim 26, wherein the parallel scheduler identifies pipelines in the parallel plan.

44. The system of claim 43, wherein the parallel scheduler constructs a pipeline dependency tree based on dependencies among operators of a parallel plan.

45. The system of claim 44, wherein the parallel scheduler determines order of execution of pipelines based on the pipeline dependency tree and available resources.

46. The system of claim 43, wherein the parallel scheduler splits a particular pipeline into a plurality of pipelines.

47. The system of claim 46, wherein said parallel scheduler adds operators for materializing the particular pipeline into a plurality of pipelines at intervals such that resource usage is evenly distributed over the plurality of pipelines.

48. A method for parallel optimization of a query requesting data from a database, the method comprising:

creating a plurality of operator trees for executing the query, the operator trees providing for execution of portions of the query in parallel;

adjusting the portions of the query to be executed in parallel based on memory resources available for executing the query;

generating a schedule for execution of each operator tree; and

selecting the operator tree having lowest execution cost based on its schedule for executing the query.

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

50. The method of claim 48, wherein said creating step includes creating an operator tree including parallel operators for execution of portions of the query in parallel.

51. The method of claim 50, wherein said parallel operators comprise iterators for applying predefined behavior to data.

52. The method of claim 50, wherein said step of creating an operator tree includes creating operators for tasks to be performed in executing the query and said parallel operator provides for executing said tasks in parallel.

53. The method of claim 50, wherein a parallel operator executes in parallel across a plurality of storage units.

54. The method of claim 50, wherein a parallel operator executes in parallel across a plurality of CPUs.

55. The method of claim 50, wherein a parallel operator provides for pipelining of intermediate results from a first set of operators to a second set of operators.

56. The method of claim 48, wherein said creating step includes creating an operator tree using a partitioning property so as to efficiently partition data among operators.

57. The method of claim 48, wherein said creating step includes generating a cost vector for each operator tree.

58. The method of claim 57, wherein said cost vector includes as components a selected one or more of work done by a processor in a given time, execution time of an operator, and resource usage of an operator for a certain time period.

59. The method of claim 57, wherein said creating step further comprises:

pruning a first operator tree having a cost vector less favorable in each vector dimension than a second operator tree.

60. The method of claim 48, wherein said creating step includes creating a plurality of operator trees based at least in part on partitioning and multi-dimensional costing.

61. The method of claim 48, wherein said adjusting step includes adjusting an operator tree for available worker processes at compile time.

62. The method of claim 48, wherein said operator tree includes parallel operators for executing portions of the query in parallel and said adjusting step includes adjusting said parallel operators if necessary based on available memory resources.

63. The method of claim 48, wherein said adjusting step includes separating a resource intensive operator into a plurality of operators.

64. The method of claim 48, wherein said generating step includes identifying pipelines in each operator tree.

65. The method of claim 64, wherein said generating step includes constructing a pipeline dependency tree based on dependencies among operators of each operator tree.

66. The method of claim 65, wherein said creating step includes determining order of execution of pipelines based on the pipeline dependency tree and available resources.

67. The method of claim 66, further comprising:

if resource usage of a particular pipeline is greater than resources available for the particular pipeline, splitting the particular pipeline into a plurality of pipelines.

68. The method of claim 67, wherein said step of splitting the particular pipeline includes adding operators for materializing the particular pipeline into a plurality of pipelines at intervals such that resource usage is evenly distributed over the plurality of pipelines.

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

70. A downloadable set of processor-executable instructions for performing the method of claim 48.