Field of the Disclosure
The field of the present disclosure pertains to batch optimization of query execution in a database system. Particularly, the disclosure relates to batch optimization of execution of dependent queries in a database system where a huge number of tables is involved.
Background
Query processing is one of the critical components in a database system. The primary reason is that queries are the most common forms of interaction between human beings and a database system.
A query optimizer is typically invoked every time a fresh query enters into the system. It is designed to determine the most efficient way to execute a given query by considering the possible query plans. If a query optimizer selects a poor query execution plan, the performance of the database system in responding to the query can be poor. In fact, the differences in cost between the least and most expensive query execution plans can be several orders of magnitude. On the other hand, it can be prohibitively expensive for the query optimizer to search exhaustively for a very optimal plan of query execution.
Certain conventional query execution engines follow a query centric approach, where each query is executed independently one after the other and independent plans are created subsequently for them. However, on the other hand, there are several concurrently running queries with common parts of data and work, which create an opportunity for sharing among concurrent queries.
Lately, some query execution engines have been found to share sub- plan results across the queries so that there is no need for doing the job again.
The existing approaches of query execution and planning usually do not consider interdependency between the queries and do not get any advantage in the case of dependent queries. Moreover, the plan moves through all possible paths, and the “combining” path is also checked.
In prior art, the intermediate results are shared across dependent queries, however, all queries are planned independently and interrelation between queries during the planning time are not considered.

Defining an optimal join order is another complicated task in query optimization and one that has been a subject of extensive research since long time. Join ordering takes huge time when multiple tables are to be joined. However, in cases when very high selectivity tables are joined, i.e. very few records are selected, then spending huge amount of time in planning is not a requirement.
Summary
In order to provide an optimized query execution technique in a database system, embodiments of the present invention disclosure relate to a method for execution of query by way of a plan which saves the overall cost of execution. For example, if a part of the query execution plan exists in any other plan, then that part is borrowed from the existing plan. Accordingly, the cost of that part is not included when the overall cost is calculated.
In an embodiment of the present invention disclosure, a method for execution of queries in a database system is disclosed.
In this claimed method for executing a query in a database system, execution of query comprises a plan having at least one step and cost associated to each step and the database system stores at least one existing plan. The method comprises establishing at least two candidate plans for executing the query, wherein one of the at least two candidate plans is a first plan, determining a cost of the first plan by cumulating costs of steps of the first plan, wherein when a step of the first plan is same as a step of the existing plan, skipping the cost of the step of cumulating, choosing the candidate plan having the least cost as the plan for executing the query and executing the query based on the chosen candidate plan.
According to an embodiment of the invention disclosure, before the step of choosing the candidate plan which has the least cost as the plan for executing the query, the method comprises adding a cost of the existing plan to the cost of the first plan as the cost of the first plan.
According to an embodiment of the invention disclosure, the database system stores outputs of steps of the existing plan, the step of executing the query based on the chosen candidate plan comprising executing the query based on the chosen candidate plan step by step, when a step of the chosen candidate plan is the same as a step of the existing plan, obtaining the output of the step of the existing plan stored in the database system as the output of the step of the chosen candidate plan.

According to another embodiment of the disclosure, after executing the query based on the chosen candidate plan, the method comprises storing the output of every step of the chosen candidate plan in the database system.
According to yet another embodiment, a database system for executing a query, every executing comprises a plan, and every plan comprises at least one step, and every step comprises a cost obtained by executing the every step, and the database system stores at least one existing plan, the database system comprising a memory and a processor coupled to the memory, wherein the memory is configured to store the existing plan. Further, the processor is configured to establish at least two candidate plans for executing the query, wherein one of the at least two candidate plans is a first plan, calculate a cost of the first plan by cumulating costs of steps of the first plan, wherein when a step of the first plan is the same as a step of the existing plan, skipping the cost of the step in the cumulating, choose the candidate plan which has the least cost as the plan for executing the query and execute the query based on the chosen candidate plan.
According to another embodiment of the invention disclosure, the processor is configured to add a cost of the existing plan to the cost of the first plan as the cost of the first plan, before choosing the candidate plan which has the least cost as the plan for executing the query.
In yet another embodiment, the processor is configured to execute the query based on the chosen candidate plan step by step, when a step of the chosen candidate plan is the same as a step of the existing plan, obtain the output of the step of the existing plan stored in the database system as the output of the step of the chosen candidate plan.
In another embodiment of the disclosure, the processor is configured to store the output of every step of the chosen candidate plan in the database system, after the executing the query based on the chosen candidate plan.
Brief Description of Figures
The detailed description is described with reference to the accompanying figures. In the figures, the left¬most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the drawings to reference like features and components.

Figure 1 illustrates a block diagram of a system according to an embodiment of the present
invention disclosure.
Figure 2 illustrates a block diagram of a Database Server, according to an embodiment of the
present invention disclosure.
Figure 3 illustrates a flow diagram of a query plan creation module, according to an embodiment
of the present invention disclosure.
Figure 4 illustrates a flow diagram of a query execution module, according to an embodiment of
the present invention disclosure.
Detailed Description
The following discussion provides a brief, general description of a suitable computing environment in which various embodiments of the present disclosure can be implemented. The aspects and embodiments are described in the general context of computer executable mechanisms such as routines executed by a handheld device e.g. a mobile phone, a personalized digital assistant, a cellular device, a tablet et al. The embodiments described herein can be practiced with other system configurations, including Internet appliances, hand held devices, multi-processor systems, microprocessor based or programmable consumer electronics, network PCs, mini computers, mainframe computers and the like. The embodiments can be embodied in a special purpose computer or data processor that is specifically programmed configured or constructed to perform one or more of the computer executable mechanisms explained in detail below.
Exemplary embodiments now will be described with reference to the accompanying drawings. The disclosure may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey its scope to those skilled in the art. The terminology used in the detailed description of the particular exemplary embodiments illustrated in the accompanying drawings is not intended to be limiting. In the drawings, like numbers refer to like elements.
The specification may refer to “an”, “one” or “some” embodiment(s) in several locations. This does not necessarily imply that each such reference is to the same embodiment(s), or that the feature only

applies to a single embodiment. Single features of different embodiments may also be combined to provide other embodiments.
As used herein, the singular forms “a”, “an” and “the” are intended to include the plural forms as well, unless expressly stated otherwise. It will be further understood that the terms “includes”, “comprises”, “including” and/or “comprising” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. It will be understood that when an element is referred to as being “connected” or “coupled” to another element, it can be directly connected or coupled to the other element or intervening elements may be present. Furthermore, “connected” or “coupled” as used herein may include wirelessly connected or coupled. As used herein, the term “and/or” includes any and all combinations and arrangements of one or more of the associated listed items.
Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this disclosure pertains. It will be further understood that terms, such as those defined in commonly used dictionaries, should be interpreted as having a meaning that is consistent with their meaning in the context of the relevant art and will not be interpreted in an idealized or overly formal sense unless expressly so defined herein.
The figures depict a simplified structure only showing some elements and functional entities, all being logical units whose implementation may differ from what is shown. The connections shown are logical connections; the actual physical connections may be different. It is apparent to a person skilled in the art that the structure may also comprise other functions and structures. It should be appreciated that the functions, structures, elements and the protocols used in communication are irrelevant to the present disclosure. Therefore, they need not be discussed in further detail here.
In addition, all logical units described and depicted in the figures include the software and/or hardware components required for the unit to function. Further, each unit may comprise within itself one or more components, which are implicitly understood. These components may be operatively coupled to each other and be configured to communicate with each other to perform the function of the said unit.
The present invention deals with batch optimization of queries in a database system. Specifically, the method relates to optimization of queries having larger number of tables to be joined. The invention addresses issues relating to cost involved in a query execution plan. While calculating the cost involved,

an original costly path is selected at first instance, so that it becomes cheaper by borrowing the existing plan. If any part of the plan exists in any other plan, that part is borrowed and hence, the cost of this part is not considered when the overall cost is being calculated.
The method is used in OLAP system where number of relations in the Join are huge and many queries might be operating on the common tables. In case of OLAP, many queries have a common intermediate node (Tables scan, join etc.) where the result is not latest. In such case, the method employed creates a best group plan and saves a huge execution cost.
Figure 1 illustrates a block diagram of a system for optimal execution of queries, according to an embodiment of the present invention disclosure. As shown, one or more client units/machines 101 (1, 2….n) are configured to process one or more queries and generate results of the queries which is processed through network 103 to a computing unit 105. The computing unit 105 comprises of a processing unit 107 within it which is meant for processing the queries, from where the processed queries and their results are subsequently transmitted to one or more database servers 109 (1, 2….to n) respectively.
Figure 2 illustrates a database server 109, which comprises of a memory 111 to store the queries and the results obtained by executing the queries. A disk 113 is enabled to be connected to the memory 111 and both the disk and memory are interconnected to a query optimizer 115. According to an embodiment, the query optimizer 115 functions in a specific manner as described in the subsequent paragraphs.
Figure 3 illustrates a flow diagram of the query optimizer 115 according to an embodiment of the present invention disclosure. Each query is prepared and parsed and an optimal plan is created. Then the other existing plans are checked and dependent nodes in the other existing plans are found, like if multiple queries are joining two tables on same conditions or multiple queries wish to scan same tables. According to an embodiment of the invention, the path for the dependent node is verified for best suitability. If it is suitable, then dependency between plan nodes is put such that the executor can store/reuse results. If it is not suitable, an alternative path is suggested for nodes and the path where sum of Cost (plan 1) and Cost (plan 2) is the least is selected. A final plan is generated based on the group cost of the two plans.
Figure 4 illustrates a plan execution module according to an embodiment of the present invention disclosure. As a first step, the plan execution is initiated node by node. If any of the nodes have

dependency on other results, the result is fetched from the other cache, else normal processing is pursued. If the result needs to be used by the other node, then results are stored in cache. The result cache gets expired by background after certain time period. Process of refreshing the cache is not a part of this invention.
The aforementioned description of the embodiments of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above. It is intended that the scope of the invention be limited not by this detailed description, rather by the claims appended hereto.
As will be appreciated by one skilled in the art, the present invention may be embodied as a method, system, or computer program product. Accordingly, the present invention may take the form of an entirely hardware embodiment, a software embodiment or an embodiment combining software and hardware aspects all generally referred to herein as a "circuit" or "module." Furthermore, the present invention may take the form of a computer program product on a computer-usable storage medium having computer-usable program code embodied in the medium.
It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.
Instructions may also be loaded onto a computer or other programmable data processing apparatus like a scanner/check scanner to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.
In the drawings and specification, there have been disclosed exemplary embodiments of the invention. Although specific terms are employed, they are used in a generic and descriptive sense only and not for purposes of limitation, the scope of the invention being defined by the following claims.

We claim: -
1. A method for executing a query in a database system, wherein execution of query comprises a
plan having at least one step and cost associated to each step and the database system stores at
least one existing plan, the method comprising:
establishing at least two candidate plans for executing the query, wherein one of the at least two candidate plans is a first plan;
determining a cost of the first plan by cumulating costs of steps of the first plan, wherein when a step of the first plan is same as a step of the existing plan, skipping the cost of the step of cumulating;
choosing the candidate plan having the least cost as the plan for executing the query;
executing the query based on the chosen candidate plan.
2. The method as claimed in claim 1, wherein before the step of choosing the candidate plan which
has the least cost as the plan for executing the query, the method comprising:
adding a cost of the existing plan to the cost of the first plan as the cost of the first plan.
3. The method as claimed in claim 1 or 2, wherein the database system stores outputs of steps of
the existing plan, the step of executing the query based on the chosen candidate plan comprising:
executing the query based on the chosen candidate plan step by step;
when a step of the chosen candidate plan is the same as a step of the existing plan, obtaining the output of the step of the existing plan stored in the database system as the output of the step of the chosen candidate plan.
4. The method as claimed in any one of claims 1 to 3, wherein after executing the query based on
the chosen candidate plan, the method comprising:
storing the output of every step of the chosen candidate plan in the database system.
5. A database system for executing a query, every executing comprises a plan, and every plan
comprises at least one step, and every step comprises a cost obtained by executing the every step,

and the database system stores at least one existing plan, the database system comprising a memory and a processor coupled to the memory;
the memory is configured to store the existing plan;
the processor is configured to:
establish at least two candidate plans for executing the query, wherein one of the at least two candidate plans is a first plan;
calculate a cost of the first plan by cumulating costs of steps of the first plan, wherein when a step of the first plan is the same as a step of the existing plan, skipping the cost of the step in the cumulating;
choose the candidate plan which has the least cost as the plan for executing the query;
execute the query based on the chosen candidate plan.
6. The database system as claimed in claim 5, the processor is configured to:
add a cost of the existing plan to the cost of the first plan as the cost of the first plan, before choosing the candidate plan which has the least cost as the plan for executing the query.
7. The database system as claimed in claim 5 or 6, the processor is configured to:
execute the query based on the chosen candidate plan step by step;
when a step of the chosen candidate plan is the same as a step of the existing plan, obtain the output of the step of the existing plan stored in the database system as the output of the step of the chosen candidate plan.
8. The database system as claimed in any one of claims 5 to 7, the processor is configured to:
store the output of every step of the chosen candidate plan in the database system, after the executing the query based on the chosen candidate plan.