Classification of data in main memory database systems

• US 9,892,146 B2
• Filed: 11/12/2016
• Issued: 02/13/2018
• Est. Priority Date: 06/30/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Levandoski, Justin Jon, Larson, Per-Ake
• Primary Examiner(s): Mackes, Kris
• Assistant Examiner(s): NGUYEN, MERILYN P
• Application Number:
  US15/350,032
• Publication Number:
  US 20170060925A1
• Time in Patent Office: 458 Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

Various technologies described herein pertain to classifying data in a main memory database system. A record access log can include a sequence of record access observations logged over a time period from a beginning time to an end time. Each of the record access observations can include a respective record ID and read timestamp. The record access log can be scanned in reverse from the end time towards the beginning time. Further, access frequency estimate data for records corresponding to record IDs read from the record access log can be calculated. The access frequency estimate data can include respective upper bounds and respective lower bounds of access frequency estimates for each of the records. Moreover, the records can be classified based on the respective upper bounds and the respective lower bounds of the access frequency estimates, such that K records can be classified as being frequently accessed records.

Claims

1. A method of managing storage of records in a main memory database system, comprising:

logging, in a record access log, a sequence of record access observations of accesses of the records in the main memory database system;

identifying a subset of the records in the main memory database system to migrate from memory to secondary storage based on the sequence of the record access observations logged in the record access log over a time period from a beginning time to an end time, the subset of the records to migrate being identified based on classification of the records in the main memory database system, the classification of the records being based on access frequency estimate data updated as the record access log is scanned in reverse from the end time towards the beginning time, the subset of the records to migrate being identified prior to a record access observation for the beginning time being read during scanning of the record access log in reverse from the end time towards the beginning time; and

migrating the subset of the records in the main memory database system from the memory to the secondary storage.

2. The method of claim 1, further comprising:

logging the sequence of the record access observations of the accesses of the records in the main memory database system during runtime of the main memory database system; and

identifying the subset of the records in the main memory database system to migrate from the memory to the second storage as part of an offline analysis.

3. The method of claim 2, further comprising:

performing the offline analysis utilizing one or more computing machines, the one or more computing machines being separate from a computing system that runs a transactional workload of the main memory database system.

4. The method of claim 1, further comprising:

sampling the accesses of the records in the main memory database system, wherein the sequence of the record access observations logged in the record access log comprises the accesses of the records in the main memory database system as sampled.

5. The method of claim 1, wherein identifying the subset of the records in the main memory database system to migrate further comprises:

discontinuing scanning the record access log prior to reading the record access observation for the beginning time.

6. The method of claim 1, wherein the record access log is divided into a plurality of record access log partitions, and wherein identifying the subset of the records in the main memory database system to migrate further comprises:

updating the access frequency estimate data as the plurality of record access log partitions are scanned in reverse.

7. The method of claim 1, wherein the access frequency estimate data comprises respective upper bounds of access frequency estimates and respective lower bounds of the access frequency estimates for one or more of the records.

8. The method of claim 7, wherein identifying the subset of the records in the main memory database system to migrate further comprises:

calculating an upper bound of an access frequency estimate for a corresponding record at a given time slice by assuming that the corresponding record is encountered at every time slice moving backward in the record access log from the given time slice.

9. The method of claim 7, wherein identifying the subset of the records in the main memory database system to migrate further comprises:

calculating a lower bound of an access frequency estimate for a corresponding record at a given time slice by assuming that the corresponding record is not encountered again moving backward in the record access log from the time slice.

10. The method of claim 1, wherein the access frequency estimate data comprises respective ranges of access frequency estimates for one or more of the records.

11. The method of claim 1, wherein identifying the subset of the records in the main memory database system to migrate further comprises:

storing the access frequency estimate data in a table; and

removing a portion of the access frequency estimate data from the table as the record access log is scanned in reverse.

12. The method of claim 1, wherein identifying the subset of the records in the main memory database system to migrate further comprises:

determining an accept threshold; and

discarding a previously unseen record read during scanning at or beyond the accept threshold, wherein the accept threshold represents a time slice in the record access log.

13. A computing system, comprising:

a data repository that comprises a record access log, wherein the record access log comprises a sequence of record access observations of accesses of records in a main memory database system logged over a time period from a beginning time to an end time;

at least one processor; and

memory that comprises computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including;

scanning the record access log in reverse from the end time towards the beginning time;

for each time slice scanned as the record access log is scanned in reverse, at least one of;

calculating access frequency estimate data for one or more of the records;

or

refining a calculation of the access frequency estimate data for the one or more of the records;

classifying the records based on the access frequency estimate data as the record access log is scanned in reverse;

identifying a subset of the records in the main memory database system to migrate from memory to secondary storage based on the classifying of the records, wherein the scanning of the record access log is discontinued prior to reading a record access observation for the beginning time.

14. The computing system of claim 13, the memory further comprising computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including:

storing the access frequency estimate data in a table; and

removing a portion of the access frequency estimate data from the table as the record access log is scanned in reverse.

15. The computing system of claim 13, the memory further comprising computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including:

determining an accept threshold; and

discarding a previously unseen record read during the scanning at or beyond the accept threshold, wherein the accept threshold represents a particular time slice in the record access log.

16. The computing system of claim 13, the memory further comprising computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including:

discontinuing the scanning of the record access log prior to reading the record access observation for the beginning time based on the classifying of the records.

17. The computing system of claim 13, wherein the access frequency estimate data comprises respective upper bounds of access frequency estimates and respective lower bounds of the access frequency estimates.

18. The computing system of claim 13, wherein the access frequency estimate data comprises respective ranges of access frequency estimates.

19. A computing system, comprising:

a data repository that comprises a record access log, wherein the record access log comprises a sequence of record access observations of accesses of records in a main memory database system logged over a time period from a beginning time to an end time;

at least one processor; and

memory that comprises computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including;

scanning the record access log in reverse from the end time towards the beginning time;

for each time slice scanned as the record access log is scanned in reverse, at least one of;

calculating access frequency estimate data for one or more of the records;

or

refining a calculation of the access frequency estimate data for the one or more of the records;

wherein the access frequency estimate data is stored in a table;

classifying the records based on the access frequency estimate data as the record access log is scanned in reverse;

removing a portion of the access frequency estimate data from the table as the record access log is scanned in reverse;

identifying a subset of the records in the main memory database system to migrate from memory to secondary storage based on the classifying of the records.

20. The computing system of claim 19, the memory further comprising computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including:

discontinuing the scanning of the record access log prior to reading a record access observation for the beginning time.