Predictive fact generation for query optimization

• US 9,619,805 B1
• Filed: 03/27/2012
• Issued: 04/11/2017
• Est. Priority Date: 03/27/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Fewtrell, Zachary G., Carr, Jacob S., Chuang, James Hsiaosung
• Primary Examiner(s): Kim, Taelor
• Application Number:
  US13/431,276
• Time in Patent Office: 1,841 Days
• CPC Class Codes: G06Q 30/00 Commerce

Abstract

A fact generation engine generates facts in response to fact requests submitted by clients. The fact generation engine also predictively generates additional facts prior to receiving a request for the additional facts from a client. The fact generation engine might determine whether to predictively generate additional facts based upon a determined probability that a client will request the additional facts. The estimated cost of predictively generating additional facts might also be utilized to determine whether to predictively generate the facts.

Claims

1. A computer-implemented method for query optimization, the computer-implemented method comprising executing instructions in a computer system to perform the operations of:

receiving a request for a fact regarding a product offered for purchase in a product catalog from a client, wherein receiving the request for a fact includes receiving a product identifier associated with the product offered for purchase;

in response to receiving the request for the fact regarding the product offered for purchase in the product catalog from the client, generating the fact regarding the product offered for purchase in the product catalog and returning the fact regarding the product offered for purchase in the product catalog to the client in response to the request;

determining a probability that the client will request one or more additional facts regarding the product offered for purchase in the product catalog, wherein the probability that the client will request the one or more additional facts is determined at least in part on historical requests data describing a probability that the one or more additional facts will be requested following a request for the fact;

determining an estimated cost of generating the one or more additional facts regarding the product offered for purchase in the product catalog, wherein the estimated cost is determined at least in part based upon historical cost data describing an actual historical cost to generate the one or more additional facts, the estimated cost comprising one or more of an estimated time, memory usage, processing capacity, or network bandwidth required to generate the one or more additional facts;

speculatively generating the one or more additional facts regarding the product offered for purchase in the product catalog based upon the determined probability and the estimated cost of generating the one or more additional facts regarding the product offered for purchase in the product catalog;

storing the speculatively generated one or more additional facts regarding the product offered for purchase in the product catalog for use in responding to a future fact request regarding the product offered for purchase in the product catalog from the client;

updating the historical cost data with an actual cost to generate the one or more additional facts;

receiving a request from the client for the one or more additional facts; and

responding to the request for the one or more additional facts with the one or more additional facts.

11. The computer-implemented method as in claim 1, further comprising storing the one or more additional facts in a fact cache.

12. The computer-implemented method as in claim 1, wherein the request for the one or more additional facts further comprises one or more optimization hints comprising preferences regarding how the one or more additional facts are to be generated.

13. The computer-implemented method as in claim 1, wherein the request for the one or more additional facts comprises a no execute flag.

14. The computer-implemented method as in claim 1, wherein responding to the request for the one or more additional facts comprises providing the estimated cost of generating the one or more additional facts regarding the product offered for purchase in the product catalog.

15. The computer-implemented method as in claim 1, wherein one of the one or more additional facts comprises a number of the product offered for purchase in the product catalog that are currently in stock by a merchant.

16. The computer-implemented method as in claim 1 wherein the speculatively generating the one or more additional facts, is based at least in part, upon a determination that the estimated cost of generating the one or more additional facts is below a threshold.

2. A non-transitory computer-readable storage medium having computer-executable instructions stored thereupon which, when executed by the computer, cause the computer to:

receive a fact request identifying one or more requested facts regarding an item identified in a product catalog, wherein receiving the fact request includes receiving a product identifier associated with the item identified in the product catalog;

in response to receiving the fact request, generate the one or more requested facts regarding the item identified in the product catalog, and to respond to the fact request with the one or more requested facts regarding the item identified in the product catalog;

determine, based at least in part upon historical fact requests, a probability that one or more additional facts regarding the item identified in the product catalog will be requested following the fact request;

determine, based at least in part upon historical cost data, an estimated cost of generating the one or more additional facts, the estimated cost comprising one or more of an estimated time, memory usage, processing capacity, or network bandwidth required to generate the one or more additional facts;

generate, based at least in part upon the determined probability being higher than a threshold amount and the estimated cost being lower than a threshold amount, the one or more additional facts regarding the item identified in the product catalog;

store the one or more additional facts for use in responding to a future fact request regarding the item offered for purchase; and

receive a request for the one or more additional facts; and

respond to the request for the one or more additional facts with the one or more additional facts.

3. The computer-readable storage medium of claim 2, having further computer-executable instructions stored thereupon which, when executed by the computer, cause the computer to respond to the fact request with the one or more additional facts regarding the item identified in the product catalog.

4. The computer-readable storage medium of claim 2, wherein the fact request further comprises one or more optimization hints comprising preferences regarding how the one or more requested facts regarding the item identified in the product catalog should be generated, and wherein generating the one or more requested facts regarding the item identified in the product catalog comprises generating the one or more requested facts regarding the item identified in the product catalog using the optimization hints provided in the fact request.

5. The computer-readable storage medium of claim 2, wherein the fact request further comprises a no execute flag, and wherein the computer-readable storage medium has further computer-executable instructions stored thereupon which, when executed by the computer, cause the computer to provide a response to the fact request comprising an estimated cost to generate the one or more requested facts regarding the item identified in the product catalog.

17. The non-transitory computer-readable storage medium as in claim 2, having further computer-executable instructions stored thereupon which, when executed by the computer, cause the computer to store the one or more additional facts in a fact cache.

18. The non-transitory computer-readable storage medium as in claim 2, having further computer-executable instructions stored thereupon which, when executed by the computer, cause the computer to determine a number of the item identified in a product catalog that are available for purchase.

6. An apparatus for optimized generation of facts, the apparatus comprising:

at least one processor; and

a computer-readable storage medium having computer-executable instructions stored thereon which, when executed on the at least one processor, cause the apparatus to;

receive a request for one or more facts regarding an item identified in a product catalog, the request including a product identifier associated with the item identified in the product catalog,

determine, based at least in part upon historical request data, a probability that one or more additional facts regarding the item identified in the product catalog will be requested following the request for the one or more facts;

determine, based at least in part upon historical cost data, an estimated cost for generating the one or more additional facts, the estimated cost comprising one or more of an estimated time, memory usage, processing capacity, or network bandwidth required to generate the one or more additional facts;

speculatively generate the one or more additional facts regarding the item identified in the product catalog based upon the probability that the one or more additional facts regarding the item identified in the product catalog will be requested; and

update the historical cost data with an actual cost to generate the one or more additional facts.

7. The apparatus of claim 6, wherein the computer-readable storage medium has further computer-executable instructions stored thereon which, when executed on the at least one processor, cause the apparatus to speculatively generate the one or more additional facts regarding the item identified in the product catalog based upon the computed probability that the one or more additional facts regarding the item identified in the product catalog will be requested following the request for the one or more facts regarding the item identified in the product catalog and an estimated cost of generating the one or more additional facts regarding the item identified in the product catalog.

8. The apparatus of claim 6, wherein the computer-readable storage medium has further computer-executable instructions stored thereon which, when executed on the at least one processor, cause the apparatus to:

store the speculatively generated one or more additional facts regarding the item identified in the product catalog in a fact cache;

receive a request for the one or more additional facts regarding the item identified in the product catalog subsequent to the request for the one or more facts regarding the item identified in the product catalog; and

respond to the request for the one or more additional facts regarding the item identified in the product catalog with the one or more additional facts regarding the item identified in the product catalog stored in the fact cache.

9. The apparatus of claim 8, wherein the request for the one or more facts regarding the item identified in the product catalog further comprises one or more optimization hints comprising preferences regarding how the one or more facts regarding the item identified in the product catalog are to be generated, and wherein the computer-readable storage medium has further computer-executable instructions stored thereon which, when executed on the at least one processor, cause the apparatus to generate the one or more facts regarding the item identified in the product catalog using the optimization hints provided in the fact request.

10. The apparatus of claim 9, wherein the request for the one or more facts regarding the item identified in the product catalog further comprises a no execute flag, and wherein the computer-readable storage medium has further computer-executable instructions stored thereon which, when executed on the at least one processor, cause the apparatus to provide a response to the request for the one or more facts regarding the item identified in the product catalog comprising an estimated cost to generate the one or more facts regarding the item identified in the product catalog.

19. The apparatus of claim 6, wherein the computer-readable storage medium has further computer-executable instructions stored thereon which, when executed on the at least one processor, cause the apparatus to determine a number of the item identified in the product catalog that are available for purchase.

20. The apparatus of claim 6, wherein the one or more additional facts regarding the item identified in the product catalog are speculatively generated based upon the estimated cost for generating the one or more additional facts.