TECHNICAL FIELD

The present disclosure relates to systems, software, and computer-implemented methods for compressed columnar data search using fingerprints in, for example, an in-memory columnar database.

As the amount of data requested by data-intensive applications increases, the amount of data managed by in-memory databases increases. To improve performance, data compression techniques can be used to keep large amount of data in-memory, instead of loading large amount of data on demand from, for example, a disk storage. However, high data compression ratio comes with both memory and performance overhead for data queries. For example, before applying a scan algorithm to answer a data query, compressed data is decompressed into vectors using hardware vectorization and parallelization.

SUMMARY

The present disclosure describes methods and systems, including computer-implemented methods, computer program products, and computer systems for compressed columnar data search using fingerprints in an in-memory database (e.g., an in-memory columnar database). One example computer-implemented method includes compressing columnar data to be stored in an in-memory database, where compressing columnar data includes dividing the columnar data into multiple data blocks and generating a particular fingerprint for each particular data block in the multiple data blocks, storing the compressed columnar data and the generated fingerprints in the in-memory database, receiving a query for the columnar data, for each particular in-memory data block in the multiple data blocks stored in the in-memory database, determining whether the particular in-memory data block satisfies the query and in response to a determination that the particular in-memory data block does not satisfy the query, pruning the particular in-memory data block from the multiple data blocks to generate an unpruned set of data blocks, decompressing the unpruned set of data blocks, and performing a query search on the decompressed unpruned set of data blocks for the received query.

The above-described implementation is implementable using a computer-implemented method; a non-transitory, computer-readable medium storing computer-readable instructions to perform the computer-implemented method; and a computer system comprising a computer memory interoperably coupled with a hardware processor configured to perform the computer-implemented method/the instructions being stored on the non-transitory, computer-readable medium.

As the amount of data requested by data-intensive applications increases, the amount of data managed by in-memory databases increases. To improve performance, data compression techniques can be used to keep large amount of data in-memory, instead of loading large amount of data on demand from, for example, a disk storage. However, high data compression ratio comes with both memory and performance overhead for data queries. For example, before applying a scan algorithm to answer a data query, compressed data is decompressed into vectors using, for example, hardware vectorization and parallelization. Decompressing the whole compressed data each time a data query for the whole compressed data is received can consume, for example, extra CPU and memory resource.

In this specification, data summaries of fine granularity at column block level are introduced to alleviate the memory and/or performance overhead in data queries for compressed data. Complementary to partition pruning, summaries of fine granularity at column block level can be designed based on data distribution in column blocks to support block pruning. Experimental results show that under same memory budget used for partition pruning, block pruning can lower false positive rates for compressed data scans, and reduce overhead of implementing data compression schemes.

The subject matter described in this specification can be implemented in particular implementations so as to realize one or more of the following advantages. First, the systems and/or methods described in the present disclosure introduces new fingerprints used to facilitate compressed columnar data search in an in-memory columnar database. The new fingerprints are orthogonal to the compression scheme (e.g., independent of a compression technique employed). Second, the systems and/or methods described in the present disclosure can perform quick compressed columnar data search using block pruning based on the fingerprints. Instead of decompressing all blocks of compressed columnar data, some blocks can be pruned and not decompressed (e.g., not searched) based on the fingerprints. As a result, decompressing portions of the compressed data for the search can reduce data decompression overhead. Third, different fingerprint schemes can be used based on data distribution in the columnar data to further decrease false positive rates and/or reduce data decompression overhead. Other advantages will be apparent to those of ordinary skill in the art.

The details of one or more implementations of the subject matter of this specification are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the subject matter will become apparent from the description, the drawings, and the claims.

