Maximum allowable runtime query governor

Techniques for managing query execution using memory compression based on maximum allowable runtimes. Embodiments may receive a query from a requesting entity and calculate an estimated execution time for executing the query. Embodiments may further determine a maximum allowable runtime for the query. An amount of memory compression for use in processing the query may then be adjusted, based on the estimated execution time and the maximum allowable runtime. The query may then be executed using the adjusted memory compression rate to produce a set of query results, which may then be returned to the requesting entity.

BACKGROUND

The present invention generally relates to database management, and more particularly, to managing query execution using a query governor.

Databases are computerized information storage and retrieval systems. A relational database management system is a computer database management system (DBMS) that uses relational techniques for storing and retrieving data. An object-oriented programming database is a database that is congruent with the data defined in object classes and subclasses.

Regardless of the particular architecture, a requesting entity (e.g., an application or the operating system) in a DBMS requests access to a specified database by issuing a database access request. Such requests may include, for instance, simple catalog lookup requests or transactions and combinations of transactions that operate to read, change and add specified records in the database. These requests (i.e., queries) are often made using high-level query languages such as the Structured Query Language (SQL). Upon receiving such a request, the DBMS may execute the request against a corresponding database, and return any result of the execution to the requesting entity.

As databases grow in size and in workload, particular queries or requests may take a substantial amount of time and resources to execute. As such, database administrators may wish to control how long queries on a database system may execute.

SUMMARY

Embodiments of the invention provide a method, product and system for managing query execution. The method, product and system include receiving a query for processing from a requesting entity. Additionally, the method, product and system include calculating an estimated execution time for executing the received query. The estimated execution time approximates an amount of time the received query will take to execute. A maximum allowable runtime for the received query is then determined. The method, product and system include also include adjusting an amount of memory compression used in executing the received query, based at least in part on the estimated execution time and the maximum allowable runtime for the received query. The query is then executed using the adjusted amount of memory compression.

DETAILED DESCRIPTION

Since all computers have a limited amount of system resources for use in running programs, proper resource management is important to ensure that these limited resources are effectively utilized. To this end, in a database system, database administrators may wish to restrict how long a particular query may run when executed. That is, if executing a particular query would tie up system resources for an excessive amount of time, to the detriment of the execution other queries and tasks on the system, the database administrators may wish to reject the query for execution. Such a rejection may be definitive (e.g., a message may be returned to the requesting entity, explaining the query was denied for processing) or the execution may be delayed to another time (e.g., the system may process the query once system resources become idle). This ensures that no single database query may monopolize the resources of the system.

Although the memory resources of a computer may be fixed, one technique for effectively increasing the memory resources is by compressing data stored therein. For example, assume a particular file has a storage size of 100 megabytes. If the particular file is then read into system memory, it will consume 100 megabytes of space in memory, but if the particular file is compressed at a compression rate of 50%, the compressed file will only consume 50 megabytes of space in memory. One example of such a memory compression technique is the Active Memory Expansion component available on POWER7™ platforms by International Business Machines (“IBM”). Although such a technique may increase the time required to process requests using the compressed data, because additional processing resources are used to compress and decompress the data, in many situations, the processing costs may be outweighed by the gains in memory capacity.

Embodiments of the invention may receive a query for processing from a requesting entity and, responsive to receiving the query, may calculate an estimated execution time for executing the query. The estimated execution time generally reflects an approximation of how long the query will take to execute. Furthermore, embodiments may estimate this time using historical data, collected from processing previous queries. Embodiments may then determine a maximum allowable runtime for the query. Such a maximum allowable runtime may be a predetermined value applied to all queries, or may be determined based on specific attributes associated with the query. Upon determining the maximum allowable runtime for the query, embodiments may optimize the query by adjusting an amount of memory compression used in processing the query. The optimization may be based on the estimated execution time and the maximum allowable runtime for the received query. The optimized query may then be executed to produce query results, which may in turn be returned to the requesting entity.

Typically, cloud computing resources are provided to a user on a pay-per-use basis, where users are charged only for the computing resources actually used (e.g. an amount of storage space consumed by a user or a number of virtualized systems instantiated by the user). A user can access any of the resources that reside in the cloud at any time, and from anywhere across the Internet. In context of the present invention, a user may access applications (e.g., a database management system or “DBMS”) or related data available in the cloud. For example, the DBMS could execute on a computing system in the cloud and receive queries pertaining to one or more databases managed by the DBMS. In such a case, a memory compression query governor182could monitor incoming queries and, for each query, calculate an estimated execution time for executing the query. The query governor182may also determine a maximum allowable runtime for the query, and may adjust an amount of memory compression used in processing the query based on the estimated execution time and the maximum allowable runtime for the query. Doing so allows a user to submit queries from any computing system attached to a network connected to the cloud (e.g., the Internet), and helps to ensure no single query consumes an impermissible amount of system resources during execution.

Referring now toFIGS. 1A-1B,FIGS. 1A-1Bare block diagrams illustrating systems configured to run a memory compression query governor, according to embodiments of the present invention. More specifically,FIG. 1Ais a block diagram illustrating a networked system for managing query execution using a query governor. As shown, the system100includes a client system120and a database server170(also referred to herein as a query governor system), connected by a network150. Generally, the client system120may submit requests (i.e., queries) over the network150to a DBMS running on the database server170. The term “query” denotes a set of commands for retrieving data from a stored database. Queries may take the form of a command language, such as the Structured Query Language (SQL), and enable programmers and programs to select, insert, update, and determine the location of data in the database.

Generally speaking, any requesting entity (i.e., different query types) can issue queries against data in a database. For example, software applications (such as by an application running on the client system120), operating systems, and, at the highest level, users may submit queries to the database. These queries may be predefined (i.e., hard coded as part of an application) or may be generated in response to input (e.g., user input). Upon receiving the request, the DBMS on the database server170may execute the request on a database specified in the request, and then return a result of the executed request.

According to one embodiment of the invention, upon receiving a query for processing, a query governor on the query governor system170may calculate an estimated execution time for the received query. The estimated execution time generally reflects an amount of time it will take the DBMS to execute the received query. The query governor may calculate the estimated execution time using historical data collected from processing previous queries. As an example, assume that three previous queries containing SELECT statements for a particular database table took 15 seconds, 20 seconds and 25 seconds to execute. If the query governor system170then receives another query containing a SELECT statement for the particular database table, the query governor may estimate that the query will take 20 seconds to execute (i.e., the average of the three previous execution times).

Once the estimated execution time is calculated, the query governor may then determine a maximum allowable runtime for the query. Generally, the maximum allowable runtime specifies a threshold amount of the time that the query should finish executing within. In one embodiment, the user or application submitting the query may specify the maximum allowable runtime as part of the query. For example, the query may include a SQL tag specifying the maximum allowable runtime. In another embodiment, the query governor may retrieve the maximum allowable runtime associated with the query from one or more configuration files. Upon determining the maximum allowable runtime for the query, the query governor adjusts an amount of memory compression that will be used in processing the query, based on the estimated execution time and the maximum allowable runtime for the query. That is, as discussed above, the more memory compression that is used in processing the query, the longer the query will take to process, since additional processing resources are consumed in compressing and decompressing the data. Accordingly, the query governor may adjust the amount of memory compression to an amount where the query may still execute within the maximum allowable time. The DBMS may then execute the query using the adjusted amount of memory compression, and once the query is executed, any results produced from executing the query may be returned to the requesting entity from which the query was received.

Advantageously, by doing this, embodiments of the invention may minimize the amount of memory that individual queries may consume on the database systems, while ensuring that the queries still finish executing within the maximum allowable runtime. By doing this, embodiments may prevent a situation where a particular query consumes a substantial portion of the system resources, to the detriment of other queries and tasks on the database systems. Furthermore, embodiments of the invention may manage query execution in a way that does not simply reject the query for processing. Rather, embodiments of the invention may still process a query whose initial estimated execution time exceeds the maximum allowable runtime by using reducing the amount of memory compression used in processing the query. By doing this, embodiments process the received query while still minimizing memory usage on the database systems.

FIG. 1Bis a block diagram illustrating a system configured to run a memory compression query governor, according to one embodiment of the present invention. As shown, the system110contains the client system120and the database server170. The client system120contains a computer processor122, storage media124, I/O devices126, memory128and a network interface card134. Computer processor122may be any processor capable of performing the functions described herein. The client system120may connect to the network150using the network interface card134. Furthermore, as will be understood by one of ordinary skill in the art, any computer system capable of performing the functions described herein may be used.

Illustratively, memory128contains a client application130and an operating system132. Although memory128is shown as a single entity, memory128may include one or more memory devices having blocks of memory associated with physical addresses, such as random access memory (RAM), read only memory (ROM), flash memory or other types of volatile and/or non-volatile memory. The client application130is generally capable of generating database queries. Once the client application130generates a query, the query may be submitted to a server (e.g., DBMS180) for execution, using the network150. The operating system132may be any operating system capable of performing the functions described herein.

The database server170contains a computer processor172, storage media174, I/O devices176, memory178and a network interface186. Computer processor172may be any processor capable of performing the functions described herein. As shown, storage media174contains data pages175. The data pages175generally contain one or more rows of data. In one embodiment of the invention, data contained in the data pages175is associated with one or more key values in the database184. I/O devices176may represent a variety of input and output devices, including keyboards, mice, visual displays, printers and so on. The database server170may connect to the network150using the network interface card186. Furthermore, as will be understood by one of ordinary skill in the art, any computer system capable of performing the functions described herein may be used.

In the pictured embodiment, memory178contains an operating system185and a database management system (hereinafter “DBMS”)180. Although memory178is shown as a single entity, memory178may include one or more memory devices having blocks of memory associated with physical addresses, such as random access memory (RAM), read only memory (ROM), flash memory or other types of volatile and/or non-volatile memory. The DBMS180contains a memory compression query governor182and a database184. The operating system185may be any operating system capable of performing the functions described herein.

As discussed above, when the DBMS180receives a query for processing, the query governor182may calculate an estimated execution time for processing the query. The query governor182may then determine a maximum allowable runtime for the received query. In one embodiment, the maximum allowable runtime is specified as part of the query. In another embodiment, the maximum allowable runtime is specified in a configuration file. The query governor182may then optimize the query by adjusting an amount of memory compression used in executing the query. Such optimize may include enabling memory compression for processing the query, if memory compression is disabled, or may include increasing or decreasing the compression rate used in processing the query. Once the query is optimized, the DBMS180may execute the query against the database184to produce a set of query results. The DBMS180may then return the set of query results to the requesting entity from which the query was received.

In one embodiment, the query governor182optimizes the query so that the actual execution time of the query is at or near the maximum allowable runtime for the query. By doing this, the query governor182may ensure that the query executes in an acceptable amount of time, while minimizing the amount of memory used in processing the query. As discussed above, because additional memory compression may result in additional processing activity, queries executed using a high amount of memory compression may take longer to execute than queries executed using a low amount or no memory compression. Thus, by adjusting the amount of memory compression so that the execution time of the query is at or near the maximum allowable runtime, the query governor182may conserve memory resources on the query governor system170while still ensuring that queries execute in an acceptable amount of time.

In one embodiment, the query governor182may consider other factors when determining the maximum allowable runtime for the query. Such factors may include, without limitation, the origin of the query, a priority value associated with the query, and a class of the query. For instance, assume that there are two applications which submit queries to the DBMS180: a mission-critical real-time application with a high priority value and a logging application for collecting database statistics with a low priority value. In such an example, the query governor182may assign a lower maximum allowable runtime to queries received from the mission-critical application than for queries received from the logging application. The DBMS180may accordingly use less memory compression in processing queries received from the higher-priority mission-critical application and accordingly expedite the processing of these queries. That is, because the use of memory compression may consume additional processing resources on the database systems, queries that are processed using a greater amount of memory compression may take longer to process than queries processed using a lesser amount or no memory compression. Thus, by setting a lower maximum allowable runtime for the processing of queries received from higher-priority application, the query governor182may process these queries more quickly. At the same time, the query governor182may set a higher maximum allowable runtime for the processing of queries received from the lower-priority application, in order to use memory compression techniques to conserve system memory in executing these queries.

FIG. 2is a block diagram illustrating the effects of memory compression, according to one embodiment of the present invention. In the depicted example, note that the memory1781without memory compression enabled has the same physical data storage capacity as the memory1782with memory compression enabled. As shown, the memory1781contains a portion of uncompressed memory2101and a portion of unused memory2401. The uncompressed portion of memory2101may store data used by one or more applications that is not compressed. The unused pool2401, in turn, represents an unused data capacity of the memory1781, in which no data is currently stored.

The memory1782, in contrast, contains an uncompressed portion2102, a compressed portion2202, an expanded portion2302and an unused portion2402of memory. In this example, the memory1782effectively contains the same data as the memory1781, but does so using memory compression. Thus, in the depicted example, the uncompressed memory2102relates to a portion of the uncompressed memory2101. Likewise, the compressed memory2202relates to the remaining portion of the uncompressed memory2101. That is, due to the use of memory compression, the data from uncompressed memory2101may be stored in uncompressed memory2102and compressed memory2202which, when combined, are smaller in size than the uncompressed memory2101.

Advantageously, by using memory compression, embodiments of the invention may effectively create the expanded memory pool2302, which may in turn be used to store additional data, either compressed or uncompressed. For example, a DBMS may use the expanded memory2302to store additional data during fetches to a storage media174. Additionally, such memory compression not only expands available memory, but because the expanded memory2302may be used for other purposes, may also reduce paging on the database system as a result. Advantageous, because paging often leads to a greater delay than compressing and decompressing data, the memory compression may improve the performance of the database system as well. Furthermore, althoughFIG. 2shows the various portions of memory as being contiguous, in practice, memory regions allocated to a pool may be fragmented. One of ordinary skill in the art will recognize, however, that in this example it is the amount of memory178occupied by each portion that is significant.

FIG. 3is a flow diagram illustrating a method for managing query runtime, according to one embodiment of the present invention. As shown, the method300begins at step320, where a DBMS receives a query from a requesting entity for processing. Such a requesting entity may be received from another software application (e.g., client application130) and may be a predefined query or a user-specified query. Upon receiving the query, the query governor182calculates an estimated execution time for processing the received query (step325). The estimated execution time generally reflects an amount of time the received query will take to execute. The query governor182may calculate the estimated execution time using historical data collected from previously processed queries.

The query governor182then determines a maximum allowable runtime for the received query (step330). As discussed above, the maximum allowable runtime generally refers to a threshold amount of time the received query should finish executing within. In one embodiment, the maximum allowable runtime may be specified (e.g., by the requesting entity) in the received query. In such an embodiment, the maximum allowable runtime may be defined using one or more SQL tags in the received query. In another embodiment, the maximum allowable runtime may be defined in a configuration file.

Additionally, the query governor182may determine the maximum allowable runtime based on a priority level or a class of the query. For example, assume a particular DBMS receives queries that may be classified as either high priority, medium priority or low priority. If the query governor182determines a particular received query is a high priority query, the query governor182may assign a relatively low maximum allowable runtime to the query. That is, because the query is of high importance, the query should generally be processed in a short amount of time. As a second example, if the query governor182determines a second received query is a low priority query, the query governor182may assign a relatively high maximum allowable runtime to the second query. That is, since the query is of low priority, it may be less important to process the query in a short amount of time, as compared to the processing of the high priority query. Furthermore, in one embodiment, the maximum allowable runtime is specified as a flat amount of time (e.g., 60 seconds). In another embodiment, the maximum allowable runtime is determined using an execution time adjustment threshold, which specifies a maximum percentage that the estimated execution time may be increased (e.g., 20%).

Once the maximum allowable runtime is determined, the query governor182adjusts the amount of memory compression used to process the received query (step335). As discussed above, generally speaking, the more memory compression used in processing a particular query, the longer the processing of the particular query will take. That is, because the database system (e.g., query governor system170) uses additional processing resources compressing and decompressing data when memory compression is enabled, these additional processing resources may not be used in the processing of the query. Accordingly, if the query governor182determines that the estimated execution time for a query is substantially less than the maximum allowable runtime for the query, the query governor182may increase the amount of memory compression used in processing the query. In one embodiment, the query governor182may increase the amount of memory compression (and thus the execution time of the query) until the estimated execution time for the query is at or near the maximum allowable runtime. By doing this, the query governor182may conserve the memory resources of the database system, while ensuring that the query will still execute within the maximum allowable runtime.

Once the amount of memory compression is adjusted, the DBMS180executes the query using the adjusted memory compression rate (step340). The DBMS180may then return a set of query results produced by executing the query to the requesting entity from which the query originated (step345). Once the set of query results are returned, the method300ends. One advantage to the method300is that because the amount of memory compression used in processing queries is adjusted based at least in part on a maximum allowable runtime for the query, embodiments may conserve system resources (i.e., memory178) while still ensuring that queries are executed in an acceptable amount of time (i.e., within the maximum allowable runtime).

FIGS. 4A-4Bare timeline diagrams illustrating the effects of memory compression on query runtime, according to embodiments of the present invention. For purposes of the discussion ofFIGS. 4A and 4B, assume that the depicted timelines represent the execution of exemplary database queries. As shown,FIG. 4Acontains two timelines400and415. As shown, the timeline400represents a first database query with an execution time of 20 seconds. In this example, the non-shaded portion4051represents the initial estimated execution time for the query, and the shaded portion4101represents the additional execution time added due to the use of memory compression. Furthermore, for the purposes of this example, assume that the query represented by timeline400is a low priority query and that the query governor182is configured to use an execution time adjustment threshold of 100% for low priority queries. Accordingly, the query governor182has determined that the maximum allowable runtime for the query is 20 seconds (a percentage increase of 100% from the original 10 second estimated execution time), thus allowing the query governor182to use an amount of memory compression that will double the execution time of the query.

In contrast, the second timeline415represents a high priority query with a total execution time of 6 seconds. As shown, the non-shaded portion4052represents the initial estimated execution time for the query, and the shaded portion4102represents the additional execution time added due to the use of memory compression. Furthermore, assume that the query governor182is configured to use an execution time adjustment threshold of 20% for high priority queries. In this example, because the query represented by the timeline415is a high priority query, the query governor182has determined that the maximum allowable runtime for the query is 6 seconds (a percentage increase of 20% from the original 5 second estimated execution time). That is, because the query is a high priority query, the query governor182may minimize any delay to the processing of the query by using a lower maximum allowable runtime. Accordingly, the query governor182may determine that less memory compression (relative to the query depicted by timeline400) should be used for processing the query depicted by the timeline415.

FIG. 4Bcontains a timeline440that represents a query with an execution time of 20 hours. In this example, the non-shaded portion445represents the initial estimated execution time for the query, and the shaded portion450represents the additional execution time added due to the use of memory compression. In this example, the query governor182has determined that because the initial estimated execution time for the query (i.e., the portion445) is sufficiently long that the requesting entity submitting the query will not expect any returned results quickly, the query governor182has set a high maximum allowed runtime of 20 hours for processing the query. In other words, because the query was estimated to take a substantial amount of time of 10 hours to process using no memory compression (as shown by portion445), the query governor182may determine that it is unlikely that a user submitting the query will notice or mind an additional delay in processing the query. As such, the query governor182may be configured to use an execution time adjustment threshold of 100% for such queries. Accordingly, in this example, the query governor182has determined that the maximum allowable runtime for the query is 20 hours (a percentage increase of 100% from the original 10 hour estimated execution time), thus allowing the query governor182to use a substantial amount of memory compression in processing the query.