# US 12,184,310 B2 · Fingerprints for compressed columnar data search > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,184,310 B2 - Document ID: US12184310B2 - Status: Granted - Kind: B2 - Application number: 18/310,251 - Filed: 2023-05-01 - Published: 2023-08-24 - Granted: 2024-12-31 - Earliest claimed: 2019-05-17 - Assignees: Sap SE - Applicants: Sap SE - Inventors: Carmen Kwan; Reza Sherkat - Web page: https://patentgrep.com/patent/US12184310B2 ## CPC - H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction - G06F 16/1847: {specifically adapted to static storage, e.g. adapted to flash memory or SSD} - G06F 16/221: {Column-oriented storage; Management thereof} - G06F 16/2272: {Management thereof} - G06F 16/24561: {Intermediate data storage techniques for performance improvement} - G06F 16/25: Integrating or interfacing systems involving database management systems - G06F 16/90335: {Query processing} - G06F 16/9035: Filtering based on additional data, e.g. user or group profiles - G06F 18/23: Clustering techniques - H03M 7/3059: {Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression} - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract The present disclosure involves systems, software, and computer implemented methods for compressed columnar data search using fingerprints. One example method includes compressing columnar data that includes dividing the columnar data into multiple data blocks and generating a fingerprint for each data block, storing the compressed columnar data and the generated fingerprints in an in-memory database, receiving a query for the columnar data, for each in-memory data block stored in the in-memory database, determining whether the in-memory data block satisfies the query and in response to a determination that the in-memory data block does not satisfy the query, pruning the 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. ## Claims ### Claim 1 A computer-implemented method, comprising: receiving a query for columnar data, wherein the columnar data is compressed, as compressed columnar data, and stored in an in-memory database, wherein the compressed columnar data in the in-memory database comprises a plurality of data blocks, wherein each data block of the plurality of data blocks is associated with a respective fingerprint indicating a data range and one or more data gaps of a respective data block, the respective fingerprint being generated using a fingerprint scheme selected for a target block distribution according to a time complexity ranking of a respective pruning ability of a pruning function, and wherein the query comprises a query predicate; for each data block in the plurality of data blocks: determining whether the respective data block satisfies the query predicate; and in response to a determination that the respective data block fails to satisfy the query predicate, pruning, by applying the pruning function, the respective data block from the plurality of data blocks to generate an unpruned set of data blocks, the pruning function corresponding to the fingerprint scheme, wherein any data block in the unpruned set of data blocks satisfies the query, and wherein decompressing the unpruned set of data blocks comprises vectorizing values in the unpruned set of data blocks; decompressing a portion of the compressed columnar data comprising the unpruned set of data blocks to generate a decompressed unpruned set of data blocks; and limiting a performance of a query search to the decompressed unpruned set of data blocks for the query by excluding pruned data blocks. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the query predicate is a range predicate, and wherein determining whether the respective data block satisfies the query predicate comprises comparing a fingerprint associated with the respective data block and an encoding of the range predicate using a bitwise AND operation. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, further comprising: in response to a determination that the respective data block satisfies the query predicate, keeping the respective data block in the plurality of data blocks. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, wherein determining and pruning are performed on the compressed columnar data and the respective fingerprint stored in the in-memory database. ### Claim 5 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: receiving a query for columnar data, wherein the columnar data is compressed, as compressed columnar data, and stored in an in-memory database, wherein the compressed columnar data in the in-memory database comprises a plurality of data blocks, wherein each data block of the plurality of data blocks is associated with a respective fingerprint indicating a data range and one or more data gaps of a respective data block, the respective fingerprint being generated using a fingerprint scheme selected for a target block distribution according to a time complexity ranking of a respective pruning ability of a pruning function, and wherein the query comprises a query predicate; for each data block in the plurality of data blocks: determining whether the respective data block satisfies the query predicate; and in response to a determination that the respective data block fails to satisfy the query predicate, pruning, by applying the pruning function, the respective data block from the plurality of data blocks to generate an unpruned set of data blocks, the pruning function corresponding to the fingerprint scheme, wherein any data block in the unpruned set of data blocks satisfies the query, and wherein decompressing the unpruned set of data blocks comprises vectorizing values in the unpruned set of data blocks; decompressing a portion of the compressed columnar data comprising the unpruned set of data blocks to generate a decompressed unpruned set of data blocks; and limiting a performance of a query search to the decompressed unpruned set of data blocks for the query by excluding pruned data blocks. ### Claim 6 (depends on 5) The non-transitory computer storage medium of claim 5, wherein the query predicate is a range predicate, and wherein determining whether the respective data block satisfies the query predicate includes comparing a fingerprint associated with the respective data block and an encoding of the range predicate using a bitwise AND operation. ### Claim 7 (depends on 5) The non-transitory computer storage medium of claim 5, the operations further comprising: in response to a determination that the respective data block satisfies the query predicate, keeping the respective data block in the plurality of data blocks. ### Claim 8 (depends on 5) The non-transitory computer storage medium of claim 5, wherein determining and pruning are performed on the compressed columnar data and the respective fingerprint stored in the in-memory database. ### Claim 9 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: receiving a query for columnar data, wherein the columnar data is compressed, as compressed columnar data, and stored in an in-memory database, wherein the compressed columnar data in the in-memory database comprises a plurality of data blocks, wherein each data block of the plurality of data blocks is associated with a respective fingerprint indicating a data range and one or more data gaps of a respective data block, the respective fingerprint being generated using a fingerprint scheme selected for a target block distribution according to a time complexity ranking of a respective pruning ability of a pruning function, and wherein the query comprises a query predicate; for each data block in the plurality of data blocks: determining whether the respective data block satisfies the query predicate; and in response to a determination that the respective data block fails to satisfy the query predicate, pruning, by applying the pruning function, the respective data block from the plurality of data blocks to generate an unpruned set of data blocks, the pruning function corresponding to the fingerprint scheme, wherein any data block in the unpruned set of data blocks satisfies the query, and wherein decompressing the unpruned set of data blocks comprises vectorizing values in the unpruned set of data blocks; decompressing a portion of the compressed columnar data comprising the unpruned set of data blocks to generate a decompressed unpruned set of data blocks; and limiting a performance of a query search to the decompressed unpruned set of data blocks for the query by excluding pruned data blocks. ### Claim 10 (depends on 9) The computer-implemented system of claim 9, wherein the query predicate is a range predicate, and wherein determining whether the respective data block satisfies the query predicate includes comparing a fingerprint associated with the respective data block and an encoding of the range predicate using a bitwise AND operation. ### Claim 11 (depends on 9) The computer-implemented system of claim 9, the operations further comprising: in response to a determination that the respective data block satisfies the query predicate, keeping the respective data block in the plurality of data blocks. ### Claim 12 (depends on 9) The computer-implemented system of claim 9, wherein determining and pruning are performed on the compressed columnar data and the respective fingerprint stored in the in-memory database.