# US 2020/0403633 A1 · Advanced database compression > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2020/0403633 A1 - Document ID: US20200403633A1 - Status: Published application - Kind: A1 - Application number: 16/729,721 - Filed: 2019-12-30 - Published: 2020-12-24 - Earliest claimed: 2019-06-21 - Assignees: Sap SE - Applicants: Sap SE - Inventors: Robert Lasch; Ismail Oukid; Norman May - Web page: https://patentgrep.com/patent/US20200403633A1 ## CPC - H03M 7/3088: {employing the use of a dictionary, e.g. LZ78} - G06F 9/38: Concurrent instruction execution, e.g. pipeline or look ahead - G06F 16/1744: {using compression, e.g. sparse files} - G06F 16/2282: {Tablespace storage structures; Management thereof} - H03M 7/3091: {Data deduplication} - H03M 7/3097: {Grammar codes} - 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 A method, a system, and a computer program product for executing a database compression. A compressed string dictionary having a block size and a front coding bucket size is generated from a dataset. Front coding is applied to one or more buckets of strings in the dictionary having the front coding bucket size to generate one or more front coded buckets of strings. One or more portions of the generated front coded buckets of strings are concatenated to form one or more blocks having the block size. Each block is compressed. A set of compressed blocks is stored. The set of the compressed blocks stores all strings in the dataset. ## Claims ### Claim 1 A computer-implemented method, comprising: generating, from a dataset, a compressed string dictionary having a block size and a front coding bucket size; applying front coding to one or more buckets of strings in the dictionary having the front coding bucket size to generate one or more front coded buckets of strings; concatenating one or more portions of the generated front coded buckets of strings to form one or more blocks having the block size, each block including a predetermined number of front coded buckets; compressing each of the one or more blocks; and storing a set of one or more compressed blocks, wherein the set of the compressed blocks storing all strings in the dataset, wherein the set of one or more compressed blocks is split into one or subsequences of compressed blocks corresponding to respective front coded buckets of strings. ### Claim 2 (depends on 1) The method according to claim 1, wherein each block in the set of compressed blocks includes a sequence of bucket headers and compressed buckets. ### Claim 3 (depends on 1) The method according to claim 1, further comprising inserting a termination character between buckets of strings in the plurality of front coded buckets of strings, wherein the termination character is not compressed. ### Claim 4 (depends on 1) The method according to claim 1, wherein each string includes a string termination character, wherein each string termination character is compressed. ### Claim 5 (depends on 1) The method according to claim 1, wherein the length of each string is stored and compressed with the string. ### Claim 6 (depends on 1) The method according to claim 1, wherein the block size is at least one of the following: a fixed size and a variable size. ### Claim 7 (depends on 1) The method according to claim 1, wherein the compressing further comprises independently executing compression of each block in the plurality of blocks in parallel. ### Claim 8 (depends on 1) The method according to claim 1, wherein one or more front-coded buckets are configured to be sampled to form one or more superblocks, wherein each one or more superblocks are configured to be compressed to generate a shared grammar for compression of the one or more blocks. ### Claim 9 (depends on 1) The method according to claim 1, wherein the compressing includes performing re-pair compression of the one or more blocks. ### Claim 10 (depends on 1) The method according to claim 1, further comprising receiving a request to access data in the set of stored compressed blocks; identifying one or more compressed blocks in the set of stored compressed blocks responsive to the received request; and at least partially decompressing the identified compressed blocks to generate uncompressed data. ### Claim 11 (depends on 10) The method according to claim 10, wherein the decompressing includes decompressing string prefixes and suffixes inside the identified compressed blocks using front coding; and decompressing string suffixes inside the identified compressed blocks using a re-pair decompression. ### Claim 12 (depends on 11) The method according to claim 11, wherein the re-pair decompression includes iteratively expanding each symbol in a symbol tree corresponding to the data stored in the identified compressed blocks. ### Claim 13 A system comprising: at least one programmable processor; and a non-transitory machine-readable medium storing instructions that, when executed by the at least one programmable processor, cause the at least one programmable processor to perform operations comprising: generating, from a dataset, a compressed string dictionary having a block size and a front coding bucket size; applying front coding to one or more buckets of strings in the dictionary having the front coding bucket size to generate one or more front coded buckets of strings; concatenating one or more portions of the generated front coded buckets of strings to form one or more blocks having the block size, each block including a predetermined number of front coded buckets; compressing each of the one or more blocks; and storing a set of one or more compressed blocks, wherein the set of the compressed blocks storing all strings in the dataset, wherein the set of one or more compressed blocks is split into one or subsequences of compressed blocks corresponding to respective front coded buckets of strings. ### Claim 14 (depends on 13) The system according to claim 13, wherein each block in the set of compressed blocks includes a sequence of bucket headers and compressed buckets. ### Claim 15 (depends on 13) The system according to claim 13, wherein the operations further comprise inserting a termination character between buckets of strings in the plurality of front coded buckets of strings, wherein the termination character is not compressed. ### Claim 16 (depends on 13) The system according to claim 13, wherein each string includes a string termination character, wherein each string termination character is compressed. ### Claim 17 (depends on 13) The system according to claim 13, wherein the length of each string is stored and compressed with the string. ### Claim 18 (depends on 13) The system according to claim 13, wherein the block size is at least one of the following: a fixed size and a variable size. ### Claim 19 (depends on 13) The system according to claim 13, wherein the compressing further comprises independently executing compression of each block in the plurality of blocks in parallel. ### Claim 20 A computer program product comprising a non-transitory machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising: generating, from a dataset, a compressed string dictionary having a block size and a front coding bucket size; applying front coding to one or more buckets of strings in the dictionary having the front coding bucket size to generate one or more front coded buckets of strings; concatenating one or more portions of the generated front coded buckets of strings to form one or more blocks having the block size, each block including a predetermined number of front coded buckets; compressing each of the one or more blocks; and storing a set of one or more compressed blocks, wherein the set of the compressed blocks storing all strings in the dataset, wherein the set of one or more compressed blocks is split into one or subsequences of compressed blocks corresponding to respective front coded buckets of strings.