Pre-caching

Abstract

This disclosure addresses the need for pre-caching of database query results which in general is the caching of the results of query evaluation before they are needed. In certain embodiments of query evaluation, the computing time required to evaluate a query is dominated by the reverse query, the evaluation of which determines the available remaining selectors and the number of items associated with each. The time to compute this reverse query is on average approximately proportional to the number of matching items. This result is used as a very convenient method of determining, before evaluation, which conjunctive queries will take the most time to evaluate—the long queries. These long queries can then be pre-cached, making them available for faster responses when they are needed. Methods of using cached conjunctive query results to more quickly evaluate certain queries comprising the disjunctive Boolean operators are also described.

1 . A computer-implemented method comprising:
 analyzing a plurality of potential database queries of which at least one has not yet been evaluated;   based on the analysis of the potential database queries, determining a priority order in a priority queue from which potential database queries should be chosen to have their results pre-cached;   executing at least one of the potential database queries which has not yet been evaluated in the order set forth in the priority queue; and   caching the results of the executed queries.   
     
     
         2 . The computer-implemented method of  claim 1 , wherein the priority queue includes an analyzed potential database query and a number of matching items associated with the potential database query. 
     
     
         3 . The computer-implemented method of  claim 2 , wherein determining the order in which potential database queries should be pre-cached is based on the frequencies of items associated with the potential database queries. 
     
     
         4 . The computer-implemented method of  claim 1 , wherein determining the order in which potential database queries should be pre-cached is based on an estimate of the amount of relative time required to evaluate the potential database queries. 
     
     
         5 . The computer-implemented method of  claim 1 , wherein the series of potential database queries comprises a conjunctive database query. 
     
     
         6 . The computer-implemented method of  claim 1 , wherein each query in the series of potential database queries comprises a query derived from a base query such that the derived query can be uniquely identified by a single detail selector and the base query. 
     
     
         7 . The computer-implemented method of  claim 1 , further comprising:
 evaluating a query comprising a plurality of selectors, and at least one disjunctive Boolean, using the results of one or more of the executed and cached queries.   
     
     
         8 . A non-transitory computer-readable storage medium having computer-readable instructions stored thereon effective for causing a computer to perform a method comprising:
 analyzing a plurality of potential database queries of which at least one has not yet been evaluated;   determining a priority order in a priority queue for which potential database queries should be pre-cached based on the analysis of the potential database queries;   executing at least one of the potential database queries which has not yet been evaluated in the order set forth in the priority queue; and   caching the results of the executed queries.   
     
     
         9 . The non-transitory computer-readable storage medium of  claim 8 , wherein the priority queue includes an analyzed potential database query and a number of items associated with the potential database query. 
     
     
         10 . The non-transitory computer-readable storage medium of  claim 9 , wherein determining the order in which potential database queries should be pre-cached is based on the frequencies of items associated with the potential database queries. 
     
     
         11 . The non-transitory computer-readable storage medium of  claim 8 , wherein determining the order in which potential database queries should be pre-cached is based on an estimate of the amount of relative time required to evaluate the potential database queries. 
     
     
         12 . The non-transitory computer-readable storage medium of  claim 8 , wherein the series of potential database queries comprises a conjunctive database query. 
     
     
         13 . The non-transitory computer-readable storage medium of  claim 8 , wherein the series of potential database queries comprises a query derived from a base query such that the derived query can be represented by an additional single detail selector and the base query identifier. 
     
     
         14 . The non-transitory computer-readable storage medium of  claim 8 , wherein the series of potential database queries comprises a disjunctive query and the method further comprises:
 separating the disjunctive portions of the query into separate queries; and   individually analyzing the separate queries.   
     
     
         15 . A system comprising:
 a processor, the processor configured to perform a method comprising:
 prior to a user request, analyzing a series of potential database queries;
 determining a priority order in a priority queue for which potential database queries should be pre-cached based on the analysis of the series of potential database queries; 
 executing the potential database queries in the order set forth in the priority queue; and 
 caching the results of the executed queries; and 
 
   a computer-readable memory configured to store a data structure representing a priority queue.   
     
     
         16 . The system of  claim 15 , wherein the priority queue includes an analyzed potential database query and a number of items associated with the potential database query. 
     
     
         17 . The system of  claim 16 , wherein the determining order in which potential database queries should be pre-cached is based on the frequencies of items associated with the potential database queries. 
     
     
         18 . The system of  claim 15 , wherein determining the order in which potential database queries should be pre-cached is based on an estimate of the amount of relative time required to evaluate the potential database queries. 
     
     
         19 . The system of  claim 15 , wherein the series of potential database queries comprises a query derived from a base query such that the derived query can be represented by an additional single detail selector and the ID of the base query. 
     
     
         20 . The system of  claim 15 , wherein the series of potential database queries comprises a disjunctive query and the method further comprises:
 separating the disjunctive portions of the query into separate queries; and   individually analyzing the separate queries.