Multi-tiered targeted querying

Patent metadata

Field	Value
Publication number	US-10229155-B2
Application number	US-201414478290-A
Country	US
Kind code	B2
Filing date	Sep 5, 2014
Priority date	Sep 5, 2014
Publication date	Mar 12, 2019
Grant date	Mar 12, 2019

Abstract

Technology is disclosed for a multi-tiered querying system to target queries to systems storing data relevant to the query. A multi-tiered targeted query system comprises at least three tiers: a web tier, an aggregator tier, and a shards tier. Servers at the web tier can be configured to service user data requests and pass them to servers at the aggregator tier. Servers at the aggregator tier can be configured to determine which selected shard servers have the requested information; formulate queries for the selected shard servers; send the queries to the selected shard servers; and aggregate results from the selected shard servers. Servers at the shard tier can be configured to store data, receive queries on that data, and return results for received queries.

First claim

We claim:

1. A method for targeted database querying based on an established distribution of user activity data, comprising:
receiving, by a first server device, a request for specified user activity data, the request specifying a criterion for identifying users from which to select the user activity data and including a parameter indicating a numerical amount of users less than all users matching the criterion;
determining, by a second server device, a category of users matching the criterion;
determining, by the second server device and from among a set of multiple computing systems storing data associated with multiple users, a subset of the computing systems that store data for the category of users matching the criterion, wherein the determining includes:
storing the data for different users in the category of users at different computing systems; and
selecting, by the second server device, at least two of the subset of the computing systems based on at least the parameter such that the selected at least two of the subset of the computing systems includes data for enough users to satisfy the numerical amount indicated by the parameter, wherein the selected subset of the computing systems comprises less than all of the computing systems within the set of computing systems that are associated with users in the specified category;

formulating, by the second server device, a query to be used by the selected subset of the computing systems to retrieve the specified user activity data;
sending, by the second server device and to the at least two of the selected subset of the computing systems, the formulated query;
receiving, by the second server device, a response from the at least two of the subset of the computing systems;
aggregating, by the second server device, into a result set the received responses from the at least two of the subset of the computing system; and
responding, by the first server device, to the request for specified user activity data by providing the result set.

2. The method of claim 1 wherein the category of users comprises at least one of: friends or friends-of-friends of one or more specified users.

3. The method of claim 1 wherein selecting the subset of the computing systems comprises:
performing an initial query to determine identifiers for the users in the category of users; and
performing a subsequent query to determine the subset of the computing systems by selecting the computing systems from among the multiple computing systems that are identified in the established distribution of user activity data as storing data for the users having the determined identifiers.

4. The method of claim 3 wherein at least one of the initial query and the subsequent query are performed locally.

5. The method of claim 1 wherein the query is a first query, the method further comprising formulating a second query, different from the first query, to be used to retrieve the specified user activity data by at least one of the selected subset of the computing systems other than the one or more of the selected subset of the computing systems.

6. The method of claim 5 wherein the second query is configured to be used by the at least one of the selected subset of the computing systems by specifying, within the second query, the users in the category of users that are designated in the established data distribution as having data including at least one of the selected subset of the computing systems.

7. The method of claim 1 wherein formulating the query comprises selecting a user-to-data index to use when executing the query.

8. The method of claim 1 wherein formulating the query comprises selecting a data-to-user index to use when executing the query.

9. The method of claim 1 wherein:
the parameter indicating the numerical amount of users less than all users matching the criterion comprises:
a parameter indicating a number of users in the category of users to check for having the specified user activity data; or
a parameter indicating a percentage of users in the category of users to check for having the specified user activity data;

selecting, by the second server device, the at least two of the subset of the computing systems comprises selecting the subset based on:
each selected computing system in the subset being higher in an ordering of the computing systems in the set of multiple computing systems than one or more computing systems of the set of computing systems that are not selected for the subset; and
a determination that checking the sum of the users in the specified category associated with all the computing systems in the selected subset would satisfy the parameter indicating the number of users to check or the parameter indicating the percentage of users to check; and
the ordering is arranged by a value assigned to each computing system indicating a priority for that computing system, wherein each priority is based on the set of users within the specified category associated with that computing system.

10. The method of claim 9 wherein the priority of each computing system is based on a total count of the set of users within the specified category associated with that computing system.

11. The method of claim 9 :
wherein a weight is assigned to each user within the specified category indicating how strongly that user is within the specified category; and
wherein the priority of each computing system is based on a sum of the weights for the users within the specified category associated with that computing system.

12. The method of claim 1 wherein two or more of the computing systems in the set of multiple computing systems are databases implemented on a single server.

13. A computer-readable memory storing instructions configured to, when executed by a computing system, cause the computing system to perform operations for targeted database querying based on an established distribution of user activity data, the operations comprising:
receiving, by a first server device, a request for specified user activity data, the request specifying a criterion for identifying users from which to select the user activity data and including a parameter indicating a numerical amount of users less than all users matching the criterion;
determining, by a second server device, a category of users matching the criterion;
determining, by the second server device and from among a set of multiple computing systems storing data associated with multiple users, a subset of the computing systems that store data for the category of users matching the criterion, wherein the determining includes:
storing the data for different users in the category of users at different computing systems; and
selecting, by the second server device, at least two of the subset of the computing systems based on at least the parameter such that the selected at least two of the subset of the computing systems includes data for enough users to satisfy the numerical amount indicated by the parameter, wherein the selected subset of the computing systems comprises less than all of the computing systems within the set of computing systems that are associated with users in the specified category;

formulating, by the second server device, a query to be used by the selected subset of the computing systems to retrieve the specified user activity data;
sending, by the second server device and to at least two of the selected subset of the computing systems, the formulated query;
receiving, by the second server device, a response from at least two of the subset of the computing systems;
aggregating, by the second server device, into a result set, the rece

Assignees

• Facebook Inc

Inventors

• Sharma Arun Dattaram
• Wu Jianming
• Zhu Chunhui

Classifications

• G06F16/328

  Management therefor · CPC title

• G06F16/9535

  Search customisation based on user profiles and personalisation · CPC title

• G06F16/244 Primary

  Grouping and aggregation · CPC title

• G06F17/30412 Primary

  Physics · mapped topic

• G06F17/30867

  Physics · mapped topic