Method and system for data compression in a relational database

Abstract

A method for applying adaptive data compression in a relational database system using a filter cascade having at least one compression filter stage in the filter cascade. The method comprises applying a data filter associated with the compression filter stage to the data input to produce reconstruction information and filtered data, then compressing the reconstruction information to be included in a filter stream. The filtered data is provided as a compression filter stage output. The method may comprise evaluating whether the compression filter stage provides improved compression compared to the data input. The filter stage output may be used as the input of a subsequent compression filter stage.

1 . A method for applying lossless data compression in a database system, the method using a filter cascade having at least one compression filter stage, the method comprising:
 providing a data input having a plurality of elements to the at least one compression filter stage of the filter cascade;   analyzing a plurality of data filters available for use in the at least one compression filter stage, to determine whether at least one of the plurality of data filters is able to be applied or reapplied to the data input;   heuristically evaluating at least one of the plurality of data filters determined as being able to be applied or reapplied to the data input;   determining a proposed data filter to be applied or reapplied to the data input that was heuristically evaluated as the best data filter out of data filters that were determined as being able to be applied or reapplied to the data input;   applying the proposed data filter to the data input to produce reconstruction information and filtered data;   compressing the reconstruction information to be included in a filter stream; and   providing the filtered data as a compression filter stage output of the compression filter stage.   
     
     
         2 . The method of  claim 1 , wherein the heuristic evaluation takes into account at least one of the expected total size of the filtered data and the compressed reconstruction information as compared to the data input, the expected total time required for decompressing the reconstruction information and retrieving the data input from the filtered data and the reconstruction information, and an expected heuristic evaluation score of data filters determined as being able to be applied or reapplied to the compression filter stage output. 
     
     
         3 . The method according to  claim 1 , wherein elements in the data input are alphanumeric, each element comprising at least one alphanumeric character, and wherein applying the proposed data filter further comprises:
 determining the longest common prefix for all elements in the data input;   storing the determined longest common prefix in the reconstruction information; and   providing the plurality of alphanumeric elements as the filtered data, wherein each subsequent element in the filtered data is provided as a subsequent element in the data input modified by subtraction of the longest common prefix.   
     
     
         4 . The method according to  claim 1 , wherein elements in the data input are alphanumeric, each element comprising at least one alphanumeric character; wherein applying the proposed data filter further comprises:
 processing the data input one element at a time, each element being processed at least one character at a time;   forming a compact directed acyclic word graph data structure where each subsequent at least one character is added to the data structure based on characters that preceded the at least one character in the element to which it belongs;   determining the probability distribution from the data structure for each subsequent at least one character based on preceding characters, where the probability distribution is updated as each at least one character is processed;   compressing the data input using a prediction by partial matching compression algorithm based on the probability distribution that is being updated;   providing a final compact directed acyclic word graph data structure, formed as a result of processing all subsequent characters in all subsequent elements in the data input, as the reconstruction information; and   providing the compressed data input as the filtered data.   
     
     
         5 . The method of  claim 1 , where applying the proposed data filter further comprises:
 changing the ordering of elements in the data input;   storing in the reconstruction information an information that provides for reversion to an original ordering of elements in the data input; and   providing the plurality of elements with changed ordering as the filtered data.   
     
     
         6 . The method of  claim 1 , where applying the proposed data filter further comprises
 providing a plurality of compression filter stage outputs, each of the plurality of compression filter stage outputs containing at least one of the plurality of elements contained in the data input; and   storing in the reconstruction information an information that provides for a merge to an original content of the data input.   
     
     
         7 . The method of  claim 1 , further comprising
 applying the proposed data filter to a plurality of data inputs; and   storing the reconstruction information common to the plurality of data inputs.   
     
     
         8 . The method of  claim 1 , further comprising
 checking a query condition against the data input, wherein the query condition is at least one of fully and partially modified to allow for running the query condition against the reconstruction information in place of the data input.   
     
     
         9 . A relational database system for applying lossless data compression, the system using a filter cascade having at least one compression filter stage, the system comprising:
 a database server having:
 a microprocessor for controlling operation of the database server; and 
 a memory coupled to the microprocessor; 
 the database server including a compression module resident in the memory for execution by the microprocessor, the compression module configured to: 
   receive a data input having a plurality of elements to at least one compression filter stage of the filter cascade;   analyze a plurality of data filters available for use in the at least one compression filter stage to determine whether at least one of the plurality of data filters is able to be applied or reapplied to the data input;   heuristically evaluate at least one of the plurality of data filters determined as being able to be applied or reapplied to the data input;   determine a proposed data filter to be applied or reapplied to the data input that was heuristically evaluated as the best data filter out of data filters that were determined as being able to be applied or reapplied to the data input;   apply the proposed data filter to the data input to produce reconstruction information and filtered data;   compress the reconstruction information to be included in a filter stream; and   provide the filtered data as a compression filter stage output for the compression filter stage.   
     
     
         10 . The system of  claim 9 , wherein the heuristic evaluation takes into account at least one of the expected total size of the filtered data and the compressed reconstruction information as compared to the data input, the expected total time required for decompressing the reconstruction information and retrieving the data input from the filtered data and the reconstruction information, and an expected heuristic evaluation score of data filters determined as being able to be applied or reapplied to the compression filter stage output. 
     
     
         11 . The system of  claim 9  wherein elements in the data input are alphanumeric, each element comprising at least one alphanumeric character, the compression module further configured to:
 determine the longest common prefix for all elements in the data input; 
 store the determined longest common prefix in the reconstruction information; and 
 provide the plurality of alphanumeric elements as the filtered data, wherein each subsequent element in the filtered data is provided as a subsequent element in the data input modified by subtraction of the longest common prefix. 
 
     
     
         12 . The system of  claim 9  wherein elements in the data input are alphanumeric, each element comprising at least one alphanumeric character; wherein applying the proposed data filter further comprises:
 processing the data input one element at a time, each element being processed at least one character at a time; 
 forming a compact directed acyclic word graph data structure where each subsequent at least one character is added to the data structure based on characters that preceded the at least one character in the element to which it belongs; 
 determining the probability distribution from the data structure for each subsequent at least one character based on preceding characters, where the probability distribution is updated as each at least one character is processed; 
 compressing the data input using a prediction by partial matching compression algorithm based on the probability distribution that is being updated; 
 providing a final compact directed acyclic word graph data structure, formed as a result of processing all subsequent characters in all subsequent elements in the data input, as the reconstruction information; and 
 providing the compressed data input as the filtered data. 
 
     
     
         13 . The system of  claim 9 , further configured to
 change the ordering of elements in the data input;   store in the reconstruction information an information that provides for reversion to an original ordering of elements in the data input; and   providing the plurality of elements with changed ordering as the filtered data   
     
     
         14 . The system of  claim 9 , further configured to
 provide a plurality of compression filter stage outputs, each of the plurality of compression filter stage outputs containing at least one of the plurality of elements contained in the data input; and   store in the reconstruction information an information that provides for a merge to an original content of the data input.   
     
     
         15 . The system of  claim 9 , further configured to
 apply the proposed data filter to a plurality of data inputs; and   store reconstruction information common to the plurality of data inputs.   
     
     
         16 . The system of  claim 9 , further configured to
 check a query condition against the data input, wherein the query condition is at least one of fully and partially modified to allow for running the query condition against the reconstruction information in place of the data input.