System and method for automating data partitioning in a parallel database

• US 20040122845A1
• Filed: 12/19/2002
• Published: 06/24/2004
• Est. Priority Date: 12/19/2002
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Zhang, Chun, Megiddo, Nimrod, Lohman, Guy Maring, Rao, Jun
• Granted Patent: US 7,562,090 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A system for automating data partitioning in a parallel database includes plural nodes connected in parallel. Each node includes a database server and two databases connected thereto. Each database server includes a query optimizer. Moreover, a partitioning advisor communicates with the database server and the query optimizer. The query optimizer and the partitioning advisor include a program for recommending and evaluating data table partitions that are useful for processing a workload of query statements. The data table partitions are recommended and evaluated without requiring the data tables to be physically repartitioned.

Claims

1. A computer program device for automatically determining the best data partitioning for a given workload in a parallel database, comprising:

logic means for recommending at least one candidate partition for at least one data table.

2. The computer program device of claim 1, further comprising:

logic means for evaluating the candidate partition based in part on a workload of query statements to determine a cost of the workload of query statements using the candidate partition without first requiring the data table to be repartitioned.

3. The computer program device of claim 2, further comprising:

logic means for determining a best candidate partition for at least one data table and a corresponding cost at least partially based on the best candidate partition, such that an overall cost of the workload of query statements is minimized.

4. The computer program device of claim 3, further comprising:

logic means for combining the candidate partition with at least one other candidate partition; and

logic means for evaluating a combination of candidate partitions to determine a cost of using the combination.

5. The computer program device of claim 1, wherein the candidate partition is recommended by:

logic means for computing a list of candidate partitions for each base table of a database that can reduce a cost of processing the workload of query statements.

6. The computer program device of claim 5, further comprising:

logic means for reducing the number of candidate partitions for each base table without losing plan quality.

7. The computer program device of claim 1, wherein the logic means for recommending recommends at least one candidate partition for at least one data table at least partially based on a predetermined cost model.

8. The computer program device of claim 2, wherein the cost of the workload of query statements is determined at least partially based on a predetermined cost model.

9. The computer program device of claim 5, further comprising:

logic means for recording a best partition for at least one table in the overall query processing plan.

10. The computer program device of claim 2, wherein the candidate partition is evaluated by:

logic means for replacing original partitions in a workload of query statements with candidate partitions.

11. The computer program device of claim 10, further comprising:

logic means for evaluating the workload of query statements with candidate partitions in place of the original partitions.

12. A method for automatically partitioning data in a parallel database, comprising:

recommending at least one candidate partition for at least one data table based in part on a workload of query statements referencing the data table; and

evaluating the candidate partition based in part on the workload of query statements to determine a cost of using the candidate partition.

13. The method of claim 12, further comprising:

determining a best candidate partition for at least one data table and a corresponding cost at least partially based on the best candidate partition.

14. The method of claim 13, further comprising:

combining the candidate partition with at least one other candidate partition; and

evaluating a combination of candidate partitions to determine a cost of using the combination.

15. The method of claim 12, wherein the candidate partition is recommended by:

computing a list of candidate partitions for each base table of a database that can reduce a cost of processing at least one query statement.

16. The method of claim 15, further comprising:

reducing the number of candidate partitions for each base table without losing plan quality.

17. The method of claim 12, wherein the candidate partition is evaluated by:

replacing original partitions in a workload of query statements with candidate partitions.

18. The method of claim 17, further comprising:

evaluating the workload of query statements with candidate partitions in place of the original partitions.

19. The method of claim 12, wherein the candidate partition is recommended at least partially based on a predetermined cost model and the candidate partition is evaluated at least partially based on the predetermined cost model.

20. A system for automating data partitioning in a parallel database, comprising:

plural nodes connected in parallel, each node including;

at least one database server;

at least one database connected to the database server;

at least one query optimizer within the database server; and

at least one partitioning advisor in communication with the database server and the query optimizer, at least one of the query optimizer and the partitioning advisor including a program for recommending and evaluating data table partitions useful for processing a workload of query statements before a data repartition is implemented.

21. The system of claim 20, wherein the program comprises:

logic means for recommending at least one candidate partition for at least one data table; and

logic means for evaluating the candidate partition to determine its cost for a query before the candidate partition is implemented.

22. The system of claim 21, wherein the computer program, further comprises:

logic means for determining a best candidate partition for at least one data table and a corresponding cost for the workload of query statements at least partially based on the best candidate partition.

23. The system of claim 22, wherein the computer program further comprises:

logic means for combining the candidate partition with at least one other candidate partition; and

logic means for evaluating a combination of candidate partitions to determine a cost of using the combination.

24. The system of claim 21, wherein the candidate partition is recommended by:

logic means for computing a list of candidate partitions for each base table of a database.

25. The system of claim 24, wherein the computer program further comprises:

logic means for reducing the number of candidate partitions for each base table without losing plan quality.

26. The system of claim 24, wherein the computer program further comprises:

logic means for returning a best overall query processing plan at least partially based on the candidate partitions.

27. The system of claim 24, wherein the computer program further comprises:

logic means for recording a best partition for at least one table in the overall query processing plan.

28. The system of claim 21, wherein the candidate partition is evaluated by:

logic means for replacing original partitions in a workload of query statements with candidate partitions.

29. The system of claim 28, wherein the computer program further comprises:

logic means for evaluating the workload of query statements with candidate partitions in place of the original partitions.

30. The system of claim 21, wherein the candidate partition is recommended at least partially based on a predetermined cost model and the candidate partition is evaluated at least partially based on the predetermined cost model.

31. A computer program device for automatically determining the best data partitioning for a given workload in a parallel database, comprising:

logic means for evaluating a candidate partition based in part on a workload of query statements to determine a cost of the workload of query statements using the candidate partition without first requiring the data table to be repartitioned.