Performance for query execution

Implementation of the present disclosure relates to a method, system and computer program product for improvement of query execution. According to one embodiment of the present invention, there is provided a method. In the method a query on data organized in a first data structure is received first. And then based on at least one property associated with the query, a second data structure is selected from a plurality of candidate data structures, wherein a performance measure of the query on the data organized in the second data structure is better than the performance measure of the query on the data organized in the first data structure. And at last the query on the data organized in the second data structure is executed. In other implementations, a system and a computer program product are disclosed.

BACKGROUND

The present invention relates to the technology of database, and more specifically, to methods and systems for improving performance for query execution.

With the development of information technology, various data needs to be stored and managed. For a given organization such as a government, a company, a school and so on, data associated with the organization are often organized in a specific data structure in order to facilitate management of the data. As an example, a relational database is widely used for the organization to store and manage the data because of its advantages in terms of consistency of transactions. A user such as a database programmer may submit a query to the database management system to obtain required data from the database. However, in some situations, even a very simple query might consume significant resource, which has negative impact on the responsiveness of the database.

SUMMARY

In a first aspect, embodiments of the present invention provide a method. In the method, a query on data organized in a first data structure is received first. Then based on at least one property associated with the query, a second data structure is selected from a plurality of candidate data structures, wherein a performance measure of the query on the data organized in the second data structure is better than the performance measure of the query on the data organized in the first data structure. And at last, the query on the data organized in the second data structure is executed.

In a second aspect, embodiments of the present invention provide a system. The system comprises a processing unit; and a memory coupled to the processing unit and storing instructions that, when executed by the processing unit, implement the above method.

In a third aspect, embodiments of the present invention provide a computer program product being tangibly stored on non-transient machine-readable medium and comprising machine-executable instructions. The machine-executable instructions, when executed on one or more processing units, may cause the one or more processing units to perform the above method.

It is to be understood that the Summary is not intended to identify key or essential features of implementations of the present disclosure, nor is it intended to be used to limit the scope of the present disclosure. Other features of the present disclosure will become easily comprehensible through the description below.

DETAILED DESCRIPTION

Characteristics are as follows:

Service Models are as follows:

Deployment Models are as follows:

Workloads layer90provides examples of functionality for which the cloud computing environment may be utilized. Examples of workloads and functions which may be provided from this layer include: mapping and navigation91; software development and lifecycle management92; virtual classroom education delivery93; data analytics processing94; transaction processing95; and query execution improvement96. The query execution improvement96may intercept a query on data organized in a first data structure, for example a relational table, and determine performance measures of the query on the data organized in a plurality of data structures. Then the query execution improvement96may select a second data structure associated with a better performance measure than the first data structure to execute the query. In this way, the performance of the execution of the query can be improved, for example, a response to the query can be accelerated, and the amount of resource occupied by the execution of the query can be reduced, and so on.

As described above, data associated with a specific organization are often stored and managed in a specific data structure. A user may use a query to access the stored data and process the data. In some situations, the query may be responded significantly slow when the query is executed on the data organized in the specific data structure. In some situations, the execution of the query may need many resources when the query is executed on the data organized in the specific data structure, etc. As an example, a relational database is often employed for an organization to store and manage the data because of its advantages in terms of consistency of transactions. In the relational database, the data are organized in a two-dimension relational table. However, in some cases, a query on the data in the relational table cannot be responded quickly, or may need many processing resources to be executed. Thus there is a need to improve the performance of the query execution while keeping the advantages of the relational database.

The inventors have found that in some cases, a query on data organized in a specific data structure may be executed with better performance if the query is executed on the data organized in another data structure. Therefore, according to embodiments of the present invention, rather than the query being directly executed on the data organized in the specific data structure, it is determined whether the data organized in a different data structure is more suitable for executing the query in terms of performance. If so, the query will be executed on the data organized in the different data structure. By taking advantage of the data organized in a more suitable data structure, the performance of the query execution can be improved.

Now some example embodiments are discussed.FIG. 4depicts a block diagram of a system400for improving performance of query execution according to an embodiment of the present invention.

As shown, data408is organized in an original data structure (referred to as “first data structure”) and is stored in a memory406. One or more copies410of the data408may be organized in one or more further data structures and also stored in the memory406. These further data structures can be obtained, for example, based on experience, prior knowledge, or the like. The data organized in one of the further data structures (referred to as “a second data structure”) is expected to result in better performance for query execution than the data organized in the first data structure. These further data structures together with the first data structure may be referred to as “candidate data structures” herein.

It is to be understood that for clarity and simplicity,FIG. 4only shows the data organized in one of the further data structures (the second data structure). However, it may be appreciated that the data can be organized in two or more further data structures.

In operation, an application402may submit a query on the data408organized in the first data structure. The query may be interpreted, for example, by a performance improvement component404. In some embodiments, the performance improvement component404is implemented in a cloud computing node10as shown inFIG. 2. As an alternative, a local deployment of the performance improvement component404is possible in some other embodiments.

Then the interpreted query can be parsed to determine at least one property associated with the query. Examples of the at least one property include, but are not limited to, a type of the query, a frequency of the query being executed, a structure of the query, a length of a record in the data structure, or a frequency of the data structure being manipulated.

The type of the query may indicate whether the query is to only access data or change data. For instance, in the case that the data408are stored in a relational database, the type of the query may indicate whether the query is a “SELECT” statement, “UPDATE” statement, “INSERT” statement, “DELETE” statement, and the like.

The frequency of the query being executed may indicate the number of times of the query being executed on the data associated with the query in the past. The frequency of the query being executed may also indicate whether the query is the most frequency query executed on the data. The structure of the query may indicate an index, a filter factor, a predicate type associated with the query, etc.

Based on the at least one determined property, the second data structure is selected from the candidate data structures. In some embodiments, the performance measures of the query on data organized in the candidate data structures may be determined based on the at least one property. The second data structure may be selected based on the performance measures, such that a performance measure of the query on the data organized in the second data structure is better than a performance measure of the query on the data organized in the first data structure. In some embodiments, the second data structure may be a data structure which is expected to provide the best performance measure among the candidate data structures. The performance measure may be any relevant metric including, but not limited to a response time, resource occupation, I/O cost, or the like.

In some embodiments, the selection of the second data structure is based on a prediction model. More specifically, the prediction model may be used to predict respective performance measures of the query on the data organized in the candidate data structures based on the at least one determined property. Then the data organized in a data structure associated with a better performance measure may be selected for executing the query. As used herein, the term “prediction model” refers to any model indicating relationships between at least one property of historical queries and performance measures of the historical queries on the data organized in the candidate data structures. The generation and use of the prediction model will be described in details below with reference toFIG. 5.

If the second data structure is selected, the query is executed on the data410organized in the second data structure instead of on the data408organized in the first data structure. For example, the performance improvement component404may execute the query on the data410organized in the selected data structure. Otherwise, if the first data structure is determined to have better performance than other data structures, the performance improvement component404may directly execute the query on the data408organized in the first data structure. The result of executing the query may be then passed to the application402for subsequent processing.

In some embodiments, the performance improvement component404may determine whether to select a different data structure from the first data structure for the query execution based on various factors. As an example, the performance improvement component404may monitor the performance measure of a query being executed on the data organized in the first data structure. If the monitored performance measure is lower than a threshold, the performance improvement component404may determine to select the second data structure so as to achieve better execution performance. In some cases, instead of directly executing the query to monitor the performance measure of the query with respect to the first data structure, the performance improvement component404may predict this performance measure using the prediction model.

Alternatively, or in addition, to select the second data structure, the performance improvement component404may consider availability of the data organized in the second data structure.FIG. 4shows an example where the data organized in the second data structures are already stored in the memory406and available. However, in some other cases, the data organized in the second data structure may be unavailable, for example, not stored in the memory406. It may take a long time to reorganize the data in the second data structure. And it might be slower to execute the query by reorganizing the data in the second data structure than to directly execute the query on the data organized in the first data structure. In this case, the query may be directly executed on the data organized in the first data structure. Moreover, after the query is executed, to facilitate subsequent query execution on the data organized in the second data structure, especially when it is monitored that the performance of the query with respect to the first data structure is low, the performance improvement component404may generate the data organized in the second data structure and store it in the memory406for a future query to use. In this way, if a subsequent query is suitable to be executed on the data organized in the second data structure, the execution performance of that query can be improved.

In this way, it is possible to ensure that the query can be executed on the data organized in a more suitable data structure. Thus the performance of executing queries can be improved compared with always executing queries on the data organized in the same original data structure. For example, a query can be responded more quickly, the amount of resources occupied by the query can be reduced, or the I/O cost associated with the execution of the query can be reduced.

As described above, a prediction model may be used to predict respective performance measures of a query on data organized in a plurality of candidate data structures.FIG. 5depicts a block diagram of a system500for generating the prediction model according to some embodiments of the present invention.

As shown, the system500includes training data storage502storing training data for generating the prediction model. As mentioned above, the prediction model indicates relationships between at least one property of historical queries in the training data set and performance measures of the historical queries on the data organized in the plurality of candidate data structure. To train such a model, the training data may include the at least one property of historical queries and the performance measure of the historical queries. These historical queries may be obtained by monitoring and collecting queries executed on the data organized in their original data structures including all the candidate data structures. The training data may be generated from the historical queries.

In some embodiments, for each of the historical queries, at least one property associated with the historical query may be extracted from the historical query. Examples of the at least one property include, but are not limited to, a type of the historical query, a frequency of the historical query being executed, a structure of the historical query, a length of a record in the original data structure, or a frequency of the original data structure being manipulated. Further, the historical query may be executed on data organized in each of the candidate data structures or at least some of the candidate data structures, so as to obtain the performance measure of the historical query on the data structure, such as the response time, resource occupation, I/O cost or any combination thereof. The at least one property extracted from a historical query and the performance measures of the historical query on the data organized in the plurality of candidate data structures may form a training sample of the training data.

As an specific example, in the case where the plurality of candidate data structures include a relational table, a hash table, a link list, a jump table, a dictionary, a data set and array, the historical query may be executed on the data organized in each of the above data structures respectively. Then the performance measures corresponding to each of the above data structures can be obtained respectively based on the execution of the query. In some embodiments, the performance measure corresponding to a given data structure may be a weighted sum of the response time, resource occupation, I/O cost of the query on the data organized in the given data structure.

The training data may be used, for example by a prediction model generating module504in the system500to generate the prediction model. The prediction model indicates relationships between at least on property of historical queries in the training data and performance measures of the historical queries on the data organized in the plurality of candidate data structure, and can be used by performance improvement component404to select a suitable data structure for executing a future query. The prediction model generating module504may be implemented in the cloud computing node10. As an alternative, a local deployment of the prediction model generating module504is possible in some other embodiments. The prediction model generating module504may use various machine learning techniques to generate the prediction based on the training data. Examples of the machine learning techniques include, but not limited to a neural network, support vector machine and the like.

The generated prediction model may be stored in prediction model storage506for use, for example, by the performance improvement component404shown inFIG. 1. Although the prediction model storage506is illustrated to be separate from the training data storage502, it should be appreciated that they may be integrated into one component.

To use the prediction model, the performance improvement component404may obtain the prediction model from the prediction model storage506and input at least one property of a received query into the prediction model. The prediction model may predict, based on the at least one property, respective performance measures of the query on the data organized in the candidate data structures and return the predicted performance measures to the performance improvement component404. The performance improvement component404may select a suitable data structure from the candidate data structures based on the performance measures.

Reference is now made toFIG. 6, which illustrates a flow chart of a method600for improving performance of query execution according to an embodiment of the present invention. The method600may be performed by the cloud computing node10, especially by the performance improvement component404implemented in the cloud computing node10.

At block602, the cloud computing node10receives a query on data organized in a first data structure. The first data structure is an original data structure for organizing the data. In an embodiment of the present invention, the first data structure includes a relational table in a relational database.FIG. 8Adepicts a relational table800A used in the relational database. As shown inFIG. 8A, the table800A organizes data in a plurality of rows802A and a plurality of columns804A.

At block604, the cloud computing node10selects, based on at least one property associated with the query, a second data structure from a plurality of candidate data structures, where a performance measure of the query on the data organized in the second data structure is better than the performance measure of the query on the data organized in the first data structure. In some embodiments, the performance measure of the query on the data organized in the second data structure is better than rest of the plurality of candidate data structures. In an embodiment of the present invention, the at least one property may include, but not limited to a type of the received query, a frequency of the query being executed, a structure of the query, a length of a record in the data structure, or a frequency of the data structure being manipulated.

In an embodiment, the second data structure is selected based on a prediction model indicating relationships between the at least one property of historical queries and performance measures of the historical queries on data organized in the plurality of candidate data structures. In the embodiment, the cloud computing node10may obtain the prediction model and input the at least one property of the query to the prediction model. The prediction model may predict, based on the at least one property, respective performance measures of the query on the data organized in the plurality of candidate data structures. The computing node10may obtain the predicted performance measures and select, from the plurality of candidate data structures, the second data structure based on the respective performance measures. In an embodiment, the prediction model may be generated by the cloud computing node10. A method for generating the prediction model will be described in details with reference toFIG. 7.

In an embodiment of the present invention, the candidate data structures may include the first data structure and may be selected from a group consisting of a table in a relational database, a link list, hash table, jump table, dictionary and data set.FIGS. 8B to 8Ddepict the data structures used in an embodiment of the present invention, respectively. These data structures illustrated inFIGS. 8B to 8Dcan be used to improve the performance of the query on the data organized in the relational table800A shown inFIG. 8A. It should be appreciated,FIGS. 8B to 8Dare merely exemplary and embodiments of the present invention are not limited to these data structures.

FIG. 8Bdepicts a diagram of a link list800B. The link list800B may include at least one node802B including a data field associated with data. In addition to the data field, the node802B further includes a pointer804B pointing to a next node of the link list800B and a pointer806B pointing to a previous node of the link list800B.

FIG. 8Cdepicts a diagram of a hash table800C. The hash table800C includes a list802C of storage addresses associated with data. An address in the list802C is determined based on a key of data via hash algorithm. The hash table800C further includes at least one node804C associated with the data. The node804C may have a pointer806C pointing to a node having the same hash value as the node804C.

FIG. 8Ddepicts a diagram of a dictionary800D. The dictionary800D includes a header802D indicating the name of the dictionary800D, the type of the dictionary800D, and on the like. The dictionary800D further includes a sub-header804D indicating the size of the data associated with the sub-header804D, address list806D of the data. A node808D in the dictionary800D indicates the information associated with the data, such as the key of the data, the value of the data, and the like.

The link list800B, hash table800C and dictionary800D shown inFIGS. 8B-8Dcan support sorted data. In some situations, for example in the case where a query on data organized in the relational table800A is for only accessing data rather than changing data, a higher performance can be obtained if the query is executed on the data organized in one of these data structures. For example, the query can be responded more quickly, the amount of resources occupied by the query can be reduced, or the I/O cost associated with the execution of the query can be reduced.

At block606, the cloud computing node10executes the query on the data organized in the second data structure. In an embodiment of the present disclosure, the cloud computing node10may transform the query to an operation associated with the second data structure and then perform the operation on the data organized in the second data structure. For example, in the case of the relational database, if the query is a “SELECT” statement for accessing a specific column, the cloud computing node10may transform the “SELECT” statement to an operation of searching for data associated with the specific column against the data organized in the second data structure.

In an embodiment of the present invention, the cloud computing node10may select the second data structure further based on at least one of the following: the performance measure of the query on the data organized in the first data structure being lower than a threshold; and availability of the data organized in the second data structure.

In an embodiment of the present invention, the cloud computing node10may generate the data organized in the second data structure in response to the data organized in the second data structure being unavailable.

Method600can discover a data structure associated with better performance measure of the execution of the query from a plurality of data structures, and execute the query on the data organized in the data structure. In this way, the execution performance of the query can be optimized. For example, the query can be responded more quickly, amount of resources occupied by the execution of the query can be reduced, the I/O cost associated with the execution of the query can be reduced, and the like.

As described above, a prediction model may be used to predict respective performance measures of the query on the plurality of candidate data structures.FIG. 7depicts a flow chart of a method700for generating the prediction model according to an embodiment of the present invention. In an embodiment of the present invention, the method700may be performed by the cloud computing node10, especially by the prediction model generating module504implemented in the cloud computing node10.

At block702, the cloud computing node10may obtain historical queries. In the case of the relational database, the historical queries may be obtained from a database management system.

At block704, the cloud computing node10may generate training data by determining the at least one property of the historical queries and determining the performance measures of the historical queries by executing the historical queries on data organized in the plurality of candidate data structures. In some embodiments, the cloud computing node10may determine, for a given historical query, the at least one property of the given historical query, and the performance measures of the given historical query by executing the given historical query on the data organized in each of the plurality of candidate data structures.

At block706, the cloud computing node10may generate the prediction model based on the training data. In some embodiments, the cloud computing node10may employ a neural network such as convolutional neural network (CNN) to generate the prediction model.

In method700, historical queries having performance measures on the data organized in the plurality of data structures are used to generate the prediction model for predicting performance measures of a future query on the data organized in the plurality of data structures. In this way, a data structure associated with better performance can be predicted, and the performance of the query execution can be improved.

Now take a relational database as an example to describe advantages of embodiments of the present invention.FIG. 9depicts a block diagram of a process900for executing a query in a traditional relational database.

In a traditional relation database, a query from the application402is firstly analyzed in a parser902. The parser902then sends the query to a respective component depending on the analysis. For example, if the query is in a form of a “SELECT” statement, the query is sent to an optimizer904for processing. If the query is in a form of an “UPDATE” statement, the query is sent to a table modification module906. If the query is in a form of a “REPAIR” statement, the query is sent to a table maintenance module908for processing. Then the query is processed by an access control module910, a table manager912, and an abstracted storage engine914. At last the query arrives at data organized in the relational table916. As can be seen, in the traditional relational database, a query needs to be processed by a plurality of components before the response to the query is returned.

In contrast, according to the present invention, if a query on the data organized in the relational table is determined to be suitable for execution on the data organized in a data structure other than the relational table, the query will be executed on the data organized in the data structure, rather than on the relational data base. Thus the processing in the parser902, optimizer904, table modification module906, table maintenance module908, access control module910, table manager912and abstracted storage engine914can be omitted. Therefore, the resources associated with the processing in the parser902, optimizer904, table modification module906, table maintenance module908, access control module910, table manager912and abstracted storage engine914can be saved, while accelerating the response to the query. Thus, the execution performance of the query can be significantly improved.

It should be noted that the processing of improving performance for query execution according to embodiments of this disclosure could be implemented by computer system/server12ofFIG. 1.