STRUCTURE OF HIERARCHICAL COMPRESSED DATA STRUCTURE FOR TABULAR DATA

• US 20100278446A1
• Filed: 11/12/2009
• Published: 11/04/2010
• Est. Priority Date: 04/30/2009
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Kamp, Jesse, Shergill, Kam, Kulkarni, Sachin, MacNicol, Roger, Marwah, Vineet, Ganesh, Amit, Kapoor, Vikram
• Granted Patent: US 8,935,223 B2
• Time in Patent Office: Days
• US Class Current: 382/243
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof

Abstract

A highly flexible and extensible structure is provided for physically storing tabular data. The structure, is referred to as a compression unit, and may be used to physically store tabular data that logically resides in any type of table-like structure. According to one embodiment, compression units are recursive. Thus, a compression unit may have a “parent” compression unit to which it belongs, and may have one or more “child” compression units that belong to it. In one embodiment, compression units include metadata that indicates how the tabular data is stored within them. The metadata for a compression unit may indicate, for example, whether the data within the compression unit is stored in row-major or column major-format (or some combination thereof), the order of the columns within the compression unit (which may differ from the logical order of the columns dictated by the definition of their logical container), a compression technique for the compression unit, the child compression units (if any), etc.

Claims

1. A method comprising:

receiving a set of tabular data;

wherein the set of tabular data is divided into a plurality of rows, each of which includes data for a particular set of columns;

storing data for a first set of rows, of said plurality of rows, in a first compression unit;

storing data for a second set of rows, of said plurality of rows, in a second compression unit;

storing data that indicates whether, within said first compression unit, data for said first set of rows is stored in column-major format or in row-major format;

wherein the steps of receiving and storing are performed by one or more computing devices.

2. The method of claim 1 wherein:

within said first compression unit, data for said first set of rows is stored in column-major format; and

within said second compression unit, data for said second set of rows is stored in column-major format.

3. The method of claim 1 wherein:

within said first compression unit, data for said first set of rows is stored in column-major format; and

within said second compression unit, data for said second set of rows is stored in row-major format.

4. The method of claim 1 wherein:

within said first compression unit, data for said first set of rows is stored in row-major format; and

within said second compression unit, data for said second set of rows is stored in row-major format.

5. The method of claim 1 wherein:

the first compression unit has a first compressed section in which data is compressed using a first compression technique; and

the second compression unit has a second compressed section in which data is compressed using a second compression technique that is different from the first compression technique.

6. A method comprising:

receiving a set of tabular data;

wherein the set of tabular data is divided into a plurality of rows, each of which includes data for a particular set of columns;

storing data for said plurality of rows in a first compression unit;

wherein the first compression unit includes a plurality of child compression units, each of which stores data for one or more columns of the particular set of columns; and

wherein steps of receiving and storing are performed by one or more computing devices.

7. The method of claim 6 wherein the plurality of child compression units includes:

a first child compression unit that has a first compressed section in which data is compressed using a first compression technique; and

a second child compression unit that has a second compressed section in which data is compressed using a second compression technique that is different from the first compression technique.

8. The method of claim 6 wherein the plurality of child compression units includes a child compression unit that contains a second plurality of child compression units.

9. A method comprising:

receiving a set of tabular data;

wherein the set of tabular data is divided into a plurality of rows, each of which includes data for a particular set of columns;

storing data for said plurality of rows in a parent compression unit that includes a plurality of child compression units;

wherein the step of storing data in the parent compression unit includes either;

(a) dividing the data between the child compression units based on rows, whereby each child compression unit stores a different set of rows of the plurality of rows;

or

(b) dividing the data between the child compression units based on columns, whereby each child compression unit stores a different set of columns of the particular set of columns;

wherein steps of receiving and storing are performed by one or more computing devices.

10. The method of claim 9 wherein the step of storing data in the parent compression unit includes dividing the data between the child compression units based on rows, whereby each child compression unit stores a different set of rows of the plurality of rows.

11. The method of claim 9 wherein the step of storing data in the parent compression unit includes dividing the data between the child compression units based on columns, whereby each child compression unit stores a different set of columns of the particular set of columns.

12. The method of claim 9 wherein:

the parent compression unit includes a compressed section and an uncompressed section;

the plurality of child compression units are stored in the compressed section of the parent compression unit; and

data within the compressed section of the parent compression unit is compressed using a first compression technique.

13. The method of claim 12 wherein:

the plurality of child compression units includes a first child compression unit;

the first child compression unit includes a compressed section; and

data within the compressed section of the first child compression unit is compressed using a second compression technique that is different from said first compression technique.

14. The method of claim 13 wherein:

the plurality of child compression units includes a second child compression unit;

the second child compression unit includes a compressed section; and

data within the compressed section of the second child compression unit is compressed using a third compression technique that is different from said first compression technique and said second compression technique.

15. The method of claim 9 wherein:

the plurality of child compression units includes a first child compression unit and a second child compression unit;

the first child compression unit includes a compressed section; and

data within the compressed section of the first child compression unit is compressed using a first compression technique;

the second child compression unit includes a compressed section; and

data within the compressed section of the second child compression unit is compressed using a second compression technique that is different from said first compression technique.

16. The method of claim 9 wherein:

the plurality of child compression units includes a first child compression unit and a second child compression unit;

data within the first child compression unit is stored in row-major format; and

data within the second child compression unit is stored in column-major format.

17. The method of claim 9 wherein:

the parent compression unit includes an uncompressed section and a compressed section;

the uncompressed section includes metadata that indicates a compression technique that was used to compress data in the compressed section; and

the plurality of child compression units are in the compressed section.

18. The method of claim 17 wherein the compressed section includes a map that indicates either (a) how many columns are in each child compression unit, or (b) how many rows are in each child compression unit.

19. The method of claim 16 wherein the compressed section includes pointers to where each child compression unit will begin after the compressed section is decompressed.

20. The method of claim 9 wherein the parent compression unit includes a flag that indicates that the parent compression unit is not a bottom-level compression unit.

21. The method of claim 9 wherein:

columns are organized in the parent compression unit in a parent column order, and

at least one of the plurality of child compression units includes a flag that indicates whether columns in the child compression unit are organized in the same order as the parent column order.

22. The method of claim 11 wherein:

the set of tabular data is tabular data for a table;

within the table, the particular set of columns has a first particular order;

within the parent compression unit, data for the set of columns is stored in a second particular order that is different than said first particular order; and

the parent compression unit includes metadata identifying the second particular order.

23. A method comprising:

storing, within a compression unit, data that logically belongs to a row of a table;

wherein at least a portion of the data is compressed; and

in response to a request to delete the row from the table, storing data that indicates the row is deleted without deleting the data for the row from the compression unit;

wherein the method is performed by one or more computing devices.

24. The method of claim 23 further comprising repackaging data from the compression unit into one or more new compression units in response to the number of deleted rows of the compression unit exceeding a threshold.

25. The method of claim 23 further comprising, in response to a request to store data in the table, storing the data in an overflow area external to the compression unit.

26. The method of claim 25 further comprising repackaging data from the overflow area into one or more compression units in response to the amount of data in the overflow area exceeding a threshold.

27. The method of claim 23 wherein the step of storing data that indicates the row is deleted includes changing a bit, within a delete vector, that corresponds to the row.

28. The method of claim 27 wherein the delete vector is stored within an uncompressed section of the compression unit.

29. A computer-readable storage storing instructions which, when executed by one or more processors, cause performance of:

receiving a set of tabular data;

wherein the set of tabular data is divided into a plurality of rows, each of which includes data for a particular set of columns;

storing data for a first set of rows, of said plurality of rows, in a first compression unit;

storing data for a second set of rows, of said plurality of rows, in a second compression unit; and

storing data that indicates whether, within said first compression unit, data for said first set of rows is stored in column-major format or in row-major format.

30. The computer-readable storage of claim 29 wherein:

within said first compression unit, data for said first set of rows is stored in column-major format; and

within said second compression unit, data for said second set of rows is stored in column-major format.

31. The computer-readable storage of claim 29 wherein:

within said first compression unit, data for said first set of rows is stored in column-major format; and

within said second compression unit, data for said second set of rows is stored in row-major format.

32. The computer-readable storage of claim 29 wherein:

within said first compression unit, data for said first set of rows is stored in row-major format; and

within said second compression unit, data for said second set of rows is stored in row-major format.

33. The computer-readable storage of claim 29 wherein:

the first compression unit has a first compressed section in which data is compressed using a first compression technique; and

the second compression unit has a second compressed section in which data is compressed using a second compression technique that is different from the first compression technique.

34. A computer-readable storage storing instructions which, when executed by one or more processors, cause performance of:

receiving a set of tabular data;

wherein the set of tabular data is divided into a plurality of rows, each of which includes data for a particular set of columns;

storing data for said plurality of rows in a first compression unit;

wherein the first compression unit includes a plurality of child compression units, each of which stores data for one or more columns of the particular set of columns.

35. The computer-readable storage of claim 34 wherein the plurality of child compression units includes:

a first child compression unit that has a first compressed section in which data is compressed using a first compression technique; and

a second child compression unit that has a second compressed section in which data is compressed using a second compression technique that is different from the first compression technique.

36. The computer-readable storage of claim 34 wherein the plurality of child compression units includes a child compression unit that contains a second plurality of child compression units.

37. A computer-readable storage storing instructions which, when executed by one or more processors, cause performance of:

receiving a set of tabular data;

wherein the set of tabular data is divided into a plurality of rows, each of which includes data for a particular set of columns;

storing data for said plurality of rows in a parent compression unit that includes a plurality of child compression units;

wherein the step of storing data in the parent compression unit includes either;

(a) dividing the data between the child compression units based on rows, whereby each child compression unit stores a different set of rows of the plurality of rows;

or

(b) dividing the data between the child compression units based on columns, whereby each child compression unit stores a different set of columns of the particular set of columns.

38. The computer-readable storage of claim 37 wherein the step of storing data in the parent compression unit includes dividing the data between the child compression units based on rows, whereby each child compression unit stores a different set of rows of the plurality of rows.

39. The computer-readable storage of claim 37 wherein the step of storing data in the parent compression unit includes dividing the data between the child compression units based on columns, whereby each child compression unit stores a different set of columns of the particular set of columns.

40. The computer-readable storage of claim 37 wherein:

the parent compression unit includes a compressed section and an uncompressed section;

the plurality of child compression units are stored in the compressed section of the parent compression unit; and

data within the compressed section of the compression unit is compressed using a first compression technique.

41. The computer-readable storage of claim 40 wherein:

the plurality of child compression units includes a first child compression unit;

the first child compression unit includes a compressed section; and

data within the compressed section of the first child compression unit is compressed using a second compression technique that is different from said first compression technique.

42. The computer-readable storage of claim 41 wherein:

the plurality of child compression units includes a second child compression unit;

the second child compression unit includes a compressed section; and

data within the compressed section of the second child compression unit is compressed using a third compression technique that is different from said first compression technique and said second compression technique.

43. The computer-readable storage of claim 37 wherein:

the plurality of child compression units includes a first child compression unit and a second child compression unit;

the first child compression unit includes a compressed section; and

data within the compressed section of the first child compression unit is compressed using a first compression technique;

the second child compression unit includes a compressed section; and

data within the compressed section of the second child compression unit is compressed using a second compression technique that is different from said first compression technique.

44. The computer-readable storage of claim 37 wherein:

the plurality of child compression units includes a first child compression unit and a second child compression unit;

data within the first child compression unit is stored in row-major format; and

data within the second child compression unit is stored in column-major format.

45. The computer-readable storage of claim 37 wherein:

the parent compression unit includes an uncompressed section and a compressed section;

the uncompressed section includes metadata that indicates a compression technique that was used to compress data in the compressed section; and

the plurality of child compression units are in the compressed section.

46. The computer-readable storage of claim 45 wherein the compressed section includes a map that indicates either (a) how many columns are in each child compression unit, or (b) how many rows are in each child compression unit.

47. The computer-readable storage of claim 44 wherein the compressed section includes pointers to where each child compression unit will begin after the compressed section is decompressed.

48. The computer-readable storage of claim 37 wherein the parent compression unit includes a flag that indicates that the parent compression unit is not a bottom-level compression unit.

49. The computer-readable storage of claim 37 wherein:

columns are organized in the parent compression unit in a parent column order, and

at least one of the plurality of child compression units includes a flag that indicates whether columns in the child compression unit are organized in the same order as the parent column order.

50. The computer-readable storage of claim 39 wherein:

the set of tabular data is tabular data for a table;

within the table, the particular set of columns has a first particular order;

within the parent compression unit, data for the set of columns is stored in a second particular order that is different than said first particular order; and

the parent compression unit includes metadata identifying the second particular order.

51. A computer-readable storage storing instructions which, when executed by one or more processors, cause performance of:

storing, within a compression unit, data that logically belongs to a row of a table;

wherein at least a portion of the data is compressed; and

in response to a request to delete the row from the table, storing data that indicates the row is deleted without deleting the data for the row from the compression unit.

52. The computer-readable storage of claim 51 further comprising instructions for repackaging data from the compression unit into one or more new compression units in response to the number of deleted rows of the compression unit exceeding a threshold.

53. The computer-readable storage of claim 51 further comprising instructions for, in response to a request to store data in the table, storing the data in an overflow area external to the compression unit.

54. The computer-readable storage of claim 53 further comprising instructions for repackaging data from the overflow area into one or more compression units in response to the amount of data in the overflow area exceeding a threshold.

55. The computer-readable storage of claim 51 wherein the step of storing data that indicates the row is deleted includes changing a bit, within a delete vector, that corresponds to the row.

56. The computer-readable storage of claim 55 wherein the delete vector is stored within an uncompressed section of the compression unit.