Back to results
US 10,019,457 B1Granted
Multi-level compression for storing data in a data store
AssigneeAmazon Technologies, Inc.
InventorsStefano Stefani, Anurag Windlass Gupta
Life of this patent
Estimating the term…
Abstract
Data to be stored in a data block for a columnar database table may be compressed according to a multi-level compression scheme. Data to be stored in the data block may be received. The data may be compressed according a column-specific compression technique to produce compressed data. The compressed data may then be compressed according to a second compression technique different than the column-specific compression technique to produce multi-level compressed data. The multi-level compressed data may be stored in the data block. When reading from the data block, multi-level compressed data may be decompressed according to the column-specific compression technique and the default compression technique applied to the data.
Claims20
A distributed data warehouse system, comprising:
- one or more computing devices comprising one or more hardware processors, the one or more computing devices configured-to implement a plurality of nodes, wherein at least some of the nodes each comprise program instructions that are executed by the one or more hardware processors to implement:
- storage for a columnar database table comprising two or more columns, wherein said storage comprises a plurality of data blocks;
- a compression selector configured to:
- evaluate metadata that describes one or more of the plurality of data blocks for a respective column of the two or more columns to select a column-specific compression technique from among a plurality of different column-specific compression techniques according to the evaluated metadata, the selected column-specific compression technique for compressing the one or more data blocks of the respective column;
- a plurality of column-specific compression engines, wherein one of the plurality of column-specific compression engines is configured to:
- receive data to be stored in a data block of the one or more data blocks for the respective column of the two or more columns of the columnar database table;
- and
- compress the data for the data block for the respective column according to the column-specific compression technique selected by the compression selector to produce compressed data;
- a system compression engine, configured to:
- receive as input the compressed data for the data block for the respective column;
- compress the compressed data according to a system compression technique different than the selected column-specific compression technique to produce multi-level compressed data that is compressed according to both the selected column-specific technique and the system compression technique for the data block for the respective column independently of data blocks for other columns of the two or more columns;
- a write module, wherein the write module is configured to:
- obtain the multi-level compressed data for the data block for the respective column;
- store the multi-level compressed data in the data block for the respective column in storage;
- and
- update the block metadata for the data block to identify the column-specific compression technique applied to the data and the system compression technique applied to the data, wherein said update comprises store information about the column-specific compression technique which indicates data values stored in the multi-level compressed data in the data block;
- and
- a data access module to:
- receive an indication of a query directed to the data stored in the data block for select data;
- and
- in response to receiving the indication of the query:
- examine the block metadata to determine that the select data is not stored in the multi-level compressed data stored in the data block based on the information which indicates the data values stored in the multi-level compressed data in the data block.
19 more elements
A method, comprising:
- performing, by one or computing devices:
- receiving, by a data access module, data to be stored in a data block in a data store, wherein the data block comprises data for a respective column of a columnar database table, the table comprising two or more columns;
- evaluating, by a compression selector, metadata describing one or more of the plurality of data blocks for the respective column of the two or more columns to select a primary compression technique from among a plurality of different column-specific compression techniques according to the evaluation, the selected primary compression technique for compressing the one or more data blocks of the selected column;
- compressing, by a compression engine of the data access module, the data for the data block for the respective column according to the primary compression technique in order to produce compressed data;
- subsequent to compressing the data according to the primary compression technique, compressing the compressed data according to a secondary compression technique different than the primary compression technique to produce multi-level compressed data that is compressed according to both the primary compression technique and the secondary compression technique for the data block for the respective column independently of data blocks for other columns of the two or more columns;
- storing the multi-level compressed data in the data block for the respective column;
- updating block metadata for the data block to identify the primary compression technique applied to the data to be stored in the data block and the secondary compression technique applied to the compressed data, wherein said updating comprises storing information about the primary compression technique which indicates data values stored in the multi-level compressed data in the data block;
- receiving an indication of a query directed to the data stored in the data block for select data;
- and
- in response to receiving the indication of the query:
- examining the block metadata to determine that the select data is not stored in the multi-level compressed data stored in the data block based on the information which indicates the data values stored in the multi-level compressed data in the data block.
8 more elements
A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices implement:
- receiving data to be stored in a data block for a respective column of a columnar database table, the table comprising two or more columns;
- evaluating, by a compression selector, metadata describing one or more of a plurality of data blocks for the respective column of the two or more columns to select a column-specific compression technique from among a plurality of different column-specific compression techniques according to the evaluation, the selected column-specific compression technique for compressing the one or more data blocks of the selected column;
- compressing the data for the one or more data block for the respective column according to the column-specific compression technique to produce compressed data;
- subsequent to compressing the data according to the column-specific compression technique, compressing the compressed data for the data block for the respective column according to a secondary compression technique different than the column-specific compression technique to produce multi-level compressed data that is compressed according to both the column-specific technique and the secondary compression technique for the data block for the respective column independently of data blocks for other columns of the two or more columns;
- storing the multi-level compressed data in the data block for the respective column;
- updating block metadata for the data block to identify the column-specific compression technique applied to the data to be stored in the data block and the secondary compression technique applied to the compressed data, wherein said updating comprises storing information about the column-specific compression technique which indicates data values stored in the multi-level compressed data in the data block;
- receiving an indication of a query directed to the data stored in the data block for select data;
- and
- in response to receiving the indication of the query:
- examining the block metadata to determine that the select data is not stored in the multi-level compressed data stored in the data block based on the information which indicates the data values stored in the multi-level compressed data in the data block.
7 more elements
Dependencies are inferred from the claim text.