The optimization is essential for any high-performance querying system. Several optimization techniques were developed and successfully implemented for relational databases. However, these techniques should be re-examined and revised for distributed heterogeneous systems of information resources supporting diverse querying paradigms. We introduce cost models for approximate query evaluation in the context of generalized algebraic operations supporting both exact and similarity queries. The proposed cost models are suitable for approximate evaluation and trade-off between computational performance and the quality of results. We present a rationale for our approach and elaborate our cost model for key operations and algorithms.
The presence of high-level declarative query languages was considered as one of major strengths of database management systems since early 70-ies and became an inherent feature of the relational database model and its variations are implemented in the industrial SQL-based systems.
Providing highly expressive declarative means for query specification, these languages both require and enable sophisticated optimization. In contrast with lowlevel imperative object-oriented programming languages, which allow only moderate code improvements with local optimization, declarative languages depend dramatically on the quality of the optimizer.
Formally, the task of a query optimizer is to choose an algebraic expression of minimal execution cost among several equivalent expressions. In other words, any high-quality optimizer is inevitably a cost-based one and, hence, the cost model is one of the critical core components of the optimizer.
The abstract concept of cost may include several different measures of query execution performance. Usually the most important is execution time (either CPU or elapsed), amount of I/O, or, in a distributed mobile environment, the battery energy. However, the actual interpretation of cost is not essential for the optimization process.
There are many optimization techniques based on cost models, but in general almost all cost models were prepared for exact query evaluation algorithms.
In broad modern contexts, such as distributed heterogeneous systems, real-time business analytics and distributed mobile environments an approximate query evaluation becomes a must. Indeed, it does not make any sense to use exact query evaluation in uncertain context or for similarity-based queries, where “top k” approach is the best. Approximate query evaluation is ultimately needed to provide timeliness for business analytics or save energy in a mobile device.
As the query evaluation is approximate, the quality of the output may decrease. Our main objective is to provide a cost model capable to support trade-off between the cost of evaluation and the quality of results. Based on our cost model, the query optimizer can either provide best possible quality for a given cost, or minimize the cost providing at least required quality of the query output.
We start from naïve exact cost models and proceed with detailed analysis of approximate operations. We define models for a number of operations including “top k” operations for single and multiple arguments.
In this research we consider query processing in a heterogeneous environment of autonomous information resources. In this type of environments data statistics might be unavailable, hence simple cost models are needed for both of exact and approximate querying.
In this paper we discuss query processing in a heterogeneous environment of autonomous information resources where all objects have scores which represent their relevance, similarity, quality and so on. Each operation takes as an input a stream of objects with scores and pushes into the output another stream of objects with their scores.
Further the specification of the cost model that supports the concept of operation result quality is presented and is followed by brief discussion of main operations and corresponding algorithms which are analyzed in this paper.
Operation cost model depends on 4 basic parameters: data size; data quality; data order; and the amount of resources needed for operation execution (operation cost).
On the one hand in traditional cost models the operation cost (amount of resources for its evaluation) can be estimated based on the size of arguments, order of objects in an argument. On the other hand, when we talk about approximate algorithms, the operation behavior depends on the quality of the arguments, the size of the arguments, order of objects in the arguments, and the amount of resources allocated for operation execution.
Thus, an operation cost model is defined as follows: opcost(resources, sizein,orderin)=(qualityout,sizeout,orderout), where • opcost is the operation cost function, opcost connects the values of the input and output parameters; • resources are resources allocated for the operation processing or the operation cost; • sizein is the operation input arguments size; • orderin is the operation input arguments order; • qualityout is the operation execution relative result quality, the relative quality of the result of the corresponding subquery; • sizeout the result size; • orderout the result order; • resources, sizein, orderin, qualityout, sizeout, orderout are objects with attributes which represent different measures of the corresponding parameter of the cost model and are discussed in details below.
Let us note that sizein and orderin are vectors of objects that describe all arguments of the operation.
The equation describes the cost model and binds all its variables and parameters. Thus, substituting in the equation the values of the variables, we can express and evaluate the remaining parameters of the cost model.
Apart from the basic cost model equations there are some restrictions on the cost models of the specific operations: resourcesmin≤resources≤resourcesmax
qualitymin≤quality≤qualitymax
If the operation has resourcesmax resources available, the result has the best possible quality with given arguments, that is relative qualityout=qualitymax.
If the operation has resourcesmin resources available, the result has the worst possible relative quality (qualityout=qualitymin) with given arguments. In this case the algorithm spends the least possible amount of resources for operation execution.
Our cost models suggest the estimation of the unknown parameters. We assume that objects are not ordered in an input or output data if no information about order is available. The value of the quality and size parameters are estimated based on the history of the previous queries and collected statistics.
Further we discuss how to measure resources and data characteristics in our cost models.
Resources needed for a particular operation processing can be measured and evaluated in different ways. For example the operation processing cost can be estimated by its execution time. However, this approach restricts the proposed cost model to a specific query processing system.
In this research we evaluate the cost of operations in terms of the number of disk accesses, sequential accesses, executions of external operations, and so on. It is important to note that in this case, the cost model is more general. In this case the proposed cost model can be tuned depending on the specific characteristics of the query processing engine.
There are several characteristics and measure resources: • • • • • • sa the number sequential accesses to read objects from pipe; dsa the number of sequential disk accesses to read objects; ma the number of random memory accesses; da the number of random disk accesses; pred the number of predicate evaluations; ha the number of hash table accesses.
The operation cost or the amount of resources needed for its execution will be evaluated in terms of these measures. The cost of each parameter in terms of time (Tsa, Tdsa, Tma, Tda, Tpred), which depends on the system configuration, will be estimated based on the experiments and available statistics. Thus the operation cost can be simply evaluated:
time = sa*Tsa+dsa*Tdsa+ma*Tma+da*Tda+pred*Tpred+ha*Tha 1.2. Size
The size of the input data, as well as the result sizes can be evaluated at least in two different ways: size, which data occupy in memory (size), and the number of objects, semantic units, which the operation processes (cardinality). These characteristics influence the behavior of algorithms that implement operations.
We distinguish absolute and relative quality which operations produce.
The absolute quality shows how the produced result suites to the user expectations. To measure the absolute quality we need to obtain the actual relevance scores which are usually not know in advance and sometimes at all.
The relative quality shows how the limited, approximate implementation of an operation changes the absolute quality of the result. In our cost models we operate with relative quality of the operations and queries. The most important property of the relative quality of a query is its monotony on the amount of resources allocated for its processing. The monotony of the relative quality depends on its definition and algorithms implementing approximate operations. 1.4. Order 2.1. Top k The order of objects in the input data influences the operation execution cost. At this phase of work, the order of objects is defined as the order of their scores in a data set. The cost models depend on the fact whether the objects in the input data are naturally ordered according to their scores.
We consider three operations in this paper. Exact and approximate algorithms implementing them are discussed in this section and corresponding cost models are developed and analyzed further.
Top k operation takes as an input the stream of objects with scores and returns to the output the stream of best k objects according to their input scores. The naïve exact algorithm orders objects according to their scores if needed and returns k first of them. An approximate top k algorithm reads objects sequentially, while free time for operation execution is available, and pastes them into the sorted list of already processed objects. When the resources are over first k objects are set to be the result.
Binary fusion operation processes two input streams of objects with scores and returns stream of received objects with newly generated aggregated scores. The naïve exact algorithm implementing fusion is based on nested loops.
The aggregation operation is the same as defined in [
Let's describe a basic cost models for different operations in case when the relative quality of the arguments and the result of the operation as the best possible and is not regulated from the outside.
Actually cost models depend on algorithms implementing this operations rather than operations themselves. Here we describe cost models for natural exact operation algorithms discussed in section 3.
All restrictions will be defined based on the cost model described by the equation: opcost(resources,sizein,orderin)=(qualityout,sizeout,orderout). 3.1. Top k For exact top k operation the cost model can be defined as follows: cardinalityout=min{k, cardinalityin} orderout=true cardinalityin≥cardinalityout sizein≥sizeout if orderin=false then sa=cardinalityin ma=C*cardinalityin*ln(k) if orderin=true then
sa=cardinalityout
Here we consider the binary fusion operation. In this case sizein,orderin represent twodimensional vectors, since the fusion operation takes two arguments. For fusion operation (based on nested loop algorithm) we have the following cost model:
First of all we describe the intermediary parameters which can help us to construct formulas: • • • t – estimated size of a table, which shows all objects with already read scores; ns – estimated number of scores needed to fill the table of size t; ks – estimated number of scores needed to fill the table of size k.
We assume independence of scores and uniform distribution and use expectation for evaluate these parameters.
orderin=true cardinalityout=min{k, cardinalityin} orderout=true cardinalityin≥cardinalityout sizein≥sizeout 3.3.1. FA 3.3.2. NRA time = cardinalityinTsa+(tlog t+4t)Tma+tTha
Summands include sorted access, sort, input/output and calculation of aggregate score as well as search for a place to insert a score just obtained from stream respectively.
After evaluation and substitution of intermediary parameters we obtain the following:
time=((3/4ln(cardinalityin)+3/2)Tma+3/4Tha)k+Tmacardinalityin+1/4cardinalityin
Summands include sorted access, sort, input/output and calculation of worst case score and best case score as well as search for a place to insert a score just obtained from stream respectively.
After evaluation and substitution of intermediary parameters we obtain the following (cin denotes as cardinalityin below):
time=(45/32-9/64ln(cin))Tmak2+((3/4cin+3-3/64cin(ln(cin)–2)+3/16cin(3/4ln(cin)– 3/2)Tma+3/4Tha)k+(1/2cin(2+1/4cin)+3/64cin 2(ln(cin)–2)Tma+cinTsa+1/4cinTha
Now we add the specific resource t0 – time operation execution. The problem is to estimate the result quality.
We create approximate model based on exact one. Let’s k’ denote the number of correct object returned by approximate algorithm. We express it in terms of t0. Hence we get number of scores which system can find for the given time. Then we consider ratio between k’ and k which means the accuracy of result.
qualityout=k’/k
For FA we obtain the following: k’=(t0-Tmacardinalityin-1/4cardinalityinTha
We will not give the inverse formula for NRA here because of the limits of paper size. 4.2. Top k
The query optimization became both required and enabled since the advent of highlevel declarative query languages, mostly in the context of the relational database model.
A brief overview of classical query optimization techniques can be found in [
The cost models proposed in this research are designed similar to those needed to traditional optimizers.
The optimization strategy based on algebraic equivalences between similarity
based operations that serve as rewrite rules is outlined in [
It is important to mention that the lack of algebraic equivalences pushes the research to the development of optimization techniques based on performance/quality tradeoffs and approximate algorithms.
The approximate query evaluation techniques were considered in the context of
very large data warehouses and mobile networks [
Handling of time constraints on complex SQL queries is proposed in [
The quality and performance trade-offs for stream processing are discussed in
[
Cost models based on estimation of operation selectivity and cardinality are
introduced in [
A sampling-based method to estimate the cardinality of rank-aware operators is
developed for costing plans [
A novel multi-criteria query optimization techniques for performing query
optimization in databases, such as multimedia and web databases, which rely on
imperfect access mechanisms and top-k predicates are proposed in [
In this paper we presented several cost models for both exact and approximate query evaluation algorithms in distributed heterogeneous systems. The more resource we use, the more accurate the result is and vice versa. Our models convert these intuitive observations into clear and distinct formulas. It provides formalism for trade-off between quality and performance.
In the future we are going to conduct experiments in order to estimate the accuracy of our cost models.