Row, table, and index compression

Patent metadata

Field	Value
Publication number	US-9424293-B2
Application number	US-201414213088-A
Country	US
Kind code	B2
Filing date	Mar 14, 2014
Priority date	Mar 14, 2014
Publication date	Aug 23, 2016
Grant date	Aug 23, 2016

Abstract

Methods, systems, and computer program products for compressing a row are described. A common prefix may be obtained and data in the row matching the common prefix may be identified. A column number of a column corresponding to a breakpoint of the common prefix may be determined and data matching the common prefix may be deleted from the row. An identifier of the common prefix may be inserted into the row and a breakpoint field in the row may be set to the determined column number.

First claim

What is claimed is:

1. A computerized method for compressing a row, the method comprising:
obtaining a common prefix;
identifying data in the row matching the common prefix;
determining, using at least one hardware processor, an ordinal column number of a column corresponding to a breakpoint of the common prefix, the breakpoint indicating a location of an end of the common prefix in the row;
setting a breakpoint field in the row to the determined ordinal column number, wherein the breakpoint field indicates the location of the end of the common prefix in the row;
deleting the identified data from the row; and
inserting an identifier of the common prefix in the row.

2. The computerized method of claim 1 , wherein the identifier of the common prefix replaces the deleted data matching the common prefix.

3. The computerized method of claim I, further comprising updating an offset segment field based on the deletion of the data matching the common prefix.

4. The computerized method of claim 1 , wherein an offset corresponding to a column that partially resides in the common prefix is computed as a count of bytes preceding the column in the common prefix.

5. The computerized method of claim 1 , wherein an offset corresponding to a column that completely resides in the common prefix is computed as a count of bytes preceding the column in the common prefix.

6. The computerized method of claim 1 , wherein an offset corresponding to a column that completely resides in the row after the deletion is computed as a count of bytes preceding the column in the row after the deletion.

7. The computerized method of claim I, further comprising generating the common prefix by comparing a plurality of rows of an index table.

8. An apparatus for compressing a row, the apparatus comprising:
one or more hardware processors;
memory to store instructions that, when executed by the one or more hardware processors perform operations comprising:
obtain a common prefix;
identify data in the row matching the common prefix;
determine an ordinal column number of a column corresponding to a breakpoint of the common prefix, the breakpoint indicating a location of an end of the common prefix in the row;
set a breakpoint field in the row to the determined ordinal column number, wherein the breakpoint field indicates the location of the end of the common prefix in the row;
delete the identified data from the row; and
insert an identifier of the common prefix in the row.

9. The apparatus of claim 8 , wherein the identifier of the common prefix replaces the deleted data matching the common prefix.

10. The apparatus of claim 8 , wherein the row compression module is configured to update an offset segment field based on the deletion of the data matching the common prefix.

11. The apparatus of claim 8 , wherein an offset corresponding to a column that partially resides in the common prefix is computed as a count of bytes preceding the column in the common prefix.

12. The apparatus of claim 8 , wherein an offset corresponding to a column that completely resides in the common prefix is computed as a count of bytes preceding the column in the common prefix.

13. The apparatus of claim 8 , wherein an offset corresponding to a column that completely resides in the row after the deletion is computed as a count of bytes preceding the column in the row after the deletion.

14. The apparatus of claim 8 , further comprising a prefix identification module for comparing a plurality of rows of an index table and a prefix generation module for generating the common prefix.

15. A non-transitory machine-readable storage medium comprising instructions that, when executed by one or more processors of a machine, cause the machine to perform operations comprising:
obtaining a common prefix;
identifying data in a row matching the common prefix;
determining an ordinal column number of a column corresponding to a breakpoint of the common prefix, the breakpoint indicating a location of an end of the common prefix in the row;
setting a breakpoint field in the row to the determined ordinal column number, wherein breakpoint field indicates the location of the end of the common prefix in the row;
deleting the identified data from the row;
inserting an identifier of the common prefix in the row.

16. The non-transitory machine-readable storage medium of claim 15 , wherein the identifier of the common prefix replaces the deleted data matching the common prefix.

17. The non-transitory machine-readable storage medium of claim 15 , further comprising instructions that cause the machine to perform an operation of updating an offset segment field based on the deletion of the data matching the common prefix.

18. The non-transitory machine-readable storage medium of claim 15 , wherein an offset corresponding to a column that partially resides in the common prefix is computed as a count of bytes preceding the column in the common prefix.

19. The non-transitory machine-readable storage medium of claim 15 , wherein an offset corresponding to a column that completely resides in the common prefix is computed as a count of bytes preceding the column in the common prefix.

20. The non-transitory machine-readable storage medium of claim 15 , wherein an offset corresponding to a column that completely resides in the row after the deletion is computed as a count of bytes preceding the column in the row after the deletion.

Assignees

• Sybase Inc

Inventors

• Qian xu-dong
• Xiong Leon

Classifications

• G06F16/22 Primary

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/24561

  Intermediate data storage techniques for performance improvement · CPC title

• G06F17/30312 Primary

  Physics · mapped topic