Fingerprints for compressed columnar data search

A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

• compressing columnar data to be stored in an in-memory database, including:
• dividing the columnar data into a plurality of data blocks;
• and
• in response to dividing the columnar data into the plurality of data blocks, for each particular data block in the plurality of data blocks, generating a particular fingerprint associated with the particular data block, wherein the particular fingerprint indicates a data range and one or more data gaps of the particular data block, and wherein the particular fingerprint is generated using one of a plurality of predefined fingerprint schemes based on data distribution in the columnar data;
• 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 plurality of data blocks stored in the in-memory database:
• determining whether the particular in-memory data block satisfies the query based on the particular fingerprint associated with the particular in-memory data block and on the data range and the one or more data gaps of the particular in-memory data block indicated by the particular fingerprint;
• 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 plurality of 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.

A computer-implemented system, comprising:

• one or more computers;
• and
• one or more computer memory devices interoperably coupled with the one or more computers and having tangible, non-transitory, machine-readable media storing one or more instructions that, when executed by the one or more computers, perform one or more operations comprising:
• compressing columnar data to be stored in an in-memory database, including:
• dividing the columnar data into a plurality of data blocks;
• and
• in response to dividing the columnar data into the plurality of data blocks, for each particular data block in the plurality of data blocks, generating a particular fingerprint associated with the particular data block, wherein the particular fingerprint indicates a data range and one or more data gaps of the particular data block, and wherein the particular fingerprint is generated using one of a plurality of predefined fingerprint schemes based on data distribution in the columnar data;
• 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 plurality of data blocks stored in the in-memory database:
• determining whether the particular in-memory data block satisfies the query based on the particular fingerprint associated with the particular in-memory data block and on the data range and the one or more data gaps of the particular in-memory data block indicated by the particular fingerprint;
• 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 plurality of 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.