Storing compression units in relational tables

• US 8,645,337 B2
• Filed: 04/28/2010
• Issued: 02/04/2014
• Est. Priority Date: 04/30/2009
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Kapoor, Vikram, Ganesh, Amit, Kamp, Jesse, Kulkarni, Sachin, Marwah, Vineet, Shergill, Kam, Macnicol, Roger, Bhattacharyya, Manosiz
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Ahluwalia, Navneet K
• Application Number:
  US12/769,205
• Publication Number:
  US 20100281004A1
• Time in Patent Office: 1,378 Days
• Field of Search: 707690-695, 707/752
• US Class Current: 707/693
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers

Abstract

A database server stores compressed units in data blocks of a database. A table (or data from a plurality of rows thereof) is first compressed into a “compression unit” using any of a wide variety of compression techniques. The compression unit is then stored in one or more data block rows across one or more data blocks. As a result, a single data block row may comprise compressed data for a plurality of table rows, as encoded within the compression unit. Storage of compression units in data blocks maintains compatibility with existing data block-based databases, thus allowing the use of compression units in preexisting databases without modification to the underlying format of the database. The compression units may, for example, co-exist with uncompressed tables. Various techniques allow a database server to optimize access to data in the compression unit, so that the compression is virtually transparent to the user.

Claims

1. A method comprising:

storing data for database tables in a storage device, the storage device comprising a memory organized into data blocks conforming to a data block format, the data block format including data block metadata and one or more data block rows;

storing uncompressed data for a first plurality of the database tables in a first set of the data blocks, each data block of the first set of the data blocks comprising a plurality of data block rows, each data block row of the plurality of data block rows storing data from only one table row from the first plurality of the database tables;

for a particular table that is not in the first plurality of the database tables, generating compressed data by compressing data from multiple table rows in the particular table, wherein said compressing comprises generating the compressed data and structuring the compressed data in a compression unit that does not conforms to the data block format;

storing the compression unit in one or more data block rows of a second set of one or more of the data blocks, said storing comprising storing at least a portion of the compression unit in a particular data block row of a particular data block of the data blocks;

wherein the portion of the compression unit comprises compressed data from a plurality of the table rows from the particular table, wherein the particular data block row thus comprises compressed data from the plurality of the table rows;

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

2. The method of claim 1, wherein the particular data block comprises a header and one or more data block rows, the one or more data block rows including the particular data block row that stores the compression unit, wherein the particular data block row comprises a row header and a column field, wherein the column field comprises said portion of the compression unit.

3. The method of claim 1, further comprising:

determining that execution of a request requires access to first data in said particular table;

retrieving, from the particular data block row, the portion of the compression unit;

decompressing the portion of the compression unit, thereby yielding an decompressed portion of the compression unit;

locating the first data in the decompressed portion of the compression unit;

executing the request, based at least partially on one or more items from the first data.

4. The method of claim 3, further comprising storing the decompressed portion in a re-usable buffer.

5. The method of claim 1, wherein the data that is compressed is a subset of the particular table, said subset including first data from a first set of one or more columns of the particular table, but not including second data from a second set of one or more columns of the particular table.

6. The method of claim 1, wherein:

the portion of the compression unit is a first portion of the compression unit;

the method further comprises;

storing a second portion of the compression unit in a second data block row of a second data block.

7. The method of claim 6, further comprising:

determining that execution of a request requires access to first data in the particular table;

retrieving, from data block rows in each of a set of data blocks, a set of portions of the compression unit;

wherein the set of data blocks includes the particular data block and the second data block;

wherein the set of portions includes the first portion and the second portion,

decompressing the set of portions, thereby yielding a decompressed set of portions;

locating the first data in the decompressed set of portions;

executing the request, based at least partially on one or more items from the first data.

8. The method of claim 1, further comprising storing compression unit metadata describing properties of the compression unit.

9. The method of claim 8, wherein the compression unit metadata is stored within the particular data block in a field of the particular data block row that precedes the portion of the compression unit.

10. The method of claim 8, further comprising determining how to retrieve the data stored into the compression unit based at least in part on the compression unit metadata.

11. The method of claim 8, wherein the compression unit metadata includes metadata indicating a data block address for each portion of the compression unit.

12. The method of claim 1, further comprising storing first metadata indicating that the particular data block consists of compressed data, wherein the database further stores second metadata indicating that one or more other data blocks consist of non-compressed data.

13. The method of claim 1, further comprising:

storing second data from table rows in a second table into a second compression unit;

storing at least a portion of the second compression unit in a different data block row of the particular data block in the database;

wherein the portion of the second compression unit comprises compressed data from a plurality of table rows from the second table.

14. The method of claim 1, wherein the plurality of the table rows is compressed inside of the compression unit, the method further comprising:

storing uncompressed data in a different data block row of the particular data block;

storing metadata in the particular data block indicating a) that the particular data block row storing the compression unit stores compressed data; and

b) that the different data block row stores uncompressed data.

15. The method of claim 1, further comprising:

storing metadata indicating, for the portion of the compression unit, a range of values for a particular column, wherein no table row in the portion of the compression unit comprises a value for the particular column that is outside of the range;

receiving a request for data from the particular table, said request including a predicate based upon the particular column;

in response to the request, determining whether to decompress the portion of the compression unit based upon the metadata and the predicate.

27. The method of claim 1, wherein generating the compressed data comprises utilizing non-block-based compression to compress the data from the multiple table rows.

16. A method comprising:

storing data for database tables in a storage device, the storage device comprising memory organized into data blocks conforming to a data block format, the data block format including data block metadata and one or more data block rows;

storing uncompressed data for a first plurality of the database tables in a first plurality of the data blocks, each data block of the first plurality of the data blocks comprising a plurality of data block rows, each data block row of the plurality of data block rows storing data from only one table row from the first plurality of the database tables;

storing, within a second plurality of data blocks of a database, compression units comprising compressed data from tables, the compression units comprising compressed data structured in a format that does not conform to the data block format;

determining that execution of a database request requires access to data from at least one or more table rows;

retrieving one or more data blocks to which the one or more table rows have been mapped;

determining whether the one or more retrieved data blocks store any of the table rows in one or more of the compression units; and

responsive to determining that the one or more retrieved data blocks store data for a particular table row of the one or more table rows in one or more particular compression units of the compression units;

based at least partially on information in the one or more retrieved data blocks, locating at least a portion of the compression unit in a data block row of the one or more retrieved data blocks,

generating a decompressed portion of the compression unit, comprising data from a plurality of table rows, by decompressing the portion of the compression unit from the located data block row;

locating the data for the particular table row in the decompressed portion of the compression unit;

reading one or more items indicated by the database request from the data for the particular table row; and

executing the database request based at least on the one or more items that were read from the data for the particular table row;

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

17. The method of claim 16, further comprising,

responsive to determining that the one or more retrieved data blocks store data from a second table row of the one or more table rows in uncompressed form outside of any of the compression units:

locating within the one or more retrieved data blocks a data block row storing raw data for the second table row;

reading one or more items indicated by the database request from the data block row; and

executing the database request based at least on the one or more items that were read from the data for the second table row.

18. The method of claim 16, wherein the portion of the compression unit comprises the entire compression unit.

19. The method of claim 16, wherein the decompressed portion of the compression unit comprises an entire table.

20. The method of claim 16, wherein the portion of the compression unit is at least partially located in multiple data blocks.

21. The method of claim 16, further comprising:

locating, in an index, an entry associating the particular table row with at least a) an address of a particular data block of the one or more data blocks and b) a row identifier within the particular data block;

wherein the step of retrieving the one or more data blocks comprises locating the particular data block based on the address of the particular data block that was indicated by the index; and

wherein the step of locating the table row in the decompressed portion of the compression unit is based on the row identifier.

22. A method comprising:

storing data for database tables in a storage device, the storage device comprising a. memory organized into data blocks conforming to a data block format, the data block format including data block metadata and one or more data block rows;

compressing a particular database table within a particular compression unit, the compression unit comprising compressed data from the table structured in a format that is different than the data block format;

dividing the particular compression unit into portions;

based on the divided portions, storing the compression unit within a plurality of data blocks of a database, wherein the compression unit spans the plurality of data blocks, each data block of the plurality of data blocks comprising one or more different portions of the divided portions;

receiving a request whose execution requires access to first data from the particular database table;

determining that the database stores the first data in the particular compression unit;

determining that the first data is stored in a first set of one or more portions of the divided portions of the particular compression unit;

retrieving the first set of one or more portions from one or more data blocks of the plurality of data blocks;

decompressing the first set of one or more portions, thereby yielding one or more decompressed portions of the particular compression unit;

locating the first data in the decompressed portion of the particular compression unit;

executing the request based at least partially on one or more items from the first data;

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

23. The method of claim 22, wherein the method is performed without having decompressed a second set of one or more portions of the divided portions of the particular compression unit.

24. The method of claim 22, further comprising retrieving, responsive to the request, only the one or more data blocks that store the first set of one or more portions of the particular compression unit, and not one or more other data blocks that store the second set of one or more portions of the particular compression unit.

25. The method of claim 24, further comprising identifying the first set of one or more portions of the compression unit, based at least partially on portion mapping data stored immediately preceding a particular portion of the compression unit within a first data block of said plurality of data blocks, said portion mapping data indicating, for each portion of the divided portions, a block at which the portion is located.

26. The method of claim 23, further comprising identifying the first set of one or more portions of the compression unit, based at least partially on metadata indicating that the first data is stored in certain portions of the compression unit.

28. One or more non-transitory computer-readable storage media storing instructions that, when executed by one or more computing devices, cause performance of:

storing data for database tables in a storage device, the storage device comprising a memory organized into data blocks conforming to a data block format, the data block format including data block metadata and one or more data block rows;

storing uncompressed data for a first plurality of the database tables in a first set of the data blocks, each data block of the first set of the data blocks comprising a plurality of data block rows, each data block row of the plurality of data block rows storing data from only one table row from the first plurality of the database tables;

for a particular table that is not in the first plurality of the database tables, generating compressed data by compressing data from multiple table rows in the particular table, wherein said compressing comprises generating the compressed data and structuring the compressed data in a compression unit that does not conform to the data block format;

storing the compression unit in one or more data block rows of a second set of one or more of the data blocks, said storing comprising storing at least a portion of the compression unit in a particular data block row of a particular data block of the data blocks;

wherein the portion of the compression unit comprises compressed data from a plurality of the table rows from the particular table, wherein the particular data block row thus comprises compressed data from the plurality of the table rows.

29. The one or more non-transitory computer-readable storage media of claim 28, wherein the particular data block comprises a header and one or more data block rows, the one or more data block rows including the particular data block row that stores the compression unit, wherein the particular data block row comprises a row header and a column field, wherein the column field comprises said portion of the compression unit.

30. The one or more non-transitory computer-readable storage media of claim 28, wherein the instructions, when executed by the one or more computing devices, further cause:

determining that execution of a request requires access to first data in said particular table;

retrieving, from the particular data block row, the portion of the compression unit;

decompressing the portion of the compression unit, thereby yielding an decompressed portion of the compression unit;

locating the first data in the decompressed portion of the compression unit;

executing the request, based at least partially on one or more items from the first data.

31. The one or more non-transitory computer-readable storage media of claim 28, wherein the instructions, when executed by the one or more computing devices, further cause storing the decompressed portion in a re-usable buffer.

32. The one or more non-transitory computer-readable storage media of claim 28, wherein the data that is compressed is a subset of the particular table, said subset including first data from a first set of one or more columns of the particular table, but not including second data from a second set of one or more columns of the particular table.

33. The one or more non-transitory computer-readable storage media of claim 28, wherein:

the portion of the compression unit is a first portion of the compression unit;

wherein the instructions, when executed by the one or more computing devices, further cause;

storing a second portion of the compression unit in a second data block row of a second data block.

34. The one or more non-transitory computer-readable storage media of claim 33, wherein the instructions, when executed by the one or more computing devices, further cause:

determining that execution of a request requires access to first data in the particular table;

retrieving, from data block rows in each of a set of data blocks, a set of portions of the compression unit;

wherein the set of data blocks includes the particular data block and the second data block;

wherein the set of portions includes the first portion and the second portion, decompressing the set of portions, thereby yielding a decompressed set of portions;

locating the first data in the decompressed set of portions;

executing the request, based at least partially on one or more items from the first data.

35. The one or more non-transitory computer-readable storage media of claim 28, wherein the instructions, when executed by the one or more computing devices, further cause storing compression unit metadata describing properties of the compression unit.

36. The one or more non-transitory computer-readable storage media of claim 35, wherein the compression unit metadata is stored within the particular data block in a field of the particular data block row that precedes the portion of the compression unit.

37. The one or more non-transitory computer-readable storage media of claim 35, wherein the instructions, when executed by the one or more computing devices, further cause determining how to retrieve the data stored in the compression unit based at least in part on the compression unit metadata.

38. The one or more non-transitory computer-readable storage media of claim 35, wherein the compression unit metadata includes metadata indicating a data block address for each portion of the compression unit.

39. The one or more non-transitory computer-readable storage media of claim 28, wherein the instructions, when executed by the one or more computing devices, further cause storing first metadata indicating that the particular data block consists of compressed data, wherein the database further stores second metadata indicating that one or more other data blocks

40. The one or more non-transitory computer-readable storage media of claim 28, wherein the instructions, when executed by the one or more computing devices, further cause:

storing second data from table rows in a second table into a second compression unit;

storing at least a portion of the second compression unit in a different data block row of the particular data block in the database;

wherein the portion of the second compression unit comprises compressed data from a plurality of table rows from the second table.

41. The one or more non-transitory computer-readable storage media of claim 28, wherein the plurality of the table rows is compressed inside of the compression unit, wherein the instructions, when executed by the one or more computing devices, wherein the instructions, when executed by the one or more computing devices, further cause:

storing uncompressed data in a different data block row of the particular data block;

storing metadata in the particular data block indicating a) that the particular data block row storing the compression unit stores compressed data; and

b) that the different data block row stores uncompressed data.

42. The one or more non-transitory computer-readable storage media of claim 28, wherein the instructions, when executed by the one or more computing devices, further cause:

storing metadata indicating, for the portion of the compression unit, a range of values for a particular column, wherein no table row in the portion of the compression unit comprises a value for the particular column that is outside of the range;

receiving a request for data from the particular table, said request including a predicate based upon the particular column;

in response to the request, determining whether to decompress the portion of the compression unit based upon the metadata and the predicate.

54. The one or more non-transitory computer-readable storage media of claim 28, wherein generating the compressed data comprises utilizing non-block-based compression to compress the data from the multiple table rows.

43. One or more non-transitory computer-readable storage media storing instructions that, when executed by one or more computing devices, cause performance of:

storing data for database tables in a storage device, the storage device comprising a memory organized into data blocks conforming to a data block format, the data block format including data block metadata and one or more data block rows;

storing uncompressed data for a first plurality of the database tables in a first plurality of the data blocks, each data block of the first plurality of the data blocks comprising a plurality of data block rows, each data block row of the plurality of data block rows storing data from only one table row from the first plurality of the database tables;

storing, within a second plurality of data blocks of a database, compression units comprising compressed data from tables, the compression units comprising compressed data structured in a format that does not conform to the data block format;

determining that execution of a database request requires access to data from at least one or more table rows;

retrieving one or more data blocks to which the one or more table rows have been mapped;

determining whether the one or more retrieved data blocks store any of the table rows in one or more of the compression units; and

responsive to determining that the one or more retrieved data blocks store data for a particular table row of the one or more table rows in one or more particular compression units of the compression units;

based at least partially on information in the one or more retrieved data blocks, locating at least a portion of the compression unit in a data block row of the one or more retrieved data blocks,

generating a decompressed portion of the compression unit, comprising data from a plurality of table rows, by decompressing the portion of the compression unit from the located data block row;

locating the data for the particular table row in the decompressed portion of the compression unit;

reading one or more items indicated by the database request from the data for the particular table row; and

executing the database request based at least on the one or more items that were read from the data for the particular table row.

44. The one or more non-transitory computer-readable storage media of claim 43, wherein the instructions, when executed by the one or more computing devices, further cause,

responsive to determining that the one or more retrieved data blocks store data from a second table row of the one or more table rows in uncompressed form outside of any of the compression units:

locating within the one or more retrieved data blocks a data block row storing raw data for the second table row;

reading one or more items indicated by the database request from the data block row; and

executing the database request based at least on the one or more items that were read from the data for the second table row.

45. The one or more non-transitory computer-readable storage media of claim 43, wherein the portion of the compression unit comprises the entire compression unit.

46. The one or more non-transitory computer-readable storage media of claim 43, wherein the decompressed portion of the compression unit comprises an entire table.

47. The one or more non-transitory computer-readable storage media of claim 43, wherein the portion of the compression unit is at least partially located in multiple data blocks.

48. The one or more non-transitory computer-readable storage media of claim 43, wherein the instructions, when executed by the one or more computing devices, further cause:

locating, in an index, an entry associating the particular table row with at least a) an address of a particular data block of the one or more data blocks and b) a row identifier within the particular data block;

wherein the step of retrieving the one or more data blocks comprises locating the particular data block based on the address of the particular data block that was indicated by the index; and

wherein the step of locating the table row in the decompressed portion of the compression unit is based on the row identifier.

49. One or more non-transitory computer-readable storage media storing instructions that, when executed by one or more computing devices, cause performance of:

storing data for database tables in a storage device, the storage device comprising a memory organized into data blocks conforming to a data block format, the data block format including data block metadata and one or more data block rows;

compressing a particular database table within a particular compression unit, the compression unit comprising compressed data from the table structured in a format that is different than the data block format;

dividing the particular compression unit into portions;

based on the divided portions, storing the compression unit within a plurality of data blocks of a database, wherein the compression unit spans the plurality of data blocks, each data block of the plurality of data blocks comprising one or more different portions of the divided portions;

receiving a request whose execution requires access to first data from the particular database table;

determining that the database stores the first data in the particular compression unit;

determining that the first data is stored in a first set of one or more portions of the divided portions of the particular compression unit;

retrieving the first set of one or more portions from one or more data blocks of the plurality of data blocks;

decompressing the first set of one or more portions, thereby yielding one or more decompressed portions of the particular compression unit;

locating the first data in the decompressed portion of the particular compression unit;

executing the request based at least partially on one or more items from the first data.

50. The one or more non-transitory computer-readable storage media of claim 49, wherein the instructions, when executed by the one or more computing devices, further cause identifying the first set of one or more portions of the compression unit, based at least partially on metadata indicating that the first data is stored in certain portions of the compression unit.

51. The one or more non-transitory computer-readable storage media of claim 49, wherein the instructions, when executed by the one or more computing devices, further cause retrieving, responsive to the request, only the one or more data blocks that store the first set of one or more portions of the particular compression unit, and not one or more other data blocks that store the second set of one or more portions of the particular compression unit.

52. The one or more non-transitory computer-readable storage media of claim 51, wherein the instructions, when executed by the one or more computing devices, further cause identifying the first set of one or more portions of the compression unit, based at least partially on portion mapping data stored immediately preceding a particular portion of the compression unit within a first data block of said plurality of data blocks, said portion mapping data indicating, for each portion of the divided portions, a block at which the portion is located.

53. The one or more non-transitory computer-readable storage media of claim 49, wherein the instructions, when executed by the one or more computing devices, are performed without having decompressed a second set of one or more portions of the divided portions of the particular compression unit.