Hierarchical data compression and computation

摘要

According to embodiments of the present invention, machines, systems, methods and computer program products for hierarchical compression of data are presented comprising creating a compression hierarchy of compression nodes, wherein each compression node is associated with a compression operation to produce compressed data. An output of any of the compression nodes may be compressed by another compression node or the same compression node. A path of one or more compression nodes is determined through said compression hierarchy based upon compression statistics to compress data, and the data is compressed by the compression nodes of the path. Various computational techniques are presented herein for manipulating the compression hierarchy to defer or reduce computation during query evaluation.

主权项

1. A system for hierarchically compressing data comprising:
one or more processors configured to:
create a compression hierarchy of compression nodes, wherein each compression node is associated with a compression operation to produce compressed data, and wherein creating a compression hierarchy comprises:
creating a run length encoding compression node in the compression hierarchy of compression nodes;determine a path of one or more compression nodes through said compression hierarchy, based upon compression statistics, to compress data; andcompress the data by the compression nodes of the path, wherein compressing the data comprises:
performing part of a join operation on the data using the run length encoding compression node, wherein the join operation is performed by applying input data to a values field of the run length encoding compression node and by applying repeat counts to a lengths field of the run length encoding compression node.