Index compression

• US 8,032,495 B2
• Filed: 06/20/2008
• Issued: 10/04/2011
• Est. Priority Date: 06/20/2008
• Status: Active Grant

• Current Assignee: Perfect Search Corporation
• Original Assignee: Perfect Search Corporation
• Inventors: Millett, Ronald P.
• Primary Examiner(s): Leroux; Etienne
• Assistant Examiner(s): Nguyen; Cindy
• Application Number:
  US12/143,432
• Publication Number:
  US 20090319549A1
• Time in Patent Office: 1,201 Days
• Field of Search: 707/681, 707/800, 711170-173
• US Class Current: 707/681
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Compressing and decompressing compressed index lists. One or more index lists include at least a portion of the list that is compressed. A method includes reading an entry from a list. The method further includes determining that the entry indicates the start of a compressed block of the list. The compressed block is compressed using a compression algorithm including a plurality of delta pointers. Each of the delta pointers point to data store entries by reference to a difference from a reference in a previous entry in the list. An entry size indicator is referenced. The entry size indicator is configured to indicate a memory storage size for a delta pointer, and the entry size indicator supports indications for all of fixed storage sizes, variable storage sizes, and run length encoding. The compressed block of the list is decompressed according to the entry size indicator.

Claims

1. A method performed by one or more processors for accessing an index list which stores pointers to records in a data store, wherein some of the pointers in the index list are compressed, the method comprising:

reading a first entry in the index list, the first entry comprising a first pointer representing an address within a data store where a first record is located, the first pointer having a first size;

reading a second entry in the index list, the second entry comprising a header of a compressed portion of the index list, the compressed portion including a plurality of delta pointers that each represent an address within the data store where a corresponding record is located, each delta pointer having a size that is smaller than the first size, and wherein the header includes a size indicator that, when set to one of a plurality of values, defines the size of each delta pointer within the compressed portion;

determining the location of a third entry comprising a first delta pointer in the compressed portion of the index list by calculating an offset from a base address of the compressed portion based on the size of the delta pointers as defined by the size indicator; and

reading the third entry by accessing the index list at the determined location.

2. The method of claim 1, wherein to the compressed portion includes 64 delta pointers or less.

3. The method of claim 1, wherein the size indicator, when set to a first specified value, defines that the size of each delta pointer within the compressed portion is variable, and wherein determining the location of a third entry comprising a first delta pointer in the compressed portion of the index list by calculating an offset from a base address of the compressed portion based on the size of the delta pointers as defined by the size indicator further comprises:

accessing a variable size list within the compressed portion to identify one or more variable compressed entry size indicators that each define the size of a corresponding delta pointer that precedes the first delta pointer in the compressed portion; and

calculating an offset from the base address of the compressed portion based on the size of the one or more corresponding delta pointers as defined by the corresponding one or more variable compressed entry size indicators.

4. The method of claim 3, wherein the variable size list is sized to correspond to a native memory bus size of a processor executing portions of the method.

5. The method of claim 3, wherein each variable compressed entry size indicator has an equal number of bits.

6. The method of claim 1, wherein the size indicator, when set to a second specified value, defines that each delta pointer within the compressed portion has been run length encoded.

7. The method of claim 1, wherein determining the location of the third entry is performed in response to following a pointer from a speed-up data structure, the speed-up data structure allowing for skipping of entries in the index list.

8. The method of claim 1, wherein the header of the compressed portion commences with an entry representing a negative number to identify that the compressed portion follows the entry representing the negative number within the index list.

9. The method of claim 1, wherein the compressed portion comprises a sufficient number of filler entries such that the compressed portion begins and ends at native memory boundaries.

10. The method of claim 9, wherein the compressed portion is a whole integer multiple of a native memory bus size of a processor executing portions of the method.

11. The method of claim 1, wherein determining the location of the third entry further comprises accessing an offset correlation table which defines an offset for each of a plurality of groupings of delta pointers in the compressed portion, each delta pointer in a grouping sharing the same offset with other delta pointers in the same grouping, the offset of a grouping comprising a number of bits at the beginning of each delta pointer in the grouping.

12. The method of claim 3, wherein calculating an offset from the base address of the compressed portion based on the size of the one or more corresponding delta pointers as defined by the corresponding one or more variable compressed entry size indicators comprises shifting an address of a previous delta pointer in the compressed portion by a number of bits as defined by the one or more variable compressed entry size indicators.

13. One or more physical storage media storing computer executable instructions which when executed by one or more processors perform a method for accessing an index list which stores pointers to records in a data store, wherein some of the pointers in the index list are compressed, the method comprising:

reading a first entry in the index list, the first entry comprising a first pointer representing an address within a data store where a first record is located, the first pointer having a first size;

reading a second entry in the index list, the second entry comprising a header of a compressed portion of the index list, the compressed portion including a plurality of delta pointers that each represent an address within the data store where a corresponding record is located, each delta pointer having a size that is smaller than the first size, and wherein the header includes a size indicator that, when set to one of a plurality of values, defines the size of each delta pointer within the compressed portion;

determining the location of a third entry comprising a first delta pointer in the compressed portion of the index list by calculating an offset from a base address of the compressed portion based on the size of the delta pointers as defined by the size indicator; and

reading the third entry by accessing the index list at the determined location.

14. The computer storage media of claim 13, wherein the size indicator, when set to a first specified value, defines that the size of each delta pointer within the compressed portion is variable, and wherein determining the location of a third entry comprising a first delta pointer in the compressed portion of the index list by calculating an offset from a base address of the compressed portion based on the size of the delta pointers as defined by the size indicator further comprises:

accessing a variable size list within the compressed portion to identify one or more variable compressed entry size indicators that each define the size of a corresponding delta pointer that precedes the first delta pointer in the compressed portion; and

calculating an offset from the base address of the compressed portion based on the size of the one or more corresponding delta pointers as defined by the corresponding one or more variable compressed entry size indicators.

15. One or more physical storage media which store a data structure, the data structure comprising one or more index lists, wherein at least one of the one or more index lists comprises:

one or more non-compressed pointers that each represent an address within a data store where a corresponding record is located, each non-compressed pointer having a first size;

a compressed portion comprising;

a header that includes a size indicator that, when set to one of a plurality of values, defines the size of each delta pointer within the compressed portion; and

a plurality of delta pointers that each represent an address within the data store where a corresponding record is located, each delta pointer having a size that is smaller than the first size, wherein each delta pointer defines an offset from an address of a previous pointer in the compressed portion.

16. The computer readable medium of claim 15, wherein the size indicator, when set to a first specified value, defines that the plurality of delta pointers of the compressed portion are compressed using run-length encoding, and wherein the delta pointers are included in the compressed portion implicitly based on the run-length encoding.

17. The computer readable medium of claim 15, wherein the size indicator, when set to a second specified value, defines that the size of each delta pointer within the compressed portion is variable, and wherein the compressed portion further comprises a variable size list that defines the size of each of the plurality of delta pointers.