EFFICIENT LARGE-SCALE PROCESSING OF COLUMN BASED DATA ENCODED STRUCTURES

• US 20100030748A1
• Filed: 11/14/2008
• Published: 02/04/2010
• Est. Priority Date: 07/31/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Petculescu, Cristian, Netz, Amir
• Granted Patent: US 8,626,725 B2
• Time in Patent Office: Days
• US Class Current: N/A
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution

Abstract

The subject disclosure relates to efficient query processing over large scale data storage. An exemplary process includes retrieving a subset of columns implicated by a query as integer encoded and compressed sequences of values corresponding to different columns of data, defining query processing buckets that span over the subset of columns based on changes of compression type occurring in the integer encoded and compressed sequences of values of the subset of data and processing the query in memory on a bucket by bucket basis and processing the query based on type of current bucket when processing the integer encoded and compressed sequences of values. The column based organization of the data, and the application of a hybrid run length encoding and bit packing technique, enable a highly efficient and speedy query response in real-time.

Claims

1. A method for processing data, comprising:

in response to a query, receiving a subset of the data as integer encoded and compressed sequences of values corresponding to different columns of the data;

defining processing buckets that span over the subset of the data received as integer encoded and compressed sequences of values based on changes of compression type occurring in any of the integer encoded and compressed sequences of values of the subset of data; and

performing operations defined by the query based on type of current bucket processed when processing the integer encoded and compressed sequences of values to return query results.

2. The method of claim 1, wherein the receiving includes receiving the subset in memory for fast memory operations and processing of the subset of the data.

3. The method of claim 1, wherein the receiving includes receiving the subset of data from a relational database and wherein the different columns of the data correspond to columns of the relational database.

4. The method of claim 1, wherein the performing includes performing operations defined by the query based on whether different portions of values in the bucket across the sequences are compressed according to a first type of compression or second type of compression.

5. The method of claim 1, wherein the performing includes performing operations defined by the query based on whether different portions of values in the bucket across the sequences are compressed according to run length encoding compression or bit packing compression.

6. The method of claim 1, wherein the performing includes performing operations defined by the query based on how many different portions of values in the bucket across the sequences are compressed according to bit packing compression.

7. The method of claim 6, wherein the performing includes performing operations defined by the query based on whether (1) the different portions of values in the bucket across the sequences are all compressed according to run length encoding compression, defining a pure bucket, (2) all but one portion compressed according to run length encoding, defining a single impurity bucket, or (3) all but two portions compressed according to run length encoding, defining a double impurity bucket.

8. The method of claim 1, wherein the performing includes performing operations defined by the query based on type of current bucket processed, and processing the buckets in order.

9. The method of claim 1, wherein the performing includes parallelizing the operations defined by the query by utilizing multiple processors and a corresponding number of segments divided from the sequences, each segment handled by a different processor.

10. The method of claim 1, wherein the performing includes performing logical OR query slice operations or query join operations between multiple tables where relationships have been specified defined by the query based on type of current bucket processed when processing the integer encoded and compressed sequences of values to return query results.

11. The method of claim 1, wherein the performing includes performing at least one of filter operations, Group By operations, proxy column operations, or aggregation operations defined by the query based on type of current bucket processed when processing the integer encoded and compressed sequences of values to return query results.

12. The method of claim 11, wherein the at least one of filter operations, Group By operations, proxy column operations, or aggregation operations are processed separate from one another in phases for the current bucket and processing occurs bucket by bucket.

13. A device for processing data, comprising:

high speed in memory storage for storing a subset of data received as integer encoded and compressed sequences of values corresponding to different fields of the data; and

at least one query processor that processes the query over the subset of the data according to a bucket walking process that defines buckets across the sequences of values based on compression algorithm transitions from run length encoding to bit packing, or vice versa, and then processes the query over the subset of data bucket by bucket according to a type of bucket determined for a current bucket being processed based on the types of compression applied across the sequences for the current bucket.

14. The device of claim 13, wherein the types of compression include run length encoding and bit packing.

15. The device of claim 13, wherein the at least one query processor processes filter operations of the query over the subset of data based on the type of bucket.

16. The device of claim 13, wherein the at least one query processor processes Group By operations of the query over the subset of data based on the type of bucket.

17. The device of claim 13, wherein the at least one query processor processes proxy column operations of the query over the subset of data based on the type of bucket.

18. The device of claim 13, wherein the at least one query processor processes aggregation operations of the query over the subset of data based on the type of bucket.

19. The device of claim 13, wherein the at least one query processor determines the query results across all of the buckets based on the different types of buckets.

20. The device of claim 13, further comprising a decoder for decoding the integer encoded and compressed sequences of values to the data fields represented.

21. Data querying apparatus, comprising:

means for retrieving a subset of columns implicated by a query as integer encoded and compressed sequences of values corresponding to different columns of data;

means for defining query processing buckets that span over the subset of columns based on changes of compression type occurring in the integer encoded and compressed sequences of values of the subset of data; and

means for processing the query in memory on a bucket by bucket basis and processing the query based on type of current bucket when processing the integer encoded and compressed sequences of values.