Multidimensional data clustering scheme for query processing and maintenance in relational databases

• US 7,080,081 B2
• Filed: 04/15/2002
• Issued: 07/18/2006
• Est. Priority Date: 04/15/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cranston, Leslie A., Agarwal, Ramesh C., Bhattacharjee, Bishwaranjan, Padmanabhan, Sriram K., Malkemus, Timothy R., Huras, Matthew A., Lai, Tony Wen Hsun
• Primary Examiner(s): Wong, Don
• Assistant Examiner(s): DANG, THANH HA T
• Application Number:
  US10/122,502
• Publication Number:
  US 20030195898A1
• Time in Patent Office: 1,555 Days
• Field of Search: 707/3, 707/101, 707/103, 707/100
• US Class Current: 707/600
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/957 Multidimensional

Abstract

Multidimensional clustered tables are provided for efficient processing and management in a relational database management system. A multidimensional clustered table is one whose data is simultaneously clustered along one or more independent dimensions, or clustering keys, and physically organized into blocks or pages on disk. When such a table is created, one can specify one or more keys as dimensions along which to cluster the table'"'"'s data. Each of the dimensions can consist of one or more columns. Further provided are efficient query processing and maintenance techniques for use in conjunction with multidimensional clustered tables.

Claims

1. A computer executable method for efficiently maintaining clustered data in a relational database, comprising the steps of:

identifying at least one dimension of a table of the relational database using at least one table definition parameter;

clustering data for each of the at least one dimension using at least one block;

creating at least one block index, each of the at least one block index being associated with one of the at least one dimension, wherein each of the at least one block index comprises at least one key that is associated with a list of at least one block identifier, and

creating a block map for the table, each element of the block map having state information for one of the at least one block, wherein each of the one or more block contains duplicate state information, and wherein the block map is created using the duplicate state information contained in the one or more block.

2. The method of claim 1, wherein each of the at least one block comprises contiguous storage space.

3. The method of claim 1, wherein each of the at least one dimension is associated with at least one column of the table.

4. The method of claim 1, wherein the at least one table definition parameter is associated with a Create Table or an Alter Table statement.

5. The method of claim 1, wherein the table is a multidimensional table.

6. The method of claim 5, wherein the multidimensional table is used to store application information.

7. The method of claim 6, wherein the application information is for a data warehouse.

8. The method of claim 5, further comprising the step of creating a composite dimension index for the multidimensional table.

9. The method of claim 8, wherein the step of creating a composite dimension index is automatically performed.

10. The method of claim 8, wherein the composite dimension index comprises a list of composite keys, each composite key being associated with a cell of the multidimensional table and having a list of at least one block identifier for the cell.

11. The method of claim 1, further including the step of processing a query for information stored in the table.

12. The method of claim 11, wherein the step of processing the query comprises:

using information from one of the at least one block index and the composite dimension index to obtain a list of block identifiers; and

scanning at least one block for records that satisfy at least one criterion using the list of block identifiers to locate the at least one block to be scanned.

13. The method of claim 11, wherein the step of processing the query comprises at least one of:

scanning the entire table for records that satisfy at least one criterion; and

using a record-based index to find records that satisfy at least one criterion.

14. The method of claim 11, wherein the step of processing the query comprises index ANDing.

15. The method of claim 11, wherein the step of processing the query comprises index ORing.

16. The method of claim 11, wherein the step of processing the query comprises developing a query plan based on a cost model and processing the query according to the query plan.

17. The method of claim 1, further comprising the step of processing a maintenance request.

18. The method of claim 17, wherein the maintenance request comprises a request for one of a load, a reorganization, an insert, a delete, a purge, and an update.

19. The method of claim 18, wherein the step of processing a maintenance request for a load or an insert comprises one of:

using one of the at least one block if there is free space; and

allocating a new block to the table if there is no free space.

20. The method of claim 17, wherein clustering of the table is maintained after the maintenance request is processed.

21. The method of claim 17, wherein the step of processing a maintenance request for a reorganization, a delete, or a purge comprises the step of reclaiming space.

22. A program storage device readable by a machine, tangibly embodying a program of instructions executable on the machine to perform method steps for efficiently maintaining clustered data in a relational database, the method steps comprising:

identifying at least one dimension of a table of the relational database using at least one table definition parameter;

clustering data for each of the at least one dimension using at least one block;

creating at least one block index, each of the at least one block index being associated with one of the at least one dimension, wherein each of the at least one block index comprises at least one key that is associated with a list of at least one block identifier; and

creating a block map for the table, each element of the block map having state information for one of the at least one block, wherein each of the one or more block contains duplicate state information, and wherein the block map is created using the duplicate state information contained in the one or more block.

23. The program storage device of claim 22, wherein each of the at least one block comprises contiguous storage space.

24. The program storage device of claim 22, wherein each of the at least one dimension is associated with at least one column of the table.

25. The program storage device of claim 22, wherein the at least one table definition parameter is associated with a Create Table or an Alter Table statement.

26. The program storage device of claim 22, wherein the table is a multidimensional table.

27. The program storage device of claim 26, wherein the multidimensional table is used to store application information.

28. The program storage device of claim 27, wherein the application information is for a data warehouse.

29. The program storage device of claim 26, further comprising the step of creating a composite dimension index for the multidimensional table.

30. The program storage device of claim 29, wherein the step of creating a composite dimension index is automatically performed.

31. The program storage device of claim 29, wherein the composite dimension index comprises a list of composite keys, each composite key being associated with a cell of the multidimensional table and having a list of at least one block identifier for the cell.

32. The program storage device of claim 22, further including the step of processing a query for information stored in the table.

33. The program storage device of claim 32, wherein the step of processing the query comprises:

using information from one of the at least one block index and the composite dimension index to obtain a list of block identifiers; and

scanning at least one block for records that satisfy at least one criterion using the list of block identifiers to locate the at least one block to be scanned.

34. The program storage device of claim 32, wherein the step of processing the query comprises at least one of:

scanning the entire table for records that satisfy at least one criterion; and

using a record-based index to find records that satisfy at least one criterion.

35. The program storage device of claim 32, wherein the step of processing the query comprises index ANDing.

36. The program storage device of claim 32, wherein the step of processing the query comprises index ORing.

37. The program storage device of claim 32, wherein the step of processing the query comprises developing a query plan based on a cost model and processing the query according to the query plan.

38. The program storage device of claim 22, further comprising the step of processing a maintenance request.

39. The program storage device of claim 38, wherein the maintenance request comprises a request for one of a load, a reorganization, an insert, a delete, a purge, and an update.

40. The program storage device of claim 39, wherein the step of processing a maintenance request for a load or an insert comprises one of:

using one of the at least one block if there is free space; and

allocating a new block to the table if there is no free space.

41. The program storage device of claim 38, wherein clustering of the table is maintained after the maintenance request is processed.

42. The program storage device of claim 38, wherein the step of processing a maintenance request for a reorganization, a delete, or a purge comprises the step of reclaiming space.