Adaptive compression optimization for effective pruning
Inventors
Bao, Junze • May, Norman • Schulze, Robert • Lemke, Christian • Zhou, Wei
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-12204517-B2
Publication Date
2025-01-21
Expiration Date
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.
Core Innovation
The invention relates to adaptive compression optimization in a database management system by dictionary-encoding data into data vectors and reordering the data vectors for database table columns using a forward pass followed by a backward pass. The forward pass sorts the at least first data vector for a first column and the second data vector for a second column based on frequency of occurrence, to move up most-frequent values.
In the backward pass, the method 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. The backward pass sorts the rest range by grouping close value identifiers together and preventing at least one rest range from being split during the sorting.
The invention additionally determines a prefix part and a non-prefix part, generates a min-max index for the non-prefix part associated with the first data vector, and stores a value of the prefix part and a length of the prefix part for at least the first data vector. The approach is described as adaptively reordering values and rest ranges to enable effective min-max index pruning without sacrificing compression.
Claims Coverage
The independent claims are method, system, and non-transitory computer-readable medium. They cover adaptive reordering of data vectors using a forward pass followed by a backward pass, combined with prefix and non-prefix part partitioning, min-max index generation for the non-prefix part, and storing the prefix part value and length. The inventive features include frequency-based forward sorting, distinct-value-identifier-based selection ordering in the backward pass, grouping close value identifiers, and preventing rest-range splitting.
Forward pass frequency-based sorting of column data vectors
The database management system reorders at least a first data vector for a first column and a second data vector for a second column using a forward pass followed by a backward pass, wherein the forward pass sorts based on frequency of occurrence.
Backward pass selection order based on distinct value identifiers in a rest range
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.
Rest-range sorting by grouping close value identifiers and preventing rest-range splitting
The backward pass sorts the rest range by grouping close value identifiers together, while preventing at least one rest range from being split during the sorting.
Prefix and non-prefix part determination for a data vector
The database management system determines, for at least the first data vector, a prefix part and a non-prefix part.
Min-max index generation for the non-prefix part
The database management system generates a min-max index for the non-prefix part associated with the first data vector.
Storing prefix part value and prefix length
The database management system stores, for at least the first data vector, a value of the prefix part and a length of the prefix part.
Across the independent claims, the core coverage combines two-pass reordering of data vectors with prefix and non-prefix part handling, min-max index generation for the non-prefix part, and storing the prefix value and its length.
Stated Advantages
Reduced scan time in experiments on TPC-H, with up to approximately 28% average reduction and 79/81 tables improved.
Similar compression metrics in most cases, indicating reordering improves pruning effectiveness without sacrificing compression.
Effective pruning using min-max index block-wise pruning.
Compression optimization time can increase.
Documented Applications
Column scan and block-wise pruning in a database management system, demonstrated using experiments on TPC-H tables LINEITEM and ORDERS and additional real-world tables.
Interested in licensing this patent?