% by Mirella M. Moro; version: January/18/2012 @ 04:16pm
% -- 01/18/2012: more discussion on SBBD + JIDM; overall revision
% -- 09/03/2010: bib file with names for proceedings and journals; cls with shrinked {received}
% -- 08/27/2010: appendix, table example, more explanation within comments, editors' data

\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{multirow}
\usepackage[english,linesnumbered,algoruled,longend,lined]{algorithm2e}
\usepackage{xcolor}
%\usepackage{subcaption}
\usepackage{listings}
%\usepackage{adjustbox}
\usepackage{subfig}

\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}

%\usepackage{cite} % NOTE: do **not** include this package because it conflicts with jidm.bst

% Standard definitions
\newtheorem{theorem}{Theorem}[section]
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newdef{definition}[theorem]{Definition}
\newdef{remark}[theorem]{Remark}

% 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{4}
\jidmNumber{1}
\jidmYear{13}
\jidmMonth{February}
\setcounter{page}{1}


% Includes headers with simplified name of the authors and article title
\markboth{Manoel M. Siqueira et. al.}
{Approaches to Model Query Interactions}
%  -> \markboth{}{}
%         takes 2 arguments
%         ex: \markboth{M. M. Moro}{Any article title}


% Title of the article
\title{Approaches to Model Query Interactions}


% 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{Manoel Siqueira\inst{1}, Jos\'{e} Maria Monteiro\inst{1}, Angelo Brayner\inst{2}, \\ Jos\'{e} Macedo\inst{1}, Javam Machado\inst{1}}


%Affiliation and email
\institute{Universidade Federal do Cear\'{a}  - Brasil \\ \email{\{manoeljr, monteiro, jose.macedo, javam\}@lia.ufc.br}
% IF THERE IS ANOTHER INSTITUTION:
\and Universidade de Fortaleza - Brasil \\
\email{brayner@unifor.br}
}


% Article abstract - it should be from 100 to 300 words
\begin{abstract}
A typical database workload consists of several query instances of
different query types running  concurrently. The execution of each
query may interact with the execution of the other queries. It is well
known that such interactions can have a significant impact on database
system performance. In this article we propose three new approaches to model and measure query instance and query type interactions. Our approaches require no
prior assumptions about the internal aspects of the database system,
making it non intrusive, namely, portable across systems. Furthermore,
to demonstrate the profit of exploiting query interactions, we have developed a novel interaction-aware query scheduler for online
workloads, called Intelligent Scheduler for Multiple-query Execution
Ordering (ISO, for short). In order to verify the efficiency of
the proposed approaches for measuring query interaction and of IOS, an
experimental evaluation using TPC-H workloads running on PostgreSQL
has been done. The results show that the proposed approach has
potential to improve the efficiency of database tuning tools.
\end{abstract}


% ACM Computing Classification System categories
\category{H.2}{Database Management}{Miscellaneous}

% Categories and Descriptors are available at the 1998 ACM Computing Classification System
% http://www.acm.org/about/class/1998/
%  -> \category{}{}{}
%         takes 3 arguments for the Computing Reviews Classification Scheme.
%         ex: \category{D.3.3}{Programming Languages}{Language Constructs and Features}
%                   [data types and structures]
%                   the last argument, in square brackets, is optional.

% Article keywords
\keywords{query interactions, query scheduling, interaction factor}
%  -> \keywords{} (in alphabetical order \keywords{document processing, sequences,
%                      string searching, subsequences, substrings})


% THE ARTICLE BEGINS
\begin{document}

% This is optional:
\begin{bottomstuff}
This work as partially funded by FUNCAP and CNPq.
% similar to \thanks
% for authors' addresses; research/grant statements
\end{bottomstuff}

\maketitle


\vspace{-0.0cm}
\section{Introduction}

A typical database workload consists of a mix of multiple query
instances of different query types that run concurrently and interact
with each other. A query type can be defined as a template for SQL
queries, which consists of a SQL expression with parameter
markers. Whenever a template is instantiated with a set of parameter
values, one has a query instance. For example, the popular TPC-H
decision support benchmark \cite{TPCH} defines 22 query
templates. From each TPC-H query template, several  query instances
can be generated. From now on, we use the term query type to represent
a query template.  Thus, there exist 22 query types in TPC-H
benchmark. 

Figures  \ref{fig:type} and \ref{fig:instance} illustrates the notions
of query type and query instance. Figure \ref{fig:type} shows a TPC-H
query type $Q_{j}$ with one parameter marker, represented by the
symbol ``?''. Different value settings of the parameter marker yield
different instances of the query type. In turn, Figure \ref{fig:instance} illustrates a query instance $q_{j_{1}}$ of the query type $Q_{j}$.

\lstset{%
language=C,
frame=single,
numbers=left,
numberstyle=\scriptsize,
tabsize=2,
keepspaces=true,
columns=fullflexible,
basicstyle=\ttfamily\scriptsize,
keywordstyle=\color{blue}
}

\newsavebox{\mylistingbox}

%\begin{figure}[tb]
%\centering
%\begin{lrbox}{\mylistingbox}
%\begin{minipage}{.4\linewidth}
%\begin{lstlisting}[language=SQL]
%SELECT *
%FROM lineitem AS l, orders AS o, 
%	supplier AS s, nation AS n
%WHERE l.l_orderkey = o.o_orderkey AND
%	l.l_suppkey = s.s_suppkey AND
%	s.s_nationkey = n.n_nationkey AND
%	n.n_name = ?;
%\end{lstlisting}
%\end{minipage}
%\end{lrbox}
%%
%\subfloat[Query type (template)]{
%\label{fig:type}
%\usebox{\mylistingbox}
%}%
%%
%\hfill
%%
%\begin{lrbox}{\mylistingbox}%
%\begin{minipage}{.4\linewidth}%
%\begin{lstlisting}[language=SQL]
%SELECT *
%FROM lineitem AS l, orders AS o, 
%	supplier AS s, nation AS n
%WHERE l.l_orderkey = o.o_orderkey AND
%	l.l_suppkey = s.s_suppkey AND
%	s.s_nationkey = n.n_nationkey AND
%	n.n_name = 'USA';
%\end{lstlisting}
%\end{minipage}
%\end{lrbox}
%%
%\subfloat[Query instance]{
%\usebox{\mylistingbox}
%\label{fig:instance}
%}%
%\caption{Query examples}
%\end{figure}


\begin{figure*}
\centering
\begin{lrbox}{\mylistingbox}
\begin{minipage}{.4\linewidth}
\begin{lstlisting}[language=SQL]
SELECT *
FROM lineitem AS l, orders AS o, 
	supplier AS s, nation AS n
WHERE l.l_orderkey = o.o_orderkey AND
	l.l_suppkey = s.s_suppkey AND
	s.s_nationkey = n.n_nationkey AND
	n.n_name = ?;
\end{lstlisting}
\end{minipage}
\end{lrbox}
%
\subfloat[Query type (template)]{
\label{fig:type}
\usebox{\mylistingbox}
}%
%
\hfill
%
\begin{lrbox}{\mylistingbox}%
\begin{minipage}{.4\linewidth}%
\begin{lstlisting}[language=SQL]
SELECT *
FROM lineitem AS l, orders AS o, 
	supplier AS s, nation AS n
WHERE l.l_orderkey = o.o_orderkey AND
	l.l_suppkey = s.s_suppkey AND
	s.s_nationkey = n.n_nationkey AND
	n.n_name = 'USA';
\end{lstlisting}
\end{minipage}
\end{lrbox}
%
\subfloat[Query instance]{
\usebox{\mylistingbox}
\label{fig:instance}
}%
\caption{Query examples}
\end{figure*}

%In database management systems (DBMSs), the concurrency level is defined by a parameter denoted multiprogramming level (MPL), which is the number of query instances that execute concurrently in the system. Then, if MPL = 10 a maximum of 10 query instances will run concurrently. If MPL=1 we have a sequential execution of the database workload.

Query instances in a workload can have interactions with a significant impact on database performance, which can be positive or negative \cite{Ahmad:09}. The papers presented in \cite{Ahmad:09,Ahmad:11} show many interesting examples of the effect of query interactions on database performance. However, very little work in the database literature deals with the problems of modeling and measuring query interactions \cite{Ahmad:09}.

In this work, we propose three new approaches to model and measure
query instance and query type interactions. The proposed approaches, denoted intercalation strategy (IS), data retrieving rate (DRR) and greedy bidimentional
array (GBA), do not require any prior assumptions on
internal aspects of the database system, which makes them non
intrusive and consequently portable to existing database systems. The proposed approaches have different inputs and preprocessing overhead. The IS approach is based only on the SQL statements and query execution plans. No preprocessing is needed. The DRR approach is based on the data retrieving rate from hard disk and requires a low level of preprocessing. GBA approach uses a preprocessed bidimentional array with estimations about the gain reached by the execution of each pair of query instances (or query types).

Based on the approaches to measure
query interactions, an intelligent scheduler for multiple-query execution
ordering, denoted ISO, has been implemented. ISO is interaction-aware query scheduler for online
workloads. Thus, given a set $Q=\{q_{1},q_{2}, ..., q_{n}\}$ of queries,
ISO is able to dynamically define the most efficient execution order
for the queries belonging to $Q$. 

%These approaches can give good reduction in workload response time. To illustrate it Figure \ref{fig:workload-example} shows a case in which the workload is benefited and hence that an strategy that reorder the query execution can be relevant. In this example, the approach with worst performance is IS with execution time of 24 minutes. However, this heuristic has a considerable reduction of 29\% compared with FIFO (34 minutes), i. e., there is a considerable gain in performance. The best response time is achieved by gain matrix strategy (13 minutes) represented by a decreasing of 62\%. This case can instigate to a big possibility in optimizing the response time of queries.

%\begin{figure}[ht]
%\centering
%\graphicspath{{figures/}}
%\includegraphics[width=.5\textwidth]{workload-example.png}
%\caption{Improvement example with approaches of this work}
%\label{fig:workload-example}
%\end{figure}

%To demonstrate the benefit of exploiting query interactions, we have developed a novel interaction-aware query scheduler for online workloads. We report an experimental evaluation of the proposed approaches using TPC-H workloads running on PostgreSQL. The evaluation shows that our approaches have potential to improve many database tuning algorithms.

%For example, consider that a query instance $q_{j_{1}}$ of the query type $Q_{j}$ runs and brings data or index pages into the memory that is then used by a query instance $q_{l_{2}}$ of the type $Q_{l}$. So, the cache can improve the hit ratio for $q_{l_{2}}$ making this query instance execute much faster if it runs after or concurrently with $q_{j_{1}}$, but it is important to note when $q_{j_{1}}$ and $q_{l_{2}}$ run concurrently they can interfere with each other on some hardware resources like CPU and memory and hence on their performance.

The remainder of this article is organized as follows. Section
\ref{sec:works} discusses related work. Section \ref{sec:approaches}
introduces the proposed approaches to model and measure query
interactions. Section \ref{sec:scheduling} presents the proposed query
scheduler.  Thereafter, Section \ref{sec:experiments} presents and
discusses the results of the executed experiments. Finally, Section
\ref{sec:conclusions} concludes the article.

\vspace{-0.00cm}
\section{Related Work}\label{sec:works}

There is little work discussing query interaction and efficient
query-execution order. In this sense, \cite{Gorman:05} describes a
scheduling algorithm based on a bidimentional array which stores in
each cell $c_{i, j}$ a rate for executing  query
instance $q_{i}$ before $q_{j}$. \cite{Ahmad:08,Ahmad:11} describe an experiment-driven modeling for batch scheduling. Also, the authors propose an online scheduling algorithm based on a metric called NRO (Normalized Runtime Overhead). All these approaches need a heavy preprocessing to be used and can be inappropriate when each query has a deadline.

Some works are intrusive and use the concurrent query execution scenario to get performance improvements. \cite{Roy:00} and \cite{Tan:95} are in this group. Each one makes changes in the DBMS query optimizer to explore some properties and reuse common data among queries that are stored in memory.

Other works (e. g. \cite{Niu:07} and \cite{Niu:09}) are based on query optimizer estimations to support workload management decisions, including scheduling ones. However, this cost does not help so much when queries have a deadline to fulfill. In fact, our solution is based on query plan, but it does not care about their estimations because this information is not good enough to indicate if a query can execute in an acceptable time.

\vspace{-0.00cm}
\section{Measuring and Modeling Query Interactions}\label{sec:approaches}

Nowadays, most databases are stored in hard disks. Data access rate in
hard disks is several magnitude orders lower than in main memory,
specially w.r.t. random accesses. 

To execute a query $q_{i}$,
the buffer manager may load data pages into the buffer pool, which are used
by another concurrently running query $q_{k}$. Such a scenario
characterizes  a query interaction between $q_{i}$ and $q_{k}$. Of
course, executing $q_{i}$ before $q_{k}$ (or vice-versa), $q_{k}$ can
profit from the fact that pages, necessary to process it, are already in
the buffer pool.  Based on this observation,  this article presents three approaches to model and measure query instance and query type interactions. In this section we will discuss these approaches in detail.

The proposed approaches uses the concept of  {\it interaction factor}, which is a number between 0 and 1. The interaction
factor quantifies the interaction between two query instances or between two query types. Values close to 1 indicate strong interaction and close to 0 weak interaction. 

%We assume that the query types that appear in the mixes are known a-priori. However, there are cases where a query workload is purely ad-hoc. In these cases, an extra step in DRR and GBA approaches is required to classify the ad-hoc queries into a fixed set of query types.

\vspace{-0.00cm}

\subsection{Table Relationships}\label{subsec:relationships}

The IS (Subsection \ref{subsec:intercalation}) and DRR (Subsection
\ref{subsec:dar}) approaches computes the interaction factor between
two queries by means of the notion of table relationship.  There are
two types of table relationships: {\it possible intersection} and {\it
  disjunction}.

Let $q_i$ and $q_j$ two query instances, $P_{q_{i}}$ and $P_{q_{j}}$ the query execution plans for $q_i$ and $q_j$ (generated by the DBMS’s query processor). Consider that $T_i$ is a set with all tables $t_i \in P_{q_{i}}$. Given a table $t_i$, such that $t_i \in P_{q_{i}}$, $O_{t_i}$ is the set of table operations on $t_i$ in $P_{q_{i}}$ (for example, {\it table scan}, {\it index scan} or {\it index seek}). Thus, $o_{t_i}$, where $o_{t_i} \in O_{t_i}$ is a table operation on $t_i$ in $P_{q_{i}}$. 

So, given two tables $t_i$ and $t_j$, the relationship between $t_i$ and $t_j$ is possible interaction if and only if: (i) $t_i = t_j$ and (ii) $\exists o_{t_{i}} \in O_{t_i}$ and $\exists o_{t_{j}} \in O_{t_j}$ such that one of the following conditions occur: (a) $o_{t_{i}}$ or $o_{t_{j}}$ is a {\it table scan} operation; (b) $o_{t_{i}}$ and $o_{t_{j}}$ are {\it index scan} using distinct columns, or; (c) $o_{t_{i}}$ and $o_{t_{j}}$ are {\it index scan} using the same columns and there are overlaps on index search keys. If one of these conditions occurs, $o_{t_{i}}$ and $o_{t_{j}}$ may access common data.

On the other hand, the table relationship between $t_i$ e $t_j$ is {\it disjunctive}, if: {\it(i)} $ t_i \neq t_j $, or; {\it (ii)} $t_i = t_j$ and none of the following conditions occurs: (a) $o_{t_{i}}$ or $o_{t_{j}}$ is a {\it table scan} operation; (b) $o_{t_{i}}$ and $o_{t_{j}}$ are {\it index scan} using distinct columns, and; (c) $o_{t_{i}}$ and $o_{t_{j}}$ are {\it index scan} using the same columns and there are overlaps on index search keys. If neither of these conditions occur, $o_{t_{i}}$ and $o_{t_{j}}$, do not access common data.


%For finding the table relationship between two query instances $q_{j}$ and $q_{k}$, it is necessary to analyze their query execution plans (denoted $P_{q_{j}}$ and $P_{q_{k}}$, respectively).  Thus, it is possible to identify each table $t_{k}$, $t_{k} \in P_{q_{k}}$ and $k>0$,  and the set $O_{k}$ of table operations on $t_{k}$ (table scan, index scan or index seek). 



%The table relationship between two query instances $q_{j}$ and $q_{k}$ is {\it possible intersection}, if  $\exists o_{k_{i}} \in O_{k}$ (i.e., table operations on $t_{k}$), $t_{k} \in P_{q_{k}}$, and  $\exists o_{j_{n}} \in O_{j}$ (i.e., table operations on $t_{j}$), $t_{j} \in P_{q_{j}}$, may access common data. Observe that, in this case, we have $j=k$. 

%On the other hand, the table relationship between two query instances $q_{j}$ and $q_{k}$ is {\it disjunctive}, if: {\it(i)} $j \neq k$, or; {\it (ii)} table operations on $t_{k}$, $t_{k} \in P_{q_{k}}$ and  $t_{j}$, $t_{j} \in P_{q_{j}}$, do not access common data.

%\begin{itemize}
%\item possible intersection: when table operations in $t_{1}$ and $t_{2}$ can access common data;
%\item disjunction: when table operations in $t_{1}$ and $t_{2}$ do not access common data.
%\end{itemize}

%If $t_{1} \neq t_{2}$, we have a disjunction. 

%For example, in the following scenarios, possible intersection occurs, considering $o_{k} \in O_{k}$ and $o_{j} \in O_{j}$: {\it (i)} $o_{k}$ or $o_{j}$ is a table scan, or; {\it (ii)} $o_{k}$ and $o_{j}$ are index scan using distinct columns, or; {\it (iii)}  $o_{k}$ and $o_{j}$ are index scan using the same columns and there are overlaps  on index search keys;


%An additional case occurs when $\forall o_{1} \in O_{1}$ and $\forall o_{2} \in O_{2}$, $o_{1}$ and $o_{2}$ are index scan operations using the same columns and there is no intersection at the index filters. In this case we have a disjunction.

%Let $Q_{1}$ and $Q_{2}$ be two queries and $t_{1}$ and $t_{2}$ be tables of them, respectively. To get the relation between $t_{1}$ and $t_{2}$ firstly is verified if $t_{1} \neq t_{2}$. In this case, there is disjunction relation. Otherwise, a more detailed analysis is done. In other words, when a table scan occurs in $t_{1}$ or $t_{2}$ or accesses by index use distinct attributes or there is intersection in the range of values of the same attributes, the relation is possible intersection. On the other hand, if the accesses in $t_{i}$ and $t_{j}$ are performed only by indexes of the same attribute and the range of values are disjunct we have a disjunction relation.

\vspace{-0.00cm}
\subsection{Intercalation Strategy (IS)} \label{subsec:intercalation}

The Intercalation Strategy is based only on the SQL statements and
query execution plans. No pre-processing is needed. Algorithm
\ref{alg:I} describes the steps of this approach to computes
interaction factor.

\begin{algorithm}\scriptsize{
\caption{Intercalation strategy}
\label{alg:I}
\SetKwData{QUm}{$q_{j_{1}}$} 
\SetKwData{I}{$i$} 
\SetKwData{QDois}{$q_{l_{2}}$} 
\SetKwData{J}{$j$} 
\SetKwData{V}{$R$} 
\SetKwData{SBD}{dbms} 
\SetKwData{EDi}{$SD_{i}$} 
\SetKwData{TUm}{$T_{q_{j_{1}}}$} 
\SetKwData{TDois}{$T_{q_{l_{2}}}$} 
\SetKwData{NomesTabelas}{tableNames} 
\SetKwData{TamanhoTotal}{totalSize} 
\SetKwData{Alfa}{$\alpha$} 
\SetKwData{ETi}{$t_{1}$} 
\SetKwData{ETj}{$t_{2}$} 
\SetKwData{Relacao}{tableRelationship} 
\SetKwData{TamanhoTabela}{tableSize} 
\SetKwData{Vi}{$R_{i}$} 
\SetKwData{Vj}{$R_{j}$} 
\SetKwData{Beta}{$\beta$} 
\SetKwData{Gama}{$\gamma$} 
\SetKwData{PesoAuxiliar}{auxWeight} 
\SetKwData{PUm}{$W_{1}$} 
\SetKwData{PDois}{$W_{2}$} 
\SetKwData{PTres}{$W_{3}$} 
\SetKwData{PQuatro}{$W_{4}$}

\SetKwFunction{ENulo}{isNull} 
\SetKwFunction{InterpretaConsulta}{parseQuery} 
\SetKwFunction{ObterTabelas}{getTables} 
\SetKwFunction{ObterNomesTabelas}{getTableNames} 
\SetKwFunction{ObterTamanhoTotal}{getTotalSize} 
\SetKwFunction{ObterRelacao}{getRelationship} 
\SetKwFunction{EPossivelIntersecao}{isPossibleIntersection} 
\SetKwFunction{ObterTamanho}{size} 
\SetKwFunction{ObterNome}{getTableName} 
\SetKwFunction{Max}{max} 
\SetKwFunction{ObterTempoEstimado}{getEstimatedTime} 
\SetKwFunction{TemEscaneamentoCompleto}{hasFullScan}

%\tcp{\Qe se refere à última consulta que foi submetida à execução,}
%\tcp{Supõe-se que \QDois executará imediatamente após \QUm e}
%\tcp{\SBD é um driver que se comunica com a base de dados}
\Input{\QUm, \QDois, \SBD}
\Output{interaction factor}

\Begin{
	\If {\ENulo{\QUm} \textbf{or} \ENulo{\QDois}} {\label{alg:I:0_1}
		\Return 0; \label{alg:I:0_2}
	} \label{alg:I:0_3}
%	\tcp{estrutura de dados com tabelas da consulta analisada e}
%	\tcp{tipos de busca sobre as tabelas desta consulta }
%	\tcp{com as comparações que interferem nos dados acessados}
	\TUm $\leftarrow$ \SBD.\InterpretaConsulta{\QUm}\;\label{alg:I:1}
	\TDois $\leftarrow$ \SBD.\InterpretaConsulta{\QDois}\;\label{alg:I:2}
%	\BlankLine
%	\tcp{considera as relações de interseção entre o par de consultas \QUm e \QDois}
	\TamanhoTotal $\leftarrow$ \ObterTamanhoTotal{\TUm, \TDois}\;\label{alg:I:3}
%	\BlankLine
	\Alfa $\leftarrow$ 0\;\label{alg:I:4}
	\ForEach{\ETi \textbf{in} \TUm} {\label{alg:I:5}
		\ForEach{\ETj \textbf{in} \TDois} {\label{alg:I:6}
			\Relacao $\leftarrow$ \ETi.\ObterRelacao{\ETj}\;\label{alg:I:7}
			\If {\EPossivelIntersecao{\Relacao}} {\label{alg:I:8}
                \uIf {\ETi.\TemEscaneamentoCompleto{} {\bf and} \ETj.\TemEscaneamentoCompleto{}} {\label{alg:I:9}
                    \PesoAuxiliar $\leftarrow$ \PUm\;\label{alg:I:10}
                } \uElseIf {\ETi.\TemEscaneamentoCompleto{} {\bf and not} \ETj.\TemEscaneamentoCompleto{}} {\label{alg:I:11}
                    \PesoAuxiliar $\leftarrow$ \PDois\;\label{alg:I:12}
                } \uElseIf {{\bf not} \ETi.\TemEscaneamentoCompleto{} {\bf and } \ETj.\TemEscaneamentoCompleto{}} {\label{alg:I:13}
                    \PesoAuxiliar $\leftarrow$ \PTres\;\label{alg:I:14}
                } \Else {\label{alg:I:15}
                    \PesoAuxiliar $\leftarrow$ \PQuatro\;\label{alg:I:16}
                }\label{alg:I:17}
				\Alfa $\leftarrow$ \Alfa + \PesoAuxiliar $\times$ $\frac{\ObterTamanho{\ETi}}{\TamanhoTotal}$\;\label{alg:I:19}
			}\label{alg:I:20}
		}\label{alg:I:21}
	}\label{alg:I:22}
%	\BlankLine
	\Return \Alfa\;\label{alg:I:23}
}}
\end{algorithm}

Algorithm \ref{alg:I} has as input the following parameters: two query instances
$q_{j_{1}}$ and $q_{l_{2}}$, where we assume that  $q_{j_{1}}$ starts
its execution before  $q_{l_{2}}$, and;  a  DBMS driver ($dbms$),
which is  responsible for accessing database catalog (metabase). The algorithm output is the interaction factor between  $q_{j_{1}}$ and $q_{l_{2}}$, denoted by $f_{q_{j_{1}},q_{l_{2}}}$. It's important to note that $f_{q_{j_{1}},q_{l_{2}}}$ can be different from $f_{q_{l_{2}},q_{j_{1}}}$.  According to the notation used in Subsection
\ref{subsec:relationships}, $T_{q_{j_{1}}}$ represents the set of tables belonging to the query execution plan $P_{q_{j_{1}}}$ and $T_{q_{l_{2}}}$ is the set of tables belonging to $P_{q_{l_{2}}}$. The variable $size(t_{k})$ represents the size of the table $t_{k}$ (in Kilobytes), $totalSize$ stores the sum of $size(t_{k})$ for each $t_{1} \in T_{q_{j_{1}}}$ and $t_{2} \in T_{q_{l_{2}}}$.

The $tableRelationship$ variable represents table relationship (possible interaction or disjunction) between two tables. From line \ref{alg:I:4} to \ref{alg:I:22} the $\alpha$ variable is calculated. Finally, in line \ref{alg:I:23}, the interaction factor ($\alpha$) is returned. During the tests $W_{1}$ and $W_{4}$ were set to 0.5, $W_{2}$ to 1 and $W_{3}$ to 0.25. These values were chosen to benefit occurrences of table scan in $t_{1}$ and index seek in $t_{2}$.

The key idea of the IS approach is to put closer queries with tables
in common in the query execution schedule. The access method is
important because the chance of improving the performance by executing
a query $q$ with an index seek operation on a table $t$
after another query $q'$ which accesses the same table $t$ by means of
a table scan operation is higher than executing  $q'$ before $q$. 

%% EXAMPLE OF HOW TO WRITE A TABLE IN LATEX
%% DO CHECK http://en.wikibooks.org/wiki/LaTeX/Tables FOR MORE TIPS & TRICKS ON TABLES
%\begin{table}[tb]% TABLES SHOULD BE AT THE TOP [t] OR BOTTOM [b} OF PAGES
%	\centering
%	\caption{The use of weights in intercalation approach} % ALWAYS INCLUDE CAPTIONS IN YOUR TABLES
%	\label{tab:weights} % USE THE CONTENT WITHIN label FOR REFERENCING IT (USE \ref WITHIN THE TEXT)
%
%	\sffamily % CHANGES THE FONT WITHIN THE TABLE TO sans serif
%	\begin{tabular}{|c|c|c|}
%		\hline
%		\multirow{2}{*}{Weight} & \multicolumn{2}{|c|}{table scan} 	\\ \cline{2-3}
%								& $e_{T_{1}}$ 	& $e_{T_{1}}$ 		\\ \hline
%		$W_{1}$ 				& Yes 			& Yes 				\\ \hline
%		$W_{2}$ 				& Yes 			& No  				\\ \hline
%		$W_{3}$ 				& No  			& Yes 				\\ \hline
%		$W_{4}$ 				& No  			& No  				\\ \hline
%	\end{tabular}
%	\rmfamily % RESTORES TO TIMES, SO THAT CAPTION IS WRITTEN PROPERLY
%\end{table}
\vspace{-0.00cm}
\subsection{Data Retrieving Rate (DRR)} \label{subsec:dar}

The implementation of the DRR approach relies on the following
parameters: SQL statements, query execution plans and  data retrieving
(access) rate for each query type. For that reason, a preprocessing
step is required. This preprocessing consists of running, for each
query type $Q_{j}$, a set $S_{j}$ of $n$ query instances $m$ times. % with free memory after each query instance execution. 
The average of the data retrieving rate for the instances in $S_{j}$
with $m$ running iterations is the DRR for the query type $Q_{j}$. %In this article we have assumed $n=1$, $n=5$ and $m=5$.
In the experiments, we have fixed $m =5$ and evaluated two values ​​for $n$: $n=1$ and $n=5$.

Actually, DRR represents the amount of data transferred from the disk
to the database buffer pool (main memory) per time unit (KB/s in our
tests). Thus, it is possible to infer that if a query type has a low
DRR its query instances will access data in a low rate as well. By
doing this, the following heuristic is applied: query instances with
greater DRRs should be executed before query instances with low DRR.

\begin{algorithm}\scriptsize{
\caption{DRR approach}
\label{alg:QT}
\SetKwData{QUm}{$q_{j_{1}}$} 
\SetKwData{QDois}{$q_{l_{2}}$}
\SetKwData{V}{$R$} 
\SetKwData{TipoUm}{$Q_{j}$} 
\SetKwData{TipoDois}{$Q_{l}$} 
\SetKwData{SBD}{dbms} 
\SetKwData{TUm}{$T_{q_{j_{1}}}$} 
\SetKwData{TDois}{$T_{q_{l_{2}}}$} 
\SetKwData{NomesTabelas}{tableNames} 
\SetKwData{TamanhoTotal}{totalSize} 
\SetKwData{Alfa}{$\alpha$} 
\SetKwData{ETi}{$t_{1}$} 
\SetKwData{ETj}{$t_{2}$} 
\SetKwData{Relacao}{tableRelationship} 
\SetKwData{TamanhoTabela}{size($t_{1}$)} 
\SetKwData{Vi}{$R_{1}$} 
\SetKwData{Vj}{$R_{t_{2}}$} 
\SetKwData{Beta}{$\beta$} 
\SetKwData{Gama}{$\gamma$} 
\SetKwData{PesoAuxiliar}{auxWeight} 
\SetKwData{PUm}{$W_{1}$} 
\SetKwData{PDois}{$W_{2}$}

\SetKwFunction{ENulo}{isNull} 
\SetKwFunction{InterpretaConsulta}{parseQuery} 
\SetKwFunction{ObterTabelas}{getTables} 
\SetKwFunction{ObterNomesTabelas}{getTableNames} 
\SetKwFunction{ObterTamanhoTotal}{getTotalSize} 
\SetKwFunction{ObterRelacao}{getRelationship} 
\SetKwFunction{EPossivelIntersecao}{isPossibleIntersection} 
\SetKwFunction{ObterTamanho}{size} 
\SetKwFunction{ObterNome}{getTableName} 
\SetKwFunction{Max}{max} 
\SetKwFunction{ObterTempoEstimado}{getEstimatedTime} 
\SetKwFunction{ObterTRDNormalizado}{getNormalizedDRR}
\SetKwFunction{TemEscaneamentoCompleto}{hasFullScan}

%\tcp{\Qe se refere à última consulta que foi submetida à execução,}
%\tcp{Supõe-se que \Qj executará imediatamente após \Qi,}
%\tcp{\V é uma matriz unidimensional com a vazão das consultas,}
%\tcp{\Memoria é a quantidade de memória que pode ser utilizada pela consulta em execução e}
%\tcp{\SBD é um driver que se comunica com a base de dados}
\Input{\QUm, \QDois, \V, \TipoUm, \TipoDois, \SBD}
\Output{interaction factor}

\Begin{
	\If {\ENulo{\QUm} \textbf{or} \ENulo{\QDois}} {\label{alg:QT:0_1}
			\Return 0\; \label{alg:QT:0_2}
		} \label{alg:QT:0_3}
%	\tcp{estrutura de dados com tabelas da consulta analisada e}
%	\tcp{tipos de busca sobre as tabelas desta consulta }
%	\tcp{com as comparações que interferem nos dados acessados}
	\TUm $\leftarrow$ \SBD.\InterpretaConsulta{\QUm}\;\label{alg:QT:1}
	\TDois $\leftarrow$ \SBD.\InterpretaConsulta{\QDois}\;\label{alg:QT:2}
%	\BlankLine
%	\tcp{considera as relações de interseção entre o par de consultas \QUm e \QDois}
	\TamanhoTotal $\leftarrow$ \ObterTamanhoTotal{\TUm, \TDois}\;\label{alg:QT:3}
%	\BlankLine
	\Alfa $\leftarrow$ 0\;\label{alg:QT:4}
	\ForEach{\ETi \textbf{in} \TUm} {\label{alg:QT:5}
		\ForEach{\ETj \textbf{in} \TDois} {\label{alg:QT:6}
			\Relacao $\leftarrow$ \ETi.\ObterRelacao{\ETj}\;\label{alg:QT:7}
			\If {\EPossivelIntersecao{\Relacao}} {\label{alg:QT:8}
				\uIf {\ETi.\TemEscaneamentoCompleto{}} {\label{alg:QT:9}
				  \PesoAuxiliar $\leftarrow$ \PUm $\times$ \ObterTRDNormalizado{\TipoDois}\;\label{alg:QT:10}
				} \Else {\label{alg:QT:11}
				  \PesoAuxiliar $\leftarrow$ \PDois $\times$ \ObterTRDNormalizado{\TipoDois}\;\label{alg:QT:12}
				}\label{alg:QT:13}
                \TamanhoTabela $\leftarrow$ \SBD.\ObterTamanho{\ETi.\ObterNome{}}\;\label{alg:QT:14}
				\Alfa $\leftarrow$ \Alfa + \PesoAuxiliar $\times$ $\frac{\ObterTamanho{\ETi}}{\TamanhoTotal}$\;\label{alg:QT:15}
			}\label{alg:QT:16}
		}\label{alg:QT:17}
	}\label{alg:QT:18}
	\Return \Alfa\;\label{alg:QT:19}
}}
\end{algorithm}

Algorithm \ref{alg:QT} describes the steps implemented by the DRR
approach. Algorithm \ref{alg:QT} has as input parameters: two query
instances $q_{j_{1}}$ and $q_{l_{2}}$ ($q_{j_{1}}$ starts its
execution before $q_{l_{2}}$); the query types $Q_{j}$ and $Q_{l}$ of
$q_{j_{1}}$ and $q_{l_{2}}$, respectively;  an array $R$ with the
computed DRR for each query type; and a DBMS driver ($dbms$)
responsible for accessing database catalog (metabase). The algorithm
output is the interaction factor between $q_{j_{1}}$ and $q_{l_{2}}$,
denoted by $f_{q_{j_{1}},q_{l_{2}}}$. In Algorithm \ref{alg:QT},
$max(R)$ represents highest value in the array $R$ and $R_{Q_{k}}$ is
the DRR for $Q_{k}$. Lines \ref{alg:QT:0_1} to \ref{alg:QT:3} do the
same as lines \ref{alg:I:0_1} to \ref{alg:I:3} from Algorithm
\ref{alg:I}. From line \ref{alg:QT:4} to \ref{alg:QT:18}, the
value of the interaction factor $\alpha$ is calculated. This process
starts with the initialization of this variable in line
\ref{alg:QT:4}. Next, it is verified the relationship between each
pair of tables computed in the nested loops, which is depicted from
line \ref{alg:QT:5} to \ref{alg:QT:18}. Whenever possible intersection
table relationships are  found, the value of $\alpha$ is modified
based on the set  $O_{1}$ (see Subsection \ref{subsec:relationships})
and the constants $W_{1}$, $W_{2}$, DRR of $Q_{l}$ and the analyzed table weight (from lines \ref{alg:QT:8} to \ref{alg:QT:16}). 

It is important to observe that the DDR approach has the same table
relationship concept as IS. Moreover, the DDR and IS approaches are
based on the heuristic in which queries accessing tables by table
scans load more data to the buffer pool, allowing thus more data page
reuse.  For that reason, during the experiments, $W_{1}$ was set to 1 and
$W_{2}$ to 0.5. Nevertheless, in the DDR approach, the value of the
interaction factor $\alpha$ should incorporate the data retrieving
rate. This is because DDR approach implements the following
heuristic:  query instances with greater DRRs should be executed before query instances with low
DDRs. The DRR parameter is used in its normalized form, computed
by $getNormalizedDRR(Q_{l})$, which basically  consists of $\frac{R_{Q_{l}}}{max(R)}$. 
%\section{Matriz Bidimensional com Partições (MBP)}
\vspace{-0.00cm}
\subsection{Greedy with bidimentional array (GBA)}\label{subsec:gba}

The GBA approach is based on a bidimentional array obtained by a preprocessing step, which is described in Algorithm \ref{alg:preGBA}. Each line $j$ of the bidimentional array built by GBA represents a query type $Q_{j}$ and each column $l$ represents a query type $Q_{l}$. Hence, a cell $c_{j,l}$ stores the gain of running a query instance of query type $Q_{l}$ after an instance of query type $Q_{j}$. This gain, denoted by $gain(Q_{j}, Q_{l})$, is calculated from the following formula: \mbox{$rt(Q_{j}, Q_{l})$ - $rt(Q_{l})$}, where $rt(Q_{j}, Q_{l})$ is the response time for an instance of $Q_{l}$ that starts its execution immediately after finishing an instance of $Q_{j}$ and $rt(Q_{l})$ is the response time for an instance of $Q_{l}$ running with free memory.

\begin{algorithm}
\scriptsize{
\caption{GBA preprocessing}
\label{alg:preGBA}
\SetKwData{D}{$D$} 
\SetKwData{QtdTipos}{typeQty} 
\SetKwData{QtdInstancias}{instanceQty} 
\SetKwData{Iteracoes}{iterations} 
\SetKwData{DBMS}{dbms} 
\SetKwData{G}{$G$}
\SetKwData{TUm}{$T$}
\SetKwData{TDois}{$T_{l}$} 
\SetKwData{TempoSQLUm}{time$_{j_{1}}$} 
\SetKwData{IUm}{$Q_{j}$} 
\SetKwData{IDois}{$Q_{l}$} 
\SetKwData{TempoSQLDois}{time$_{l_{2}}$} 
\SetKwData{JUm}{$i_{j_{1}}$} 
\SetKwData{SQLUm}{$q_{j}$} 
\SetKwData{JDois}{$i_{l}$} 
\SetKwData{SQLDois}{$q_{l}$} 
\SetKwData{K}{k}

\SetKwFunction{CriarMatriz}{createArray} 
\SetKwFunction{LiberarMemoria}{freeMemory} 
\SetKwData{ExecutarConsulta}{runQuery} 
\SetKwData{Normalizar}{normalize}

\Input{\D, \QtdTipos, \QtdInstancias, \Iteracoes, \DBMS}
\Output{\G}

\Begin{
	\TUm $\leftarrow$ \CriarMatriz{\QtdTipos}\;\label{alg:preGBA:1}
	\G $\leftarrow$ \CriarMatriz{\QtdTipos, \QtdInstancias}\;\label{alg:preGBA:1_5}
	\For {$\IUm \leftarrow 1$ \KwTo \QtdTipos} {\label{alg:preGBA:2}
		\TempoSQLUm $\leftarrow$ 0\;\label{alg:preGBA:3}
		\For {$\IDois \leftarrow 1$ \KwTo \QtdTipos} {\label{alg:preGBA:4}
			\TempoSQLDois $\leftarrow$ 0\;\label{alg:preGBA:5}
			\For {$\JUm \leftarrow 1$ \KwTo \QtdInstancias} {\label{alg:preGBA:6}
				\SQLUm $\leftarrow$ $\D_{\IUm, \JUm}$\;\label{alg:preGBA:7}
				\For {$\JDois \leftarrow 1$ \KwTo \QtdInstancias} {\label{alg:preGBA:8}
					\SQLDois $\leftarrow$ $\D_{\IDois, \JDois}$\;\label{alg:preGBA:9}
					\For {$\K \leftarrow 1$ \KwTo \Iteracoes} {\label{alg:preGBA:10}
						\LiberarMemoria{}\;\label{alg:preGBA:11}
						\TempoSQLUm $\leftarrow$ \TempoSQLUm $+$ \DBMS.\ExecutarConsulta{\SQLUm}\;\label{alg:preGBA:12}
						\TempoSQLDois $\leftarrow$ \TempoSQLDois $+$ \DBMS.\ExecutarConsulta{\SQLDois}\;\label{alg:preGBA:13}
					}\label{alg:preGBA:14}
				}\label{alg:preGBA:15}
			}\label{alg:preGBA:16}
			$\G_{\IUm, \IDois}$ $\leftarrow$ $\frac{\TempoSQLDois}{\QtdInstancias^{2} \times\mbox{ }\Iteracoes}$\;\label{alg:preGBA:17}
		}\label{alg:preGBA:18}
		$\TUm_{\IUm}$ $\leftarrow$ $\frac{\TempoSQLUm}{\QtdTipos\mbox{ }\times\mbox{ }\QtdInstancias^{2} \times\mbox{ } \Iteracoes}$\;\label{alg:preGBA:19}
	}\label{alg:preGBA:20}
	\For {$\IUm \leftarrow 1$ \KwTo \QtdTipos} {\label{alg:preGBA:21}
		\For {$\IDois \leftarrow 1$ \KwTo \QtdTipos} {\label{alg:preGBA:22}
			$\G_{\IUm, \IDois}$ $\leftarrow$ $\TUm_{\IUm} - \G_{\IUm, \IDois}$\;\label{alg:preGBA:23}
		}\label{alg:preGBA:24}
	}\label{alg:preGBA:25}
	%\G $\leftarrow$ \Normalizar{\G}\;\label{alg:preGBA:26}
	\Return \G\;\label{alg:preGBA:27}
}}
\end{algorithm}


The input parameter for Algorithm \ref{alg:preGBA} are: a set $D$ of query instances used to calculate the $gain(Q_{j},Q_{l})$; the number of query types (parameter $typeQty$); the variable $instanceQty$ containing  the number of query instances for each query type; the total number of iterations (parameter $iterations$) for each pair of query instances to be run; and a DBMS driver ($dbms$) responsible for accessing database catalog (metabase). 

The first steps of Algorithm \ref{alg:preGBA} are responsible creating and initializing the arrays $T$ and $G$. In order to illustrate how  Algorithm \ref{alg:preGBA} works, consider that $Q_{j}$ and $Q_{l}$ are query types currently being analyzed and that query instances from $Q_{j}$ are executed before query instances of $Q_{l}$. Between lines \ref{alg:preGBA:3} and \ref{alg:preGBA:19}, the execution time for $Q_{j}$ is calculated. This is obtained by computing the average of response time of all $Q_{j}$ query instance execution.  From line \ref{alg:preGBA:5} to line \ref{alg:preGBA:17} it is computed the execution time for $Q_{l}$ when running after query instances of $Q_{j}$. 
Thereafter, the gain matrix is built (from lines \ref{alg:preGBA:21} to \ref{alg:preGBA:25}). %In line \ref{alg:preGBA:26}, the gain matrix is normalized. Finally, the normalized gain array $G$ is returned (line \ref{alg:preGBA:27}). 
In line \ref{alg:preGBA:27}, the gain matrix $G$  is returned.

\begin{algorithm}\scriptsize{
\caption{GBA approach}
\label{alg:GBA}
\SetKwData{I}{$Q_{j}$} 
\SetKwData{J}{$Q_{l}$} 
\SetKwData{G}{$G$}
\SetKwData{Alfa}{$\alpha$}

\SetKwFunction{ENulo}{isNull} 
\SetKwFunction{Max}{max}

%\tcp{\Qe se refere à última consulta que foi submetida à execução,}
%\tcp{Supõe-se que uma consulta do tipo \J executará imediatamente após uma do tipo \I,}
%\tcp{\G é uma matriz bidimensional de ganhos}
\Input{\I, \J, \G}
\Output{interaction factor}

\Begin{
	\Alfa $\leftarrow$ 0\;\label{alg:GBA:1}
	\If{\textbf{not} \ENulo{\I} \textbf{and not} \ENulo{\J}} {\label{alg:GBA:2}
		\Alfa $\leftarrow \frac{\G_{Q_j,Q_l}}{max(G)}$\;\label{alg:GBA:3}
	}\label{alg:GBA:4}
	\Return \Alfa\;\label{alg:GBA:5}
}}
\end{algorithm}

After the bidimentional array GBA is built, Algorithm \ref{alg:GBA} is triggered. According to the steps of Algorithm \ref{alg:GBA}, in the same way as previous approaches, $\alpha$ is initialized with value 0, as it is showed in line \ref{alg:GBA:1}. Next, in line \ref{alg:GBA:2}, it is verified if $Q_{j}$ and $Q_{l}$ are defined types (not null). In this case, in line \ref{alg:GBA:3}, the performance gain is read in the cell $G_{Q_{j}, Q_{l}}$ and $\alpha$ (the interaction factor) receives $\frac{G_{Q_j,Q_l}}{max(G)}$, where $max(G)$ is the maximum value stored in $G$, $Q_j$ is a line of $G$ and $Q_l$ is a column of $G$. So, the value of the interaction factor is normalized ($[0,1]$). Finally, the interaction factor is returned in line \ref{alg:GBA:5}.

\vspace{-0.00cm}
\section{ISO: An Interaction-aware Query Scheduler}\label{sec:scheduling}

\begin{algorithm} \scriptsize{
\caption{Interaction-aware query scheduling}
\label{alg:S1}
\SetKwData{F}{$S$} 
\SetKwData{Fi}{$S_{i}$} 
\SetKwData{QNova}{$q_{new}$} 
\SetKwData{UltimaConsulta}{$q_{last}$} 
\SetKwData{SBD}{dbms} 
\SetKwData{MelhorPosicao}{bestPosition} 
\SetKwData{ConsultaPredecessora}{previousQuery} 
\SetKwData{MelhorDeltaFator}{$\Delta_{factor_{max}}$} 
\SetKwData{DeltaFator}{$\Delta_{factor}$} 
\SetKwData{ConsultaSucessora}{nextQuery} 
\SetKwData{I}{$i$}

\SetKwFunction{EstaVazia}{isEmpty} 
\SetKwFunction{Inserir}{add} 
\SetKwFunction{ObterTamanho}{getLength} 
\SetKwFunction{ObterFator}{getFactor}

\Input{\F, \QNova, \UltimaConsulta, \SBD}

\Begin{
	\MelhorPosicao $\leftarrow$ 1\;\label{alg:S1:4}
	\MelhorDeltaFator $\leftarrow$ -1\;\label{alg:S1:5}
	\ConsultaPredecessora $\leftarrow$ \UltimaConsulta\;\label{alg:S1:6}
	\For{\I $\leftarrow 1$ \KwTo \F.\ObterTamanho{}} {\label{alg:S1:7}
		\ConsultaSucessora $\leftarrow$ \Fi\;\label{alg:S1:8}
		\DeltaFator $\leftarrow$ \ObterFator{\ConsultaPredecessora, \QNova, \SBD} \\\Indp\Indp\Indp\Indp\Indp+ \ObterFator{\QNova, \ConsultaSucessora, \SBD} \\- \ObterFator{\ConsultaPredecessora, \ConsultaSucessora, \SBD}\;\label{alg:S1:9}
		\Indm\Indm\Indm\Indm\Indm\If {\DeltaFator $\geq$ \MelhorDeltaFator} {\label{alg:S1:10}
			\MelhorPosicao $\leftarrow$ \I\;\label{alg:S1:11}
			\MelhorDeltaFator $\leftarrow$ \DeltaFator\;\label{alg:S1:12}
		}\label{alg:S1:13}
		\ConsultaPredecessora $\leftarrow$ \ConsultaSucessora\;\label{alg:S1:14}
	}\label{alg:S1:15}
	\DeltaFator $\leftarrow$ \ObterFator{\ConsultaPredecessora, \QNova, \SBD}\;\label{alg:S1:16}
	\If {\DeltaFator $\geq$ \MelhorDeltaFator} {\label{alg:S1:17}
		\MelhorPosicao $\leftarrow$ \F.\ObterTamanho{} + 1\;\label{alg:S1:18}
	}\label{alg:S1:19}
	\F.\Inserir{\MelhorPosicao, \QNova}\;\label{alg:S1:20}
}}
\end{algorithm}

% COLOCAR UMA FIGURA DE ESCALONAMENTO

%Take into account scheduling problem, a global approach, that chooses the query orders with less workload response time, is impracticable because it would request the knowledge about all possible cases. If the performance verification of a query execution order is $O(n)$ then we have $O(n \times n!)$ complexity, a very high one. Also, it's infeasible get accuracy about the data put in memory before a query begins to execute because it depends on the operating system and the data the DBMS will access. Thus, this decision problem can be solved with heuristics rather than optimal algorithms and because of it, this work uses heuristics as approaches, that are based on query interaction because the possibility of reusing common data.

\begin{figure*}[ht]
\centering
\graphicspath{{figures/}}
\subfloat[Preprocessing overhead]{
	\label{fig:preprocessing}
	\includegraphics[width=.35\textwidth]{preprocessing.pdf}
}\qquad
\subfloat[Scheduling overhead]{
	\label{fig:scheduling}
	\includegraphics[width=.35\textwidth]{scheduling.pdf}
}\\
\subfloat[Effectiveness]{
	\label{fig:effectiveness}
	\includegraphics[width=.35\textwidth]{effectiveness.pdf}
}\qquad
\subfloat[Efficiency]{
	\label{fig:gain}
	\includegraphics[width=.35\textwidth]{gain.pdf}
}
\caption{Comparative analysis between IS, DRR, GBA and FIFO with one instance per query type}
%\label{3figs}
\end{figure*}

Based on the proposed approaches to model and measure query interactions
(IS, DRR and GBA), we have developed a interaction-aware query
scheduler for online (and batch) workloads, denoted ISO. ISO uses the
interaction factor to define the query execution order. The scheduler
goal is to optimize workload query response time by dynamically choosing, for each
query instance, the position in the scheduling queue which provides the highest interaction factor gain. 

The steps
implemented by ISO are showed in Algorithm \ref{alg:S1}. 
%The online scheduling algorithm schedules a new query whenever a running query finishes. While making each scheduling decision, the online algorithm has to work with a limited lookahead, namely, the queries in the arrival queue. No assumptions are made about the future workload. In particular, no query is held up by our scheduling algorithm with the hope that other queries arriving in future could have positive interactions with this query. Thus, the challenge is to get the best possible global performance while being limited to local decisions under partial information.
The Algorithm \ref{alg:S1} requires three input parameters: the
scheduling queue $S$; the query instance to be scheduled $q_{new}$;
the last query instance $q_{last}$, which left the queue $S$, and; the
database driver $dbms$. The first steps executed by Algorithm
\ref{alg:S1} consist of the initialization of the following variables
(lines from \ref{alg:S1:4} to \ref{alg:S1:6}): $bestPosition$, which
represents the position for $q_{new}$ in $S$; $\Delta_{factor_{max}}$,
containing  the greatest interaction gain, and; $previousQuery$, which
stores the position in $S$ of the previous query if $q_{new}$ has to
be added to  current position in $S$. In line \ref{alg:S1:8}, variable
$nextQuery$ is set to $previousQuery$. % with the difference that it  refers to the instance with the lowest index in $S$ that would be postponed in case of $q_{new}$ being added in the current index of $S$.
 Between lines \ref{alg:S1:7} and \ref{alg:S1:19}, $q_{new}$ is tested in each position of $S$. The query instance $q_{new}$ will occupy  the position in $S$ which provides the greatest global gain obtained by the formula depicted in line \ref{alg:S1:10}. Finally, in line \ref{alg:S1:20}, $q_{new}$ is inserted in the best estimated position of the scheduling queue.

\begin{figure*}[ht]
\centering
\graphicspath{{figures/}}
\subfloat[Preprocessing overhead]{
	\label{fig:qi-preprocessing}
	\includegraphics[width=.35\textwidth]{preprocessing.pdf}
}\qquad
\subfloat[Scheduling overhead]{
	\label{fig:qi-scheduling}
	\includegraphics[width=.35\textwidth]{scheduling.pdf}
}\\
\subfloat[Effectiveness]{
	\label{fig:qi-effectiveness}
	\includegraphics[width=.35\textwidth]{qi-effectiveness.pdf}
}\qquad
\subfloat[Efficiency]{
	\label{fig:qi-gain}
	\includegraphics[width=.35\textwidth]{qi-gain.pdf}
}
\caption{Comparative analysis between IS, DRR, GBA and FIFO with five instances per query type}
%\label{3figs}
\end{figure*}

\vspace{-0.00cm}
\section{Evaluation}\label{sec:experiments}

In order to evaluate the proposed three approaches to model and
measure query interactions and ISO scheduler, we have chosen a
scenario in which  queries are  executed in a sequential way. The
choice for such a scenario was motivated by the discussion about the need of predictability in the current
paradigm of optimization problem \cite{Florescu:09}. The idea is to
ensure that the queries are executed in an acceptable time, but not as
quick as possible. According to this approach, optimizing for the 99 percentile is more important than for the average. Thus, for instance, in the case that each query has its deadline, a solution that is optimized by 99 percentile is more appropriate. One example of this is showed in \cite{Chi:11}, that describes a solution based on agreements called SLAs (Service Level Agreements) with a specific metric: query response time. In this case, each query has to be run in a defined period of time to generate profit to the service provider, otherwise penalties can be applied.

When each query has a maximum time to be run, the use of a concurrent solution can be an inefficient way to schedule queries because of the complexity in predicting their response times if compared with sequential approaches. Many factors such as operating system scheduling algorithm and resource utilization impact of each query during the execution interfere in concurrent solution effectiveness. In fact, they can decrease the workload response time, but it is harder than in sequential solutions to control the query deadline fulfillment or to guarantee the profit in an SLA environment that uses query response time as metric, for example. Therefore, a sequential solution shows to be more feasible in some situations than a concurrent one.

\vspace{-0.00cm}
\subsection{Experimental Setup}

A 2 GHz Intel Core 2 Duo machine with 3 GB of RAM and 500 GB of HD,
using Ubuntu 11.10 of 64 bits as operating system, has been used to
execute the experiments. The tests were run implementing the TPC-H
benchmark with scale factor of 2 GB, using DBGEN/DBT-3 project, in
PostgreSQL 9.1.3 database system.  

The experiments have been conducted by using two different workloads, based
on the number of queries to be scheduled. In the first workload, one
query instance has been created for each TPC-H query type, totaling 22
queries. These instances were generated setting different values
for the template parameters, using QGEN/DBT-3. Thereafter, ten different orderings have been randomly yielded, each of which with 22 query instances. For this workload, the DRR vector, used by DRR approach, was created using $n=1$. In the second
workload, five query instances have been created for each TPC-H query type, totaling 110 queries. For this second workload, the DRR vector, used by DRR approach, was created using $n=5$. Furthermore, twenty different ordering have been
randomly produced. It is important to note that the different
orderings simulate the orders in which the queries are arriving to be
executed. For each defined ordering, a FIFO strategy is used to send
queries to ISO.

%TPC-H workload composed of one instance of each query type with ten random different arrival orders

%For each TPC-H template (query type),  115 query instances have been created. %These instances was generated setting different values (choosed randomly) for the template parameters, using QGEN/DBT-3. During the tests, query instances were used for approach preprocessing or test execution. All workload execution had random arrival orders. 

\vspace{-0.00cm}
\subsection{Test Results}

In this section, we present the results of the experiments we carried out. For that, we used four metrics: preprocessing-step
execution time; execution time for computing the query-execution
schedule; effectiveness and
efficiency.  
Since the DRR and GBA approaches require a pre-processing step, we
have used preprocessing-step
execution time metric. Figure \ref{fig:preprocessing} depicts the
results regarding that metric for the first workload (22 query instances and
10 random orderings). In turn, Figure \ref{fig:qi-preprocessing}
brings the results for the second workload (110 query and 20 random
orderings).  The second metric has the functionality to specify how
much time each approach takes to define the query-execution schedule.
Figure \ref{fig:scheduling} presents the results for the first workload
and Figure \ref{fig:qi-scheduling} for the second workload.

The effectiveness metric has been used to compare how many times each
scheduling approach has presented a better result than FIFO
approach (the queries are executed according to the random
ordering), which was used as baseline. We have considered ``Draw''  when the absolute difference
between execution times is less or equal than one minute (about 3
seconds of margin of error for each query instance).  Figure
\ref{fig:effectiveness}  illustrates the effectiveness of the three
proposed approaches for the first workload.  IS and DRR presented
better performance in 90\% of cases, and GBA was better than FIFO in
all cases. Regarding
effectiveness for the second workload (Figure
\ref{fig:qi-effectiveness}), only IS approach was not better than FIFO.


Efficiency has been applied to measure the total time consumed to
execute queries by using the schedules produced by the three
approaches and by a FIFO schedule. As Figure \ref{fig:gain} (results
for the first workload) 
illustrates, IS was executed in 3.7 hours, saving 1 hour w.r.t. the
execution time for the FIFO approach (22\% of
reduction). DRR had a better response time, since the schedule
produced by DRR has consumed 3.5 hours to be executed (25\% of
reduction). Nevertheless, the most efficient strategy was GBA with
reduction of 40\%, saving 1.9 hours and hence being the only solution
with execution time less
than 3 hours. 
%It is important to note that the completion time of a workload W was defined as the time elapsed from the beginning execution of the first query till all queries in W have finished their executions.

%In the previous scenario GBA had an excellent result, but in a more realistic environment, where instances for preprocessing are different from ones for running, the results can be different. To illustrate it, we created a pool of 105 query instances per query type, used 5 for preprocessing and 100 for running different workloads composed of 5 query instances per query type, resulting in 20 different workloads, with a random arrival order for each one.

Figure \ref{fig:qi-gain} brings the results of efficiency when the
second workload (110 query and 20 random
orderings)  was executed. IS was executed in 33.6 hours, saving 9.9 hours  w.r.t. the
execution time for the FIFO approach (reduction of 23\% ). DRR had the
best response time, during 28.8 hours (reduction of 33\%). However GBA was also good with reduction of 33\%, saving 14.7 hours.

\begin{figure}[ht]
\centering
\graphicspath{{figures/}}
\includegraphics[width=.35\textwidth]{qi-query-execution.pdf}
\caption{Query type performance evaluation}
\label{fig:qi-queries}
\end{figure}

The results presented in Figure \ref{fig:qi-queries} highlight the
benefits of taking into account query interaction. For that
experiment, we have picked up the execution time for seven TPC-H
queries with highest execution time when execute in schedules produced
by three
approaches (IS, DRR, GBA) and FIFO. Observe that for
each of those queries, the execution time is less than when they are
executed in the FIFO approach. Recall that in FIFO query interaction is not
considered. 

\vspace{-0.0cm}
\section{Conclusion and Future Work}\label{sec:conclusions}

In this article we propose three new approaches to model and measure query instance and query type interactions. Our approaches require no prior assumptions about the internal aspects of the database system or the reason of query interactions, making it non intrusive, namely, portable across systems. To demonstrate the profit of exploiting query interactions, we have developed a novel interaction-aware query scheduler for online workloads. The test results show that significant speed-ups are achieved. Besides, the evaluation shows that our approaches have potential to improve many database tuning algorithms. It may be interesting to incorporate the proposed approaches into other database system components such as query optimizers, physical design advisors and buffer manager, making them query interaction awareness. These possibilities represent interesting directions for future researches.

%Understanding query interactions can be used to improve the solutions to many administration and performance tuning problems in database systems. 

%After all analysis done in this work, it is possible to conclude that query interaction is a powerful property. Approaches that are based on this concept can offer relevant improvements in query response times. For illustrating it, the three algorithms showed in these article have good results. However, it is important to notice that all of them have pros and cons, e. g., whereas one has the best response time gain another has no preprocessing.

%To improve the researches in sequential scheduling based on interactiveness it may be possible to understand deeply other properties related to it that can give good results, too. For example, the order of table utilization can help to know if the possibility of a good interaction is high. The predictability about the quantity of data accessed in a table can give informations about possible good interactions too because if a query has a high data retrieving rate, for instance, but few data is retrieved, the gain obtained can be very poor.

%Another context beyond the local environment is data management in cloud computing. Nowadays it has a big space to new researches and these algorithms can impact in a positive way the provider profit. Then a possible work to do is adapt at least one of the showed approaches to support some data management decisions in cloud, such as scheduling and dispatching that are problems discussed in \cite{Chi:11}, using query response time as SLA metric. In this case, due to predictability requirement by query a sequential solution is more appropriate than a concurrent one.
	
% INCLUDE BIBLIOGRAPHY WHICH MUST FOLLOW jidm.bst TEMPLATE
\bibliographystyle{jidm}
\bibliography{jidmb}
% For information on how to write bibliography entries, 
% see file jidmb.bib

\begin{received}
\end{received}

\end{document}
