Classification of data in main memory database systems

A system that classifies data in a main memory database system, comprising:

• a data repository that comprises a record access log, wherein the record access log comprises a sequence of record access observations logged over a time period from a beginning time to an end time, wherein each of the record access observations comprises a respective record identifier (ID) and access timestamp;
• a backward scan component that scans the record access log in reverse from the end time towards the beginning time;
• a frequency estimation component that calculates access frequency estimate data for records corresponding to record IDs read from the record access log, wherein the access frequency estimate data comprises respective upper bounds of access frequency estimates and respective lower bounds of the access frequency estimates for each of the records, wherein the access frequency estimates are based on exponential smoothing;
• and
• a bound evaluation component that classifies the records based on the respective upper bounds of the access frequency estimates and the respective lower bounds of the access frequency estimates, wherein K records are classified as being frequently accessed records.

A computer-readable storage medium including computer-executable instructions that, when executed by a processor, cause the processor to perform acts including:

• causing a plurality of worker threads to scan respective record access log partitions in reverse from an end time towards a beginning time, wherein the respective record access log partitions comprises respective sequences of record access observations logged over a time period from the beginning time to the end time;
• causing the plurality of worker threads to report statistics pertaining to records respectively included in the record access log partitions, wherein the statistics comprise at least a first number of records that have lower bounds of access frequency estimates above or equal to a threshold and a second number of records that have upper bounds of the access frequency estimates above the threshold;
• until a first sum of the first number of records reported from the plurality of worker threads equals K, and until the first sum of the first number of records reported from the plurality of worker threads equals a second sum of the second number of records reported from the plurality of worker threads, at least one of:
• adjusting the threshold;
• or
• causing the plurality of worker threads to further scan the respective record access log partitions in reverse towards the beginning time;
• and
• outputting record identifiers (IDs) for records with upper bounds of the access frequency estimates above the threshold when the first sum equals K and the first sum equals the second sum.