Serving cached query results based on a query portion

• US 20070203890A1
• Filed: 02/28/2006
• Published: 08/30/2007
• Est. Priority Date: 02/28/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Isard, Michael, Kumar, Girish, Sareen, Gaurav, Yu, Yinzhe
• Granted Patent: US 7,797,298 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

The embodiments contemplate a system and method for obtaining related results for a portion of a query and for generating an updated set of queries for a cache of a server. Other queries beginning with the portion of the query may be identified and obtained from a data structure that includes a server cache and a set of common queries. Once the other queries are identified, results for the other queries are obtained from the server cache or from a back-end database. A set of common queries, which may include deleted and additional queries, may be utilized to generate the updated set of queries for the server. Both missing queries and deleted queries that may belong to the server based on an assignment function are inserted into a queue, which is later delivered to the cache of the server. The transfer may occur during a low-activity or idle state.

Claims

1. A method of providing query results, the method comprising:

obtaining a portion of a query;

assigning the portion of the query to a server;

obtaining other queries beginning with the portion of the query; and

obtaining results of some or all of the other queries based on the portion of the query.

2. The method of claim 1, further comprising:

computing a representation of the portion of the query;

wherein assigning the portion of the query to a server comprises assigning the portion of the query to a server based upon the representation.

3. The method of claim 1, further comprising:

determining if the portion of the query matches a predetermined entry; and

assigning succeeding characters as the portion of the query.

4. The method of claim 1, further comprising:

storing cache queries and a set of common queries in a data structure;

wherein obtaining other queries beginning with the portion of the query comprises obtaining other queries beginning with the portion of the query from the data structure.

5. The method of claim 4, further comprising:

modifying the data structure to reflect changes made to the cache queries and changes made to the set of common queries.

6. The method of claim 4, further comprising:

storing the cache queries and the set of common queries according to a frequency of use; and

displaying the results of each of the other queries beginning with the portion of the query in a descending order of the frequency of use.

7. The method of claim 1, wherein obtaining results of each of the other queries beginning with the portion of the query comprises obtaining results of each of the other queries from a cache of the server.

8. The method of claim 1, wherein obtaining results of each of the other queries beginning with the portion of the query comprises obtaining results of each of the other queries from a back-end server.

9. The method of claim 1, further comprising:

providing an empty result if the other queries beginning with the portion of the query cannot be obtained.

10. A query system, comprising:

a distributor server that receives a portion of a query;

a data structure that stores cache queries and a set of common queries;

a results structure that provides results for the cache queries and the set of common queries; and

a front-end server that consults the data structure and the results structure to provide related results based on the portion of the query.

11. The system of claim 10, further comprising a back-end database.

12. The system of claim 10, wherein the distributor server assigns the portion of the query to the front-end server.

13. The system of claim 10, wherein the portion of the query is a prefix of the query.

14. A method of constructing a set of common queries, the method comprising:

compiling entries deleted from a cache of a front-end server;

forming a set of common queries comprised of the deleted entries, wherein the deleted entries are from a predetermined time range; and

distributing the set of common queries to another front-end server.

15. The method of claim 14, wherein distributing the set of common queries to another front-end server comprises distributing the set of common queries to multiple front-end servers.

16. The method of claim 14, further comprising:

generating additional queries based on a predetermined list; and

adding the additional queries to the set of common queries.

17. The method of claim 14, further comprising:

computing an updated set of queries for a front-end server, wherein the updated set of queries is comprised of assigned queries in the set of common queries that are assigned to the front-end server; and

constructing a data structure for the front-end server, wherein the contents of the data structure are comprised of the updated set of queries and cache queries.

18. The method of claim 17, further comprising:

computing missing queries, wherein the missing queries belong in a cache of the front-end server; and

inserting the missing queries a queue.

19. The method of claim 18, further comprising:

removing the missing queries from the queue;

sending the missing queries from the queue to a back-end database; and

inserting the missing queries in the cache of the front-end server.

20. The method of claim 17, further comprising:

determining if an expired query that is expired from the cache of the server belongs to the updated set of queries;

inserting the expired query into a queue.

removing the expired query from the queue;

sending the expired query from the queue to a back-end database; and

inserting the expired query in the cache of the front-end server.