
\documentclass[jidm,a4paper]{jidm} % NOTE: JIDM is published on A4 paper
\usepackage{graphicx,url}  % for using figures and url format
\usepackage[T1]{fontenc}   % avoids warnings such as "LaTeX Font Warning: Font shape 'OMS/cmtt/m/n' undefined"

\usepackage{times,amsmath,epsfig}
\usepackage{algo}

% New environment definition
\newenvironment{latexcode}
{\ttfamily\vspace{0.1in}\setlength{\parindent}{18pt}}
{\vspace{0.1in}}

% ALL FIELDS UNTIL BEGIN{document} ARE MANDATORY

% The following data (volume, number and page) are given by the editors prior to publishing your article
\jidmVolume{3}
\jidmNumber{3}
\jidmYear{13}
\jidmMonth{October}
\setcounter{page}{1}


% Includes headers with simplified name of the authors and article title
\markboth{A. Magalhaes, J.M. Monteiro, J. A. Macedo, A. Brayner}
{On Using an Automatic and Non-Intrusive Approach for Rewriting  SQL Queries}



% Title of the article
\title{On Using an Automatic, Autonomous and Non-Intrusive Approach for Rewriting  SQL Queries}


% List of authors
%IF THERE ARE TWO or more institutions, please use:
%\author{Name of Author1\inst{1}, Name of Author2\inst{2}, Name of Author3\inst{2}}
\author{Arlino H. M. de Araujo\inst{1}, Jose Maria Monteiro\inst{1}, Jose Antonio F. de Macedo\inst{1}, Angelo Brayner\inst{2}}


%Affiliation and email
\institute{Federal University of Ceara, Brazil \\ \email{\{arlino,monteiro,jose.macedo\}@lia.ufc.br}
\and University of Fortaleza, Brazil \\ \email{brayner@unifor.br}}
% IF THERE IS ANOTHER INSTITUTION:
%\and Name_of_the_second_institution \\
%\email{address@whatever.com}



\begin{abstract} 
Database applications have become very complex, dealing with a huge volume of data and database objects. Concurrently, low query response time and high transaction throughput have emerged as mandatory requirements to be ensured by database management systems (DBMSs). Among other possible interventions regarding database performance, SQL query rewriting has been shown quite efficient. The idea is to rewrite a new SQL statement semantically equivalent to the statement initially formulated, where the new SQL statement  provides performance gains w.r.t. query response time. In this paper, we propose  an automatic and non-intrusive approach for rewriting SQL queries. The proposed approach has been implemented and its behavior was evaluated in three different DBMSs using TPC-H benchmark. The results show that the proposed approach is quite efficient and can be effectively considered by database professionals.
\end{abstract}

%TODO: Destacar o ganho

% w.r.t. With Regard To"

\category{H.3.0}{Information Storage and Retrieval}{General}
\category{H.3.2}{Information Storage and Retrieval}{Information Storage}[File organization]
\category{H.3.3}{Information Storage and Retrieval}{Information Search and Retrieval}[Retrieval models]

\keywords{Query processing, Database tuning, Query rewriting}
%

\begin{document}

\maketitle

\section{Introduction}
%
Database queries are expressed by means of high-level declarative languages, such as SQL (Structured Query Language), for instance. Such queries are submitted to the query engine, which is responsible for processing queries in database mangement systems (DBMSs). Thus, query engines should implement four main activities: query parsing, logical execution plan (LEP) generation, physical execution plan (PEP) generation and PEP execution. LEP and PEP generation and PEP execution are often called the query optimization. The main functionality of the query optimizer is to find an efficient execution plan for a given  query. For that purpose, cost-based optimizers search, in a large space of alternatives, called search space, the PEP, which is expected to be executed in the less amount of time. 

The cost models implemented by current query optimizers are very complex and rely on factors which may induce the optimizers to produce inaccurate results. Consequently, query optimizers might not be able to yield efficient PEPs. In order to overcome such an issue, there are strategies to help optimizers, such as to provide query hints and index creation recommendations \cite{garcia-molina}. 

Nevertheless, there is another alternative to provide support to optimizers in the task of building efficient execution plans, the query rewriting.  The rewriting technique consists in  rewriting a new SQL statement $Q_{b}$ semantically equivalent to the statement $Q_{a}$ initially formulated. Two queries are semantically equivalent if and only if their execution produces the same result \cite{Ramakrishnan08}. Thus, the execution of $Q_{a}$ and $Q_{b}$ return the same result. However, $Q_{b}$ execution  provides performance gains w.r.t. $Q_{a}$ execution. In order to illustrate performance gains achieved by means of query rewriting, consider the queries $Q_{a}$ and $Q_{b}$ depicted in Figures \ref{fig:S1} and \ref{fig:S2}, respectively. In order to execute those queries, the TPC-H benchmark's database has been created in a PostgreSql server.

\begin{figure}[h]
\begin{minipage}[b]{6cm}
\centering
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{SELECT * }}{}
\algnoline{0}{\scriptsize{FROM orders }}{}
\algnoline{0}{\scriptsize{WHERE o\_totalprice $<$ ALL (SELECT o\_totalprice}}{}			
\algnoline{0}{\scriptsize{\hspace*{2cm} FROM orders}}{}
\algnoline{0}{\scriptsize{\hspace*{2cm} WHERE o\_orderpriority = `2-HIGH')}}{}
\algnoline{0}{\scriptsize{}}{}
\algnoline{0}{\scriptsize{Execution time = 13,685 ms}}{}
\end{algthm}
\caption{SQL expression for $Q_{a}$.}
\label{fig:S1}
\end{minipage}
\hspace*{1.5cm}
%\begin{figure}[h!]
\begin{minipage}[b]{6cm}
\centering
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{SELECT * }}{}
\algnoline{0}{\scriptsize{FROM orders }}{}
\algnoline{0}{\scriptsize{WHERE o\_totalprice $<$ (SELECT MIN(o\_totalprice)}}{}			
\algnoline{0}{\scriptsize{\hspace*{2cm} FROM orders}}{}
\algnoline{0}{\scriptsize{\hspace*{2cm} WHERE o\_orderpriority = `2-HIGH')}}{}
\algnoline{0}{\scriptsize{}}{}
\algnoline{0}{\scriptsize{Execution time = 1,825ms}}{}
\end{algthm}
\caption{SQL expression for $Q_{b}$.}
\label{fig:S2}
\end{minipage}
\end{figure}

\newpage
Looking more closely to Figures \ref{fig:S1} and \ref{fig:S2}, one can observe that $Q_{a}$ and $Q_{b}$ are semantically equivalent, i.e., their execution produces the same result. Nonetheless, $Q_{a}$ execution lasts $13.685 ms$, while $Q_{b}$ is executed in $1.825ms$, one order of magnitude less then the time to execute $Q_{a}$. In fact, $Q_{b}$ was obtained by removing the $ALL$ operator from $Q_{a}$ and including the $MIN$ operator in subquery of $Q_{a}$. 

%TODO: Confirmar com o Ângelo
% one order of magnitude less then the time to execute $Q_{a}$

Therefore, we may formulate the following hypothesis, the way a query Q is formulated in terms of SQL commands induces the query optimizer to produce a given PEP for Q. To empirically show the veracity of our hypothesis, consider the execution plans for queries $Q_{a}$ and $Q_{b}$ depicted in Figures \ref{fig:P1} and \ref{fig:P2}. Those plans have been yielded by PostgreSql's query engine. The PEP showed in Figure \ref{fig:P2} is more efficient (1,825 ms) than PEP depicted in Figure \ref{fig:P1} (13,685 ms). This fact stems from the least amount of data materialized in the ``Materialize'' operation, which is performed after the ``Aggregate'' operation (in the PEP illustrated in Figure \ref{fig:P2}).

\begin{figure}[h]
\begin{minipage}[b]{6.75cm}
\flushleft
\includegraphics[width=6.5cm]{P1.pdf}
\flushleft
\vspace*{-.5cm}
\caption{PEP $P_{Q_{a}}$ yielded by PostgreSQL for processing $Q_{a}$}
\label{fig:P1}
\end{minipage}
\hspace*{.5cm}
\begin{minipage}[b]{8.4cm}
\flushleft
\includegraphics[width=8.3cm]{P2.pdf}
\vspace*{-.5cm}
\caption{PEP $P_{Q_{b}}$ yielded by PostgreSQL for processing $Q_{b}$}
\label{fig:P2}
\end{minipage}
\end{figure}


Database query tuning explore these aspects in order to help query optimizers to produce better PEPs. These tools may be categorized as {\it (i)} online or
offline; {\it (ii)} autonomous or non-autonomous; and {\it (iii)}
intrusive or non-intrusive. Offline approaches rely on human intervention
for specifying the time window for capturing the workload. In
addition, they do not allow the system to react to workload dynamics
\cite{Weikum02,cha06}. On the other hand, an online index tuning tool is able to dynamically capture database workload.
Autonomous query tuning tools have the ability of automatically triggering adjustments to improve query performance. Conversely, non-autonomous tools  transfer to the DBA  the responsibility for making such adjustments. This include the definition of the most appropriate moment to apply  the recommended  query changes and to choose, among the suggested actions, those that in fact should be executed and in which order.
Intrusive solutions are those that require changes in the DBMS code and, therefore, are
tightly coupled to a particular DBMS. Non-intrusive solutions are those that are disconnected from %the DBMS code
a particular DBMS implementation
and that are usually not affected by any new DBMS release.
%implementation changes.

In fact, there are already tools which aim at tuning database query performance by providing rewriting recommendations. However, they adopt an offline approach, since they provide recommendations only when an human (e.g., DBA) require such recommendations. Most of them are intrusive, which means that they are DBMS-specific. Additionally, they present a strong issue, for a given query they may provide several rewriting recommendations. In this case, the DBA is in charge to choose one of them  without any indication (from the tool) that the choose recommendation will provide the best performance gains regarding response time. 

In this paper, we propose  an automatic, autonomous and non-intrusive approach for rewriting SQL queries, denoted ARe-SQL. The proposed approach provides the necessary support to implement two different strategies for SQL-query rewriting.  In the first strategy,  ARe-SQL autonomously captures SQL queries submitted by users or applications and identify which queries should be rewritten. Thereafter, queries are sent to the database query engine. The second strategy  works as an autonomous advisor, which analyze previously executed SQL statements in order to recommend (through alerts, reports and wizards) SQL tuning opportunities. In both strategies, the rewritten queries profit from performance gains as we show in Section  \ref{results}. 

%TODO: Confirmar com o Angelo
%TODO: In both strategies, the rewritten queries profit from performance gains as we show in Section

The key goal of ARe-SQL is to assist optimizers in build efficient query physical execution plan. In a proactive manner, ARe-SQL rewrites SQL statements which will induce query engine to produce better plans than those that would be built by executing the original SQL statements.  We advocate that the main features presented by ARe-SQL are:
\vspace*{-.35cm}
\begin{itemize}
\item {\sf Implementation of a non-intrusive strategy.} Due to this feature ARe-SQL may be applied to different database systems. In other words, it is not DBMS-specific.
\item {\sf Autonomy.} ARe-SQL has the ability of automatically triggering query rewritings or recommendations. This include the definition of the most appropriate moment to apply  the recommended  rewritings and to choose, among the suggested actions, those that in fact should be executed and in which order.
\item {\sf Low-overhead tuning activity.}  By using our approach, the database system keeps running while our automatic tool runs continuously capturing the
workload, in a lightweight manner.
\end{itemize}

We have implemented the proposed approach and evaluated its behavior in three different DBMSs considering the TPC-H benchmark. The results show that our approach can be effectively considered by database professionals.

The rest of the paper is structured as follows. Section \ref{secRelWork} discuss most relevant related work. The proposed approach is presented and analyzed in Section \ref{proposta}.  In turn, Section \ref{results} brings and analyzes experimental results. Finally, Section \ref{concl} concludes this paper.


%Such  (a) cardinality estimates, that are inferred based on correlation and uniformity; (b) calibration constants used for estimate costs, that might not be fully accurate and depends on underlying hardware (e.g., the cost of a hard disk I$/$O); (c) cost formulas cannot capture every details on the algorithms used in execution plans; (d) parameter settings database affect execution costs of queries (e.g., the amount of buffer pool memory); e (e) even if we could determine the precise cost of a single query in isolation, in pratice, queries perform concurrent and a query executing can influence the runtime of others, due to factors like contention of indexes, excessive locking \cite{Bruno09}.



\section{Related Work}
\label{secRelWork}

It is well-known that index structures considerably speed up data access. Nevertheless, even using efficient access methods, query optimizers may not produce optimal plans. As already mentioned, an efficient alternative to induce optimizers to build optimal physical execution plans is to tune the SQL statements. For that, two strategies are often used: {\it (i)} SQL statement rewriting, and;  {\it (ii)} query hinting use \cite{Shasha02,Bruno09,garcia-molina}.

The idea behind the use of query hints is to instruct the query optimizer to reduce its search space to a subset of execution plans. This can be done, for instance, by imposing  the use a certain kind of index, the join order or the physical join operator (e.g., merge join or hash join).  The hints should be introduced into  SLQ statement by the means of human intervention (the DBA, for example). However, there is no guarantee that efficient plans will be build. In fact, one should first observe if the plan built after inserting query hints provides in fact better performance regarding query response time \cite{Bruno09}. Most commercial database systems provide the query hint approach.

The SQL statement rewriting relies on the premisse that the execution of two semantically equivalent SQL queries may present different response time. Thus, the key goal is to rewrite a new SQL statement from the statement initially formulated, assuring that the two statements are semantically equivalent (i.e., they produce the same result). 

Bruno {\it et al} propose in \cite{Bruno09} a framework, called Power Hints, which enables the creation and use of hints. In the proposed framework, hints are created by means of regular expressions, making it easy and flexible to create restrictions for query execution plans, allowing more precise tuning.

%The work proposed in \cite{Herodotou09} presents a tool called zTuned whose purpose is to facilitate experiments related to tune SQL queries. The tool produces sets of plans with operators that have the same cardinality (called neighborhood plans) and chooses the optimal plan among the best plans for each neighborhood, using the mechanism of cost estimative of the DBMS. The tool works decoupled from the query optimizer and can potentially be used with any DBMS that has a cost-based optimizer.

In \cite{Krishnaprasad04}, the author describes a technique to transform an XML query in an equivalent query in the relational model or object-relational through rewritten at compile time.

\newpage
In Oracle 10g is introduced a component called Automatic SQL Tuning Advisor that provides recommendations to creating indexes based on predicates present in SQL statements and recommendations of opportunities to rewrite queries using semantic equivalences \cite{Dagevil06}.

The tool IBM Optim Development Studio \cite{Studio10} collects query performance metrics in DB2. The metrics are query execution frequency, cost and time. Thus, with such metrics, it is possible to identify queries, for which query rewriting recommendation are worthwhile.  It is important to mention that the should triggered for given period of time whenever the DBA consider is necessary. 

Embarcadero DB Optimizer XE \cite{Optimizer10} has the functionality of identifying hints which should be encoded in a given SQL statement, i.e., it does not propose query rewritings. Its goal is mainly to eliminate unnecessary outer joins and cartesian products. Additionally, Embarcadero may provide recommendation for improving index configuration. Quest SQL Optimizer for Oracle \cite{Quest10} provides semantically equivalent SQL statements for a given query. In this case, the DBA should pass to the tool which query should be analyzed. Moreover, it is up to the DBA to choose one of the several recommended SQL statements. 

Schnaitter {\it et al} present in \cite{Sch06,Sch07} a prototype of a self-tuning framework called COLT (Continuous On-Line Tuning). This tool continuously monitors queries submitted to the DBMS and autonomously adjusts  the index configuration in order to tune database query performance. COLT is implemented in an intrusive manner into PostgreSQL, since it replaces the PostgreSQL's query optimizer by a module, denoted {\it Extended Query Optimizer} (EQO), and adds a Self-Tuning Module (STM) to PostgreSQL's query engine. COLT implements the classic self-tuning steps composed by Observation, Prediction and Reaction phases.
The main drawback in this COLT approach stem from the notion of {\it epoch}. By %fixing
assigning to an {\it epoch} a fixed number of 10 queries, COLT may take too much time to react. Actually, any fixed number may not be consistent with the database system needs.

In \cite{Maier2010,Alagiannis2010} an intrusive solution, called %the authors present
PARINDA (PARtition and INDex Advisor), is presented. It is an interactive physical designer for PostgreSQL that works as follows: given a workload containing a set of queries, PARINDA allows the DBA to manually suggest a set of candidate indexes and the tool shows the benefits of the suggested index set and index interactions visually. Besides, the tool can find the optimal index partition for a given query workload. It also suggests a schedule to implement the suggested indexes.  Finally, the tool can continuously monitors the performance of the DBMS under incoming queries, and  it suggests  new  indexes  when  they  offer  sufficient workload speedup. Bruno et al propose in \cite{Bruno2010} an intrusive and interactive tool for Microsoft's SQL Server, which is similar to PARINDA since it makes tuning sessions interactive, allowing DBAs to try different tuning options and interactively obtain a feedback.


Therefore, all the investigated SQL tuning tools (Automatic SQL Tuning Advisor \cite{Dagevil06}, IBM Optim Development Studio \cite{Studio10}, Embarcadero DB Optimizer XE \cite{Optimizer10} and Quest SQL Optimizer for Oracle \cite{Quest10}) adopt an offline approach. In this sense, they  transfer to the DBA  the responsibility for defining the set of queries to evaluated and for choose one of several alternatives provided by them. Observe that DBAs work in a reactive way, i.e., they only triggers a tool or an advisor when the problem already exist. Furthermore, after identifying the problem (a time consuming query) and a possible solution, a DBA should rewrite the SQL statement, test and send it to a programmer to change the application code which is using the SQL statement. This whole process is rather time consuming.


%We have not found any work related SQL tuning which holds the following characteristics: a) assisted, non-intrusive and independent of location or b) automatic, on-the-fly, non-intrusive and independent of location.

%The Database Administrator (DBA) uses the SQL rewrite and the inclusion of hints to adjust (tune) SQL statements. However, this process requires a high level of expertise in areas like (i) query optimization, execution of query plan operators, configuration parameter settings; (ii) identification of missing indexes and other access structures; (iii) statistics maintained about the data; and
%(iv) characteristics of the underlying storage system \cite{Herodotou09}.

%Moreover, in general, the DBA works in a reactive way, i.e., he only fires when it is perceived that a particular SQL statement is slow (in general, this is detected by a user). After monitoring and identifing the problem, he adjusts the SQL statement, tests and sends it to the programmer to change the application code that is using the SQL statement. This whole process is rather time consuming, so the DBA as the programmer.


\section{ARe-SQL: An Automatic, Autonomous and Non-Intrusive Approach for Rewriting  SQL Queries}
\label{proposta}

ARe-SQL's main functionality is to influence query optimizer to choose an effectual query execution plan. ARe-SQL proactively rewrites SQL statements which will induce query engine to produce better plans In order to achieve its goal, ARe-SQL works directed by a set of heuristics. The heuristics consist of rules to identify potential opportunities for tuning SQL statements and the ways to rewrite the statements.

Table \ref{tab:heuristics} brings the eleven heuristics applied by ARe-SQL for rewriting SQL statements. Furthermore, it indicates whether  or not each heuristic is currently implemented by the three major DBMSs: PostgreSQL 8.1, Oracle 11g and SQL Server 2008.

\begin{table}[h]
	\caption{Heuristics for SQL Tuning.}
	\label{tab:heuristics}
	\centering
	\begin{tabular}{|p{.5cm}| p{8.5cm}|p{1.2cm}|p{.7cm}|p{1.4cm}|}
		\hline
		 	&	Heuristcs for SQL Tuning & PostgreSQL & Oracle & SQL Server	\\
		\hline
		H1	&	Transform queries which create and use temporary table into an equivalent sub-query. & No & No & No	\\
		\hline
		H2	&	Eliminate unnecessary GROUP BY. & No & No & No\\
		\hline 
		H3	&	Remove having clause whose predicates do not have any aggregate function. The predicates should be moved to a WHERE clause. & No & No & No\\
		\hline
		H4	&	Change query with disjunction in the WHERE to a union of query results. & No & Yes & No\\
		\hline
		H5	&	Remove ALL operation with greater/less-than comparison operators by including a MAX or MIN aggregate function in the subquery. & No & Yes & No\\
		\hline
		H6	&	Remove SOME operation with greater/less-than comparison operators by including a MAX or MIN aggregate function in the subquery. & No & Yes & No\\
		\hline
		H7	&	Remove ANY operation with greater/less-than comparison operators by including a MAX or MIN aggregate function in the subquery. & No & Yes & No\\
		\hline 
		H8	&	Replace IN set operation by a join operation. & No & Yes & No\\
		\hline
		H9	&	Eliminate unnecessary DISTINCT. & No & No & No\\
		\hline
		H10	&	Move function applied to a column index to another position in the expression. & No & No & No\\
		\hline
		H11	&	Move arithmetic expression applied to a column index to another position in the expression. & No & No & No\\
		\hline
	\end{tabular}
\end{table}

Next, we discuss the heuristics depicted in Table \ref{tab:heuristics}. Examples which illustrate the use of the heuristics are presented. It is important to make clear that the queries depicted on the following were submitted to PostgreSql and the used database has been the one of the TPC-H benchmark \cite{tpch}.

The main goal of applying heuristic H1 is to make possible to  rewrite two queries $Q_{1}$ and $Q_{2}$, where $Q_{1}$ defines a temporary table and $Q_{2}$ refers to it, in order to produce a single query $Q_{3}$. The idea is to replace the reference to the temporary table in $Q_{2}$ by a subquery. The performance gain in Q3 due to the fact that it is no longer necessary the physical creation of a temporary table. Figures \ref{fig:Q1}, \ref{fig:Q2} and \ref{fig:Q3} illustrates the use of H1. Observe that the execution time for Q3 is about $\frac{1} {4}$ of the time to execute $Q_{1}$ and $Q_{2}$. 

\begin{figure}[h]
\begin{minipage}[b]{4.5cm}
\flushleft
\begin{algthm}{aa}
\algnoline{-2}{\scriptsize{\bf SELECT * INTO temp  }}{}
\algnoline{-2}{\scriptsize{\bf FROM customer c,orders o }}{}
\algnoline{-2}{\scriptsize{\bf WHERE c.c\_custkey = o.o\_custkey }}{}			
\algnoline{-2}{\scriptsize{\bf }}{}
\algnoline{-2}{\scriptsize{\bf Execution time = 88,222ms}}{}
\end{algthm}
\flushleft
\caption{Query $Q_{1}$ (creates a temporary table called temp).}
\label{fig:Q1}
\end{minipage}
\hspace*{0.3cm}
\begin{minipage}[b]{4.5cm}
\flushleft
\begin{algthm}{aa}
\algnoline{-2}{\scriptsize{\bf SELECT c\_name, AVG(o\_totalprice)}}{}
\algnoline{-2}{\scriptsize{\bf FROM temp}}{}
\algnoline{-2}{\scriptsize{\bf GROUP BY c\_name}}{}			
\algnoline{-2}{\scriptsize{\bf }}{}
\algnoline{-2}{\scriptsize{\bf Execution time = 31,140ms}}{}
\end{algthm}
\flushleft
\caption{Query $Q_{2}$ (uses the temporary table temp created by $Q_{1}$).}
\label{fig:Q2}
\end{minipage}
%\end{figure}
\hspace*{.3cm}
%\begin{figure}[h]
\begin{minipage}[b]{4.5cm}
\flushleft
\begin{algthm}{aa}
\algnoline{-2}{\scriptsize{\bf SELECT c\_name, AVG(o\_totalprice) }}{}
\algnoline{-2}{\scriptsize{\bf FROM (SELECT * }}{}
\algnoline{-2}{\scriptsize{\bf \hspace*{0.1cm} FROM customer AS c, orders AS o }}{}	
\algnoline{-2}{\scriptsize{\bf \hspace*{0.1cm} WHERE c.c\_custkey = o.o\_custkey) AS temp }}{}	
\algnoline{-2}{\scriptsize{\bf GROUP BY c\_name }}{}	
\algnoline{-2}{\scriptsize{\bf }}{}
\algnoline{-2}{\scriptsize{\bf Execution time = 33,384ms}}{}
\end{algthm}
\caption{Query $Q_{3}$ (rewritten from $Q_{1}$ and $Q_{2}$ by applying heuristic H1).}
\label{fig:Q3}
\end{minipage}
\end{figure}

There are two strategies to implement the {\it Group by} operator. The first strategy is to cluster tuples by applying a sort operation where the operands are the attributes which appear in the {\it Group by} clause. PostgreSql uses that strategy. The second strategy is to use a hash function in order to cluster tuples in buckets. Of course, in this case that hash function is applied on the attributes which are the operands of the {\it Group by} clause. The query engines of Oracle and SQL Server implement the second strategy. In either cases, the cost to execute a group by operation is too high. Thus, heuristic H2 has the functionality of removing unnecessary of group by operations. A {\it Group by} operation can be removed case it does not present a {\it Having} clause and at least one of the following conditions is satisfied:
	\begin{enumerate}
		\item	The SELECT clause of a query Q contains only one column, which has an aggregate function.
		\item	The SELECT of a query Q does not contain any aggregate  function (e.g., {\it SUM, AVG}) and one of the attributes in the {\it Group by} is a primary key PK, where one of the following restrictions is valid:
		\begin{enumerate}
			\item	The query Q refers only one table.
			\item	 The query Q referes more than one table and the primary key PK is not foreign key in
any other table referred by Q.
		\end{enumerate}
	\end{enumerate}

To illustrate the use of H2, consider the  Figures \ref{fig:Q4} and \ref{fig:Q5}. Observe in Figure in \ref{fig:Q4} that for query $Q_{4}$ there is no aggregation function in the {\it Select} clause and one of the attributes in the {\it Group by} clause is a primary key, namely the attribute {\it c\_custkey}, which it is not a foreign key in any other table referenced in $Q_{4}$. For that reason, H2 can be applied to rewrite $Q_{4}$ to remove the {\it Group by operation}. Query $Q_{5}$ depicted in Figure \ref{fig:Q5} is yielded after applying H2 to $Q_{4}$. It is worthwhile to mention that $Q_{4}$ and $Q_{5}$ semantically equivalent, i.e. both queries deliver the same result. Nevertheless, the execution time od $Q_{5}$ is approximately 16\% less than the time to execute $Q_{4}$.

\begin{figure}[h]
\centering
\begin{minipage}[b]{6cm}
%\centering
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT c\_custkey, c\_name, c\_address, c\_phone }}{}
\algnoline{0}{\scriptsize{\bf FROM customer, nation, region }}{}
\algnoline{0}{\scriptsize{\bf WHERE c\_nationkey = n\_nationkey AND }}{}
\algnoline{0}{\scriptsize{\bf n\_regionkey = r\_regionkey }}{}
\algnoline{0}{\scriptsize{\bf GROUP BY  c\_custkey, c\_name, c\_address, c\_phone }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 8,397ms}}{}
\end{algthm}
\caption{Query $Q_{4}$ with an unnecessary GROUP BY.}
\label{fig:Q4}
\end{minipage}
%\end{figure}
\hspace*{1.5cm}
%\begin{figure}[h]
\begin{minipage}[b]{6cm}
\centering
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT c\_custkey, c\_name, c\_address, c\_phone }}{}
\algnoline{0}{\scriptsize{\bf FROM customer, nation, region }}{}
\algnoline{0}{\scriptsize{\bf WHERE c\_nationkey = n\_nationkey AND }}{}
\algnoline{0}{\scriptsize{\bf n\_regionkey = r\_regionkey }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 7,040ms}}{}
\end{algthm}
\caption{Query $Q_{5}$ (rewritten from $Q_{4}$ by applying H2).}
\label{fig:Q5}
\end{minipage}
\end{figure}


The goal of applying heuristic H3 is to remove an unnecessary {\it Having} clause. This is possible whenever there is no aggregation function in the {\it Having} clause. In fact,  for removing the {\it Having} clause, it is necessary to move its predicate  to the {\it Where} clause. By doing this, it is possible to apply heuristic H2, since the {\it Having} clause had been removed. Figures \ref{fig:Q6} and \ref{fig:Q7} show how H3 may be applied. In query $Q_{6}$ (Figure \ref{fig:Q6}), there is no aggregation function in the  {\it Having} clause. Thus, by H3, that clause can be removed and its predicate, namely  {\it o\_orderpriority = `5-LOW'}, moved to the {\it Where} clause. Thereafter, H2 may be applied and the {\it Group by} operation may removed. Query  $Q_{7}$ represents the rewritten form of  $Q_{6}$. Looking more closely to  Figures \ref{fig:Q6} and \ref{fig:Q7}, one can see that to execute $Q_{7}$ the query engine of PostgreSql consumes 20\% less time then to execute $Q_{6}$.

\begin{figure}[h]
\flushleft
\begin{minipage}[b]{7cm}
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT o\_orderkey, o\_custkey, o\_orderpriority, o\_clerk }}{}
\algnoline{0}{\scriptsize{\bf FROM orders }}{}
\algnoline{0}{\scriptsize{\bf GROUP BY o\_orderkey, o\_custkey, o\_orderpriority, o\_clerk }}{}
\algnoline{0}{\scriptsize{\bf HAVING o\_orderpriority = `5-LOW'  }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 11,430ms}}{}
\end{algthm}
\caption{Query $Q_{6}$ with unnecessary HAVING.}
\label{fig:Q6}
\end{minipage}
%\end{figure}
\hspace*{1cm}
%\begin{figure}[h]
\begin{minipage}[b]{7cm}
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT o\_orderkey, o\_custkey, o\_orderpriority, o\_clerk }}{}
\algnoline{0}{\scriptsize{\bf FROM orders }}{}
\algnoline{0}{\scriptsize{\bf WHERE o\_orderpriority = `5-LOW'  }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 9,072ms}}{}
\end{algthm}
\caption{Query $Q_{7}$ (rewritten from $Q_{6}$ by applying H3 and H2).}
\label{fig:Q7}
\end{minipage}
\end{figure}

It is well known that the presence of logical disjunctions (connector {\it or}) in {\it Where} clause of a query Q may induce query optimizer database to choose an execution plan for Q which does not use available indexes. To solve this problem the heuristic H4 rewrites Q into a union of queries $Q_{i}, i>1$. Each query $Q_{i}$ is constructed as follows: {\it (i)} the attributes in the {\it Select} clause of the original query Q should appear in the {\it Select} clause of $Q_{i}$, {\it (ii)} the tables referenced in the {\it From} clause of Q should appear in $Q_{i}$, and; {\it (iii)} only one of the predicates connected by {\it or} in Q should appear in {\it Where} clause of $Q_{i}$. In order to illustrate how H4 may be applied, consider Figures \ref{fig:Q8} and \ref{fig:Q9}. Figure  \ref{fig:Q8} presents query $Q_{8}$, which has two predicates ($l\_quantity<20$, $l\_linenumber>5$) connect by {\it or} (a disjunction of predicates). Although there are indexes for the attributes l\_quantity and l\_linenumber, the plan used by PostgreSql to execute $Q_{8}$ do not use them due the disjunction in {\it Where} clause of $Q_{8}$. By applying H4, query $Q_{8}$ is rewritten into an union of two queries (see Figure \ref{fig:Q9}). Observe that both queries in Figure \ref{fig:Q9} have the same operands for  {\it Select}  and {\it From} clauses as query $Q_{8}$ and each query presents one predicate of the original query $Q_{8}$. 

\begin{figure}[h]
\centering
\begin{minipage}[b]{7cm}
\centering
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT l\_orderkey }}{}
\algnoline{0}{\scriptsize{\bf FROM lineitem }}{}
\algnoline{0}{\scriptsize{\bf WHERE l\_quantity $<$ 20 or l\_linenumber $>$ 5 }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 10,729ms}}{}
\end{algthm}
\caption{Query $Q_{8}$ with disjunction in {\it WHERE} clause.}
\label{fig:Q8}
\end{minipage}
%\end{figure}
\hspace*{1cm}
%\begin{figure}[h]
\begin{minipage}[b]{7cm}
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT l\_orderkey }}{}
\algnoline{0}{\scriptsize{\bf FROM lineitem  WHERE l\_quantity $<$ 20}}{}
%\algnoline{0}{\scriptsize{\bf WHERE l\_quantity $<$ 20}}{}
\algnoline{0}{\scriptsize{\bf UNION }}{}
\algnoline{0}{\scriptsize{\bf SELECT l\_orderkey }}{}
\algnoline{0}{\scriptsize{\bf FROM lineitem WHERE l\_linenumber $>$ 5}}{}
%\algnoline{0}{\scriptsize{\bf WHERE l\_linenumber $>$ 5}}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 9,671ms}}{}
\end{algthm}
\caption{Query $Q_{9}$ (Union of queries from $Q_{8}$ after applying H4).}
\label{fig:Q9}
\end{minipage}
\end{figure}

In SQL, the operator {\it All} compares a scalar values with a set of values. In query $Q_{a}$ depicted in Figure \ref{fig:S1}, the predicated returns true if and only if all values of the subquery are greater than o\_totalprice. In order to avoid to compare the attribute {\it o\_totalprice} with all values returned by the subquery, heuristic H5 make possible to remove the {\it All} operator by including {\it Max} or {\it Min} aggregate functions in the subquery, depending on the comparison operator: {\it (i)} for greater-than operator ($>$), a  {\it Max} function should be included in the subquery; {\it (i)} for less-than operator ($<$), a  {\it Min} function should be included. Figures \ref{fig:S1} and \ref{fig:S2} brings an example of removing an {\it All} operator. Since the comparison operator in query $Q_{a}$ is less-than ($<$), the aggregate function to be included in the rewritten query should be {\it Min} (query $Q_{b}$ depicted in Figure \ref{fig:S2}). Observe that the time to execute $Q_{b}$ is 7.4 times less than the time to execute $Q_{a}$.

The heuristics H6 and H7 work similarly to H5. H6 is applied to remove the operator {\it Some} (Figures \ref{fig:10} and \ref{fig:Q11}), H7 is used to remove the operator {\it Any} (Figures \ref{fig:Q12} and \ref{fig:Q13}).

\begin{figure}[h]
\begin{minipage}[b]{7cm}
\centering
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT o\_orderkey, o\_custkey, o\_orderstatus, o\_totalprice  }}{}
\algnoline{0}{\scriptsize{\bf FROM orders }}{}
\algnoline{0}{\scriptsize{\bf WHERE o\_totalprice $>$ SOME (SELECT o\_totalprice }}{}
\algnoline{1}{\scriptsize{\bf FROM orders  }}{}
\algnoline{1}{\scriptsize{\bf WHERE o\_orderpriority = `2-HIGH') }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 49,880ms}}{}
\end{algthm}
\caption{SQL expression for query $Q_{10}$ with the operator {\it SOME}.}
\label{fig:Q10}
\end{minipage}
%\end{figure}
\hspace*{1cm}
%\begin{figure}[h]
\begin{minipage}[b]{7cm}
\centering
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT o\_orderkey, o\_custkey, o\_orderstatus, o\_totalprice  }}{}
\algnoline{0}{\scriptsize{\bf FROM orders }}{}
\algnoline{0}{\scriptsize{\bf WHERE o\_totalprice $>$ (SELECT MIN(o\_totalprice) }}{}
\algnoline{1}{\scriptsize{\bf        FROM orders  }}{}
\algnoline{1}{\scriptsize{\bf        WHERE o\_orderpriority = `2-HIGH') }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 34,640ms}}{}
\end{algthm}
\caption{Query $Q_{11}$ obtained by applying  H6 on $Q_{10}$).}
\label{fig:Q11}
\end{minipage}
\end{figure}


The heuristic H7 uses operator ANY  that is synonymous with SOME, as a consequence, H7 works similarly to H6. Therefore, we will not discuss H7 \cite{Elmasri05}.

\begin{figure}
\begin{minipage}[b]{7cm}
\centering
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT o\_orderkey, o\_custkey, o\_orderstatus, o\_totalprice  }}{}
\algnoline{0}{\scriptsize{\bf FROM orders }}{}
\algnoline{0}{\scriptsize{\bf WHERE o\_totalprice $>$ ANY (SELECT o\_totalprice }}{}
\algnoline{1}{\scriptsize{\bf            FROM orders  }}{}
\algnoline{1}{\scriptsize{\bf            WHERE o\_orderpriority = `2-HIGH') }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 50,341ms}}{}
\end{algthm}
\caption{SQL expression for query$Q_{12}$ with the operator {\it ANY}.}
\label{fig:Q12}
\end{minipage}
%\end{figure}
\hspace*{1cm}
%\begin{figure}[h]
\begin{minipage}[b]{7cm}
\centering
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT o\_orderkey, o\_custkey, o\_orderstatus, o\_totalprice  }}{}
\algnoline{0}{\scriptsize{\bf FROM orders }}{}
\algnoline{0}{\scriptsize{\bf WHERE o\_totalprice $>$ (SELECT MIN(o\_totalprice) }}{}
\algnoline{1}{\scriptsize{\bf          FROM orders  }}{}
\algnoline{1}{\scriptsize{\bf          WHERE o\_orderpriority = '2-HIGH') }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 31,382ms}}{}
\end{algthm}
\caption{Query $Q_{13}$ obtained by rewriting $Q_{12}$ based on H7.}
\label{fig:Q13}
\end{minipage}
\end{figure}

Figure \ref{fig:Q14} shows a query ($Q_{14}$) which use the set operator {\it In}. To process $Q_{14}$, a table scan on the table {\it lineitem} is executed. In order to avoid that operation, an efficient strategy is to rewrite $Q_{14}$ by removing the {\it In} operator and including a join operation. This is the functionality of heuristic H8. Figure \ref{fig:Q15} depicts $Q_{15}$, which is the query resulting from applying H8 to  $Q_{14}$. The response time for $Q_{15}$ is 52\% less that $Q_{14}$'s response time.

\begin{figure}[h]
\centering
\begin{minipage}[b]{7cm}
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT o\_orderkey,o\_custkey  }}{}
\algnoline{0}{\scriptsize{\bf FROM orders }}{}
\algnoline{0}{\scriptsize{\bf WHERE o\_orderkey IN (SELECT l\_orderkey }}{}
\algnoline{11}{\scriptsize{\bf                       FROM lineitem }}{}
\algnoline{11}{\scriptsize{\bf                       GROUP BY l\_orderkey }}{}
\algnoline{11}{\scriptsize{\bf                       HAVING SUM(l\_quantity) $>$ 3 ) }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 62,354ms}}{}
\end{algthm}
\caption{Query $Q_{14}$ with IN set operation.}
\label{fig:Q14}
\end{minipage}
%\end{figure}
\hspace*{1cm}
%\begin{figure}[h]
\begin{minipage}[b]{7cm}
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT o\_orderkey,o\_custkey  }}{}
\algnoline{0}{\scriptsize{\bf FROM orders, lineitem }}{}
\algnoline{0}{\scriptsize{\bf WHERE (o\_orderkey = l\_orderkey)  }}{}
\algnoline{0}{\scriptsize{\bf GROUP BY o\_orderkey, o\_custkey  }}{}
\algnoline{0}{\scriptsize{\bf HAVING  SUM(l\_quantity) $>$ 3 }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 35,097ms}}{}
\end{algthm}
\caption{Query $Q_{15}$ obtained by rewriting $Q_{14}$ based on H8.}
\label{fig:Q15}
\end{minipage}
\end{figure}

\newpage
The use of the DISTINCT command may increase query response time, because this command requires sorting operation, which involves high computational cost of I/O \cite{Shasha02,Ramakrishnan08}. The heuristic H9 removes unnecessary DISTINCT in an SQL query. This is possible whenever DISTINCT is applied to a primary key PK in a query Q and one of the following conditions holds:
	\begin{itemize}
		\item	Q references only one table.
		\item	Q references more than one table and PK is not foreign key any table in Q.
	\end{itemize}

Figures \ref{fig:Q16} and \ref{fig:Q17} illustrates the use of H9.

\begin{figure}[h]
\centering
\begin{minipage}[b]{7cm}
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT DISTINCT (o\_orderkey), o\_totalprice, c\_name }}{}
\algnoline{0}{\scriptsize{\bf FROM customer, orders }}{}
\algnoline{0}{\scriptsize{\bf WHERE c\_custkey = o\_custkey  }}{}
\algnoline{0}{\scriptsize{\bf ORDER BY o\_orderkey}}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 52,634ms}}{}
\end{algthm}
\caption{SQL statement for query $Q_{16}$ with an unnecessary DISTINCT.}
\label{fig:Q16}
\end{minipage}
%\end{figure}
\hspace*{1cm}
%\begin{figure}[h]
\begin{minipage}[b]{7cm}
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT o\_orderkey, o\_totalprice, c\_name }}{}
\algnoline{0}{\scriptsize{\bf FROM customer, orders }}{}
\algnoline{0}{\scriptsize{\bf WHERE c\_custkey = o\_custkey  }}{}
\algnoline{0}{\scriptsize{\bf ORDER BY o\_orderkey}}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 46,224ms}}{}
\end{algthm}
\caption{Query $Q_{17}$ created by rewriting $Q_{16}$ based on H9.}
\label{fig:Q17}
\end{minipage}
\end{figure}

Heuristic 10 checks for the presence of an index column in a function. The query optimizer of DBMS can not use the available index because the function avoids it. To solve this problem, the column with index may be removed from the function, without losing the semantics of expression where the function is contained. Figures \ref{fig:Q18} and \ref{fig:Q19} illustrates the use of H10.

\begin{figure}[h]
\centering
\begin{minipage}[b]{7cm}
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT * }}{}
\algnoline{0}{\scriptsize{\bf FROM lineitem }}{}
\algnoline{0}{\scriptsize{\bf WHERE CAST(l\_quantity AS VARCHAR) = `28' }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 15,913ms}}{}
\end{algthm}
\caption{Query $Q_{18}$ with an index column (l\_quantity) used in a function (CAST).}
\label{fig:Q18}
\end{minipage}
%\end{figure}
\hspace*{1cm}
%\begin{figure}[h]
\begin{minipage}[b]{7cm}
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT * }}{}
\algnoline{0}{\scriptsize{\bf FROM lineitem }}{}
\algnoline{0}{\scriptsize{\bf WHERE l\_quantity = CAST(`28' AS INT) }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 11,580ms}}{}
\end{algthm}
\caption{Query $Q_{19}$ rewritten by applying  H10 on $Q_{18}$.}
\label{fig:Q19}
\end{minipage}
\end{figure}

Heuristics 11 checks for the presence of a column with index in an arithmetic expression. If a column with index is involved in operations in an arithmetic expression, the query optimizer can not choose an execution plan that uses the index available. To solve this problem, the column index should be isolated in arithmetic expression, i.e., it should not be operating of the any operators in the expression. Thus, the optimizer can use the available index for the column. The query $Q_{20}$ (Figure \ref{fig:Q20}) illustrates a SQL query which presents an index column evolved in an arithmetic expression. The query $Q_{21}$ (Figure \ref{fig:Q21}) is obtained by rewritten from $Q_{20}$ by applying H11.


\begin{figure}[h]
\centering
\begin{minipage}[b]{6cm}
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT * }}{}
\algnoline{0}{\scriptsize{\bf FROM lineitem }}{}
\algnoline{0}{\scriptsize{\bf WHERE l\_quantity/2 = 40 }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 3,638ms}}{}
\end{algthm}
\caption{Query $Q_{20}$, which presents an index column in an arithmetic expression.}
\label{fig:Q20}
\end{minipage}
\hspace*{1.cm}
\begin{minipage}[b]{6cm}
\begin{algthm}{aa}
\algnoline{0}{\scriptsize{\bf SELECT * }}{}
\algnoline{0}{\scriptsize{\bf FROM lineitem }}{}
\algnoline{0}{\scriptsize{\bf WHERE l\_quantity = 40*2 }}{}
\algnoline{0}{\scriptsize{\bf }}{}
\algnoline{0}{\scriptsize{\bf Execution time = 1,4ms}}{}
\end{algthm}
\caption{Query $Q_{21}$ (rewritten from $Q_{20}$ by applying H11.}
\label{fig:Q21}
\end{minipage}
\end{figure}

As already mentioned, the set of heuristics used by ARe-SQL makes possible the implementation of two different types of tools for SQL-query rewriting. One type of tool  works as an autonomous advisor, which analyze previously executed SQL statements. The other type autonomously captures SQL queries submitted by users or applications and identify which queries should be rewritten. Thereafter, queries are sent to the database query engine. In both strategies, the rewritten queries profit from performance gains. Next, both types of tools for SQL-query rewriting are described.


%The proposed approaches also have the following characteristics:
%\begin{itemize}
%\item	Non-intrusive: completely decoupled from the source code of the DBMS. This allows the conceived solution can be used with any DBMS.
%\item	Independent of location: it can run on a machine different than that used to host the DBMS, not consuming server resources where the DBMS is hosted.
%\end{itemize}


\section{Implementing ARe-SQL}

In order to implement ARe-SQL, two different approaches had been employed: assisted and automatic. For each approach, a different tool had been implemented. However, both approaches present the following features:
\begin{itemize}
\item	Non-intrusive: completely decoupled from the source code of the DBMS. This allows the conceived solution can be used with any DBMS.
\item	Independent of location: it can run on a machine different than that used to host the DBMS, not consuming server resources where the DBMS is hosted.
\end{itemize}

\subsection{Assisted Approach}

A query-rewriting tool based on assisted approach consists of an advisor which has the ability: {\it (i)} to capture the previously SQL statements executed by DBMS; {\it (ii)} to analyze these statements, and; {\it (iii)} to recommend (through alerts, reports or wizards) SQL tuning opportunities. Thus, the advisor can identify SQL statements that could be rewritten. Additionally, such a type of tool allow the DBA to interact with the tuning process. For instance, a DBA may select a subset of available heuristics to be applied for the  SQL-query tuning process. In other words, the DBA can specify that some heuristics are unnecessary or inappropriate for a given database sustem or a given statement.

We have implemented a tool, called ARe-SQL Advisor, which implements an assisted approach for ARe-SQL. Figure \ref{fig:arqAsistida} depicts an abstract model of ARe-SQL Advisor architecture. To utilize ARe-SQL Advisor in a given DBMS, it is necessary to instantiate two specific drivers: a driver for workload access (DWA) and a driver for statistics access (DSA). These drivers are the only components ofARe-SQL Advisor which are  DBMS-specific. Nevertheless, these drivers are implemented in a non-intrusive fashion. We have so far implemented drivers for the following DBMSs: PostgreSQL 8.4, Oracle 11g and SQL Server 2008 (see Section \ref{results}).

The main components of the architecture illustrated in Figure  \ref{fig:arqAsistida} are the following:

\begin{itemize}
\item	Agent for Workload Obtainment (AWO): This agent observes the operations submitted to the DBMS and retrieves the SQL statements and then stores them in the local metabase (Local MetaData - LM). This agent can be configured to run continuously (On-the-fly).
\item	Local Meta Data (LM): Database which stores workloads captured by AWO.
\item	Driver for Workload Access (DWA): This component enables ARe-SQL Advisor to access metabase (catalog) of a given DBMS.
\item	Agent for Statistics Obtainment (ASO): This component is in charge of accessing statistics information of the target DBMS, such as table cardinality, the amount of disk pages required to store a database table, the height of ($b^{+}$ tree) index structures and so forth.
\item	Driver for Statistics Access (DSA): driver that allows the ASO to retrieve statistics for a specific DBMS.
\item	Heuristic Set (HS): set of heuristics used by the agents to identify SQL statements with oportunities of tuning and in order to rewrite them. HS is composed of 11 heuristics, which are depicted in Table \ref{tab:heuristics}. However, new heuristics can be defined and inserted into HS.
\item	Agent for SQL Tuning (AST): Component responsible for tuning a particular SQL statement using the set of heuristics (HS).
\item	Tuning Settings (TS): This component is preference file containing pairs $<$SQL statement $Q$, subset of heuristics H$>$ defined by the DBA. Each pair indicates a heuristic chosen by DBA from HS that he/she wants to be applied for tuning $Q$. 
\end{itemize}

\begin{figure}[h]
	\centerline{\psfig{figure=advisor.pdf,width=10cm} }
	\caption{ ARe-SQL Advisor's  Architecture.}
	\label{fig:arqAsistida}
\end{figure}

\subsection{Automatic Approach}

The automatic approach consists of a middleware, ARe-SQL Mid, that works between the application and the DBMS. This middleware is responsible for: {\it (i)} automatically receiving SQL statements sent by applications; {\it (ii)} analyzing and rewriting them whenever  necessary, and; {\it (iii)} submitting the statements (rewritten or not) to the DBMS.

The architecture designed for the automatic approach is illustrated in Figure \ref{fig:arqAutomatica}. The main components of this architecture, in addition to components that are also present in Figure \ref{fig:arqAutomatica}, are:

\begin{itemize}
\item	Middleware for SQL Tuning (MST): is responsible for receiving SQL statements from the applications; send them to the agent AST examine them; and receive the statements rewrited (or not) and send them to the DBMS; receive the result of executing these queries and send them to the applications.
\item Driver for Data Access (DDA): driver that allows the engine of the middleware (Middleware for SQL Tuning) to send the SQL statements to the target DBMS.
\end{itemize}

\begin{figure}[h]
	\centerline{\psfig{figure=midlleware.pdf,width=10cm} }
	\caption{Architecture of ARe-SQL's Automatic Approach.}
	\label{fig:arqAutomatica}
\end{figure}



\section{Experimental Results}
\label{results}

In order to show the potentials of ARe-SQL, several experiments have been conducted. The main results achieved so far are presented and discussed in this section. Thus, we first provide information on how the experimentation environment was set up. Thereafter, empirical results are quantitatively presented and qualitatively discussed.

\subsection{Simulation Setup}

In order to validate both approaches, assisted and automatic, implemented by Are-SQL, we have evaluated ARe-SQL in three different scenarios. In the first scenario, TPC-H benchmark has been used, including its database and workload, which is composed of 23 queries. In the second scenario, a workload of 30 synthetic queries has been executed on TPC-H database. Finally, in the third scenario, we exploit the database of a system used in several brazilian universities, called Integrated Management System (IMS), and another synthetic workload. The IMS database has more than 900 tables. The synthetic workloads are designed using the following strategy. Each synthetic workload is formed by 30 SQL queries. Each SQL query was written in order to enable the application of one of the heuristics presented in the Table \ref{tab:heuristics}. 

All experiments were run on a Core i3-2100 (3.10GHz) server, with 4GB RAM and 500 GB HD. PostgreSQL 8.1, Oracle 11g and SQL Server 2008 have been used as database systems. 

For each experimentation scenario, three different experiments have been performed:
\begin{enumerate}
 \item The workload containing the original queries has been submitted to a database system. The results of this experiment have been  be used as baseline; 
\item The workload submitted to ARe-SQL advisor (assisted approach). Thereafter, the workload with tuned SQL queries were manually submitted to a database system, and;
\item Each query from original workload has been sent to the automatic approach of ARe-SQL. In this case, after tuning SQL queries, ARe-SQL automatically submits those queries to a database system. 
\end{enumerate}

For each test we have executed we have executed the set of queries belonging to used workload once, twice, 4, 8, 16, and 32 times. For each different number of executions (iterations), the sum of execution time of the whole set of queries was computed. For instance, in scenario 1 (Full TPC-H Benchmark), to get the execution time for 32 executions, we have execute the set of TPC-H queries 32 times, measured the time interval for executing all queries and computed the sum of the 32 measured execution times.

Finally, we varied the order in which the queries in a workload were performed. For this, we used three distinct strategies, called: sequential, random and random steady. In the sequential strategy, queries are run sequentially (in the original order). In random strategy, before each iteration, the query execution order is chosen randomly. In the random steady strategy, before the first iteration, an execution order is chosen randomly, which is maintained in all subsequent iterations. The Figures \ref{fig:23tpchPost}, \ref{fig:23tpchSQL}, \ref{fig:23tpchOra}, \ref{fig:30tpchPost}, \ref{fig:30tpchSQL}, \ref{fig:30tpchOra} and \ref{fig:gis}) show the results of different tests using the sequential strategy for define the queries execution order.

\subsection{Scenario 1: Full TPC-H Benchmark}

%Two queries (18 and 20) of the 23 queries that comprise the TPC-H benchmark, have been rewritten (tuned) by AST agent, using the heuristic H8, for DBMS SQL Server and PostgreSQL. In Figures \ref{fig:23tpchPost} and \ref{fig:23tpchSQL} we can conclude that the assisted approach had a small decrease in runtime of the workload. What is explained by the fact that only two TPC-H queries have presented opportunities for tuning. However, these two queries were not rewritten by AST agent for Oracle, since it already implements this heuristic. Thus, we observe in Figure \ref{fig:23tpchOra} that the automatic approach had a slight worsening compared to baseline. What is explained by the fact that the automatic approach had the overhead of trying to rewrite each of the queries received and none of them have the opportunity to tune on Oracle.

Figures \ref{fig:23tpchPost} and \ref{fig:23tpchSQL} bring the result of using the assisted and automatic approach of ARe-SQL running on PostgreSQL and SQL Server, respectively. It is important to observe that from the 23 queries that comprise the TPC-H benchmark, two (18 and 23) have been rewritten (tuned) by ARe-SQL advisor (see Section \ref{assisted}). Regarding the results presented in Figures \ref{fig:23tpchPost} and \ref{fig:23tpchSQL}, the assisted approach had a small decrease in workload runtime. This can be explained by the fact that only two TPC-H queries have presented opportunities for tuning. 


\begin{figure}[h]
\centering
\begin{minipage}[b]{7.5cm}
	\centerline{\psfig{figure=Teste1.pdf,width=7.5cm} }
	\caption{Benchmark TPC-H on PostgreSQL}
	\label{fig:23tpchPost}
\end{minipage}
\hspace*{0.25cm}
\begin{minipage}[b]{7.5cm}

	\centerline{\psfig{figure=Teste5.pdf,width=7.5cm} }
	\caption{Benchmark TPC-H on SQL Server}
	\label{fig:23tpchSQL}

\end{minipage}
\end{figure}

%\hspace*{1.cm}
%\begin{minipage}[b]{6cm}

Figure \ref{fig:23tpchOra} depicts the results of using ARe-SQL on Oracle. Since Oracle implements heuristic H8However, TPC-H queries 18 and 23 have not been  rewritten by ARe-SQL advisor. Regarding the ARe-SQL automatic approach, one may observe in Figure \ref{fig:23tpchOra} that it had a slight worsening compared to baseline. This is because the automatic approach had the overhead of trying to rewrite both queries.
\begin{figure}

	\centerline{\psfig{figure=Teste8.pdf,width=7.5cm} }
	\caption{Benchmark TPC-H on Oracle}
	\label{fig:23tpchOra}

%\end{minipage}

\end{figure}


%\begin{figure}[h]
%	\centerline{\psfig{figure=Teste1.pdf,width=9cm} }
%	\caption{Benchmark TPC-H on PostgreSQL}
%	\label{fig:23tpchPost}
%\end{figure}

%\begin{figure}[h]
%	\centerline{\psfig{figure=Teste5.pdf,width=9 cm} }
%	\caption{Benchmark TPC-H no SQL Server}
%	\label{fig:23tpchSQL}
%\end{figure}

%\begin{figure}[h]
%	\centerline{\psfig{figure=Teste8.pdf,width=9cm} }
%	\caption{Benchmark TPC-H no Oracle}
%	\label{fig:23tpchOra}
%\end{figure}


%A Tabela \ref{tab:consultasTpch18e20} mostra os tempos de execução das consultas TPC-H 18 e 20 em seus formatos originais e após serem reescritas.

Table \ref{tab:consultasTpch18e20} shows the execution time of  TPC-H queries 18 and 20 in their original formats and after being rewritten.

\begin{table}[!]
	\caption{Execution times of the TPC-H queries 18 and 20 in their original formats and after being rewritten.}
	\label{tab:consultasTpch18e20}
	\centering
	\begin{tabular}{|c|c|c|c|c|}
		\hline
		  &	\multicolumn{2}{c|}{\textbf{PostgreSQL}} 	&	\multicolumn{2}{c|}{ \textbf{SQL Server}}	\\
		\hline
		  &	 \textbf{Original}	&  \textbf{Rewritten}	&  \textbf{Original}	&  \textbf{Rewritten}	\\
		\hline
		 \textbf{Query TPC-H 18} 	&	134.807ms	&	111.933ms	&	19s	&	14s	\\
		\hline
		 \textbf{Query TPC-H 20} 	&	912ms	&	712ms	&	15s	&	11s	\\
		\hline 
		
	\end{tabular}
\end{table}



%No experimento realizado utilizando-se a estratégia aleatória com o benchmark TPC-H no PostgreSQL, a execução das 32 iterações da carga de trabalho original (sem reescrita) demorou 304 segundos, enquanto a execução  das 32 iterações da carga de trabalho gerada após a aplicação da abordagem assistida teve duração de 283 segundos. Neste caso, a abordagem assistida proporcionou um ganho de 21 segundos. 

%In the experiment using the random strategy (with the TPC-H benchmark) on PostgreSQL, the runtime for the 32 iterations of the original workload (without rewriting) took 304s, while the runtime for the 32 iterations of the workload generated after applying the assisted approach lasted 283 seconds. In this case, assisted approach yielded a gain of 21 seconds (6.9\%).


\subsection{Scenario 2: TPC-H Database with Synthetic Workload}

Figures \ref{fig:30tpchPost}, \ref{fig:30tpchSQL} and \ref{fig:30tpchOra} show that using ARe-SQL advisor ensure a significant reduction in query response. On the other hand, ARe-SQL's automatic approach presents smaller benefits than ARe-SQL advisor, since it involves the overhead of tuning the SQL statements received in runtime.

\begin{figure}[h]
\centering
\begin{minipage}[b]{7.5cm}

	\centerline{\psfig{figure=Teste10.pdf,width=7.5cm} }
	\caption{Synthetic queries in TPC-H database on PostgreSQL}
	\label{fig:30tpchPost}

\end{minipage}
\hspace*{0.25cm}
\begin{minipage}[b]{7.5cm}

	\centerline{\psfig{figure=Teste13.pdf,width=7.5cm} }
	\caption{Synthetic queries in TPC-H database on SQL Server}
	\label{fig:30tpchSQL}
\end{minipage}
\end{figure}


It's important to note that in the test on Oracle (Figure \ref{fig:30tpchOra}) automatic approach presents a small decrease in the execution time of the workload. This is explained by the fact that from the total of eleven heuristics five are already implemented by Oracle (H4, H5, H6, H7 and H8). Besides, from the six remaining heuristics, three of them (H9, H10 and H11) make use of statistical information, and, therefore, require additional access to DBMS, which significantly increased the overhead to rewrite SQL queries.

\begin{figure}[h]

\centerline{\psfig{figure=Teste16.pdf,width=7.5cm} }
	\caption{Synthetic queries in TPC-H database on Oracle}
	\label{fig:30tpchOra}
\end{figure}

%\begin{figure}[h]
%	\centerline{\psfig{figure=Teste10.pdf,width=9cm} }
%	\caption{Synthetic queries in TPC-H database on PostgreSQL}
%	\label{fig:30tpchPost}
%\end{figure}

%\begin{figure}[h]
%	\centerline{\psfig{figure=Teste13.pdf,width=9cm} }
%	\caption{Synthetic queries in TPC-H database on SQL Server}
%	\label{fig:30tpchSQL}
%\end{figure}

%\begin{figure}[h]
%	\centerline{\psfig{figure=Teste16.pdf,width=9cm} }
%	\caption{Synthetic queries in TPC-H database on Oracle}
%	\label{fig:30tpchOra}
%\end{figure}

%Vale destacar que nos testes realizados no Oracle (Figuras \ref{fig:teste16}, \ref{fig:teste17} e \ref{fig:teste18}) a abordagem automática apresentou apenas uma pequena diminuição no tempo de execução da carga de trabalho. Das onze heurísticas disponíveis na abordagem, cinco já são implementadas pelo Oracle (H4, H5, H6, H7 e H8). E das seis heurísticas que restaram para ajustar a carga de trabalho, três delas (H9, H10 e H11) fazem uso de informações estatísticas e, consequentemente, necessitam de acessos adicionais ao SGBD aumentado significativamente o \textit{overhead} ao ajustar as instruções SQL.

%A Figura \ref{fig:teste18} ilustra o resultado do teste aleatório fixo com o 30 consultas sintéticas na base TPC-H no Oracle. Neste experimento, a execução das 32 iterações da carga de trabalho original (sem reescrita) demorou 673,28 segundos. Já a execução  das 32 iterações da carga de trabalho gerada após a aplicação da abordagem assistida teve duração de 49,43 segundos. Neste caso, a abordagem assistida proporcionou um ganho de 623 segundos. Já o mesmo teste com a abordagem automática demorou 645,95. Esse resultado decorre do fato que a maioria das heurísticas que o Oracle ainda implementa (H1, H2, H3, H9, H10 e H11) utilizam operações estatísticas, o que implica na execução de consultas adicionais para recuperar essas informações do SGBD. 

In the experiment using the random strategy (with TPC-H Database and Synthetic Workload) on Oracle, the runtime for the 32 iterations of the original workload (without rewriting) took 673.28s, while the runtime for the 32 iterations of the workload generated after applying the assisted approach lasted 49.43 seconds. In this case, assisted approach yielded a gain of 623 seconds (92.5\%). 
%However, the same test with the automatic approach took 645.95s, providing a gain of 27.33s. The aspects previously discussed explain this. This is explained by the fact that from the six heuristics that Oracle doesn't implement three make use of statistical information.

\subsection{Scenario 3: IMS Database with Synthetic Workload}

For this scenario, only PostgreSQL has been used, since, IMS database is only available for that DBMS. Again, the proposed approaches have provided a high reduction in time execution of the submitted workload (Figure \ref{fig:gis}). In the experiment using the random strategy (with IMS Database and Synthetic Workload) on PostgreSQL, the runtime for the 32 iterations of the original workload (without rewriting) took 314.32s, while the runtime for the 32 iterations of the workload generated after applying the assisted approach lasted 34.72 seconds. In this case, assisted approach yielded a gain of 280 seconds (89\%). 

\begin{figure}[h]
	\centerline{\psfig{figure=Teste20.pdf,width=7.5cm} }
	\caption{Synthetic queries in IMS database on PostgreSQL.}
	\label{fig:gis}
\end{figure} 

\vspace{-0.25cm}
\subsection{Overhead Analysis}

To analyze the overhead in SQL rewriting process we made an experiment using TPC benchmark. The idea was measure the time needed to rewrite each one of the 23 SQL queries in the TPC benchmark workload. For this, we have used as a baseline the rewritten time produced by \textit{Quest SQL Optimizer for Oracle}. This tool was chosen because it is widely used in real scenarios.

Table \ref{tab:testeQuest} shows a piece of the report generated by \textit{Quest SQL Optimizer for Oracle} using TPC-H queries with input. This report indicated that from the total of 23 SQL queries 16 could be rewritten successfully. Only 7 SQL queries couldn't be tuned (1, 6, 10, 13, 17, 19 and 23). However, after to perform (with empty cache), for each one of these 16 SQL queries, the best SQL command (w.r.t cost estimate) generated by the \textit{Quest SQL Optimizer for Oracle} tool,  we noted that only 5 SQL queries  had reduced their runtimes (queries 2, 3, 11, 12 and 20). In practice, queries 4, 5, 7, 8, 9, 14, 16, 18, 21 and 22 had a worsening in their execution times. It's important to note that in some cases, like queries 4 and 7, the rewritten SQL response time was much greater than the original query runtime. Additionally, \textit{Quest SQL Optimizer for Oracle} tool is DBMS-specific (running only with Oracle). Besides, in some cases, this tool may generate tens or hundreds of rewritten SQL instructions for tune the same SQL statement, such as, for example, for query 5, 228 different rewritten SQL instructions were generated. This fact could increase so much the rewritten time, producing a high overhead, and making this tool unfeasible for online scenarios, that is, those where the SQL statement needs to be adjusted automatically (at runtime). On the other hand, we submitted the synthetic workload used at the scenario 2 to ARe-SQL and measured the time needed to rewrite each one of the 30 SQL queries. ARe-SQL spent in average 29.83s to rewrite a query on Oracle, 19.33s on SQL Server and 40.66 on PostgreSQL.


\begin{table}[!htb] 
	\caption{\textit{SQL Optimizer for Oracle} using TPC-H \textit{benchmark}.}
	\label{tab:testeQuest}
	\centering
	\begin{tabular}{|c|p{2 cm}|p{1.6 cm}|p{2 cm}|p{2 cm}|p{2 cm}|p{2 cm}|}
		\hline
		Query	
		& No. of generated SQL commands
		& Rewriting Overhead	
		& No. of SQL clauses with cost estimate less than the original SQL 
		& No. of SQL clauses with response time estimate less than the original SQL
		& Original SQL response time
		& Execution time for the best rewritten SQL
		\\
		\hline 
		%1	&	0	&	1s	&	-		&	-	&	8210ms	&	-	\\
		%\hline
		2	&	115	&	116s	&	3		&	3	&	310ms	&	128ms	\\
		\hline
		3	&	53	&	58s	&	3		&	1	&	6393ms	&	4900ms	\\
		\hline
		\textbf{4}	&	14	&	15s	&	1		&	0	&	4204ms	&	1 min\\
		\hline
		5	&	228	&	229s	&	5		&	0	&	4658ms	&	4666ms	\\
		\hline
		%6	&	1	&	1s	&	0		&	0	&	2313ms	&	-	\\
		%\hline
		\textbf{7}	&	110	&	111s	&	1		&	0	&	4658ms	&	7808ms	\\
		\hline
		%8	&	140	&	141s	&	1		&	0	&	4567ms	&	4770ms	\\
		%\hline
		%9	&	191	&	192s	&	5		&	0	&	6181ms	&	6749 ms	\\
		%\hline
		%10	&	118	&	120s	&	0		&	0	&	3160ms	&	-	\\
		%\hline
		11	&	139	&	140s	&	8		&	4	&	600ms	&	259ms	\\
		\hline
		12	&	20	&	21s	&	1		&	1	&	1995ms	&	1993	\\
		\hline
		%13	&	2	&	3s	&	0		&	0	&	1995ms	&	-	\\
		%\hline
		14	&	5	&	6s	&	1		&	0	&	512ms	&	538ms	\\
		\hline
		16	&	35	&	36s	&	2		&	0	&	278.244ms&	280.190 ms\\
		\hline
		%17	&	29	&	30s	&	0		&	0	&	1.635ms	&	-	\\
		%\hline
		18	&	160	&	161s	&	1		&	0	&	17.384ms	&	22.306 ms\\
		\hline
		%19	&	86	&	87s	&	0		&	0	&	3.228ms	&	-	\\
		%\hline
		20	&	92	&	93s	&	8		&	3	&	3.261ms	&	3.212ms	\\
		\hline
		21	&	120	&	121s	&	5		&	0	&	8.660ms	&	8.787ms	\\
		\hline
		22	&	1	&	1s	&	1		&	0	&	407ms	&	418ms	\\
		\hline
	\end{tabular}
\end{table}

%O relatório gerado pela ferramenta \textit{Quest SQL Optimizer for Oracle} indicou que das 22 consultas analisadas apenas 6 consultas não poderiam ser ajustadas, ou seja, a ferramenta não conseguiu gerar uma instrução SQL equivalente (reescrita) que proporcionasse um tempo de execução estimado melhor que o tempo de execução estimado da instrução original. Foram essas as consultas 1, 6, 10, 13, 17 e 19. Logo, o relatório indicou que 16 consultas poderiam ser otimizadas com sucesso.

%O próximo passo do experimento consistiu em executar (com \textit{cache} vazio) para cada uma dessas 16 consultas a instrução SQL original e a melhor instrução SQL equivalente gerada pelo \textit{Quest SQL Optimizer for Oracle}. O resultado desse experimento mostrou que das 16 consultas ajustadas apenas 5 tiveram seu tempo de execução reduzido (foram elas as consultas 2, 3, 11, 12 e 20). Já as consultas 4, 5, 7, 8, 9, 14, 16, 18, 21 e 22 tiveram, na prática, uma piora nos seus tempos de execução. Logo, a ferramenta errou em 11 consultas e acertou em apenas 5 comandos SQL, de um total de 16 instruções SQL. Vale observar que em alguns casos, como nas consultas 4 e 7, o tempo de resposta da instrução SQL gerada pela ferramenta da \textbf{Quest} foi muito maior que o tempo de resposta da consulta original, piorando bastante o desempenho dessas consultas.

%Adicionalmente, a ferramenta \textit{Quest SQL Optimizer for Oracle} possui a limitação de poder ser utilizada apenas com o SGBD Oracle. Além disso, a ferramenta pode gerar algumas dezenas ou centenas de instruções para ajustar uma determinada instrução SQL, tornando o seu tempo de sintonia bastante demorado. Isso inviabiliza a utilização da ferramenta em cenários onde a instrução SQL precisa ser ajustada automaticamente, ou seja, em tempo de execução.

\vspace{-0.3cm}
\section{Conclusions}
\label{concl}

\vspace{-0.2cm}

%We present two approaches to tune SQL statements: an assisted approach and an automatic approach. The proposed solutions are applicable to situations where the query optimizer can not produce optimal plans, even using access methods and assessment strategies supported by the DBMS. The results of experiments indicate that both approaches can provide performance gains.

In this paper, we propose an automatic, autonomous and non-intrusive approach for rewriting SQL queries, denoted ARe-SQL. The key goal of ARe-SQL is to assist optimizers in build efficient query physical execution plan. For this, ARe-SQL rewrites SQL statements, using a set of 11 heuristics. The heuristics consist of rules to identify potential opportunities for tuning SQL statements and the ways to rewrite the statements. Based on ARe-SQL, two different strategies for SQL-query rewriting, denoted assisted and automatic, were implemented. These strategies were evaluated in three different DBMSs considering three different scenarios: TPC-H benchmark; TPC-H database and a synthetic workload; and a real database (used in several Brazilian universities) with another synthetic workload. The experimental results indicate that both strategies can provide performance gains. In some cases, such performance gains  reach 92.5\%. The proposed solutions are applicable to situations where the query optimizer cannot produce optimal plans, even using access methods and assessment strategies supported by the DBMS. As future work we intend to investigate and implement heuristics based on query hints to tune SQL queries.

\bibliographystyle{jidm}

\bibliography{IEEEabrv}
\begin{received} 
\end{received}
\end{document}
