# US 2024/0048153 A1 · Data compression for columnar databases into arbitrarily-sized persistent pages

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0048153 A1
- Document ID: US20240048153A1
- Status: Published application
- Kind: A1
- Application number: 18/483,824
- Filed: 2023-10-10
- Published: 2024-02-08
- Earliest claimed: 2021-09-21
- Assignees: Sap SE
- Applicants: Sap SE
- Inventors: Ivan Schreter
- Web page: https://patentgrep.com/patent/US20240048153A1

## CPC

- H03M 7/3088: {employing the use of a dictionary, e.g. LZ78}
- G06F 16/221: {Column-oriented storage; Management thereof}
- H03M 7/3077: {Sorting}
- H03M 7/4081: {Static prefix coding}
- H03M 7/607: {Selection between different types of compressors}
- H03M 7/46: Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
- H03M 7/6082: {Selection strategies}
- 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 for compressing columnar data may include generating, for a data column included in a data chunk, a dictionary enumerating, in a sorted order, a first set of unique values included in the first data column. A compression technique for generated a compressed representation of the data column having a fewest quantity of bytes may be identified based at least on the dictionary. The compression technique including a dictionary compression applying the dictionary and/or another compression technique. A compressed data chunk may be generated by applying the compression technique to compress the data column included in the data chunk. The compressed data chunk may be stored at a database in a variable-size persistent page whose size is allocated based on the size of the compressed representation of the data column. Related systems and articles of manufacture are also provided.

## Claims

### Claim 1

A system, comprising:
at least one data processor; and
at least one memory storing instructions which, when executed by the at least one data processor, cause operations comprising:
generating, for a first data column included in a data chunk, a first dictionary enumerating, in a sorted order, a first set of unique values included in the first data column;
identifying, based at least on the first dictionary, a first compression technique for generating a first compressed representation of the first data column having a fewest quantity of bytes, the first compression technique including a dictionary compression applying the first dictionary and/or another compression technique;
generating a compressed data chunk by at least applying the first compression technique to compress the first data column included in the data chunk; and
storing, in a persistent page at a database, the compressed data chunk.

### Claim 2 (depends on 1)

The system of claim 1, wherein the persistent page is associated with a variable size, and wherein the persistent page is allocated based at least on a size of the first compressed representation of the first data column such that a size of the persistent page corresponds to that of the compressed data chunk.

### Claim 3 (depends on 1)

The system of claim 1, wherein the first compression technique comprises a null-value compression instead of the dictionary compression if the first dictionary includes a single NULL value.

### Claim 4 (depends on 1)

The system of claim 1, wherein the first compression technique comprises a single-value compression instead of the dictionary compression if the first dictionary includes a single non-NULL value.

### Claim 5 (depends on 1)

The system of claim 1, wherein the first compression technique comprises the dictionary compression if the first dictionary includes multiple non-NULL values and a first size of the first data column is greater than a second size of the first dictionary and a data vector generated by replacing each value in the first data column with a corresponding index value from the first dictionary.

### Claim 6 (depends on 1)

The system of claim 1, wherein the first compression technique comprises a prefix/suffix compression instead of or in addition to the dictionary compression if the first dictionary includes more than a threshold quantity of unique values with prefixes and/or suffixes.

### Claim 7 (depends on 1)

The system of claim 1, wherein the first compression technique comprises a run-length encoding instead of or in addition to the dictionary compression if the first data column includes less than a threshold quantity of runs of a same value and/or the first dictionary is less than a threshold size.

### Claim 8 (depends on 1)

The system of claim 1, wherein the first compression technique comprises a frame of reference compression instead of or in addition to the dictionary compression if the first dictionary includes less than a threshold quantity of outlier values relative to a range of values.

### Claim 9 (depends on 1)

The system of claim 1, wherein the database comprises a columnar database.

### Claim 10 (depends on 1)

The system of claim 1, the operations may further comprise:
generating, for a second data column included in the data chunk, a second dictionary enumerating, in the sorted order, a second set of unique values included in the second data column;
identifying, based at least on the second dictionary, a second compression technique for generating a second compressed representation of the second data column having the fewest quantity of bytes, the second compression technique including a dictionary compression applying the second dictionary and/or another compression technique; and
generating the compressed data chunk including by applying the second compression technique to compress the second data column included in the data chunk.

### Claim 11

A computer-implemented method, comprising:
generating, for a first data column included in a data chunk, a first dictionary enumerating, in a sorted order, a first set of unique values included in the first data column;
identifying, based at least on the first dictionary, a first compression technique for generating a first compressed representation of the first data column having a fewest quantity of bytes, the first compression technique including a dictionary compression applying the first dictionary and/or another compression technique;
generating a compressed data chunk by at least applying the first compression technique to compress the first data column included in the data chunk; and
storing, in a persistent page at a database, the compressed data chunk.

### Claim 12 (depends on 11)

The method of claim 11, wherein the persistent page is associated with a variable size, and wherein the persistent page is allocated based at least on a size of the first compressed representation of the first data column such that a size of the persistent page corresponds to that of the compressed data chunk.

### Claim 13 (depends on 11)

The method of claim 11, wherein the first compression technique comprises a null-value compression instead of the dictionary compression if the first dictionary includes a single NULL value.

### Claim 14 (depends on 11)

The method of claim 11, wherein the first compression technique comprises a single-value compression instead of the dictionary compression if the first dictionary includes a single non-NULL value.

### Claim 15 (depends on 11)

The method of claim 11, wherein the first compression technique comprises the dictionary compression if the first dictionary includes multiple non-NULL values and a first size of the first data column is greater than a second size of the first dictionary and a data vector generated by replacing each value in the first data column with a corresponding index value from the first dictionary.

### Claim 16 (depends on 11)

The method of claim 11, wherein the first compression technique comprises a prefix/suffix compression instead of or in addition to the dictionary compression if the first dictionary includes more than a threshold quantity of unique values with prefixes and/or suffixes.

### Claim 17 (depends on 11)

The method of claim 11, wherein the first compression technique comprises a run-length encoding instead of or in addition to the dictionary compression if the first data column includes less than a threshold quantity of runs of a same value and/or the first dictionary is less than a threshold size.

### Claim 18 (depends on 11)

The method of claim 11, wherein the first compression technique comprises a frame of reference compression instead of or in addition to the dictionary compression if the first dictionary includes less than a threshold quantity of outlier values relative to a range of values.

### Claim 19 (depends on 11)

The method of claim 11, further comprising:
generating, for a second data column included in the data chunk, a second dictionary enumerating, in the sorted order, a second set of unique values included in the second data column;
identifying, based at least on the second dictionary, a second compression technique for generating a second compressed representation of the second data column having the fewest quantity of bytes, the second compression technique including a dictionary compression applying the second dictionary and/or another compression technique; and
generating the compressed data chunk including by applying the second compression technique to compress the second data column included in the data chunk.

### Claim 20

A non-transitory computer readable medium storing instructions, which when executed by at least one data processor, result in operations comprising:
generating, for a first data column included in a data chunk, a first dictionary enumerating, in a sorted order, a first set of unique values included in the first data column;
identifying, based at least on the first dictionary, a first compression technique for generating a first compressed representation of the first data column having a fewest quantity of bytes, the first compression technique including a dictionary compression applying the first dictionary and/or another compression technique;
generating a compressed data chunk by at least applying the first compression technique to compress the first data column included in the data chunk; and
storing, in a persistent page at a database, the compressed data chunk.
