FIELD OF THE INVENTION

This application relates to the database technology and in particular, to a method of optimizing SQL (Structured Query Language) query and an optimizer.

BACKGROUND

Structured query language (SQL) is one kind of database query and programming language, it is used to store and retrieve the data as well as allow querying in the relational database system.

The SQL language's development began in 1974, proposed by Boyce and Chamberlin, at that time called SEQUEL; In 1976, IBM Corporation's Sanjase research institute changes SQL when developed RDBMS SYSTEM R; ORACLE Corporation published firstly in 1979 based on the SQL commercialization RDBMS product; American country Standardization organization ANSI announced that SQL takes the database industrial standard in 1986.

The SQL language contains 4 parts: A). Data definition language (DDL), contains CREATE, DROP and ALTER. B). Data manipulation language (DML), contains INSERT, UPDATE and DELETE. C). Data Query language (DQL), contains SELECT. D). Data management language (DCL), contains SQL statements such as GRANT, REVOKE, COMMIT, ROLLBACK.

Commonly, the execution step of SQL sentence may include:

1. Parse (Syntax Check), It parses the SQL statement syntax and decides whether it conform to the standard.

2. Analyze, It checks the objects (tables, columns, etc.) used in SQL statement exist in Database and extracts any bind variable if there are any.

3. Optimize, It chooses the best plan for query execution based on cost.

4. Execute, It executes the best plan generates in previous step and returns the result.

Nowadays, one or more bind values (bind variables) have been used in SQL statement and

there are some optimization technologies for the execution of SQL queries which have bind values. Such as Default Selectivity, Bind Value Peeking and Adaptive Cursor Sharing.

However, the applicant found that only selectivity was considered as a parameter to decide on new plan selection in the prior art. In many cases when the order in which data stored is changed, the plan can also be different. The existing technology doesn't consider that other parameters which can lead to sub-optimal plan selection.

SUMMARY

Embodiments of the present invention pertain to a method of optimizing SQL query and an optimizer. The aim is to optimize the SQL query to a higher degree and reduce the overall query execution time.

According to a first aspect of the embodiments of the present invention, there is provided a method of optimizing SQL query, the method includes:

extracting one or more bind values from an inputted SQL query statement;

calculating selectivity and correlation coefficient for the bind values; wherein the correlation coefficient indicates the correlation between the physical order of table tuples and the ordering of data values of particular column;

acquiring an execution plan based on the selectivity and the correlation coefficient.

According to a second aspect of the embodiments of the present invention, there is provided an optimizer, applied for optimizing SQL query, the optimizer includes:

an extracting unit, configured to extract one or more bind values from an inputted SQL query statement;

a first calculating unit, configured to calculate selectivity and correlation coefficient for the bind values; wherein the correlation coefficient indicates the correlation between the physical order of table tuples and the ordering of data values of particular column;

an acquiring unit, configured to acquire an execution plan based on the selectivity and the correlation coefficient.

The advantages of the present invention exist in that: through calculates selectivity and correlation coefficient for the bind values and acquires an execution plan based on the selectivity and the correlation coefficient, the SQL query can be optimized to a higher degree and the overall query execution time can be reduced.

These and further aspects and features of the present invention will be apparent with reference to the following description and attached drawings. In the description and drawings, particular embodiments of the invention have been disclosed in detail as being indicative of some of the ways in which the principles of the invention may be employed, but it is understood that the invention is not limited correspondingly in scope. Rather, the invention includes all changes, modifications and equivalents coming within the spirit and terms of the appended claims.

Features that are described and/or illustrated with respect to one embodiment may be used in the same way or in a similar way in one or more other embodiments and/or in combination with or instead of the features of the other embodiments.

It should be emphasized that the term "comprises/comprising" when used in this specification is taken to specify the presence of stated features, integers, steps or components but does not preclude the presence or addition of one or more other features, integers, steps, components or groups thereof.

Many aspects of the invention can be better understood with reference to the following drawings. The components in the drawings are not necessarily to scale, emphasis instead being placed upon clearly illustrating the principles of the present invention. To facilitate illustrating and describing some parts of the invention, corresponding portions of the drawings may be exaggerated in size, e.g., made larger in relation to other parts than in an exemplary device actually made according to the invention. Elements and features depicted in one drawing or embodiment of the invention may be combined with elements and features depicted in one or more additional drawings or embodiments. Moreover, in the drawings, like reference numerals designate corresponding parts throughout the several views and may be used to designate like or similar parts in more than one embodiment.

BRIEF DESCRIPTION OF THE DRAWING

The drawings are included to provide further understanding of the present invention, which constitute a part of the specification and illustrate the preferred embodiments of the present invention, and are used for setting forth the principles of the present invention together with the description. The same element is represented with the same reference number throughout the drawings. In the drawings:

Figure 1 is a flowchart of the method of an embodiment of the present invention  Figure 2 is a flowchart showing an example of selective estimate " = " condition Figure 3 is another flowchart of the method of an embodiment of the present invention 

Figure 4 is a flowchart showing parse query operation

Figure 5 is a flowchart showing repair an existing execution plan

Figure 6 shows the initial plan of the example 

Figure 7 shows the repaired plan of the example

Figure 8 shows the re-created plan of the example

Figure 9 is a schematic diagram of the optimizer of an embodiment of the present invention 

Figure 10 is another schematic diagram of the optimizer of an embodiment of the present invention

Figure 11 is a schematic diagram of the acquiring unit

Figure 12 is a schematic diagram of the repairing unit.

DETAILED DESCRIPTION

The many features and advantages of the embodiments are apparent from the detailed specification and, thus, it is intended by the appended claims to cover all such features and advantages of the embodiments that fall within the true spirit and scope thereof. Further, since numerous modifications and changes will readily occur to those skilled in the art, it is not desired to limit the inventive embodiments to the exact construction and operation illustrated and described, and accordingly all suitable modifications and equivalents may be resorted to, falling within the scope thereof.

The preferred embodiments of the present invention are described as follows in reference to the drawings.

Embodiment 1

This embodiment of the present invention provides a method of optimizing SQL query. Figure 1 is a flowchart of the method of an embodiment of the present invention. As shown in Figure 1, the method includes:

Step 101, extract one or more bind values from an inputted SQL query statement;

Step 102, calculate selectivity and correlation coefficient for the bind values;

Step 103, acquire an execution plan based on the selectivity and the correlation coefficient.

wherein the correlation coefficient indicates the correlation between the physical order of table tuples and the ordering of data values of particular column.

In implement, the correlation coefficient may be calculated based on the mathematical formula: Correlation(r) = [ N * F (XY) - (F (X) * F(X))] / [N * F(X^2) - (F (X) * F(X))];

where N is the value in sample, X and Y are values from 0 to N, T is the tuple number in value array (value array contains sorted tuples with actual physical tuple location. Tuple location is tuple number), and

F(X) = (N)*(N-l)/2
F (X^2) = (N) * (N-l) * (2*N -1) / 6.0
F (XY) can be calculated as below
For (i=0..N) F (XY) += i * T

It is noted that the above formulas are described as embodiments of this application. However, it is not limited thereto, and particular implement way may be determined as actually required.

As for selectivity, it is the estimation for number of rows that can be selected based on expression. Following statistics of a column may be used to calculate selectivity:

- MCV - It contains the K most common non-null values appearing in the column and their frequency.

- Histogram - It describes the distribution of data. It contains M (>=2) non-null values that divide the non-null column data values into M-l bins of approximately equal population.

- Estimation of Distinct values

- Estimation of Null values.

Figure 2 is a flowchart showing an example of selective estimate " = " condition. As shown in Figure 2, selectivity can be calculated using some statistics.

In this embodiment, all the above statistics may be calculated on sample data by background thread and store it in a system table. The detail of how to calculate selectivity may be referred in the prior art and it is not described there any more.

In this embodiment, for the queries having bind values, default selectivity is selected for the expressions in which they are used. During execution, the selectivity can be calculated and correlation coefficient can be referred when the actual value was received.

It can be seen from the above embodiment that through calculates selectivity and correlation coefficient for the bind values and acquires an execution plan based on the selectivity and the correlation coefficient, the SQL query can be optimized to a higher degree and the overall query execution time can be reduced.

Embodiment 2

Based on the embodiment 1, this embodiment of the present invention further provides a method of optimizing SQL query. The same content will not be described.

Figure 3 is a flowchart of the method of an embodiment of the present invention. As shown in Figure 3, the method includes:

Step 301, create an execution plan using default value of selectivity and correlation coefficient and store the execution plan in cache.

In this embodiment, as for the queries having bind values, default selectivity and correlation coefficient may be selected for the expressions in which they are used.

Figure 4 is a flowchart showing parse query operation. As shown in Figure 4, Parse tree is generated for the SQL query sent by the user. Parse tree is checked to see if there are any bind parameters in the query. A plan is created using the default values of selectivity and correlation coefficient if bind values are present in the query.

Step 302, extract one or more bind values from an inputted SQL query statement.

Step 303, calculate selectivity and correlation coefficient for the bind values.

In this embodiment, one or more bind values may be extracted from the SQL query sent by the user. And values of selectivity and correlation coefficient may be calculated for the bind values.

Step 304, calculate a difference value by comparing the selectivity and the correlation coefficient with stored values of execution plans in cache.

In this embodiment, these values of selectivity and correlation coefficient may be compared with the ones stored in each of the plans in the plan cache. Those plans in the plan cache may be created in step 101 and the number of those plans may be configured so that the comparing time is not too long.

In this embodiment, the selectivity and the correlation coefficient calculated in step 303may compare with the selectivity and the correlation coefficient of each plan stored in cache.

In implement, the closest value may be used to calculate the difference value. For example, the selectivity calculated in step 303 is 6 and the correlation coefficient calculated in step 303 is 8, the closest value of selectivity in cache is 6.2 and the closest value of correlation coefficient is 8.4, then the difference value may be calculated: [(6.2-6)+(8.4-8)]/2=0.3.

It is noted that the above content is just described as an example. However, it is not limited thereto, and particular implement way may be determined as actually required.

Step 305, compare the difference value with a first threshold and a second threshold;

and execute step 306 if the difference value is greater than the first threshold value and less than the second threshold value; execute step 307 if the difference value is less than the first threshold value; execute step 308 if the difference value is greater than the second threshold value Step 306, repair an existing execution plan.

In this embodiment, the execution plan corresponding to the closest value in step 304 may be repaired.

Step 307, select an existing execution plan.

In this embodiment, the execution plan corresponding to the closest value in step 304 may be selected directly.

Step 308, create a new execution plan.

In this embodiment, optimizer may be called to recompile the plan.

In this embodiment, the difference value (Diff) is the difference between the values of 'correlation coefficient' and 'selectivity' of the columns of current query and the values of 'correlation coefficient' and 'selectivity' of stored plans. The first threshold (Threshold 1) is the value such that a plan will neither be repaired nor be re-created if 'Diff is less than 'Thresholdl'. The second threshold (Threshold2) is the value such that a plan will be repaired if 'Diff' is higher than 'Thresholdl' but less than 'Threshold2'. A new plan will be generated if 'Diff is higher than 'Threshold2'.

Figure 5 is a flowchart showing repair an existing execution plan of step 306. As shown in Figure 5, repair an existing execution plan may specifically include:

Step 501, identify expressions where the bind values are used;

Step 502, identify all tables which are used in the expressions where the bind values are used;

Step 503, change the scan mode of the identified tables if required.

Step 504, judge if change in join order is required; execute step 505 if required and execute step 506 if not required.

Step 505, change the join order.

Step 506, return the repaired execution plan.

In this embodiment, there may be 2 levels of margin of error. If it crossed first level then plan repair will be attempted, if it crossed second level then entirely new plan will be constructed.

Furthermore, n number of plans will be maintained corresponding to different bind values where n will be configurable. The appropriate plan will be selected or re-selected during execution when the bind parameters will be received.

Furthermore, there can be configuration based on which the above plan modification during execution can be done. This configuration can be at server level, session level or at query level.

In this embodiment, an example with some cases has been provided to describe the present application in an even better fashion. In this example, consider tables T1 and T2 with the following schema.

For Query -Select * from tl,t2 where tl.coll = t2.coll and tl.coll < :a

Figure 6 shows the initial plan of the example.

Case 1: If the query ran with the value of :a as 1000, there will not be much of a difference between selectivity and correlation coefficient. So, the plan will remain the same.

Case 2: The rows are updated such a way that they are not ordered on coll anymore and the query ran with the value of :a as 1000.

In this case, selectivity is same, but the correlation coefficient value has changed, so, based on the threshold value it is decided to repair the plan.

Figure 7 shows the repaired plan of the example.

Case 3: If the query ran with the value of :a as 80000.

In this case, the correlation coefficient is same but the selectivity for the new bind value has very high difference. So, a new plan will be created.

Figure 8 shows the re-created plan of the example.

It can be seen from the above embodiment that through calculates selectivity and correlation coefficient for the bind values and acquires an execution plan based on the selectivity and the correlation coefficient, the SQL query can be optimized to a higher degree and the overall query execution time can be reduced.

Embodiment 3

This embodiment of the present invention further provides an optimizer, applied for optimizing SQL query. This embodiment corresponds to the method of the above embodiment 1 and the same content will not be described.

Figure 9 is a schematic diagram of the optimizer of an embodiment of the present invention. As shown in Figure 9, the optimizer 900 includes: an extracting unit 901, a first calculating unit 902 and an acquiring unit 903. Other parts of the optimizer 900 can refer to the existing technology and not be described in the present application.

Wherein, the extracting unit 901 is configured to extract one or more bind values from an inputted SQL query statement; the first calculating unit 902 is configured to calculate selectivity and correlation coefficient for the bind values; the acquiring unit 903 is configured to acquire an execution plan based on the selectivity and the correlation coefficient.

In this embodiment, the correlation coefficient indicates the correlation between the physical order of table tuples and the ordering of data values of particular column.

In implement, the correlation coefficient may be calculated based on the mathematical formula: Correlation(r) = [ N * F (XY) - (F (X) * F(X))] / [N * F(X^2) - (F (X) * F(X))];

where N is the value in sample, X and Y are values from 0 to N, T is the tuple number in value array, and F( X) = (N) * (N-l) / 2, F (X^2) = (N) * (N-l) * (2*N -1) / 6.0, F (XY) can be calculated as below

For (i=0..N) F (XY) += i * T

However, it is not limited thereto, and particular implement way may be determined as actually required.

It can be seen from the above embodiment that through calculates selectivity and correlation coefficient for the bind values and acquires an execution plan based on the selectivity and the correlation coefficient, the SQL query can be optimized to a higher degree and the overall query execution time can be reduced.

Embodiment 4

This embodiment of the present invention further provides an optimizer based on the embodiment 3. This embodiment corresponds to the method of the above embodiment 2 and the same content will not be described.

Figure 10 is another schematic diagram of the optimizer of an embodiment of the present invention. As shown in Figure 10, the optimizer 1000 includes: an extracting unit 901, a first calculating unit 902 and an acquiring unit 903, as described in embodiment 3.

As shown in Figure 10, the optimizer 1000 may further include: a second creating unit 1004 and a storing unit 1005;

Wherein the second creating unit 1004 is configured to create an execution plan using default value of selectivity and correlation coefficient; the storing unit 1005 is configured to store the execution plan in cache.

In this embodiment, the acquiring unit 903 may include more components. Figure 11 is a schematic diagram of the acquiring unit 903. As shown in Figure 11, the acquiring unit 903 may specifically include: a second calculating unit 1101 and a repairing unit 1102.

Wherein, the second calculating unit 1101 is configured to calculate a difference value by comparing the selectivity and the correlation coefficient with stored values of execution plans in cache; the repairing unit 1102 is configured to repair an existing execution plan if the difference value is greater than a first threshold value and less than a second threshold value.

As shown in Figure 11, the acquiring unit 903 may further include: a selecting unit 1103, the selecting unit 1103 is configured to select an existing execution plan if the difference value is less than the first threshold value.

As shown in Figure 11, the acquiring unit 903 may further include: a first creating unit 1104, the first creating unit 1104 is configured to create a new execution plan if the difference value is greater than the second threshold value.

Figure 12 is a schematic diagram of the repairing unit 1102. As shown in Figure 12, the repairing unit 1102 may specifically include: a first identifying unit 1201, a second identifying unit 1202 and a handling unit 1203;

Wherein, the first identifying unit 1201 is configured to identify expressions where the bind values are used; the second identifying unit 1202 is configured to identify all tables which are used in the expressions where the bind values are used; the handling unit 1203 is configured to repair an existing execution plan by changing the scan mode of the identified tables.

In this embodiment, the handling unit 1203 may further be configured to repair an existing execution plan by changing the join order.

It can be seen from the above embodiment that through calculates selectivity and correlation coefficient for the bind values and acquires an execution plan based on the selectivity and the correlation coefficient, the SQL query can be optimized to a higher degree and the overall query execution time can be reduced.

It should be understood that each of the parts of the present invention may be implemented by hardware, software, firmware, or a combination thereof. In the above embodiments, multiple steps or methods may be realized by software or firmware that is stored in the memory and executed by an appropriate instruction executing system. For example, if it is realized by hardware, it may be realized by any one of the following technologies known in the art or a combination thereof as in another embodiment: a discrete logic circuit having a logic gate circuit for realizing logic functions of data signals, application-specific integrated circuit having an appropriate combined logic gate circuit, a programmable gate array (PGA), and a field programmable gate array (FPGA), etc.

The description or blocks in the flowcharts or of any process or method in other manners may be understood as being indicative of comprising one or more modules, segments or parts for realizing the codes of executable instructions of the steps in specific logic functions or processes, and that the scope of the preferred embodiments of the present invention comprise other implementations, wherein the functions may be executed in manners different from those shown or discussed, including executing the functions according to the related functions in a substantially simultaneous manner or in a reverse order, which should be understood by those skilled in the art to which the present invention pertains.

The logic and/or steps shown in the flowcharts or described in other manners here may be, for example, understood as a sequencing list of executable instructions for realizing logic functions, which may be implemented in any computer readable medium, for use by an instruction executing system, device or apparatus (such as a system including a computer, a system including a processor, or other systems capable of extracting instructions from an instruction executing system, device or apparatus and executing the instructions), or for use in combination with the instruction executing system, device or apparatus.

The above literal description and drawings show various features of the present invention. It should be understood that those skilled in the art may prepare appropriate computer codes to carry out each of the steps and processes as described above and shown in the drawings. It should be also understood that all the terminals, computers, servers, and networks may be any type, and the computer codes may be prepared according to the disclosure to carry out the present invention by using the apparatus.

Particular embodiments of the present invention have been disclosed herein. Those skilled in the art will readily recognize that the present invention is applicable in other environments. In practice, there exist many embodiments and implementations. The appended claims are by no means intended to limit the scope of the present invention to the above particular embodiments. Furthermore, any reference to "a device to..." is an explanation of device plus function for describing elements and claims, and it is not desired that any element using no reference to "a device to..." is understood as an element of device plus function, even though the wording of "device" is included in that claim.

Although a particular preferred embodiment or embodiments have been shown and the present invention has been described, it is obvious that equivalent modifications and variants are conceivable to those skilled in the art in reading and understanding the description and drawings. Especially for various functions executed by the above elements (portions, assemblies, apparatus, and compositions, etc.), except otherwise specified, it is desirable that the terms (including the reference to "device") describing these elements correspond to any element executing particular functions of these elements (i.e. functional equivalents), even though the element is different from that executing the function of an exemplary embodiment or embodiments illustrated in the present invention with respect to structure. Furthermore, although the a particular feature of the present invention is described with respect to only one or more of the illustrated embodiments, such a feature may be combined with one or more other features of other embodiments as desired and in consideration of advantageous aspects of any given or particular application.

WE CLAIM:

1. A method of optimizing SQL (Structured Query Language) query, the method comprising:

extracting one or more bind values from an inputted SQL query statement;

calculating selectivity and correlation coefficient for the bind values; wherein the correlation coefficient indicates the correlation between the physical order of table tuples and the ordering of data values of particular column;

acquiring an execution plan based on the selectivity and the correlation coefficient.

2. The method according to claim 1, wherein acquiring an execution plan based on the selectivity and the correlation coefficient specifically comprising:

calculating a difference value by comparing the selectivity and the correlation coefficient with stored values of execution plans in cache;

repairing an existing execution plan if the difference value is greater than a first threshold value and less than a second threshold value.

3. The method according to claim 2, wherein the method further comprising:

selecting an existing execution plan if the difference value is less than the first threshold value;

4. The method according to claim 2, wherein the method further comprising:

creating a new execution plan if the difference value is greater than the second threshold value.

5. The method according to claim 2, wherein repairing an existing execution plan if the difference value is greater than a first threshold value and less than a second threshold value specifically comprising:

identifying expressions where the bind values are used;

identifying all tables which are used in the expressions where the bind values are used;

repairing an existing execution plan by changing the scan mode of the identified tables.

6. The method according to claim 5, wherein the method further comprising: repairing an existing execution plan by changing the join order.

7. The method according to claim 1, wherein the method further comprising: creating an execution plan using default value of selectivity and correlation coefficient; storing the execution plan in cache.

8. An optimizer, applied for optimizing SQL (Structured Query Language) query, the optimizer comprising:

an extracting unit, configured to extract one or more bind values from an inputted SQL query statement;

a first calculating unit, configured to calculate selectivity and correlation coefficient for the bind values; wherein the correlation coefficient indicates the correlation between the physical order of table tuples and the ordering of data values of particular column;

an acquiring unit, configured to acquire an execution plan based on the selectivity and the correlation coefficient.

9. The optimizer according to claim 8, wherein the acquiring unit specifically comprising:

a second calculating unit, configured to calculate a difference value by comparing the selectivity and the correlation coefficient with stored values of execution plans in cache;

a repairing unit, configured to repair an existing execution plan if the difference value is greater than a first threshold value and less than a second threshold value.

10. The optimizer according to claim 9, wherein the acquiring unit further comprising:

a selecting unit, configured to select an existing execution plan if the difference value is less than the first threshold value;

11. The optimizer according to claim 9, wherein the acquiring unit further comprising:

a first creating unit, configured to create a new execution plan if the difference value is greater than the second threshold value.

12. The optimizer according to claim 9, wherein the repairing unit specifically comprising:

a first identifying unit, configured to identify expressions where the bind values are used;

a second identifying unit, configured to identify all tables which are used in the expressions where the bind values are used;

a handling unit, configured to repair an existing execution plan by changing the scan mode of the identified tables.

13. The optimizer according to claim 12, wherein the handling unit further configured to repair an existing execution plan by changing the join order.

14. The optimizer according to claim 8, wherein the optimizer further comprising:

a second creating unit, configured to create an execution plan using default value of selectivity and correlation coefficient;

a storing unit, configured to store the execution plan in cache.