Distributed pre-cached query results and refresh method

• US 7,302,425 B1
• Filed: 06/09/2003
• Issued: 11/27/2007
• Est. Priority Date: 06/09/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dani, Nishant, Fu, Xiongjian, Bernstein, Simon D.
• Primary Examiner(s): Alam; Hosain
• Assistant Examiner(s): Ahluwalia; Navneet K
• Application Number:
  US10/458,511
• Time in Patent Office: 1,632 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205, 711/129, 711/146
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/3349 Reuse of stored results of previous queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Query results are pre-cached for a substantial portion of or all queries that are likely to be issued by users. One query can be entirely different from another query, yet because corresponding query results are pre-cached, the database need not be accessed, improving response performance. Pre-cached queries are also distributed into multiple partitions to apportion work among multiple computing machines to further enhance performance and provide redundancy in case of the failure of any particular partition. Pre-cached query results are selectively refreshed so that users may enjoy up-to-date information by focusing on queries that are popular as well as queries that are old.

Claims

1. A networked system for responding to a query of a user, comprising:

an application executing on a computer for issuing the query;

software executing on computers of the networked system for unraveling a protocol envelope of the query by stripping from the query protocol-specific codes into a form suitable for pre-caching processing by using a tag-based language translator;

multiple servers on which multiple partitions are distributed and not on one server, each partition including a primary partition and a secondary partition, the second partition being a duplicate of the primary partition, each primary partition being located on one server and each secondary partition being located on another server, each partition containing a subset of a set of pre-cached query results;

a service executing on another computer for responding to the query by providing a corresponding query result, the corresponding query result being found in a set of pre-cached query results, the query being mapped to a query permutation using a hashing function which uses a query search space that describes the layout and the associations of query permutations and queries, each pre-cached query result being generated by executing a corresponding query prior to issuance of the query; and

a refresh component executing on a further computer for refreshing query permutations that are popular with users based on the number of times the users have requested them and then refreshing those whose have oldest dates of access by users.

2. The networked system of claim 1, wherein the application is a Web browser.

3. The networked system of claim 1, further comprising a network on which the query is transmitted from the application to the service.

4. The networked system of claim 1, wherein the service is a member directory service, which contains profiles of members of an online service.

5. The networked system of claim 4, wherein the corresponding query result is a portion of the profile of a member of the online service.

6. A computer system for responding to queries of users, comprising:

multiple servers for responding to the queries of the users, a protocol envelope of the queries being unraveled by computers of the multiple servers by stripping from the queries protocol-specific codes into a form suitable for pre-caching processing by using a tag-based language translator, the queries being mapped to query permutations using a hashing function which uses a query search space that describes the layout and the associations of the query permutations and the queries;

multiple servers on which multiple partitions are distributed and not on one server, each partition including a primary partition and a secondary partition, the second partition being a duplicate of the primary partition, each primary partition being located on one server and each secondary partition being located on another server, each partition containing a portion of pre-cached query results, each pre-cached query result being generated by executing a corresponding query prior to the time the query is requested by a user; and

a refresh component executing on a computer for refreshing the query permutations that are popular with users based on the number of times the users have requested them and then refreshing those whose have oldest dates of access by users.

7. The computer system of claim 6, wherein each pre-cached query result is stored in a file, each file being stored in a remotely accessible directory on a server.

8. The computer system of claim 7, wherein the file has a file name, the file name being a numerical transformation of a query whose query result is contained in the file.

9. A computer system for responding to queries of users, comprising:

a hashing component executing on the computer system for mapping a query to a partition on a server, the query being mapped to a query permutation using the hashing component which uses a query search space that describes the layout and the associations of query permutations and queries;

a lookup component executing on the computer system for mapping the query to a filename of a file in a partition and on the server, the file containing a query result for the query, the query result being pre-cached prior to the issuance of the query by a user;

multiple servers on which multiple partitions are distributed and not on one server, each partition including a primary partition and a secondary partition, the second partition being a duplicate of the primary partition, each primary partition being located on one server and each secondary partition being located on another server, each partition containing a portion of pre-cached query results;

a refresh component executing on the computer system for refreshing the query permutations that are popular with users based on the number of times the users have requested them and then refreshing those whose have oldest dates of access by users; and

software executing on computers of the computer system for unraveling a protocol envelope of the query by stripping from a query protocol-specific codes into a form suitable for pre-caching processing by using a tag-based language translator.

10. The computer system of claim 9, further comprising a refresh file in which a mapping is described regarding the correspondence of queries;

access counts, each being indicative of the number of times the query result is retrieve by users since the last date on which the query result was refreshed; and

update timestamps, each being indicative of the last date on which the query result was refreshed.

11. The computer system of claim 9, further comprising a query search space.

12. The computer system of claim 9, further comprising a pre-cache partition file in which a mapping is described regarding the correspondence of servers and partitions allocated to the servers.

13. A computer-implemented method for responding to queries, comprising:

unraveling a protocol envelope of queries by a computer by stripping from the queries protocol-specific codes into a form suitable for pre-caching processing by using a tag-based language translator;

pre-caching query results by another computer by executing the queries prior to any search requests;

distributing the pre-cached query results by a further computer into multiple partitions;

responding to a query by obtaining a corresponding pre-cached query result using multiple servers on which multiple partitions are distributed and not on one server, each partition including a primary partition and a secondary partition, the second partition being a duplicate of the primary partition, each primary partition being located on one server and each secondary partition being located on another server, each partition containing a portion of pre-cached query results, the query being mapped to a query permutation using a bashing function which uses a query search space that describes the layout and the associations of query permutations and queries; and

refreshing the query permutations by a refresh component running on an additional computer that are popular with users based on the number of times the users have requested them and then refreshing those whose have oldest dates of access by users.

14. The method of claim 13, further comprising creating an identifier for a query permutation which corresponds to the query.

15. The method of claim 14, further comprising determining the validity of the query permutation.

16. The method of claim 15, further comprising determining the search string that would invoke the query permutation.

17. The method of claim 16, further comprising creating a query search space to capture all valid query permutations.

18. The method of claim 17, further comprising assigning each partition, which is defined as a primary partition, to a server and a copy of the partition, which is defined as a secondary partition, to another server.

19. The method of claim 18, further comprising creating a pre-cache partition file to capture the partition assignments among partitions and servers.

20. The method of claim 19, further comprising executing a valid query to obtain a query result.

21. The method of claim 20, further comprising storing the query result in a file, whose name is the identifier of the executed query.

22. The method of claim 21, further comprising placing the file in a remotely accessible directory at a server assigned to store a corresponding partition.

23. The method of claim 13, further comprising examining a query result file, on start-up, for a corresponding query.

24. The method of claim 23, further comprising queuing the query to a database to generate a query result file if the query result file is missing and there is not another query result file that can be duplicated.

25. The method of claim 24, further comprising copying another query result file from another partition if the query result file is missing and there is another query result file that can be duplicated.

26. The method of claim 25, further comprising discarding the query result file if the query result file has expired.

27. The method of claim 26, further comprising copying another query result file from another partition if the query result file has not expired and there is another query result file that can be duplicated.

28. The method of claim 13, further comprising receiving the query and distributing the query via a load balancing system to a server.

29. The method of claim 28, further comprising obtaining a partition at which the query result for the query resides by inputting the query as a search string into a hashing function.

30. The method of claim 29, further comprising determining a server on which resides a primary partition that contains the query result.

31. The method of claim 30, further comprising accessing a database to execute the query if neither the primary partition nor a secondary partition is available to access the query result.

32. The method of claim 30, further comprising mapping a search string to a query identifier, which is the name of a file containing the query result.

33. The method of claim 32, further comprising incrementing an access count for the query and updating a timestamp for a query result indicating a date of refresh.

34. The method of claim 33, further comprising formatting the query result into a format presentable to a user.

35. The method of claim 13, further comprising sorting a set of queries in the order of their count values.

36. The method of claim 35, further comprising refreshing a set of query results in a primary partition that corresponds to the set of queries that have the highest count values, the act of refreshing terminating when a predetermined number of query results have been refreshed.

37. The method of claim 36, further comprising copying the set of refreshed query results to a secondary partition from the primary partition.

38. The method of claim 13, further comprising sorting a set of queries in the order of their staleness.

39. The method of claim 38, further comprising refreshing a set of query results in a primary partition that corresponds to the set of queries that have the oldest timestamps, the act of refreshing terminating when a predetermined number of query results have been refreshed.

40. The method of claim 39, further comprising copying the set of refreshed query results to a secondary partition from the primary partition.

41. A computer-readable medium having computer-readable instructions stored thereon that implement a method for responding to queries, the method comprising:

unraveling a protocol envelope of queries by executing software on computers for stripping from the queries protocol-specific codes into a form suitable for pre-caching processing by using a tag-based language translator;

pre-caching query results by executing the queries prior to any search requests using software executing on a computer;

distributing the pre-cached query results into multiple partitions using software executing on the computer;

responding to a query by obtaining a corresponding pre-cached query result using multiple servers on which multiple partitions are distributed and not on one server, each partition including a primary partition and a secondary partition, the second partition being a duplicate of the primary partition, each primary partition being located on one server and each secondary partition being located on another server, each partition containing a portion of pre-cached query results, the query being mapped to a query permutation using a hashing function which uses a query search space that describes the layout and the associations of query permutations and queries; and

selectively refreshing pre-cached query results using a refresh component executing on the computer by focusing on the queries that have high frequency of use and the queries that are old.

42. The method of claim 41, further comprising creating an identifier for a query permutation which corresponding to the query.

43. The method of claim 42, further comprising determining the validity of the query permutation.

44. The method of claim 43, further comprising determining the search string that would invoke the query permutation.

45. The method of claim 44, further comprising creating a query search space to capture all valid query permutations.

46. The method of claim 45, further comprising assigning each partition, which is defined as a primary partition, to a server and a copy of the partition, which is defined as a secondary partition, to another server.

47. The method of claim 46, further comprising creating a pre-cache partition file to capture the partition assignments among partitions and servers.

48. The method of claim 47, further comprising executing a valid query to obtain a query result.

49. The method of claim 48, further comprising storing the query result in a file, whose name is the identifier of the executed query.

50. The method of claim 49, further comprising placing the file in a remotely accessible directory at a server assigned to store a corresponding partition.

51. The method of claim 41, further comprising examining a query result file, on start-up, for a corresponding query.

52. The method of claim 51, further comprising queuing the query to a database to generate a query result file if the query result file is missing and there is not another query result file that can be duplicated.

53. The method of claim 52, further comprising copying another query result file from another server containing the partition if the query result file is missing and there is another query result file that can be duplicated.

54. The method of claim 53, further comprising discarding the query result file if the query result file has expired.

55. The method of claim 54, further comprising copying another query result file from another partition if the query result file has not expired and there is another query result file that can be duplicated.

56. The method of claim 41, further comprising receiving the query and distributing the query via a load balancing system to a server.

57. The method of claim 56, further comprising obtaining a partition at which the query result for the query resides by inputting the query as a search string into a hashing function.

58. The method of claim 57, further comprising determining a server on which resides a primary partition that contains the query result.

59. The method of claim 58, further comprising accessing a database to execute the query if neither a primary server containing the partition nor a secondary server containing the partition is available to access the query result.

60. The method of claim 58, further comprising mapping a search string to a query identifier, which is the name of a file containing the query result.

61. The method of claim 60, further comprising incrementing an access count for the query and updating a timestamp for the query result indicating a date of refresh.

62. The method of claim 61, further comprising formatting the query result into a format presentable to a user.

63. The method of claim 41, further comprising sorting a set of queries in the order of their count values.

64. The method of claim 63, further comprising refreshing a set of query results in a primary partition that corresponds to the set of queries that have the highest count values, the act of refreshing terminating when a predetermined number of query results have been refreshed.

65. The method of claim 64, further comprising copying the set of refreshed query results to a secondary partition from the primary partition.

66. The method of claim 41, further comprising sorting a set of queries in the order of their staleness.

67. The method of claim 66, further comprising refreshing a set of query results in a primary partition that corresponds to the set of queries that have the oldest timestamps, the act of refreshing terminating when a predetermined number of query results have been refreshed.

68. The method of claim 67, further comprising copying the set of refreshed query results to a secondary partition from the primary partition.