STORING COMPRESSION UNITS IN RELATIONAL TABLES

• US 20100281004A1
• Filed: 04/28/2010
• 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: Shergill, Kam, Macnicol, Roger, Bhattacharyya, Manosiz, Ganesh, Amit, Kamp, Jesse, Kapoor, Vikram, Kulkarni, Sachin, Marwah, Vineet
• Granted Patent: US 8,645,337 B2
• Time in Patent Office: Days
• 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 from table rows in a table into a compression unit;

storing at least a portion of the compression unit in a data block row of a data block in

a database;

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

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

2. The method of claim 1, wherein the data block comprises a header and one or more data block rows, the one or more data block rows including the data block row that stores the compression unit, wherein the 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 table;

retrieving, from the 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 is a subset of the table, said subset including first data from a first set of one or more columns of the table, but not including second data from a second set of one or more columns of the table.

6. The method of claim 1, wherein:

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

the data block row of the data block is a data block row of a first data block; and

the method further comprises;

storing a second portion of the compression unit in a 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 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 first 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 to the request, based at least partially on one or more items from the first data.

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

9. The method of claim 8, wherein the metadata is stored within the data block in a field of the 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 metadata.

11. The method of claim 8, wherein the 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 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 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 table rows is compressed inside of the compression unit, the methdo further comprising:

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

storing metadata in the data block indicating a) that the 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 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.

16. A method comprising:

determining that execution of a database request requires access to at least one or more items in a table row;

retrieving a data block to which the table row has been mapped;

determining whether the table row is stored in one or more compression units; and

if the table row is stored in one or more compression units, then;

based at least partially on information in the data block, locating at least a portion of the compression unit in a data block row of the data block,

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

wherein the decompressed portion of the compression unit comprises data from a plurality of table rows;

locating the table row in the decompressed portion of the compression unit;

reading the one or more items from the table row; and

executing the database request based on the one or more items;

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

17. The method of claim 16, further comprising,

if the table row is not stored in one or more compression units, then:

locating within the data block a data block row storing raw data for the table row;

reading the one or more items from the data block row; and

executing the database request based on the one or more items.

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 another data block.

21. The method of claim 16, wherein:

the step of retrieving the data block comprises locating, in an index, an entry associating the table row with a) an address of the data block and b) a row identifier;

the step of retrieving the data block further comprises locating the data block based on the address of the data block; and

the step of locating the table row in the decompressed portion of the compression unit is based on the data block row identifier;

wherein the data block row is associated with a data block row identifier;

wherein the data block row identifier is not the same as the row identifier;

22. A method comprising:

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

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

determining that the database stores the compression unit in a plurality of portions;

decompressing a first set of one or more portions of the compression unit, thereby yielding one or more decompressed portions 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;

wherein the method is performed without decompressing a second set of one or more portions of the compression unit;

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

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

24. The method of claim 22, wherein each of the plurality of portions is stored in a separate data block of a plurality of data blocks.

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 plurality of portions, a block at which the portion is located.