Adaptive compression optimization for effective pruning

Patent metadata

Field	Value
Publication number	US-12204517-B2
Application number	US-202217933903-A
Country	US
Kind code	B2
Filing date	Sep 21, 2022
Priority date	Dec 14, 2018
Publication date	Jan 21, 2025
Grant date	Jan 21, 2025

Abstract

A database management system is described that can encode data to generate a plurality of data vectors. The database management system can perform the encoding by using a dictionary. The database management system can adaptively reorder the plurality of data vectors to prepare for compression of the plurality of data vectors. During a forward pass of the adaptive reordering, most frequent values of a data vector of the plurality of data vectors can be moved-up in the data vector. During a backward pass of the adaptive reordering, content within a rest range of a plurality of rest ranges can be rearranged within the plurality of data vectors according to frequencies of the content. The reordering according to frequency can further sort the rest range by value. Related apparatuses, systems, methods, techniques, computer programmable products, computer readable media, and articles are also described.

First claim

What is claimed is:

1. A method comprising:
reordering, by a database management system, at least a first data vector for a first column of a database table and a second data vector for a second column of the database table using a forward pass followed by a backward pass, wherein the forward pass sorts, based on frequency of occurrence, at least the first data vector and the second data vector, wherein the backward pass prioritizes a selection order of the first data vector or the second data vector based on a number of distinct value identifiers in a rest range of at least one of the first data vector or the second data vector, wherein the backward pass sorts by sorting the rest range in at least the first data vector and the second data vector by at least grouping close value identifiers together, wherein at least one rest range is prevented from being split during the sorting;
determining, by the database management system and for at least the first data vector, a prefix part and a non-prefix part;
generating, by the database management system, a min-max index for the non-prefix part associated with the first data vector; and
storing, for at least the first data vector, a value of the prefix part and a length of the prefix part.

2. The method of claim 1 , wherein the backward pass prioritizes the selection order of the first data vector over the second data vector, in response to the first data vector having a higher quantity of distinct values of value identifiers when compared to the second data vector.

3. The method of claim 1 , wherein the backward pass further comprises grouping close value identifiers together.

4. The method of claim 1 , further comprising: encoding, by the database management system, data of at least the first column and the second column of the database table to generate a plurality of data vectors including the first data vector for the first column and the second data vector for the second column.

5. The method of claim 4 , wherein the encoding comprises dictionary encoding.

6. The method of claim 1 , wherein the forward pass comprises moving-up, by the database management system, a most frequently occurring value in at least one of the first data vector or the second data vector.

7. A system comprising:
at least one processor; and
at least one memory including code which when executed by the at least one processor causes operations comprising:
reordering, by a database management system, at least a first data vector for a first column of a database table and a second data vector for a second column of the database table using a forward pass followed by a backward pass, wherein the forward pass sorts, based on frequency of occurrence, at least the first data vector and the second data vector, wherein the backward pass prioritizes a selection order of the first data vector or the second data vector based on a number of distinct value identifiers in a rest range of at least one of the first data vector or the second data vector, wherein the backward pass sorts by sorting the rest range in at least the first data vector and the second data vector by at least grouping close value identifiers together, wherein at least one rest range is prevented from being split during the sorting;
determining, by the database management system and for at least the first data vector, a prefix part and a non-prefix part;
generating, by the database management system, a min-max index for the non-prefix part associated with the first data vector; and
storing, for at least the first data vector, a value of the prefix part and a length of the prefix part.

8. The system of claim 7 , wherein the backward pass prioritizes the selection order of the first data vector over the second data vector, in response to the first data vector having a higher quantity of distinct values of value identifiers when compared to the second data vector.

9. The system of claim 7 , wherein the backward pass further comprises grouping close value identifiers together.

10. The system of claim 7 , further comprising: encoding, by the database management system, data of at least the first column and the second column of the database table to generate a plurality of data vectors including the first data vector for the first column and the second data vector for the second column.

11. The system of claim 10 , wherein the encoding comprises dictionary encoding.

12. The system of claim 7 , wherein the forward pass comprises moving-up, by the database management system, a most frequently occurring value in at least one of the first data vector or the second data vector.

13. A non-transitory computer-readable medium storing instructions that, when executed by a computer, cause operations comprising:
reordering, by a database management system, at least a first data vector for a first column of a database table and a second data vector for a second column of the database table using a forward pass followed by a backward pass, wherein the forward pass sorts, based on frequency of occurrence, at least the first data vector and the second data vector, wherein the backward pass prioritizes a selection order of the first data vector or the second data vector based on a number of distinct value identifiers in a rest range of at least one of the first data vector or the second data vector, wherein the backward pass sorts by sorting the rest range in at least the first data vector and the second data vector by at least grouping close value identifiers together, wherein at least one rest range is prevented from being split during the sorting;
determining, by the database management system and for at least the first data vector, a prefix part and a non-prefix part;
generating, by the database management system, a min-max index for the non-prefix part associated with the first data vector; and
storing, for at least the first data vector, a value of the prefix part and a length of the prefix part.

14. The non-transitory computer-readable medium of claim 13 , wherein the backward pass prioritizes the selection order of the first data vector over the second data vector, in response to the first data vector having a higher quantity of distinct values of value identifiers when compared to the second data vector.

15. The non-transitory computer-readable medium of claim 13 , wherein the backward pass further comprises grouping close value identifiers together.

16. The non-transitory computer-readable medium of claim 13 , further comprising: encoding, by the database management system, data of at least the first column and the second column of the database table to generate a plurality of data vectors including the first data vector for the first column and the second data vector for the second column.

17. The non-transitory computer-readable medium of claim 16 , wherein the encoding comprises dictionary encoding.

18. The non-transitory computer-readable medium of claim 13 , wherein the forward pass comprises moving-up, by the database management system, a most frequently occurring value in at least one of the first data vector or the second data vector.

Assignees

• Sap Se

Inventors

• Bao Junze
• May Norman
• Schulze Robert
• Lemke Christian
• Zhou Wei

Classifications

• G06F16/2237

  Vectors, bitmaps or matrices · CPC title

• G06F7/36

  Combined merging and sorting · CPC title

• G06F16/24556

  Aggregation; Duplicate elimination · CPC title

• H03M7/30

  Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction · CPC title

• G06F16/2272

  Management thereof · CPC title