SYSTEMS AND METHODS FOR DETECTING MISSING DATA IN QUERY RESULTS

• US 20150032726A1
• Filed: 07/25/2013
• Published: 01/29/2015
• Est. Priority Date: 07/25/2013
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Barykin, Oleksandr, Metzler, Josh
• Granted Patent: US 9,501,521 B2
• Time in Patent Office: Days
• US Class Current: 707/722
• CPC Class Codes: G06F 16/245 Query processing

Abstract

Techniques provided herein allow for estimating data missing in query results provided in response to queries performed on data managed by a data management system. In the event that one or more leaf nodes are unable or unavailable to process a query, a final query result provided in response to the original query may be missing data that exists on those leaf nodes. A data accounting service monitors what managed data is being stored on the leaf nodes and on what leaf node. The data accounting service can estimate how much data is missing from a final query result when one or more of the leaf nodes are unable or unavailable to process a query.

Claims

1. A computer system comprising:

at least one processor; and

a memory storing instructions configured to instruct the at least one processor to perform;

receiving a data set for storage;

storing a data subset of the data set at at least one leaf node of a plurality of leaf nodes;

storing data accounting information regarding storage of the data subset at the at least one leaf node;

receiving an initial query configured to be performed on the data set;

submitting a first query on the data set to one or more of the plurality of leaf nodes, wherein the first query is based on the initial query;

performing a second query on the data accounting information, wherein the second query is based on the initial query; and

comparing a first result, received in response to the first query, to a second result, received in response to the second query, to determine whether the first result is missing data.

2. The computer system of claim 1, wherein the first result includes one or more query results received from the one or more of the plurality of leaf nodes.

3. The computer system of claim 1, wherein the data accounting information comprises storage information generated by the at least one leaf node.

4. The computer system of claim 3, further comprising receiving the storage information from the at least one leaf node.

5. The computer system of claim 1, further comprising generating the data accounting information.

6. The computer system of claim 1, wherein the storing the data accounting information comprises storing the data accounting information at one or more data accounting nodes that are separate from the plurality of leaf nodes.

7. The computer system of claim 6, wherein the performing the second query on the data accounting information comprises:

submitting the second query to the data accounting nodes; and

receiving the second result from the data accounting nodes.

8. The computer system of claim 6, wherein at least a portion of the data accounting nodes are synchronized.

9. The computer system of claim 1, wherein the data accounting information comprises one or more identifiers for the data subset stored at the at least one leaf node.

10. The computer system of claim 9, wherein the data accounting information further comprises one or more identifiers for the at least one leaf node.

11. The computer system of claim 9, wherein the data accounting information further comprises an identifier for a table associated with a data element of the data subset.

12. The computer system of claim 9, wherein the data accounting information further comprises a timestamp associated with a data element of the data subset.

13. The computer system of claim 1, further comprising receiving the second result.

14. The computer system of claim 1, wherein the second result comprises information regarding an amount of data to be expected in the first result.

15. The computer system of claim 1, wherein the initial query comprises structured query language (SQL).

16. The computer system of claim 1, further comprising determining an amount of data missing in the first result.

17. The computer system of claim 1, wherein the data set comprises log data associated with operation of a social networking system.

18. The computer system of claim 17, wherein the log data comprises one or more time-stamped data elements regarding user activity occurring on the social networking system.

19. A computer-storage medium storing computer-executable instructions that, when executed, cause a computer system to perform a computer-implemented method comprising:

receiving a data set for storage;

storing a data subset of the data set at at least one leaf node of a plurality of leaf nodes;

storing data accounting information regarding storage of the data subset at the at least one leaf node;

receiving an initial query configured to be performed on the data set;

submitting a first query on the data set to one or more of the plurality of leaf nodes, wherein the first query is based on the initial query;

performing a second query on the data accounting information, wherein the second query is based on the initial query; and

comparing a first result, received in response to the first query, to a second result, received in response to the second query, to determine whether the first result is missing data.

20. A computer implemented method comprising:

receiving, by a computer system, a data set for storage;

storing, by the computer system, a data subset of the data set at at least one leaf node of a plurality of leaf nodes;

storing, by the computer system, data accounting information regarding storage of the data subset at the at least one leaf node;

receiving, by the computer system, an initial query configured to be performed on the data set;

submitting, by the computer system, a first query on the data set to one or more of the plurality of leaf nodes, wherein the first query is based on the initial query;

performing, by the computer system, a second query on the data accounting information, wherein the second query is based on the initial query; and

comparing, by the computer system, a first result, received in response to the first query, to a second result, received in response to the second query, to determine whether the first result is missing data.