Structure of hierarchical compressed data structure for tabular data

Abstract

A highly flexible and extensible structure is provided for physically storing tabular data. The structure, referred to as a compression unit, may be used to store tabular data that logically resides in any type of table-like structure. According to one embodiment, compression units are recursive. Thus, a compression unit may have a “parent” compression unit to which it belongs, and may have one or more “child” compression units that belong to it. In one embodiment, compression units include metadata that indicates how the tabular data is stored within them. The metadata for a compression unit may indicate, for example, whether the data is stored in row-major or column major-format the order of the columns within the compression unit (which may differ from the logical order of the columns dictated by the definition of their logical container), a compression technique for the compression unit, the child compression units (if any), etc.

1 . A method comprising:
 receiving a set of tabular data;   wherein the set of tabular data is divided into a plurality of rows, each of which includes data for a particular set of columns;   storing data for a first set of rows, of said plurality of rows, in a first compression unit;   storing data for a second set of rows, of said plurality of rows, in a second compression unit;   storing data that indicates whether, within said first compression unit, data for said first set of rows is stored in column-major format or in row-major format;   wherein the steps of receiving and storing are performed by one or more computing devices.   
     
     
         2 . The method of  claim 1  wherein:
 within said first compression unit, data for said first set of rows is stored in column-major format; and 
 within said second compression unit, data for said second set of rows is stored in column-major format. 
 
     
     
         3 . The method of  claim 1  wherein:
 within said first compression unit, data for said first set of rows is stored in column-major format; and 
 within said second compression unit, data for said second set of rows is stored in row-major format. 
 
     
     
         4 . The method of  claim 1  wherein:
 within said first compression unit, data for said first set of rows is stored in row-major format; and 
 within said second compression unit, data for said second set of rows is stored in row-major format. 
 
     
     
         5 . The method of  claim 1  wherein:
 the first compression unit has a first compressed section in which data is compressed using a first compression technique; and 
 the second compression unit has a second compressed section in which data is compressed using a second compression technique that is different from the first compression technique. 
 
     
     
         6 . The method of  claim 5 , further comprising:
 storing, within the first compression unit, data that indicates the first compression technique.   
     
     
         7 . The method of  claim 6 , wherein:
 the data that indicates the first compression technique is stored in a particular section of the first compression unit that is not compressed using the first compression technique.   
     
     
         8 . The method of  claim 7 , wherein the particular section is not compressed with any compression technique. 
     
     
         9 . The method of  claim 1 , wherein:
 within each row of the set of tabular data, the data for the particular set of columns appears in a first column order;   the method further comprises storing data that indicates whether the data for the first set of rows appears within the first compression unit in the first column order.   
     
     
         10 . The method of  claim 9 , further comprising:
 storing data that indicates a second column order for the data for the first set of rows stored within the first compression unit;   wherein the second column order is different than the first column order.   
     
     
         11 . A non-transitory computer-readable storage storing instructions which, when executed by one or more processors, cause performance of:
 receiving a set of tabular data;   wherein the set of tabular data is divided into a plurality of rows, each of which includes data for a particular set of columns;   storing data for a first set of rows, of said plurality of rows, in a first compression unit;   storing data for a second set of rows, of said plurality of rows, in a second compression unit; and   storing data that indicates whether, within said first compression unit, data for said first set of rows is stored in column-major format or in row-major format.   
     
     
         12 . The non-transitory computer-readable storage of  claim 11  wherein:
 within said first compression unit, data for said first set of rows is stored in column-major format; and 
 within said second compression unit, data for said second set of rows is stored in column-major format. 
 
     
     
         13 . The non-transitory computer-readable storage of  claim 11  wherein:
 within said first compression unit, data for said first set of rows is stored in column-major format; and 
 within said second compression unit, data for said second set of rows is stored in row-major format. 
 
     
     
         14 . The non-transitory computer-readable storage of  claim 11  wherein:
 within said first compression unit, data for said first set of rows is stored in row-major format; and 
 within said second compression unit, data for said second set of rows is stored in row-major format. 
 
     
     
         15 . The non-transitory computer-readable storage of  claim 11  wherein:
 the first compression unit has a first compressed section in which data is compressed using a first compression technique; and 
 the second compression unit has a second compressed section in which data is compressed using a second compression technique that is different from the first compression technique. 
 
     
     
         16 . The non-transitory computer-readable storage of  claim 15 , further comprising instructions for:
 storing, within the first compression unit, data that indicates the first compression technique.   
     
     
         17 . The non-transitory computer-readable storage of  claim 16 , wherein:
 the data that indicates the first compression technique is stored in a particular section of the first compression unit that is not compressed using the first compression technique.   
     
     
         18 . The non-transitory computer-readable storage of  claim 17 , wherein the particular section is not compressed with any compression technique. 
     
     
         19 . The non-transitory computer-readable storage of  claim 11 , wherein:
 within each row of the set of tabular data, the data for the particular set of columns appears in a first column order; and   the instruction include instruction for storing data that indicates whether the data for the first set of rows appears within the first compression unit in the first column order.   
     
     
         20 . The non-transitory computer-readable storage of  claim 19 , further comprising instructions for:
 storing data that indicates a second column order for the data for the first set of rows stored within the first compression unit;   wherein the second column order is different than the first column order.