Query predicate evaluation and computation for hierarchically compressed data

Patent metadata

Field	Value
Publication number	US-10901948-B2
Application number	US-201615060926-A
Country	US
Kind code	B2
Filing date	Mar 4, 2016
Priority date	Feb 25, 2015
Publication date	Jan 26, 2021
Grant date	Jan 26, 2021

Abstract

According to embodiments of the present invention, machines, systems, methods and computer program products for processing data are provided. Compressed data is received and a requested operation for uncompressed data is performed on the compressed data by determining an intermediate location in a compression hierarchy of compression nodes and applying the requested operation to the data at that intermediate location.

First claim

What is claimed is:

1. A computer-implemented method, in a data processing system comprising at least one processor and at least one memory, the at least one memory comprising instructions executed by the at least one processor to cause the at least one processor to process data, the computer-implemented method comprising:
implementing a compression hierarchy including a plurality of compression nodes performing different types of data compression, wherein data from table columns of a database is compressed by a first compression node and is subsequently compressed by one or more subsequent compression nodes in the compression hierarchy;
receiving a requested operation for uncompressed data within a query predicate to evaluate the query predicate for a chunk of data from one or more of the table columns of the database, wherein the requested operation is a computation on data in the chunk for the query predicate and is applicable to compressed data produced by a corresponding type of compression, and wherein the corresponding type of compression generates the compressed data comprising a plurality of parameters including a value parameter specifying a subset of values of data in the chunk and an attribute parameter indicating an arrangement of the subset of values for generating the uncompressed data, and wherein the corresponding type of compression includes one or more from a group of: run length encoding and dictionary encoding;
pushing evaluation of the query predicate through the compression hierarchy by determining an intermediate location in the compression hierarchy of compression nodes to apply the requested operation to compressed data of the chunk, wherein determining the intermediate location comprises:
evaluating a type of compression and characteristics of compressed data produced by each of the plurality of compressions nodes; and
determining the intermediate location in the compression hierarchy providing compressed data with the corresponding type of compression for the requested operation;

applying the requested operation to the value parameter of compressed data produced by a compression node proximate the determined location to produce result values without decompressing the compressed data, wherein the result values include the attribute parameters from the compressed data of the compression node proximate the determined location and the value parameters from the compressed data of the compression node proximate the determined location modified by application of the requested operation;
applying the result values to a subsequent compression node in the compression hierarchy to produce compressed data having the requested operation applied; and
evaluating the query predicate on the chunk of data with the requested operation applied and retrieving and decompressing data satisfying the query from the database.

2. The computer-implemented method of claim 1 , wherein applying the requested operation further comprises:
performing the operation, in parallel, on streams of data values of compressed data of the compression node proximate the determined location to produce the result values; and
applying the result values to the subsequent compression node to produce compressed data having the operation applied.

3. The computer-implemented method of claim 1 , wherein the query predicate includes a plurality of different parameters, and applying the requested operation further comprises:
transforming one or more parameters to provide the plurality of parameters in a common type as the compressed data of the compression node proximate the determined location; and
wherein evaluating the query predicate is based on the transformed parameters.

4. The computer-implemented method of claim 1 , wherein the computation of the requested operation includes a unary computation having a function with a single argument, and the computer-implemented method further comprising:
determining that the compressed data of the compression node proximate the determined location includes a number (N) of the same values; and
performing the unary computation on a single value of the compressed data of the compression node proximate the determined location to generate a data set containing N copies of a result of the unary computation.

5. The computer-implemented method of claim 1 , wherein the computation of the requested operation includes a unary computation having a function with a single argument, and the computer-implemented method further comprising:
determining that the compressed data of the compression node proximate the determined location has been compressed by plural compression nodes, and includes plural compression types and data for performing the unary computation;
determining a compression type of the plural compression types associated with the compressed data of the compression node proximate the determined location; and
performing the unary computation recursively on each of the plural compression types of the compressed data of the compression node proximate the determined location until encountering a bitshaved compression type.

6. The computer-implemented method of claim 1 , wherein the computation of the requested operation includes a binary computation having a function with first and second variables, and the computer-implemented method further comprising:
determining that the compressed data of the compression node proximate the determined location includes data for performing the binary computation, the compressed data of the compression node proximate the determined location comprising data for the first and second variables;
determining whether each value of data for the first variable is the same; and
performing the binary computation on the compressed data of the compression node proximate the determined location by treating the binary computation as a unary computation, wherein the first variable of the binary computation is bound to the determined same value of each value of the data for the first variable and the unary computation includes a function having a single argument pertaining to the second variable of the binary computation.

7. The computer-implemented method of claim 6 , wherein the data for the first and second variables have been compressed according to a dictionary encoded compression scheme or a run length encoding compression scheme, and the computer-implemented method further comprising:
performing the requested operation on the compressed data of the compression node proximate the determined location, wherein the compressed data of the compression node proximate the determined location has been further compressed to reduce an amount of computation.

8. The computer-implemented method of claim 1 , further comprising:
determining that the compressed data of the compression node proximate the determined location comprises data for the computation, wherein the computation includes a function having at least two variables and the compressed data for at least one of the two variables is compressed via a compression scheme using unary encoding, and wherein unary encoding comprises encoding by a function having a single argument;
determining a compatible encoding for the at least two variables, wherein the compatible encoding is performed by a compression node in the compression hierarchy subsequent the compression node proximate the determined location providing the compressed data using the unary encoding, and wherein the compatible encoding corresponds to one of: run length encoding and dictionary encoding;
removing the unary encoding from the compressed data of the subsequent compression node performing the compatible encoding and performing the requested operation on the compressed data in the compatible

Assignees

• IBM

Inventors

• Ackerman William B
• Dickie Garth A
• Keller Jeffrey M

Classifications

• G06F16/1744 Primary

  using compression, e.g. sparse files · CPC title