Query and Exadata Support for Hybrid Columnar Compressed Data

• US 20120054225A1
• Filed: 08/30/2010
• Published: 03/01/2012
• Est. Priority Date: 08/30/2010
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Marwah, Vineet, Kapoor, Vikram, Shergill, Kam, Macnicol, Roger, Ganesh, Amit, Kamp, Jesse, Kulkami, Sachin
• Granted Patent: US 8,832,142 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/2457 with adaptation to user needs

Abstract

A method and apparatus is provided for optimizing queries received by a database system that relies on an intelligent data storage server to manage storage for the database system. Storing compression units in hybrid columnar format, the storage manager evaluates simple predicates and only returns data blocks containing rows that satisfy those predicates. The returned data blocks are not necessarily stored persistently on disk. That is, the storage manager is not limited to returning disc block images. The hybrid columnar format enables optimizations that provide better performance when processing typical database workloads including both fetching rows by identifier and performing table scans.

Claims

1. A method comprising:

a storage system storing rows of a database table in one or more persistently stored compression units, wherein each compression unit of the one or more persistently stored compression units stores, in hybrid-row-columnar format, a different subset of said rows;

said storage system receiving a request to return compression units, wherein the request includes one or more criteria and the requested compression units contain rows with columns having values that satisfy said one or more criteria;

said storage system scanning said persistently stored compression units for rows having column values that satisfy said criteria;

said storage system returning in returned compression units'"'"' rows having column values that satisfy said criteria, wherein at least one returned compression unit of said returned compression units includes a first row and a second row, wherein the first row and the second row are stored in different persistently stored compression units.

2. The method of claim 1, wherein:

said one or more criteria is based on set of one or more predicates from a database query, wherein each predicate of the set of one or more predicates identifies a column of the database table;

retrieving data values only for a first column identified in a first predicate, and evaluating the first predicate based on the data values in the first column of one or more rows;

storing at a position within a vector a predicate satisfaction value corresponding to a row of the one or more rows that indicates that a data value in the first column of the row that satisfies the first predicate;

wherein the position within the vector corresponds to a row of the one or more rows.

3. The method of claim 2, wherein the request includes a plurality of predicates;

and further comprising;

determining, whether a predicate satisfaction value corresponding to any row is stored in the vector; and

in response to determining that no predicate satisfaction value is stored in the vector for any row, determining not to evaluate a second predicate.

4. The method of claim 2, wherein the vector is a cumulative vector, and further comprising:

determining, whether a predicate satisfaction value corresponding to any row is stored in the vector; and

in response to determining that at least one predicate satisfaction value is stored in the vector for any row, determining to evaluate a second predicate.

storing at a position within a second vector a second predicate satisfaction value corresponding to a row of the one or more rows that indicates that a data value in a second column of the row that satisfies the second predicate;

wherein the position within the second vector corresponds to a row of the one or more rows.

wherein the second predicate identifies the second column;

performing an operation on the second vector and the cumulative vector and storing results of the operation in the cumulative vector.

5. The method of claim 4, wherein only rows having a corresponding predicate satisfaction value stored in the cumulative vector are stored in a returned compression unit and returned.

6. The method of claim 1, further comprising compressing data in rows persistently stored within a compression unit.

7. The method of claim 6, wherein each column is compressed independent from every other column.

8. The method of claim 7, wherein compressing the data further comprises performing a first level of compression on the data;

and

after performing a first level of compression on the data, performing a second level of compression on the data.

9. The method of claim 8, wherein said one or more criteria includes a set of one or more

predicates from a database query, wherein each predicate of the set of one or more predicates identifies a column of the database table;

evaluating a first predicate that identifies a first column, wherein evaluating the first predicate only requires retrieving column data values by performing a first level of decompression on said first column, and evaluating the first predicate based on the column data values.

10. The method of claim 6, further comprising storing within each compression unit metadata associated with each column that indicates a range of values stored within the column.

11. The method of claim 10, further comprising evaluating a query that compares a column value to a range of values based on the metadata associated with the column stored within each compression unit, and evaluating the query without performing first level decompression or second level decompression.

12. A method comprising:

in response to a request for one or more compression units stored in a data storage system, a database system receiving at least one compression unit containing a plurality of rows, wherein said plurality of rows are rows of a database table stored in hybrid-row-columnar format;

wherein said at least one compression unit includes a first row and a second row, wherein a first persistently stored compression unit that stores the first row is different from a second persistently stored compression unit that stores second row;

rewriting data stored in each compression unit of said at least one compression unit into row-major format, wherein rewriting further comprises;

determining a number of columns for said each compression unit;

determining a number of rows based on said number of columns and a processor cache size;

iteratively performing until all rows returned in said each compression unit are read;

reading said number of rows from said each compression unit stored in column-major order and storing said number of rows into a matrix;

reading said number of rows from said matrix and writing said number of rows into a return buffer in row-major order; and

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

13. The method of claim 12, wherein the size of the matrix is less than the size of the processor cache;

and

once the matrix is stored in the processor cache, operations on the data stored within matrix are guaranteed not require any addition I/O operations.

14. The method of claim 12, wherein the size of the matrix is one third of the size of the processor cache.

15. The method of claim 12, wherein the compression unit containing a plurality of rows is fully compressed and received from the data storage system with a vector;

wherein the vector contains an entry corresponding to each row of the plurality of rows, and data in said each vector entry indicating which rows of the plurality of rows belong to a resultset.