Lazy operations on 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 physically store tabular data that logically resides in any type of table-like structure. Techniques are employed to avoid changing tabular data within existing compression units. Deleting tabular data within compression units is avoided by merely tracking deletion requests, without actually deleting the data. Inserting new tabular data into existing compression units is avoided by storing the new data external to the compression units. If the number of deletions exceeds a threshold, and/or the number of new inserts exceeds a threshold, new compression units may be generated. When new compression units are generated, the previously-existing compression units may be discarded to reclaim storage, or retained to allow reconstruction of prior states of the tabular data.

1 . A method comprising:
 storing, within a compression unit, data that logically belongs to a row of a table;   wherein at least a portion of the data is compressed; and   in response to a request to delete the row from the table, storing data that indicates the row is deleted without deleting the data for the row from the compression unit;   wherein the method is performed by one or more computing devices.   
     
     
         2 . The method of  claim 1  further comprising repackaging data from the compression unit into one or more new compression units in response to the number of deleted rows of the compression unit exceeding a threshold. 
     
     
         3 . The method of  claim 1  further comprising, in response to a request to store data in the table, storing the data in an overflow area external to the compression unit. 
     
     
         4 . The method of  claim 3  further comprising repackaging data from the overflow area into one or more compression units in response to the amount of data in the overflow area exceeding a threshold. 
     
     
         5 . The method of  claim 1  wherein the step of storing data that indicates the row is deleted includes changing a bit, within a delete vector, that corresponds to the row. 
     
     
         6 . The method of  claim 5  wherein the delete vector is stored within an uncompressed section of the compression unit. 
     
     
         7 . The method of  claim 1  further comprising, in response to a request to update data stored in the table, storing the update in an overflow area external to the compression unit and updating a delete vector which corresponds to the data stored in the table to indicate that the data stored in the table is deleted. 
     
     
         8 . The method of  claim 7  further comprising repackaging updates from the overflow area into one or more compression units in response to the amount of updates in the overflow area exceeding a threshold. 
     
     
         9 . The method of  claim 1  further comprising, in response to a request to store data in the table, storing the data in an uncompressed compression unit which has space available. 
     
     
         10 . The method of  claim 9  further comprising, compressing the uncompressed compression unit in response to the amount of data in the uncompressed compression unit exceeding a threshold. 
     
     
         11 . A non-transitory computer-readable storage storing instructions which, when executed by one or more processors, cause performance of:
 storing, within a compression unit, data that logically belongs to a row of a table;   wherein at least a portion of the data is compressed; and   in response to a request to delete the row from the table, storing data that indicates the row is deleted without deleting the data for the row from the compression unit.   
     
     
         12 . The non-transitory computer-readable storage of  claim 11  further comprising instructions for repackaging data from the compression unit into one or more new compression units in response to the number of deleted rows of the compression unit exceeding a threshold. 
     
     
         13 . The non-transitory computer-readable storage of  claim 11  further comprising instructions for, in response to a request to store data in the table, storing the data in an overflow area external to the compression unit. 
     
     
         14 . The non-transitory computer-readable storage of  claim 13  further comprising instructions for repackaging data from the overflow area into one or more compression units in response to the amount of data in the overflow area exceeding a threshold. 
     
     
         15 . The non-transitory computer-readable storage of  claim 11  wherein the step of storing data that indicates the row is deleted includes changing a bit, within a delete vector, that corresponds to the row. 
     
     
         16 . The non-transitory computer-readable storage of  claim 15  wherein the delete vector is stored within an uncompressed section of the compression unit. 
     
     
         17 . The non-transitory computer-readable storage of  claim 10  further comprising instructions for, in response to a request to update data stored in the table, storing the update in an overflow area external to the compression unit and updating a delete vector which corresponds to the data stored in the table to indicate that the data stored in the table is deleted. 
     
     
         18 . The non-transitory computer-readable storage of  claim 17  further comprising instructions for repackaging updates from the overflow area into one or more compression units in response to the amount of updates in the overflow area exceeding a threshold. 
     
     
         19 . The non-transitory computer-readable storage of  claim 10  further comprising instructions for, in response to a request to store data in the table, storing the data in an uncompressed compression unit which has space available. 
     
     
         20 . The non-transitory computer-readable storage of  claim 19  further comprising instructions for, compressing the uncompressed compression unit in response to the amount of data in the uncompressed compression unit exceeding a threshold.