Structure of hierarchical compressed data structure for tabular data

• US 8,935,223 B2
• Filed: 11/12/2009
• Issued: 01/13/2015
• Est. Priority Date: 04/30/2009
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ganesh, Amit, Kapoor, Vikram, Marwah, Vineet, Shergill, Kam, MacNicol, Roger, Kulkarni, Sachin, Kamp, Jesse
• Primary Examiner(s): Kim, Jung
• Assistant Examiner(s): Wilcox, James J
• Application Number:
  US12/617,669
• Publication Number:
  US 20100278446A1
• Time in Patent Office: 1,888 Days
• Field of Search: None
• US Class Current: 707/693
• 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, referred to as a compression unit, may be used to 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 is stored in row-major or column major-format, 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 to populate a database table;

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

storing to a non-volatile storage, data for a first set of rows, of said plurality of rows, in a first compression unit, wherein the first set of rows is organized within the first compression unit in row-major format;

wherein the first set of rows includes a first row, a second row, and a third row;

wherein, within the particular row order, the first row precedes the second row, and the second row precedes the third row;

wherein the row-major format organization is such that

the entirety of the first row precedes the entirety of the second row,

the entirety of the second row precedes the entirety of the third row, and

within each of the first, second and third rows, each column is stored in the non-volatile storage according to the particular column order;

storing to the non-volatile storage, data for a second set of rows, of said plurality of rows, in a second compression unit, wherein the second set of rows is organized within the second compression unit in column-major format;

wherein the second set of rows include a fourth row, a fifth row, and a sixth row;

wherein the column-major format is such that

values for a first column of the fourth, fifth and sixth rows precede values for a second column of the fourth, fifth and sixth rows; and

values for the second column of the fourth, fifth and sixth rows precede values for a third column of the fourth, fifth and sixth rows; and

for each of the first, second and third columns, values for the column are stored in the non-volatile storage according to the particular row order;

wherein the first compression unit and the second compression unit are structures on the non-volatile storage for organizing the tabular data;

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:

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.

3. A method comprising:

receiving a set of tabular data to populate a database table;

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 to a non-volatile storage, data for said particular set of columns in a first compression unit;

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

wherein the first compression unit includes a first set of columns of the particular set of columns and a second set of different columns of the particular set of columns; and

wherein the first set of columns is stored in a first child compression unit of the plurality of child compression units; and

wherein the second set of different columns is stored in a second child compression unit of the plurality of child compression units;

wherein the first child compression unit does not store any column of the second set of different columns and the second child compression unit does not store any column of the first set of columns;

wherein the first child compression unit is different than the second child compression unit;

storing metadata indicating that the first compression unit has children;

wherein the first compression unit and each child compression unit of the plurality of child compression units are structures on the non-volatile storage for organizing the tabular data; and

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

4. The method of claim 3 wherein:

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

the second child 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.

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

6. The method of claim 3, wherein the metadata indicating that the first compression unit has children is stored within the first compression unit.

10. The method of claim 5 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.

7. A method comprising:

receiving a set of tabular data for populating a database table;

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 to a non-volatile storage, 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, wherein the parent compression unit stores a first set of rows of the plurality of rows and a second set of different rows of the plurality of rows, and the first set of rows is stored in a first child compression unit of the plurality of child compression units and the second set of rows is stored in a second child compression unit of the plurality of child compression units, wherein the first child compression unit does not store any row of the second set of different rows and the second child compression unit does not store any row of the first set of rows, wherein the first child compression unit is different than the second child compression unit;

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 the parent compression unit stores a first set of columns of the plurality of columns and a second set of different columns of the plurality of columns, and the first set of columns is stored in a third child compression unit of the plurality of child compression units and the second set of different columns is stored in a fourth child compression unit of the plurality of child compression units, wherein the third child compression unit does not store any column of the second set of different columns and the fourth child compression unit does not store any column of the first set of columns, wherein the third child compression unit is different than the fourth child compression unit;

storing metadata indicating whether or not each compression unit of the parent compression unit and the plurality of child compression units has children;

wherein the parent compression unit and each child compression unit of the plurality of child compression units are structures on the non-volatile storage for organizing the tabular data; and

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

8. The method of claim 7 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.

9. The method of claim 7 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.

11. The method of claim 7 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.

12. The method of claim 11 wherein:

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.

13. The method of claim 12 wherein:

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.

14. The method of claim 7 wherein:

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.

15. The method of claim 7 wherein:

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.

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

17. The method of claim 7 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 7 wherein the parent compression unit includes a flag that indicates that the parent compression unit is not a bottom-level compression unit.

20. The method of claim 7 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.

21. The method of claim 7, wherein each compression unit of the parent compression unit and the child compression units stores a flag that indicates whether the compression unit has children.

22. A method comprising:

storing to a non-volatile storage, 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 to the non-volatile storage metadata that indicates the row is deleted without deleting the data for the row from the compression unit;

in response to a request to perform an operation while the data for the row is still in the compression unit, determining that the metadata indicates that the row is deleted and performing the operation as though the row were deleted;

in response to a determination that the number of deleted rows of the compression unit exceeds a threshold, repackaging data from the compression unit into one or more new compression units;

wherein the compression unit and each of the one or more new compression units are data structures on the non-volatile storage for organizing the data that logically belongs to the row of the table;

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

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

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

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

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

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

receiving a set of tabular data to populate a database table;

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

storing to a non-volatile storage, data for a first set of rows, of said plurality of rows, in a first compression unit, wherein the first set of rows is organized within the first compression unit in row-major format;

wherein the first set of rows includes a first row, a second row, and a third row;

wherein, within the particular row order, the first row precedes the second row, and the second row precedes the third row;

wherein the row-major format organization is such that

the entirety of the first row precedes the entirety of the second row,

the entirety of the second row precedes the entirety of the third row, and

within each of the first, second and third rows, each column is stored in the non-volatile storage according to the particular column order;

storing to the non-volatile storage, data for a second set of rows, of said plurality of rows, in a second compression unit, wherein the second set of rows is organized within the second compression unit in column-major format;

wherein the second set of rows include a fourth row, a fifth row, and a sixth row;

wherein the column-major format is such that

values for a first column of the fourth, fifth and sixth rows precede values for a second column of the fourth, fifth and sixth rows; and

values for the second column of the fourth, fifth and sixth rows precede values for a third column of the fourth, fifth and sixth rows; and

for each of the first, second and third columns, values for the column are stored in the non-volatile storage according to the particular row order;

wherein the first compression unit and the second compression unit are structures on the non-volatile storage for organizing the tabular data;

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.

28. The non-transitory computer-readable storage medium of claim 27 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.

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

receiving a set of tabular data to populate a database table;

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 to a non-volatile storage, data for said particular set of columns in a first compression unit;

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

wherein the first compression unit includes a first set of columns of the particular set of columns and a second set of different columns of the particular set of columns and the first set of columns is stored in a first child compression unit of the plurality of child compression units and the second set of different columns is stored in a second child compression unit of the plurality of child compression units;

wherein the first child compression unit does not store any column of the second set of different columns and the second child compression unit does not store any column of the first set of columns;

wherein the first child compression unit is different than the second child compression unit;

storing metadata indicating that the first compression unit has children;

wherein the first compression unit and each child compression unit of the plurality of child compression units are structures on the non-volatile storage for organizing the tabular data.

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

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

the second child 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.

31. The non-transitory computer-readable storage medium of claim 29 wherein the plurality of child compression units includes a child compression unit that contains a second plurality of child compression units.

32. The non-transitory computer-readable storage medium of claim 29, wherein the metadata indicating that the first compression unit has children is stored within the first compression unit.

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

receiving a set of tabular data for populating a database table;

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 to a non-volatile storage, 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, wherein the parent compression unit stores a first set of rows of the plurality of rows and a second set of different rows of the plurality of rows, and the first set of rows is stored in a first child compression unit of the plurality of child compression units and the second set of rows is stored in a second child compression unit of the plurality of child compression units, wherein the first child compression unit does not store any row of the second set of different rows and the second child compression unit does not store any row of the first set of rows, wherein the first child compression unit is different than the second child compression unit;

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 the parent compression unit stores a first set of columns of the plurality of columns and a second set of different columns of the plurality of columns, and the first set of columns is stored in a third child compression unit of the plurality of child compression units and the second set of different columns is stored in a fourth child compression unit of the plurality of child compression units, wherein the third child compression unit does not store any column of the second set of different columns and the fourth child compression unit does not store any column of the first set of columns, wherein the third child compression unit is different than the fourth child compression unit;

storing metadata indicating whether or not each compression unit of the parent compression unit and the plurality of child compression units has children;

wherein the parent compression unit and each child compression unit of the plurality of child compression units are structures on the non-volatile storage for organizing the tabular data.

34. The non-transitory computer-readable storage medium of claim 33 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.

35. The non-transitory computer-readable storage medium of claim 33 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.

36. The non-transitory computer-readable storage medium of claim 35 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.

37. The non-transitory computer-readable storage medium of claim 33 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.

38. The non-transitory computer-readable storage medium of claim 37 wherein:

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.

39. The non-transitory computer-readable storage medium storage of claim 38 wherein:

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.

40. The non-transitory computer-readable storage medium of claim 33 wherein:

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.

41. The non-transitory computer-readable storage medium of claim 33 wherein:

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.

42. The non-transitory computer-readable storage medium of claim 41 wherein the compressed section includes pointers to where each child compression unit will begin after the compressed section is decompressed.

43. The non-transitory computer-readable storage medium claim 33 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.

44. The non-transitory computer-readable storage medium claim 43 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.

45. The non-transitory computer-readable storage medium of claim 33 wherein the parent compression unit includes a flag that indicates that the parent compression unit is not a bottom-level compression unit.

46. The non-transitory computer-readable storage medium of claim 33 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.

47. The non-transitory computer-readable medium of claim 33, wherein each compression unit of the parent compression unit and the child compression units stores a flag that indicates whether the compression unit has children.

52. The non-transitory computer-readable storage medium of claim 42 wherein the delete vector is stored within an uncompressed section of the compression unit.

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

storing to a non-volatile storage, 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 to the non-volatile storage metadata that indicates the row is deleted without deleting the data for the row from the compression unit;

in response to a request to perform an operation while the data for the row is still in the compression unit, determining that the metadata indicates that the row is deleted and performing the operation as though the row were deleted;

in response to a determination that the number of deleted rows of the compression unit exceeds a threshold, repackaging data from the compression unit into one or more new compression units;

wherein the compression unit and each of the one or more new compression units are data structures on the non-volatile storage for organizing the data that logically belongs to the row of the table.

49. The non-transitory computer-readable storage medium of claim 48 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.

50. The non-transitory computer-readable storage medium of claim 49 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.

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