Serving cached query results based on a query portion

• US 7,797,298 B2
• Filed: 02/28/2006
• Issued: 09/14/2010
• Est. Priority Date: 02/28/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Isard, Michael Acheson, Yu, Yinzhe, Kumar, Girish, Sareen, Gaurav
• Primary Examiner(s): Mahmoudi; Tony
• Assistant Examiner(s): McCue; Brittany N
• Application Number:
  US11/363,895
• Publication Number:
  US 20070203890A1
• Time in Patent Office: 1,659 Days
• Field of Search: 707/200, 707/3
• US Class Current: 707/706
• 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 at a distributor server and from a user a beginning portion of a query comprising a number of characters at a beginning of the query;

determining at the distributor server whether the obtained portion of the query matches a predetermined ignore entry corresponding to a portion of the query that is to be ignored, the determining being performed prior to obtaining a succeeding portion of the query from the user;

if the obtained portion of the query matches the predetermined ignore entry corresponding to the portion of the query that is to be ignored, obtaining at the distributor server the succeeding portion of the query from the user, the succeeding portion of the query comprising a succeeding number of characters of the query immediately after the beginning of the query, and assigning at the distributor server the portion of the query comprising the beginning portion of the query followed by the succeeding portion of the query to a front-end server;

if the obtained portion of the query does not match the predetermined ignore entry corresponding to the portion of the query that is to be ignored, assigning at the distributor server the beginning portion of the query to a front-end server;

obtaining at the assigned front-end server and from a data structure a plurality of other queries beginning with the assigned portion of the query, the data structure including a cache of previously submitted queries, at least some of the previously submitted queries in the cache having a corresponding set of results in a results structure;

for each of the plurality of obtained queries beginning with the assigned portion of the query;

obtaining at the front-end server the corresponding set of results from the results structure if present therein;

obtaining at the front-end server the corresponding set of results from another source if the corresponding set of results is not present in the results structure;

for all of the plurality of obtained queries beginning with the assigned portion of the query, combining at the front-end server the obtained corresponding sets of results into a combined set of results; and

returning the combined set of results from the front-end server to the user,

wherein the assigned portion of the query is assigned by the distributor server to one of a plurality of front-end servers, the assigning of the assigned portion of the query to one of the plurality of front-end servers comprising;

applying the assigned portion of the query to a hash function to obtain a hash result; and

applying the hash result to a mapping function to obtain a mapping result comprising one of the plurality of front-end servers, the hash function and the mapping function operating to ensure that a particular assigned portion of a query is assigned to a articular one of the plurality of front-end servers.

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 the 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 front-end 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.

14. The method of claim 1 wherein the data structure further includes a cache of common queries, at least some of the common queries in the cache having a corresponding set of results in the results structure, the method further comprising constructing a set of common queries, the method comprising:

compiling entries deleted from the cache of previously submitted queries;

forming the 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 front-end 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.

10. A query system comprising:

a distributor server that;

receives from a user a portion of a query comprising a number of characters at a beginning of the query;

determines whether the obtained portion of the query matches a predetermined ignore entry corresponding to a portion of the query that is to be ignored, the determining being performed prior to obtaining a succeeding portion of the query from the user;

if the obtained portion of the query matches the predetermined ignore entry corresponding to a portion of the query that is to be ignored, obtains at the distributor server the succeeding portion of the query from the user, the succeeding portion of the query comprising a succeeding number of characters of the query immediately after the beginning of the query, and assigning at the distributor server a portion of the query comprising the beginning portion of the query and the succeeding portion of the query to a front-end server; and

if the obtained portion of the query does not match the predetermined ignore entry corresponding to a portion of the query that is to be ignored, assigns the beginning portion of the query to a front-end server;

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

the front-end server that;

obtains from the data structure a plurality of other queries beginning with the assigned portion of the query;

for each of the plurality of obtained queries beginning with the assigned portion of the query;

obtains at the front-end server the corresponding set of results from the results structure if present therein;

obtains at the front-end server the corresponding set of results from another source if the corresponding set of results is not present in the results structure;

for all of the plurality of obtained queries beginning with the assigned portion of the query, combines at the front-end server the obtained corresponding sets of results into a combined set of results; and

returns the combined set of results from the front-end server to the user,

the query system further comprising a plurality of the front-end servers, the assigned portion of the query being assigned by the distributor server to one of the plurality of front-end servers by;

applying the assigned portion of the query to a hash function to obtain a hash result; and

applying the hash result to a mapping function to obtain a mapping result comprising one of the plurality of front-end servers, the hash function and the mapping function operating to ensure that a particular assigned portion of a query is assigned to a particular one of the plurality of front-end servers.

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.