Memory analytics

• US 10,157,209 B1
• Filed: 07/07/2015
• Issued: 12/18/2018
• Est. Priority Date: 07/07/2014
• Status: Active Grant

• Current Assignee: Microstrategy Incorporated
• Original Assignee: Microstrategy Incorporated
• Inventors: Cappiello, Scott, Du, Yi
• Primary Examiner(s): Pham, Tuan A
• Assistant Examiner(s): Dang, Thai V
• Application Number:
  US14/792,906
• Time in Patent Office: 1,260 Days
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/248 Presentation of query results

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for memory analytics are disclosed. In one aspect, a method includes receiving input that requests a particular number of data items that are highest ranking in the data storage system based on a characteristic. The method includes accessing sets of data items to use in satisfying the request by selecting, from each of the independent data partitions, a set of data items that includes less than the particular number of data items that are highest ranking in the respective independent data partition based on the characteristic. The method includes comparing the sets of data items accessed from the plurality of independent data partitions. The method includes selecting the particular number of data items that are ranked highest based on the characteristic. The method includes providing, for output, the selected particular number of data items.

Claims

1. A computer-implemented method comprising:

receiving, by a data storage system that includes a number of independent data partitions that each store a stored number of data items, input that requests a number of data items that are highest ranking in the data storage system based on a characteristic of each data item;

determining a load of the data storage system;

based on the load of the data storage system, determining a confidence threshold that reflects an acceptable probability that a given number of highest ranking data items from each independent data partition includes the requested number of data items that are highest ranking in the data storage system;

based on (i) the number of independent data partitions, (ii) the stored number of data items in each independent data partition, and (iii) the requested number of data items, determining a particular number of highest ranking data items to request from each of the independent data partitions to satisfy the confidence threshold that all of the highest ranking data items requested from the independent data partitions include the requested number of data items that are highest ranking in the data storage system;

accessing, from each of the independent data partitions, the particular number of the highest ranking data items;

comparing all of the highest ranking data items accessed from the independent data partitions;

based on comparing all of the highest ranking data items accessed from the independent data partitions, selecting, from among all of the highest ranking data items accessed from the independent data partitions, the requested number of the data items that are ranked highest based on the characteristic;

providing, for output, the selected number of the data items;

accessing, from each of the independent data partitions, the requested number of the data items that are ranked highest in each independent data partition; and

based on the requested number of the data items that are ranked highest in each independent data partition, increasing or decreasing, for subsequent data requests, the particular number of the highest ranking data items selected from each of the independent data partitions.

2. The method of claim 1, wherein the particular number of highest ranking data items accessed from each of the independent data partitions is equal to the number of the data items that are highest based on the characteristic.

3. The method of claim 1, comprising:

associating each of the independent data partitions with at least one of a plurality of processing units such that data items in a corresponding independent data partitions are processed by the at least one of the plurality of processing units; and

providing a query execution engine for causing the plurality of processing units to execute, in parallel, a series of data requests to the independent data partitions.

4. The method of claim 3, wherein the independent data partitions are distributed over a plurality of nodes, each node comprising one or more of the plurality of processing units.

5. The method of claim 3, wherein:

determining a load of the data storage system comprises monitoring a processing status of the plurality of processing units, and

determining the confidence threshold that reflects the acceptable probability that the given number of highest ranking data items from each independent data partition includes the requested number of data items that are highest ranking in the data storage system comprises balancing a processing load across the plurality of processing units.

6. The method of claim 1, wherein providing, for output, the selected number of data items comprises presenting, within a dashboard, a visualization of the selected number of data items.

7. The method of claim 6, comprising:

generating a data query based on data inputted into the dashboard.

8. The method of claim 1, comprising:

identifying independent data partitions that are associated with each of the selected number of the data items;

determining that each of the selected number of the data items is associated with a same independent data partition; and

accessing each data item that is stored in the same independent data partition.

9. The method of claim 1, wherein the particular number of highest ranking data items is less than the requested number of data items that are highest ranking in the data storage system based on the characteristic.

10. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

receiving, by a data storage system that includes a number of independent data partitions that each store a stored number of data items, input that requests a number of data items that are highest ranking in the data storage system based on a characteristic of each data item;

determining a load of the data storage system;

based on the load of the data storage system, determining a confidence threshold that reflects an acceptable probability that a given number of highest ranking data items from each independent data partition includes the requested number of data items that are highest ranking in the data storage system;

based on (i) the number of independent data partitions, (ii) the stored number of data items in each independent data partition, and (iii) the requested number of data items, determining a particular number of highest ranking data items to request from each of the independent data partitions to satisfy the confidence threshold that all of the highest ranking data items requested from the independent data partitions include the requested number of data items that are highest ranking in the data storage system;

accessing, from each of the independent data partitions, the particular number of the highest ranking data items;

comparing all of the highest ranking data items accessed from the independent data partitions;

based on comparing all of the highest ranking data items accessed from the independent data partitions, selecting, from among all of the highest ranking data items accessed from the independent data partitions, the requested number of the data items that are ranked highest based on the characteristic;

providing, for output, the selected number of the data items;

accessing, from each of the independent data partitions, the requested number of the data items that are ranked highest in each independent data partition; and

based on the requested number of the data items that are ranked highest in each independent data partition, increasing or decreasing, for subsequent data requests, the particular number of the highest ranking data items selected from each of the independent data partitions.

11. The system of claim 10, wherein the particular number of highest ranking data items accessed from each of the independent data partitions is equal to the number of the data items that are highest based on the characteristic.

12. The system of claim 10, wherein the operations further comprise:

associating each of the independent data partitions with at least one of a plurality of processing units such that data items in a corresponding independent data partitions are processed by the at least one of the plurality of processing units; and

providing a query execution engine for causing the plurality of processing units to execute, in parallel, a series of data requests to the independent data partitions.

13. The system of claim 10, wherein providing, for output, the selected number of data items comprises presenting, within a dashboard, a visualization of the selected number of data items.

14. The system of claim 13, wherein the operations further comprise:

generating a data query based on data inputted into the dashboard.

15. The system of claim 12, wherein the independent data partitions are distributed over a plurality of nodes, each node comprising one or more of the plurality of processing units.

16. The system of claim 12, wherein:

determining a load of the data storage system comprises monitoring a processing status of the plurality of processing units, and

determining the confidence threshold that reflects the acceptable probability that the given number of highest ranking data items from each independent data partition includes the requested number of data items that are highest ranking in the data storage system comprises balancing a processing load across the plurality of processing units.

17. The system of claim 10, wherein the operations further comprise:

identifying independent data partitions that are associated with each of the selected number of the data items;

determining that each of the selected number of the data items is associated with a same independent data partition; and

accessing each data item that is stored in the same independent data partition.

18. The system of claim 10, wherein the particular number of highest ranking data items is less than the requested number of data items that are highest ranking in the data storage system based on the characteristic.

19. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

receiving, by a data storage system that includes a number of independent data partitions that each store a stored number of data items, input that requests a number of data items that are highest ranking in the data storage system based on a characteristic of each data item;

determining a load of the data storage system;

based on the load of the data storage system, determining a confidence threshold that reflects an acceptable probability that a given number of highest ranking data items from each independent data partition includes the requested number of data items that are highest ranking in the data storage system;

based on (i) the number of independent data partitions, (ii) the stored number of data items in each independent data partition, and (iii) the requested number of data items, determining a particular number of highest ranking data items to request from each of the independent data partitions to satisfy the confidence threshold that all of the highest ranking data items requested from the independent data partitions include the requested number of data items that are highest ranking in the data storage system;

accessing, from each of the independent data partitions, the particular number of the highest ranking data items;

comparing all of the highest ranking data items accessed from the independent data partitions;

based on comparing all of the highest ranking data items accessed from the independent data partitions, selecting, from among all of the highest ranking data items accessed from the independent data partitions, the requested number of the data items that are ranked highest based on the characteristic;

providing, for output, the selected number of the data items;

accessing, from each of the independent data partitions, the requested number of the data items that are ranked highest in each independent data partition; and

based on the requested number of the data items that are ranked highest in each independent data partition, increasing or decreasing, for subsequent data requests, the particular number of the highest ranking data items selected from each of the independent data partitions.

20. The medium of claim 19, wherein the particular number of highest ranking data items accessed from each of the independent data partitions is equal to the number of the data items that are highest based on the characteristic.