
\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{Arlino H. M. de Araujo et. al.}
{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 Ara\'{u}jo\inst{1,2}, Jos\'{e} Maria Monteiro\inst{2}, Jos\'{e} Ant\^{o}nio F. de Mac\^{e}do\inst{2}, J\'{u}lio A. Tavares\inst{3}, Angelo Brayner\inst{3}, S\'{e}rgio Lifschitz\inst{4}}


%Affiliation and email
\institute{
Federal University of Piau\'{i}, Brazil 
\and Federal University of Cear\'{a}, Brazil \\ \email{\{arlino,monteiro,jose.macedo\}@lia.ufc.br}
\and University of Fortaleza, Brazil \\ \email{brayner@unifor.br}
\and Pontifical Catholic University of Rio de Janeiro \\ \email{sergio@inf.puc-rio.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 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]
\category{H.2}{Database Management}{Miscellaneous}

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

\begin{document}

\maketitle

\vspace{-1.1cm}
\section{Introduction}
\vspace{-0.2cm}

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 inefficient PEPs. In order to overcome such an issue, there are strategies to help optimizers, such as to provide query hints and query rewriting \cite{garcia-molina}. 

The rewriting technique consists in writing a new SQL statement $Q_{b}$ equivalent to the statement $Q_{a}$ initially formulated. Two queries are equivalent if and only if their execution produces the same result \cite{Ramakrishnan08}. Thus, the executions 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}

Looking more closely to Figures \ref{fig:S1} and \ref{fig:S2}, one can observe that $Q_{a}$ and $Q_{b}$ are equivalent. Nonetheless, $Q_{a}$ execution lasts $13.685 ms$, while $Q_{b}$ is executed in $1.825ms$. %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 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.7cm}
\flushleft
\includegraphics[width=6.5cm]{P1.pdf}
\flushleft
\vspace*{-.5cm}
\caption{PEP $P_{Q_{a}}$ yielded by PostgreSQL for $Q_{a}$}
\label{fig:P1}
\end{minipage}
\hspace*{.2cm}
\begin{minipage}[b]{8.5cm}
\flushleft
\includegraphics[width=8.3cm]{P2.pdf}
\vspace*{-.2cm}
\caption{PEP $P_{Q_{b}}$ yielded by PostgreSQL for $Q_{b}$}
\label{fig:P2}
\end{minipage}
\end{figure} 

%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 a particular DBMS implementation and that are usually not affected by any new DBMS release.


Database query tuning explores these aspects in order to help query optimizers to produce better PEPs. In fact, %there are already tools which aim at tuning database query performance by providing rewriting recommendations. 
there are tools that 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) requires 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 chosen 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}. 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}.

\vspace{-0.3cm}
\section{Related Work}
\label{secRelWork}
\vspace{-0.2cm}

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 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 this tool collects metrics for a given period of time (defined by the DBA). 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. 

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 be evaluated for choosing one of the several alternatives provided by them. Observe that DBAs work in a reactive way, i.e., they only trigger a tool or an advisor when the problem already exists. 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.

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

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. Furthermore, it indicates whether or not each heuristic is currently implemented by three major DBMSs: PostgreSQL 8.3, Oracle 11g and SQL Server 2008.

\vspace{-0.5cm}
\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}

\vspace{-0.3cm}
\subsection{Implementing ARe-SQL}
\vspace{-0.2cm}

In order to implement ARe-SQL, two different approaches were employed: assisted and automatic. For each approach, a different tool was implemented. However, both approaches present the following features: {\it (i)} Non-intrusive: completely decoupled from the source code of the DBMS. This allows that the conceived solution can be used with any DBMS and {\it (ii)} 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.

\vspace{-0.2cm}
\subsubsection{Assisted Approach}
\label{assisted}
\vspace{-0.2cm}

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 system or a given statement. We have implemented a tool, called ARe-SQL Advisor, which implements an assisted approach for ARe-SQL. The main components of the architecture illustrated in Figure  \ref{fig:arqAsistida} are the following:%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:

\vspace{-0.3cm}
\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 that 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 subset chosen by DBA from HS that he/she wants to be applied for tuning $Q$. If there isn't an entry in this file for a given statement $Q$, all 11 heuristics are applied for tuning $Q$ (in both, Assisted and Automatic Approaches).
\end{itemize}

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

	\centerline{\psfig{figure=advisor.pdf,width=7.5cm} }
	\vspace{-0.2cm}
	\caption{ARe-SQL Advisor's Architecture.}
	\label{fig:arqAsistida}

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

	\centerline{\psfig{figure=midlleware.pdf,width=7.5cm} }
	\vspace{-0.2cm}
	\caption{Architecture of ARe-SQL's Automatic Approach.}
	\label{fig:arqAutomatica}
	
\end{minipage}
\end{figure}

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

\vspace{-0.4cm}
\subsubsection{Automatic Approach}
\label{automatic}
\vspace{-0.2cm}

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:arqAsistida}, are:

\vspace{-0.3cm}
\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 rewritten (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}

\vspace{-0.6cm}
\section{Experimental Results}
\label{results}
\vspace{-0.2cm}

%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}
\vspace{-0.2cm}

%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. In both scenarios, we have used TPC-H benchmark with scale factor of 2 GB. 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 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: i) The workload containing the original queries has been submitted to a database system. The results of this experiment have been  be used as baseline; ii) The workload submitted to ARe-SQL advisor (assisted approach). Thereafter, the workload with tuned SQL queries were manually submitted to a database system, and; iii) 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. 
For each test 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.

\vspace{-0.35cm}
\subsection{Scenario 1: Full TPC-H Benchmark}
\vspace{-0.2cm}

%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 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. Table \ref{tab:consultasTpch18e20} shows the execution time of  TPC-H queries 18 and 23 in their original formats and after being rewritten.

\vspace{-0.4cm}
\begin{figure}[h]
\centering
\begin{minipage}[b]{7.5cm}
	\centerline{\psfig{figure=Teste1.pdf,width=7.5cm} }
	\vspace{-0.25cm}
	\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} }
	\vspace{-0.25cm}
	\caption{Benchmark TPC-H on SQL Server}
	\label{fig:23tpchSQL}

\end{minipage}
\end{figure}

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

\vspace{-0.3cm}
On Oracle, however, TPC-H queries 18 and 23 were not rewritten by ARe-SQL advisor, since Oracle implements heuristic H8. So, the ARe-SQL automatic approach had a slight worsening compared to baseline (24.95\%). This is because the automatic approach had the overhead of trying to rewrite both queries. 

%\vspace{-0.3cm}
%\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.

\vspace{-0.3cm}
\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 23} 	&	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 ensures 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]
\centering
\begin{minipage}[b]{7.5cm}

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

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

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

%\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 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, as the 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 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.



%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 building efficient query physical execution plan. For this, ARe-SQL rewrites SQL statements, using a set of 11 heuristics. 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. 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.

\vspace{-0.4cm}
\bibliographystyle{jidm}

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