RESOURCE ESTIMATION FOR QUERIES IN LARGE-SCALE DISTRIBUTED DATABASE SYSTEM

• US 20170213257A1
• Filed: 01/27/2016
• Published: 07/27/2017
• Est. Priority Date: 01/27/2016
• Status: Active Grant

• Current Assignee: Amobee, Inc. (Nexxen International Ltd.)
• Original Assignee: Turn (Nexxen International Ltd.)
• Inventors: Murugesan, Mummoorthy, Qi, Yan, Shen, Jianqiang
• Granted Patent: US 10,762,539 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06Q 30/0275 Auctions
• CPC Class Codes: G06Q 30/0277 Online advertisement

Abstract

Disclosed are systems and methods for managing queries on on-line advertisement data. The system includes a query engine device for receiving queries from and outputting query results to query client devices and a training engine for generating and adjusting a model for predicting an estimation of resource usage for execution of each received query based on each query'"'"'s corresponding feature vector having values pertaining to the query and a system status. The query engine device is further configured to provide the estimation of resource usage for each query to the corresponding query client device and, in response, receive input from such corresponding query client device and specifying whether to proceed with the corresponding query. A database system receives input from each query'"'"'s corresponding query client device as to whether to proceed with the query and, in response, initiates or inhibits execution of such query with respect to a database storage system.

Claims

1. A database system for managing queries on on-line advertisement data, the system comprising:

a query engine device configured for receiving queries from a corresponding plurality of query client devices and outputting query results to such corresponding query clients;

a training engine device configured for generating and adjusting a model for predicting an estimation of resource usage for execution of each received query based on each query'"'"'s corresponding feature vector having a plurality of values pertaining to the query and a system status;

wherein the query engine device is further configured to provide the estimation of resource usage for each query to the corresponding query client device and, in response, receive input from such corresponding query client device and specifying whether to proceed with the corresponding query; and

a database system for receiving input from each query'"'"'s corresponding query client device as to whether to proceed with the query and, in response, initiating or inhibiting execution of such query with respect to a database storage system.

2. The system of claim 1, wherein the estimation of resource usage for each query is provided prior to executing such query, which is subsequently executed if input specifies that such query is to be executed, and wherein, such query is, otherwise, inhibited if such input specifies that such query is not be executed.

3. The system of claim 1, wherein the estimation of resource usage for each query specifies a predicted elapsed time, CPU usage, or I/O usage for such query.

4. The system of claim 3, wherein the estimation of resource usage for each query further specifies a predicted execution time, including map time and reduce time, for such query.

5. The system of claim 1, wherein a model is generated and adjusted individually for each received query of each particular query client by:

generating an initial model for use with a plurality of queries having different feature vectors, received from a plurality of new query clients, wherein the initial model is configured to provide an estimation of resource usage for each of such new query clients'"'"' query based on such query'"'"'s particular values of its feature vector, wherein the initial model has a plurality of weights for applying to the feature vector of the newly received queries;

prior to adjusting the weights of the initial model, tracking actual resource usage during execution of each newly received query having different feature vectors; and

for each particular query client, dynamically adjusting the weights of the initial model so as to generate an adjusted model for use with such particular query client'"'"'s subsequently received queries, wherein the weights are only adjusted if a condition is met when comparing actual resource usage and estimation of resource usage for executing a current query from such particular query client.

6. The system of claim 5, wherein the condition is met for a particular query client if the actual resource usage for executing such particular query client'"'"'s query differs from the estimation of resource usage of such particular query client'"'"'s query by a predefined threshold.

7. The system of claim 6, wherein the training engine is further configured to dynamically customize a different model for each particular query client.

8. The system of claim 7, wherein the different feature vectors include different combination of values for a plurality of query parameters for each query'"'"'s content, a plurality of execution parameters for each query, a plurality of database system esource specifications for each query client, and a plurality of database system operating parameters.

9. The system of claim 8, wherein the query parameters include one or more of the following:

a specification of query text, a specification of type and number of tables, a specification of number and type of aggregate functions, a specification of number and type of list function tables, a specification of presence of “

order by”

clauses, a specification of number and type of columns in each referenced table, a specification for presence of “

having”

clauses, a specification of number and types of nesting, a specification of number of queried days or other queried timeframe, or a specification of presence and type of a filtering condition,

10. The system of claim 7, wherein the estimation of resource usage includes a predicted mapping time, a predicted reducing time, and a predicted total elapsed time, and wherein the actual resource usage includes an actual mapping time, an actual reducing time, and an actual total elapsed time, wherein the condition is met when a difference between any time of the estimation of resource usage and actual resource usage is above a predefined threshold.

11. The system of claim 7, wherein the weights are only adjusted until a difference between the actual resource usage and the estimation of resource usage is minimized.

12. The system of claim 7, wherein the weights are only adjusted until a difference between the actual resource usage and the estimation of resource usage is changed by a predefined percentage so that the estimation of resource usage moves closer to, but does not equal, the actual resource usage.

13. The system of claim 5, wherein the query engine device is further configured to provide a suggestion for changing each query so as to reduce the query'"'"'s estimation of resource usage to the corresponding query client device, wherein the suggestion includes a predefined number of feature vector values that contribute the most to the estimation of resource usage.

14. A method of managing queries on on-line advertisement data, comprising:

receiving queries from a corresponding plurality of query client devices;

generating and adjusting a model for predicting an estimation of resource usage for execution of each received query based on each query'"'"'s corresponding feature vector having a plurality of values pertaining to the query and a system status; and

providing the estimation of resource usage for each query to the corresponding query client device and, in response, receiving input from such corresponding query client device and specifying whether to proceed with the corresponding query and, in response, initiating or inhibiting execution of such query with respect to a database storage system.

15. The method of claim 14, wherein the estimation of resource usage for each query specifies a predicted elapsed time for such query and a predicted execution time, including map time and reduce time, for such query.

16. The method of claim 14, wherein a model is generated and adjusted individually for each received query of each particular query client by:

generating an initial model for use with a plurality of queries having different feature vectors, received from a plurality of new query clients, wherein the initial model is configured to provide an estimation of resource usage for each of such new query clients'"'"' query based on such query'"'"'s particular values of its feature vector, wherein the initial model has a plurality of weights for applying to the feature vector of the newly received queries;

prior to adjusting the weights of the initial model, tracking actual resource usage during execution of each newly received query having different feature vectors; and

for each particular query client, dynamically adjusting the weights of the initial model so as to generate an adjusted model for use with such particular query client'"'"'s subsequently received queries, wherein the weights are only adjusted if a condition is met when comparing actual resource usage and estimation of resource usage for executing a current query from such particular query client.

17. The method of claim 16, wherein the condition is met for a particular query client if the actual resource usage for executing such particular query client'"'"'s query differs from the estimation of resource usage of such particular query client'"'"'s query by a predefined threshold.

18. The method of claim 17, further comprising dynamically customizing a different model for each particular query client.

19. The method of claim 18, wherein the different feature vectors include different combination of values for a plurality of query parameters for each query'"'"'s content, a plurality of execution parameters for each query, a plurality of database system resource specifications for each query client, and a plurality of database system operating parameters.

20. The method of claim 18, wherein the estimation of resource usage includes a predicted mapping time, a predicted reducing time, and a predicted total elapsed time, and wherein the actual resource usage includes an actual mapping time, an actual reducing time, and an actual total elapsed time, wherein the condition is met when a difference between any time of the estimation of resource usage and actual resource usage is above a predefined threshold.

21. The method of claim 18, wherein the weights are only adjusted until a difference between the actual resource usage and the estimation of resource usage is minimized.

22. The method of claim 18, wherein the weights are only adjusted until a difference between the actual resource usage and the estimation of resource usage is changed by a predefined percentage so that the estimation of resource usage moves closer to, but does not equal, the actual resource usage.

23. The method of claim 16, wherein the query engine device is further configured to provide a suggestion for changing each query if the condition is met so as to reduce the query'"'"'s estimation of resource usage to the corresponding query client device, wherein the suggestion includes a predefined number of feature vector values that contribute the most to the estimation of resource usage.

24. One or more computer readable media having instructions stored thereon for performing a method, the method comprising:

receiving queries from a corresponding plurality of query client devices;

generating and adjusting a model for predicting an estimation of resource usage for execution of each received query based on each query'"'"'s corresponding feature vector having a plurality of values pertaining to the query and a system status; and

providing the estimation of resource usage for each query to the corresponding query client device and, in response, receiving input from such corresponding query client device and specifying whether to proceed with the corresponding query and, in response, initiating or inhibiting execution of such query with respect to a database storage system.