Managing Storage of Individually Accessible Data Units

• US 20080104149A1
• Filed: 11/01/2006
• Published: 05/01/2008
• Est. Priority Date: 11/01/2006
• Status: Active Grant

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Software Corporation
• Inventors: Richardson, John L., Vishniac, Ephraim Meriwether, Bromley, H. Mark, Bay, Paul, Isman, Marshall A.
• Granted Patent: US 8,229,902 B2
• Time in Patent Office: Days
• US Class Current: 707/205
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures

Abstract

A method for managing data includes receiving individually accessible data units, each identified by a key value; storing a plurality of blocks of data, each of at least some of the blocks being generated by combining a plurality of the data units; and providing an index that includes an entry for each of the blocks. One or more of the entries enable location, based on a provided key value, of a block that includes data units corresponding to a range of key values that includes the provided key value.

Claims

1. A method for managing data, the method including:

receiving individually accessible data units, each identified by a key value;

storing a plurality of blocks of data, each of at least some of the blocks being generated by combining a plurality of the data units; and

providing an index that includes an entry for each of the blocks, wherein one or more of the entries enable location, based on a provided key value, of a block that includes data units corresponding to a range of key values that includes the provided key value.

2. The method of claim 1, wherein at least some of the blocks are generated by combining the data units based on a defined order for the key values.

3. The method of claim 2, wherein the defined order is alphabetical.

4. The method of claim 2, wherein the defined order is numerical.

5. The method of claim 2, wherein respective blocks are generated from respective sets of data units, and the sets correspond to non-overlapping ranges of key values according to the defined order.

6. The method of claim 1, wherein one or more of the entries in the index identify a range of key values corresponding to data units from which a corresponding block was generated.

7. The method of claim 6, wherein the range of key values is identified by information including at least one extremum of the range of key values.

8. The method of claim 7, wherein the range of key values is identified by a first extremum from a first entry in the index and a second extremum from a second entry in the index.

9. The method of claim 6, wherein the range of key values is identified by information including at least one extremum of the key values associated with the data units from which the corresponding block was generated.

10. The method of claim 9, wherein the range of key values is identified by a first extremum from a first entry in the index and a second extremum from a second entry in the index.

11. The method of claim 6, wherein each of at least some of the entries in the index identifies a storage location of the corresponding block.

12. The method of claim 1, wherein generating a block by combining a plurality of the data units comprises compressing a set of data units.

13. The method of claim 12, wherein decompressing a block generated by compressing a set of data units data units includes processing the entire block.

14. The method of claim 1, wherein the data units are records that each have one or more values associated with corresponding fields.

15. The method of claim 14, wherein a key value that identifies a received data unit corresponds to one or more fields associated with the given data unit before being received.

16. The method of claim 14, wherein a key value that identifies a received data unit is assigned to the data unit after being received.

17. The method of claim 16, wherein key values are assigned monotonically.

18. The method of claim 17, wherein key values are assigned sequentially.

19. The method of claim 1, wherein the stored blocks of data are stored as a first set of blocks.

20. The method of claim 19, wherein the first set of blocks are stored in a file.

21. The method of claim 19, further including storing a second set of one or more blocks of data, each of at least some of the blocks in the second set being generated from a plurality of data units received after storing the first set of blocks.

22. The method of claim 21, wherein at least some of the blocks in the second set are generated by compressing a set of data units.

23. The method of claim 21, further including providing an index that includes an entry for each of the blocks in the second set, wherein one or more of the entries enable location, based on a provided key value, of a block that includes data units corresponding to a range of key values that includes the provided key value.

24. The method of claim 21, further including:

processing the first and second sets of blocks to recover the data units from which the blocks were generated;

sorting the data units recovered from the first set and the data units recovered from the second set according to an order for key values corresponding to the data units to generate a set of sorted data units; and

generating a third set of blocks, each of at least some of the blocks in the third set being generated by combining a plurality of the sorted data units.

25. The method of claim 24, wherein sorting the data units recovered from the first set and the data units recovered from the second set includes merging the data units recovered from the first set with the data units recovered from the second set according to an order for key values corresponding to the data units to generate a set of sorted data units

26. The method of claim 24, further including providing an index for the third set that includes an entry for each of the blocks in the third set, wherein one or more of the entries enable location, based on a provided key value, of a block that includes data units corresponding to a range of key values that includes the provided key value.

27. The method of claim 1, further including providing a screening data structure associated with the stored blocks for determining a possibility that a data unit that includes a given attribute value was included in the data units from which the blocks were generated.

28. The method of claim 27, wherein the attribute value includes a key value that identifies a data unit.

29. The method of claim 27, wherein the screening data structure determines, for a given attribute value, either that a data unit including the given attribute value was definitely not included, or that a data unit including the given attribute value was possibly included.

30. The method of claim 29, wherein the probability that the screening data structure determines that a data unit including the given attribute value was possibly included when the data unit was not included depends on the size of the data structure.

31. The method of claim 30, further including selecting the size of the screening data structure based on the number of data units from which the blocks were generated.

32. The method of claim 1, further including providing a secondary index associated with the stored blocks for determining one or more key values of data units that include a given attribute value.

33. The method of claim 32, wherein the data units are records that each have one or more values associated with corresponding fields, the key value identifying a record corresponds to a primary key value, and the attribute value associated with the secondary index corresponds to a secondary key value.

34. The method of claim 32, wherein the secondary index includes a table having rows sorted by attribute values in the data units other than the key values.

35. A system for managing data, the system including:

means for receiving individually accessible data units, each identified by a key value;

means for storing a plurality of blocks of data, each of at least some of the blocks being generated by combining a plurality of the data units; and

means for providing an index that includes an entry for each of the blocks, wherein one or more of the entries enable location, based on a provided key value, of a block that includes data units corresponding to a range of key values that includes the provided key value.

36. A computer program, stored on a computer-readable medium, for managing data, the computer program including instructions for causing a computer to:

receive individually accessible data units, each identified by a key value;

store a plurality of blocks of data, each of at least some of the blocks being generated by combining a plurality of the data units; and

provide an index that includes an entry for each of the blocks, wherein one or more of the entries enable location, based on a provided key value, of a block that includes data units corresponding to a range of key values that includes the provided key value.