Indexing based on object type

• US 9,158,801 B2
• Filed: 07/27/2012
• Issued: 10/13/2015
• Est. Priority Date: 07/27/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Lassen, Soren Bogh, Ahrens, Spencer Greg
• Primary Examiner(s): LIAO, JASON G
• Application Number:
  US13/560,212
• Publication Number:
  US 20140032563A1
• Time in Patent Office: 1,173 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2291 User-Defined Types; Storage management thereof
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

In one embodiment, a method includes maintaining data stores for objects of a social-networking system, each data store being configured to store objects of a particular one of multiple object types indexed by a search index; receiving an object; identifying an object type of the received object; storing the received object in at least one data store being configured to store objects of the identified object type; and updating the search index of the at least one data store based on the received object.

Claims

1. A method comprising, by one or more computing devices:

receiving a search request for at least one of a plurality of objects of a social-networking system, wherein;

the social-networking system comprises a social graph that comprises a plurality of nodes and a plurality of edges connecting the nodes;

each object corresponds to a node of the social graph;

the objects of the social-networking system are stored by a plurality of partitions of a database that are each configured to store objects of only a particular one of a plurality of object types;

the objects in the partitions are indexed by a plurality of search indices that each index only a particular one of the plurality of partitions; and

each search index indexes objects with information identifying edges connecting the nodes represented by the objects to other nodes in the social graph and with information identifying the other nodes;

determining one or more search queries based on the search request wherein, each search query has a single object type for its expected search results;

sending each search query to the partition that is configured to store objects of only the particular one of the object types that the search query has for its expected search results;

for each search query, attempting to retrieve one or more search results from the partition that the search query was sent to, wherein the search results were identified using the search index that indexes only the partition; and

aggregating search results retrieved from the partitions that the search queries were sent to.

2. The method of claim 1, wherein the plurality of object types comprise user profile, photo, post, web page, or application.

3. The method of claim 1, wherein one or more of the search queries each comprise a nested search query.

4. The method of claim 1, wherein sending each search query to the partition that is configured to store objects of only the particular one of the object types that the search query has for its expected search results comprises sending the search query to the search index that indexes only the partition that is configured to store objects of only the particular one of the object types that the search query has for its expected search results.

5. The method of claim 1, wherein each partition comprises the search index that indexes only the partition.

6. The method of claim 1, wherein the information identifying edges that each search index indexes object with comprises relationships indicated by edges.

7. The method of claim 1, wherein each search index is hosted by a respective one of a plurality of servers.

8. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

receive a search request for at least one of a plurality of objects of a social-networking system, wherein;

the social-networking system comprises a social graph that comprises a plurality of nodes and a plurality of edges connecting the nodes;

each object corresponds to a node of the social graph;

the objects of the social-networking system are stored by a plurality of partitions of a database that are each configured to store objects of only a particular one of a plurality of object types;

the objects in the partitions are indexed by a plurality of search indices that each index only a particular one of the plurality of partitions; and

each search index indexes objects with information identifying edges connecting the nodes represented by the objects to other nodes in the social graph and with information identifying the other nodes;

determine one or more search queries based on the search request wherein, each search query has a single object type for its expected search results;

send each search query to the partition that is configured to store objects of only the particular one of the object types that the search query has for its expected search results;

for each search query, attempt to retrieve one or more search results from the partition that the search query was sent to, wherein the search results were identified using the search index that indexes only the partition; and

aggregate search results retrieved from the partitions that the search queries were sent to.

9. The media of claim 8, wherein the plurality of object types comprise user profile, photo, post, web page, or application.

10. The media of claim 8, wherein one or more of the search queries each comprise a nested search query.

11. The media of claim 8, wherein sending each search query to the partition that is configured to store objects of only the particular one of the object types that the search query has for its expected search results comprises sending the search query to the search index that indexes only the partition that is configured to store objects of only the particular one of the object types that the search query has for its expected search results.

12. The media of claim 8, wherein each partition comprises the search index that indexes only the partition.

13. The media of claim 8, wherein the information identifying edges that each search index indexes object with comprises relationships indicated by edges.

14. The media of claim 8, wherein each search index is hosted by a respective one of a plurality of servers.

15. A system comprising:

one or more processors; and

one or more computer-readable non-transitory storage media embodying software that is operable when executed by the processors to;

receive a search request for at least one of a plurality of objects of a social-networking system, wherein;

the social-networking system comprises a social graph that comprises a plurality of nodes and a plurality of edges connecting the nodes;

each object corresponds to a node of the social graph;

the objects of the social-networking system are stored by a plurality of partitions of a database that are each configured to store objects of only a particular one of a plurality of object types;

the objects in the partitions are indexed by a plurality of search indices that each index only a particular one of the plurality of partitions; and

each search index indexes objects with information identifying edges connecting the nodes represented by the objects to other nodes in the social graph and with information identifying the other nodes;

determining one or more search queries based on the search request wherein, each search query has a single object type for its expected search results;

sending each search query to the partition that is configured to store objects of only the particular one of the object types that the search query has for its expected search results;

for each search query, attempting to retrieve one or more search results from the partition that the search query was sent to, wherein the search results were identified using the search index that indexes only the partition; and

aggregate search results retrieved from the partitions that the search queries were sent to.

16. The system of claim 15, wherein the plurality of object types comprise user profile, photo, post, web page, or application.

17. The system of claim 15, wherein one or more of the search queries each comprise a nested search query.

18. The system of claim 15, wherein sending each search query to the partition that is configured to store objects of only the particular one of the object types that the search query has for its expected search results comprises sending the search query to the search index that indexes only the partition that is configured to store objects of only the particular one of the object types that the search query has for its expected search results.

19. The system of claim 15, wherein each partition comprises the search index that indexes only the partition.

20. The system of claim 15, wherein the information identifying edges that each search index indexes object with comprises relationships indicated by edges.