FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
COMPLETE SPECIFICATION
(See Section 10 and Rule 13)
TITLE OF INVENTION:
METHOD AND SYSTEM FOR ESTIMATING DATABASE QUERY COST FOR PRODUCTION DATABASE DURING APPLICATION DEVELOPMENT
Applicant
Tata Consultancy Services Limited A company Incorporated in India under The Companies Act, 1956
Having address:
Nirmal Building, 9th Floor,
Nariman Point, Mumbai 400021,
Maharashtra, India
The following specification particularly describes the invention and the manner in which it is to be performed.

FIELD OF THE INVENTION
[001] This invention generally relates to the field of software testing and development. More particularly, the invention relates to prediction of query elapsed response time for a large size database during an application development stage.
BACKGROUND OF THE INVENTION
[002] Now days the utilization of databases has been widely increased such that each and every sector of society relies on databases and database management systems for their internal and external development and commercialization. Operational Databases or Production Databases are very important to a business as large amount of information is stored in these databases which can be retrieved quickly and accurately as per the requirement. The operational database used is designed to speed up the retrieval of large amounts of information with high efficiency. The operational database provides real time execution of read or writes requests through pre-defined SQL queries. These complex SQL queries are executed on mass amount of data. As a developer, these SQLs are generated during application development stage and are tested against a fraction of production database size to check the (Service Level Agreement) SLA compliance. However, once the application is deployed, the database size grows with the time and earlier tested SQLs no longer meet the SLA requirements.
[003] It is very important to optimize an SQL query so that it may meet the service level
agreement at any point of time, particularly, after the deployment of the application.
[004] One such method has disclosed a Query performance prediction module as a part
of an applications layer. This module correlates estimated system cost information for a database query with statistics compiled from previous queries in order to estimate the system response time. Thus, it depends on the history of past executed queries.
[005] In one of the method and apparatus, the database query cost estimation is based on
the total computer resources used and estimated elapsed time for the production of a first row and last row of operator involved in the query. Preliminary costs are assigned to the

operators and the costs of operators are combined including the blocking operators. Thus, this optimization is based on the query content only and involves execution in development database only while not considering the production database size. [006] Another method discussed in prior art estimates the query statement's costs by analyzing components of the query statement and the trigger procedure that is invoked in response to execution of the query to determine a processing time. Per row cost of execution is calculated and applied further to calculate it for multiple rows. This invention is mainly related to the estimation of time required for execution of trigger procedure which gets invoked in response of query execution. Cost estimation is based on query components and triggers procedure components analysis and required processing time. Here, they are considering the query execution on real time application database and not speaking about the large size production database. So there is need of consideration of large size production database requirement at the time of application development. [007] Most of the approaches disclosed in the prior art predict a query cost based on the past history of the executed queries on the database i.e. machine learning approach. This requires maintaining history of past executions of different queries on database. This will not be applicable at application development time. In some of the cases the work is specific to the internal of the DB server.
[008] Also these techniques are based on execution of query in current production
database and remains silent on consideration of the several times large size production database in future.
[009] Therefore, there is a need of a system and method which is capable of optimizing
the query by considering the size of the database. The system and method should be capable of optimizing the query in order to hold the service level agreements with the passage of time.
OBJECTIVES OF THE INVENTION
[0010] The principle object of the present invention is to optimize database query cost at the development phase of a software application.

[0011] Another significant object of the invention is to emulate a production database which can adhere to properties of a production database.
[0012] It is another object of the present invention to execute queries on a virtually emulated production database and optimize the cost of the query according to the SLA requirements. Further, this helps a developer to understand the query execution path in the production database.
[0013] Still another significant object of the present invention is to consider different most sensitive statistics of a production database which influence the query cost and accordingly develop the emulated production database.
SUMMARY OF THE INVENTION
[0014] The present invention discloses a method for predicting elapsed response time for one or more database queries with respect to a cost based optimized (CBO) relational database in an application development environment. The method comprises of determining an estimate amount of cost and elapsed response time for the execution of at least one database query with respect to a first relational database, identifying one or more parameters from the first relational database affecting the database query cost, such that these parameters are sensitive to size of a second relational database and impact the database query execution cost and the database query elapsed response time and emulating the second relational database by extrapolating the identified parameters at an application development stage. The method further comprises of predicting the database query elapsed response time with respect to the second relational database and further predicting the query cost in both the first relational database and the emulated second relational database in the application development environment.
[0015] The present invention also discloses a system for predicting elapsed response time (ERT) for one or more database queries with respect to a relational database in an

application development environment.The system comprises of a first relational database and a database query in the application development environment, a cost estimation module configured to determine an estimate amount of cost for database query execution with respect to a first relational database and an identification module configured to identify one or more sensitive statistics of the database or parameters from the first relational database affecting database query cost, such that these parameters are sensitive to size of a second relational database and impact the database query execution cost and database query elapsed response time. The system further comprises of an emulated database configured by extrapolating the identified parameters/statistics by means of a calculation module at the application development stage and a prediction module configured to predict the database query elapsed response time with respect to the second relational database and further predicting the query cost in both the first relational database and emulated database in the application development environment.
BRIEF DESCRIPTION OF DRAWINGS
[0016] Figure 1 illustrates the system architecture in accordance with an embodiment of
the invention. [0017] Figure 2 illustrates the query elapsed response time in accordance with an
exemplary embodiment of the system. [0018] Figure 3 illustrated the query elapsed response time in accordance with an
exemplary embodiment of the system. [0019] Figure 4 illustrates the query elapsed time in accordance with an exemplary
embodiment of the invention. [0020] Figure 5 illustrates the process flow for predicting an elapsed response time for
one or more database queries with respect to a relational database in an application
development environment in accordance with one or more embodiment of the invention.

DETAILED DESCRIPTION
[0021] Some embodiments of this invention, illustrating its features, will now be discussed:
[0022] The words "comprising", "having", "containing", and "including", and other forms thereof, are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items.
[0023] It must also be noted that as used herein and in the appended claims, the singular forms "a", "an", and "the" include plural references unless the context clearly dictates otherwise. Although any systems, methods, apparatuses, and devices similar or equivalent to those described herein can be used in the practice or testing of embodiments of the present invention, the preferred, systems and parts are now described. In the following description for the purpose of explanation and understanding reference has been made to numerous embodiments for which the intent is not to limit the scope of the invention.
[0024] One or more components of the invention are described as module for the understanding of the specification. For example, a module may include self-contained component in a hardware circuit comprising of logical gate, semiconductor device, integrated circuits or any other discrete component. The module may also be a part of any software program executed by any hardware entity for example processor. The implementation of module as a software program may include a set of logical instructions to be executed by the processor or any other hardware entity. Further a module may be incorporated with the set of instructions or a program by means of an interface.
[0025] The disclosed embodiments are merely exemplary of the invention, which may be embodied in various forms.
[0026] The present invention relates to a method and system for predicting elapsed response time for one or more database queries with respect to a relational database in an application development environment. The method and system for identifies one or more parameters/database statistics which are sensitive to size of one or more relational database. A large size relational database is emulated at an application development stage

by extrapolating the identified parameters which affects the query response time for predicting the elapsed response time for the large size relational database.
[0027] In accordance with an embodiment referring to figure 1, the system (l00)comprises of a first relational database (102) and a database query (104) in an application development environment. The system (100) further comprises of a cost estimation module (106). a second relational database (108), an identification module (110) and a prediction module (112).
[0028] The cost estimation module (106) is configured to determine an estimate amount of cost for database query (104) execution with respect to the first relational database (102) (as shown in step 502 of figure 5).
[0029] The relational database comprises of a CBO (Cost Based Optimizer) database. The first relational database (102) comprises of a development database and a second relational database (108) comprises of a production database. The production database is the projected large size database assumed to be having uniform distribution of data.
[0030] In accordance with a method embodiment of the invention implemented by the system (100) CBO database stores important data, which could impact a query performance, about all database objects created by a user such as table, index, and view etc in system tables. This information is referred as statistics by DB community. Cost estimation module (106) in CBO database determines the amount of resources required by the query without actually executing it and measured in terms of 'cost'. It is based on the critical statistics of the database system and the database schema.
[0031] The system (100) further comprises of an identification module (110) configured to identify one or more parameters from the first relational database (102). These parameters affect the database query cost and are sensitive to the size of the second relational database (production database) (108). These parameters also affect the database query elapsed response time (as shown in step 504 of figure 5).
[0032] The identified parameters affecting the database query cost and its elapsed response time comprises at least one of database schema, optimizer parameters and database size sensitive schema statistics.

[0033] In accordance with another embodiment, the one or more identified parameters may include but is not limited to table statistics such as number of rows, number of blocks and average row length, column statistics such as average column length, low value, high value, density values and histograms, and index statistics such as number of levels, distinct values, number of rows, leaf blocks, clustering factor, average number of leaf blocks per key and average number of data blocks per key.
[0034] Further, the cost estimation module (106) considers the system statistics and database statistics which may capture certain extent of the impact of query ERT dependence parameters (as mentioned earlier) to estimate the cost. The system statistics capture the CPU speed and I/O seek and data transfer times. The database statistics capture schema and data details. The schema details include types of indexes on the indexed columns for each table. The data details include the size of each table with the data distribution in each column of every table. Therefore, the cost estimation module (106) can be used for query ERT prediction on any of the database without executing the query. For example, for any large size production database which is not available at application design time the cost estimation module can be used.
[0035] The Cost estimation module (106) estimates the execution cost for this database query at the development stage which is referred as "EstimatedCostDevDB''•
[0036] Since the second relational database (production database) is not available at the development stage, the system (100) further comprises of an emulated production database (108). The production database (108) is emulated by means of a calculation means (114) which extrapolates the database schema statistics and the system statistics as provided at the development stage by the identification module (110). The emulation of the database is made by extrapolation of the database statistics identified by the identification module (110) (as shown in step 506 of figure 5).
[0037] The cost estimation module (106) also determines an estimate amount of cost for the second relational database.

[0038] The emulated second relational database (108) further comprises of at least one of
imported metadata from the first relational database (102) and schema of the first
relational database (102) and the extrapolated schema statistics. [0039] A database schema has three main components - tables, columns and indexes. A
cost based optimizer (CBO) evaluates various execution paths, with their costs, for a
query before choosing the best execution plan. [0040] The cost of an execution plan depends on;
1. The various statistics of table, columns and indexes involved in the query execution.
2. The system statistics on which the query is executing and
3. The DB Server settings.
[0041] Different DB servers may have different types of statistics for each of these objects. Using all these statistics may increase the complexity of the system. Therefore, using query traces, by way of specific example, 10053 from Oracle, available by Database Server, it is understood that even a small change in values for some statistics highly impact the query estimated cost, such statistics are referred as sensitive statistics. These identified sensitive statistics changes with change in data size or its values, for each object of the database. [0042] Table sensitive statistics: The table statistics of all the user tables in the database are stored in the system tables such as USER TABLES. This table stores all the physical details of the tables. However, variation in a query performance with increase in database size is most sensitive to the followings table statistics:
Number of rows in the tables being accessed
Number of blocks allocated to the table
Average row length [0043] Column Sensitive Statistics: The column statistics of all tables are stored in the system table such as USER_TAB_COLUMNS. The system table stores physical details of all columns of each table, however following are the most important ones to discuss in the perspective of query performance.
Number of distinct values for a column

Number of nulls in a column Density
Low Value/High Value Histogram [0044] Index sensitive statistics: The physical storage details of various indexes created in column(s) are stored in system table such as USERfNDEXES. The followings statistics of index affect query response time.
Number of leaf blocks allocated to indexes
Number of levels in the B-Tree
Clustering factor - how the order of the index matches the order of the table rows
Number of rows on which the index is created.
Average number of leaf nodes per key
Average number of data blocks per key
[0045] There are various other statistics which are specific to DB server such as block size and multi-block read count, and the DB hardware system such as single block read time (spreadtime) and CPU speed etc.. which impacts the query estimated cost. However, these statistics do not change with change in the database size i.e. invariant to the data.
[0046] The schema statistics on objects- table, column and index change with increase in number of rows in the corresponding table. The schema statistics are extrapolated by the computation module and are based on the number of rows and pattern of columns values and data distribution.
[0047] By way of specific example, let us consider a development database. We can run the DB proprietary SQLs to gather schema and data statistics on the database.
[0048] Let these statistics are as follows.
[0049] For each table, let us assume NumBlkDev: number of blocksNumRowsDev': number of rows. Please note that the Average row length does not change with increase in database size due to uniform distribution of data.

1. For each columns of every table assumeNumDtDev- number of distinct values, DensityDev-Density,NumNullsDev; number of nulls. The histogram, low value and high value of a column depend on data distribution. It is expected from user to provide this information for production database: otherwise they are kept at the same value as at the development database.
[0050] For each index consider,CFDev: value for clustering factor NumLBDev: number of leaf blocks, NumIRowsDev: number of rows on which the index is build and NumLevelsDev: number of levels in the index B+ tree.Avg_Dblk_keyDev: Average data blocks per key and Avg_lfblk_keyDev: Average number of leaf blocks per key.
[0051 ] The projected values of these parameters for production database of number of
rows, NumRowsprod, as given by the user are discussed as follows. [0052] Since the size of database block and average row length is fixed, the number of
blocks required for a table increases proportionately with increase in number of rows.
Therefore, for each table the extrapolated number of blocks is

[0053] Uniform distribution of data is assumed, therefore number of distinct values in a column, its density (which generally is inverse to number of distinct values) and number of nulls increases in proportion to increase in the number of rows. Therefore, for every column of every table the extrapolated values are:

[0054] Now, since the number of distinct values of a column are increasing proportional to increase in DB size, hence the index size on the column also increases in proportion and hence the number of leaf nodes. The clustering factor signifies order in which the rows have been inserted and hence their storage (whether sequential or scattered). Since there is

no special reason for changing the rows insertion patterns, it is also uniformly increased. Therefore, for each index the extrapolated statistics are:

NumLevelsProd is the depth of the B+ tree having NumlRowsProd rows and of

[0055] The system (100) further comprises of the prediction module (112) which communicates with the cost estimation module (106) and is configured to interact with the first relational database (development database) (102) and the emulated database (108) to predict the database query elapsed response time. The system (100) also predicts the query execution cost for both the first relational database (development database) (102) and the second relational database (production database) through the emulated database (108). The predicted cost of the SQL query is then passed to the time estimation module (not shown in figure)which predicts elapsed response time of the query at different saturation levels of the system (100)as shown below (as shown in step 508 of figure 5).

[0056] In accordance with another embodiment, the elapsed response time of the second relational database by means of the emulated database (108) is predicted in terms of query execution cost in first relational database and second relational database.
[0057] The preceding description has been presented with reference to various embodiments of the invention. Persons skilled in the art and technology to which this

invention pertains will appreciate that alterations and changes in the described structures and methods of operation can be practiced without meaningfully departing from the principle, spirit and scope of this invention.
[0058] The system and method illustrated for facilitating the predicting elapsed response time for one or more database queries with respect to relational database in an application development environment is interpreted further for a specific purpose may be illustrated by working examples stated in the following paragraph; the process is not restricted to the said examples only:
[0059] Let us consider a specific DB server, Oracle 10gR2, as a case study to show the applicability of the system and method as described above. Let us conduct the experiment on quad core server with 4GB RAM connected to fiber channel SAN with 1TB storage. Let us take measurements for TPC-H benchmarks and applied the system for prediction,
[0060] Let us take the measurements for three TPC-H queries which access only the table limitem, which is the largest sized table (approx 80% of the total size) in the TPC-H database. These three queries are shown in the Table 1.
Table 1TPC-H Queries used for Measurements
Query 1: Complex STQ with Sort and Group By operators
select
lreturnflag,
1_linestatus,
sum(l_quantity) as sum_qty,
sum(l_extendedprice) as sum_base_price,
sum(l_extendedprice * (1 - l_discount)) as sum_disc_price,
sum(l_extendedprice * (1 - l_discount) * (1 + l_tax)) as sum_charge,
avg(I_quantity) as avg_qty,
avg(l extendedprice) as avg_price,
avg(l_discount) as avg_disc,

count(*) as count order
from
lineitem
where
I_shipdate<= date '1998-12-01' - interval 75' day (3)
group by
1_return flag,
1_linestatus
order by
1_returnflag,
l_linestatus;
Query 2: Simple STQ
select
sum(l_extendedprice * l_discount) as revenue
from
lineitem
where
l_shipdate>= date '1994-01-01'
and 1 shipdate< date '1994-01-01' + interval T year
and Idiscount between 0.02 - 0.01 and 0.02 + 0.01
and l_quantity< 25;
Query 3: STQ with index scan on Ishipdate
select
sum(l_extendedprice * l_discount) as revenue
from
lineitem
where
1 shipdate = date '1994-01-01';
[0061] These are complex queries requiring sorting, grouping and index access. We show applicability of the system (100) for these queries. However, this is extendible to multi-table queries as well. Let us take multiple samples for each query execution to balance out the deviation in multiple measurements. Let us eliminate the effect of cache on query

execution by flushing the OS and DB buffer cache before taking the measurements. To manage SAN cache, we take measurements after running query at least two times, so the data is loaded in SAN cache before the measurements are taken.
[0062] Fig 2, 3 and 4 show the actual measurements and extrapolated response time for queries 1, 2 and 3 (as mentioned in Table 1) respectively using the system (100). Let us measure the queries response time on 10 MB database and predict the response time for these queries on higher database varying from size 20 MB. 0.5GB. 1 GB etc. till 128GB. The measurement shows that for query 1,2 and 3 the extrapolated and actual measurements are close to each other with error percentage in the range of 0% to 20%.
[0063] The deviation in response time at larger database size could be due to several other factors such as RAM size, cache size, and DB optimizer parameters which could play its role in indexing and sorting. The extrapolation is performed using ERT on small size database. However, at larger size of database, these parameters may start playing their role so that actual ERT may be higher than the extrapolated ERT.

WE CLAIM:
1. A computer implemented method for predicting an elapsed response time for one
or more database queries with respect to a CBO based relational database in an application
development environment. the method comprising steps of:
determining an estimate amount of cost and the elapsed response time for execution of at least one database query with respect to a first relational database;
identifying one or more parameters from the first relational database affecting the database query cost, such that the parameters are sensitive to size of a second relational database and impact the database query execution cost and the elapsed response time for the database query;
emulating the second relational database by extrapolating the identified size sensitive parameters at an application development stage; and
predicting the elapsed response time for the database query with respect to the second relational database and further predicting the query cost in both the first relational database and the second relational database so emulated in the application development environment.
2. The method of claim 1 further comprises of determining the estimated amount of cost for the emulated second relational database.
3. The method of claim 1, wherein the relational database comprises of a CBO (Cost Based Optimizer) database.
4. The method of claim 1, wherein the first relational database includes a development database and the second relational database includes a projected production database.

5. The method of claim 1, wherein one or more parameters affecting the database query cost and the elapsed response time for database query comprises at least one of database schema, optimizer parameters and database size sensitive schema statistics.
6. The method of claim 5, wherein the one or more parameters affecting the database query cost and the elapsed response time for the database query further comprises of table statistics such as number of rows, number of blocks and average row length, column statistics such as average column length, low value, high value, density values and histograms, and index statistics such as number of levels, distinct values, number of rows, leaf blocks, clustering factor, average number of leaf blocks per key and average number of data blocks per key.
7. The method of claim 1, wherein the second relational database so emulated comprises at least one of imported metadata from the first relational database and schema of the first relational database and the extrapolated schema statistics.
8. The method of claim 1, wherein the elapsed response time of the second relational database is predicted in terms of query execution cost in the first and second relational database.
9. A system for predicting elapsed response time (ERT) for one or more database queries with respect to a relational database in an application development environment, the system comprising:
a first relational database and a database query in the application development
environment;
a cost estimation module configured to determine an estimate amount of cost for
execution of the database query with respect to a first relational database;
an identification module configured to identify one or more parameters from the first
relational database affecting the database query cost, such that the parameters are
sensitive to size of a second relational database and impact the cost of execution of the
database query and the elapsed response time for the database query;

an emulated database configured by extrapolating the identified parameters by means of a calculation module at the application development stage; and
a prediction module configured to predict the elapsed response time for database query with respect to the second relational database and further predicting the database query cost in both the first relational database and the emulated database in the application development environment.
10. The system of claim 9, wherein the cost estimation module further determines the estimated amount of cost for the emulated database.
11. The system of claim 9, wherein the relational database comprises of a CBO (Cost Based Optimizer) database.
12. The system of claim 9, wherein the first relational database comprises a development database and a second relational database comprises a production database.
13. The system of claim 9, wherein one or more parameters affecting the database query cost and its elapsed response time comprises at least one of database schema, optimizer parameters and database size sensitive schema statistics.
14. The system of claim 13, wherein the one or more parameters affecting the database query cost and its elapsed response time further comprises table statistics such as number of rows, number of blocks and average row length, column statistics such as average column length, low value, high value, density values and histograms, and index statistics such as number of levels, distinct values, number of rows, leaf blocks, clustering factor, average number of leaf blocks per key and average number of data blocks per key.
15. The system of claim 9, wherein the emulated database comprises of at least one of imported metadata from the first relational database and schema of the first relational database and the extrapolated schema statistics.

16. The system of claim 9, wherein the elapsed response time of the production database is predicted in terms of query execution cost for the first and second relational database in an application development environment.