Managing storage of data for range-based searching

• US 9,811,570 B2
• Filed: 07/06/2012
• Issued: 11/07/2017
• Est. Priority Date: 07/08/2011
• Status: Active Grant

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Inventors: Stanfill, Craig W.
• Primary Examiner(s): Hutton, Nan
• Application Number:
  US13/543,339
• Publication Number:
  US 20130013606A1
• Time in Patent Office: 1,950 Days
• Field of Search: 707711
• CPC Class Codes: G06F 16/213 with details for schema evolution support
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data
• CPC Class Codes: G06F 16/2477 Temporal data queries

Abstract

In general, a value of a numerical attribute of a record stored in a data structure is received. A numerical range is generated that includes the value of the numerical attribute. An entry is stored, in an index associated with the data structure, that specifies a location of the record within the data structure and that includes a first index key and a second index key. The first index key corresponds to a value of an attribute of the record different from the numerical attribute, and the second index key corresponds to the generated numerical range.

Claims

1. A method for managing storage of data including:

for each of multiple records stored in a data structure, assigning an identifier that represents a range of values based on an attribute of the record, the range being specific to the record, in which assigning an identifier for a particular record includes;

determining a value based on a difference between a value of the attribute of the particular record and a first reference value, and

determining the identifier that represents the range of values for the particular record based on a relationship between the value based on the difference and a second reference value; and

storing entries in an index associated with the data structure, each entry specifying a location of a corresponding record within the data structure, the storing including, for each entry;

storing a first index key in the entry, in which the first index key is indicative of the identifier that represents the range of values for the corresponding record, and

storing a second index key in the entry, the second index key based on a value stored in the corresponding record,

wherein the index is sorted by both (i) the first index key indicative of the identifier that represents the range of values and (ii) the second index key.

2. The method of claim 1, wherein the attribute is represented by a time stamp, and the range of values corresponds to a range of time.

3. The method of claim 2, wherein the first reference value corresponds to a time stamp from a predetermined point in time, and wherein determining a value based on the difference between the value of the attribute of the particular record and the first reference value includes:

determining a first value in time units that separates a time corresponding to the time stamp from the predetermined point in time.

4. The method of claim 3, wherein the second reference value corresponds to a predetermined time duration, and wherein determining the identifier that represents the range of values includes:

dividing the first value by the predetermined time duration to provide a quotient that represents the range of values.

5. The method of claim 1, wherein each entry specifies a location, within the data structure, of a second record that is associated with the first index key and the second index key.

6. The method of claim 5, wherein the record is a first record, and wherein the attribute of the first record and the attribute of the second record are each represented by a different time stamp.

7. The method of claim 5, including:

receiving a query that requests the retrieval of records that are associated with the second index key and that are associated with a time between a first time and a second time.

8. The method of claim 7, including:

assigning first and second identifiers that represent respective ranges of values for the first time and the second time.

9. The method of claim 8, wherein assigning the first and second identifiers that represent the respective ranges of values includes:

determining a second value in time units based on a separation between the first time and a second predetermined point in time; and

determining a third value in time units based on a separation between the second time and the second predetermined point in time.

10. The method of claim 9, wherein assigning the first and second identifiers that represent the respective ranges of values includes:

dividing the second value by a predetermined time duration to provide a quotient that represents a numerical range for the first time; and

dividing the third value by the predetermined time duration to provide a quotient that represents a numerical range for the second time.

11. The method of claim 10, including:

identifying one or more entries within the index that include the second index key, and that include a first index key that corresponds to the range of values for the first time or the range of values for the second time or that is between the respective ranges of values for the first time and the second time.

12. The method of claim 1, wherein the entries are sorted in the index primarily by the first index key indicative of the identifier that represents the range of values.

13. The method of claim 1, wherein the entries are sorted in the index primarily by the second index key.

14. The method of claim 1, wherein the attribute has a value that satisfies the range of values.

15. The method of claim 14, wherein the value of the attribute is within the range of values.

16. The method of claim 1, wherein determining the identifier that represents the range of values comprises dividing the value based on the difference by the second reference value to provide a quotient that represents the range of values.

17. A non-transitory computer-readable storage medium storing a computer program for managing the storage of data, the computer program including instructions for causing a computing system to:

for each of multiple records stored in a data structure, assigning an identifier that represents a range of values based on an attribute of the record, the range being specific to the record, in which assigning an identifier for a particular record includes;

determining a value based on a difference between a value of the attribute of the particular record and a first reference value, and

determining the identifier that represents the range of values for the particular record based on a relationship between the value based on the difference and a second reference value; and

store entries in an index associated with the data structure, each entry specifying a location of a corresponding record within the data structure, the storing including, for each entry;

storing a first index key in the entry, in which the first index key is indicative of the identifier that represents the range of values for the corresponding record, and

storing a second index key in the entry, the second index key based on a value stored in the corresponding record,

wherein the index is sorted by both (i) the first index key indicative of the identifier that represents the range of values and (ii) the second index key.

18. The non-transitory computer-readable storage medium of claim 17, wherein the attribute is represented by a time stamp, and the range of values corresponds to a range of time.

19. The non-transitory computer-readable storage medium of claim 18, wherein the first reference value corresponds to a time stamp from a predetermined point in time, and wherein determining a value based on the difference between the value of the attribute of the particular record and the first reference value includes:

determining a first value in time units that separates a time corresponding to the time stamp from the predetermined point in time.

20. The non-transitory computer-readable storage medium of claim 19, wherein the second reference value corresponds to a predetermined time duration, and wherein determining the identifier that represents the range of values includes:

dividing the first value by the predetermined time duration to provide a quotient that represents the range of values.

21. The non-transitory computer-readable storage medium of claim 17, wherein each entry specifies a location, within the data structure, of a second record that is associated with the first index key and the second index key.

22. The non-transitory computer-readable storage medium of claim 21, wherein the record is a first record, and wherein the attribute of the first record and the attribute of the second record are each represented by a different time stamp.

23. The non-transitory computer-readable storage medium of claim 21, including instructions for causing a computing system to:

receive a query that requests the retrieval of records that are associated with the second index key and that are associated with a time between a first time and a second time.

24. The non-transitory computer-readable storage medium of claim 23, including instructions for causing a computing system to:

assign first and second identifiers that represent respective ranges of values for the first time and the second time.

25. The non-transitory computer-readable storage medium of claim 24, wherein assigning the first and second identifiers that represent the respective ranges of values includes:

determining a second value in time units based on a separation between the first time and a second predetermined point in time; and

determining a third value in time units based on a separation between the second time and the second predetermined point in time.

26. The non-transitory computer-readable storage medium of claim 25, wherein assigning the first and second identifiers that represent the respective ranges of values includes:

dividing the second value by a predetermined time duration to provide a quotient that represents a numerical range for the first time; and

dividing the third value by the predetermined time duration to provide a quotient that represents a numerical range for the second time.

27. The non-transitory computer-readable storage medium of claim 26, including instructions for causing a computing system to:

identify one or more entries within the index that include the second index key, and that include a first index key that corresponds to the range of values for the first time or the range of values for the second time or that is between the respective ranges of values for the first time and the second time.

28. The non-transitory computer-readable storage medium of claim 17, wherein the attribute has a value that satisfies the range of values.

29. The non-transitory computer-readable storage medium of claim 28, wherein the value of the attribute is within the range of values.

30. The non-transitory computer-readable storage medium of claim 17, wherein determining the identifier that represents the range of values comprises dividing the value based on the difference by the second reference value to provide a quotient that represents the range of values.

31. A computing system for managing the storage of data, the computing system including:

at least one processor configured to;

for each of multiple records stored in a data structure, assigning an identifier that represents a range of values based on an attribute of the record, the range being specific to the record, in which assigning an identifier for a particular record includes;

determining a value based on a difference between a value of the attribute of the particular record and a first reference value, and

determining the identifier that represents the range of values for the particular record based on a relationship between the value based on the difference and a second reference value; and

store entries in an index associated with the data structure, each entry specifying a location of a corresponding record within the data structure, the storing including, for each entry;

storing a first index key in the entry, in which the first index key is indicative of the identifier that represents the range of values for the corresponding record, and

storing a second index key in the entry, the second index key based on a value stored in the corresponding record,

wherein the index is sorted by both (i) the first index key indicative of the identifier that represents the range of values and (ii) the second index key.

32. The computing system of claim 31, wherein the attribute is represented by a time stamp, and the range of values corresponds to a range of time.

33. The computing system of claim 32, wherein the first reference value corresponds to a time stamp from a predetermined point in time, and wherein determining a value based on the difference between the value of the attribute of the particular record and the first reference value includes:

determining a first value in time units that separates a time corresponding to the time stamp from the predetermined point in time.

34. The computing system of claim 33, wherein the second reference value corresponds to a predetermined time duration, and wherein determining the identifier that represents the range of values includes:

dividing the first value by the predetermined time duration to provide a quotient that represents the range of values.

35. The computing system of claim 31, wherein each entry specifies a location, within the data structure, of a second record that is associated with the first index key and the second index key.

36. The computing system of claim 35, wherein the record is a first record, and wherein the attribute of the first record and the attribute of the second record are each represented by a different time stamp.

37. The computing system of claim 35, the at least one processor configured to:

receive a query that requests the retrieval of records that are associated with the second index key and that are associated with a time between a first time and a second time.

38. The computing system of claim 37, the at least one processor configured to:

assign first and second identifiers that represent respective ranges of values for the first time and the second time.

39. The computing system of claim 38, wherein assigning the first and second identifiers that represent the respective ranges of values includes:

determining a second value in time units based on a separation between the first time and a second predetermined point in time; and

determining a third value in time units based on a separation between the second time and the second predetermined point in time.

40. The computing system of claim 39, wherein assigning the first and second identifiers that represent the respective ranges of values includes:

dividing the second value by a predetermined time duration to provide a quotient that represents a numerical range for the first time; and

dividing the third value by the predetermined time duration to provide a quotient that represents a numerical range for the second time.

41. The computing system of claim 40, the at least one processor configured to:

identify one or more entries within the index that include the second index key, and that include a first index key that corresponds to the range of values for the first time or the range of values for the second time or that is between the respective ranges of values for the first time and the second time.

42. The computing system of claim 31, wherein the attribute has a value that satisfies the range of values.

43. The computing system of claim 42, wherein the value of the attribute is within the range of values.

44. The computing system of claim 31, wherein determining the identifier that represents the range of values comprises dividing the value based on the difference by the second reference value to provide a quotient that represents the range of values.

45. A computing system for managing the storage of data, the computing system including:

means for indexing one or more records, the indexing including;

for each of multiple records stored in a data structure, assigning an identifier that represents a range of values based on an attribute of the record, the range being specific to the record, in which assigning an identifier for a particular record includes;

determining a value based on a difference between a value of the attribute of the particular record and a first reference value, and

determining the identifier that represents the range of values for the particular record based on a relationship between the value based on the difference and a second reference value; and

storing entries in an index associated with the data structure, each entry specifying a location of a corresponding record within the data structure, the storing including, for each entry;

storing a first index key in the entry, in which the first index key is indicative of the identifier that represents the range of values for the corresponding record, and

storing a second index key in the entry, the second index key based on a value stored in the corresponding record,

wherein the index is sorted by both (i) the first index key indicative of the identifier that represents the range of values and (ii) the second index key.

46. The computing system of claim 45, wherein the attribute is represented by a time stamp, and the range of values corresponds to a range of time.

47. The computing system of claim 46, wherein the first reference value corresponds to a time stamp from a predetermined point in time, and wherein determining a value based on the difference between the value of the attribute of the particular record and the first reference value includes:

determining a first value in time units that separates a time corresponding to the time stamp from the predetermined point in time.

48. The computing system of claim 47, wherein the second reference value corresponds to a predetermined time duration, and wherein determining the identifier that represents the range of values includes:

dividing the first value by the predetermined time duration to provide a quotient that represents the range of values.

49. The computing system of claim 45, wherein each entry specifies a location, within the data structure, of a second record that is associated with the first index key and the second index key.

50. The computing system of claim 49, wherein the record is a first record, and wherein the attribute of the first record and the attribute of the second record are each represented by a different time stamp.

51. The computing system of claim 49, the indexing including:

receiving a query that requests the retrieval of records that are associated with the second index key and that are associated with a time between a first time and a second time.

52. The computing system of claim 51, the indexing including:

assigning first and second identifiers that represent respective ranges of values for the first time and the second time.

53. The computing system of claim 45, wherein the attribute has a value that satisfies the range of values.

54. The computing system of claim 53, wherein the value of the attribute is within the range of values.