Chiraz Moumen
email: moumen@irit.fr

Franck Morvan
email: morvan@irit.fr

Abdelkader Hameurlain
email: hameurlain@irit.fr

Handling Estimation Inaccuracy in Query Optimization

Keywords: Query optimization, Robust plans, Estimation errors

Cost-based Optimizers choose query execution plans using a cost model. The latter relies on the accuracy of estimated statistics. Unfortunately, compile-time estimates often differ significantly from runtime values, leading to a suboptimal plan choices. In this paper, we propose a compile-time strategy, wherein the optimization process is fully aware of the estimation inaccuracy. This is ensured by the use of intervals of estimates rather than single-point estimates of error-prone parameters. These intervals serve to identify plans that provide stable performance in several run-time conditions, so called robust. Our strategy relies on a probabilistic approach to decide which plan to choose to start the execution. Our experiments show that our proposal allows a considerable improvement of the ability of a query optimizer to produce a robust execution plan in case of large estimation errors.

Introduction

In database query processing, query optimization constitutes a critical stage due to its impact on query processing performance. During this stage, a query optimizer 1 generates several execution plans for a query, estimates the cost of each plan using a cost model and chooses the plan with the lowest estimated cost to execute the query [START_REF] Selinger | Access path selection in a relational database management system[END_REF]. This plan is called best plan [START_REF] Kabra | Efficient mid-query re-optimization of sub-optimal query execution plans[END_REF][START_REF] Markl | Robust query processing through progressive optimization[END_REF][START_REF] Selinger | Access path selection in a relational database management system[END_REF]. Best plan selection requires accurate estimates of the costs of alternative plans. Unfortunately, these estimates are often significantly erroneous with respect to values encountered at run-time. Such errors, which may be in orders of magnitude [START_REF] Ioannidis | On the propagation of errors in the size of join results[END_REF], arise due to a variety of reasons [START_REF] Christodoulakis | Implications of certain assumptions in database performance evaluation[END_REF]. One of the main reasons is the imprecision of statistics about data (e.g., sizes of temporary relations) as well as the use of outdated statistics. Indeed, values of parameters which are important for costing possible query plans may vary unpredictably between compile-time and run-time (e.g., available memory amount).

An adverse effect of estimation errors is to lead the optimizer to a sub-optimal plan choice, resulting in inflated response time. A considerable body of literature was dedicated to find solutions to this problem. These solutions include mainly: (i) techniques for better quality of the statistical metadata [START_REF] Chen | Adaptive selectivity estimation using query feedback[END_REF][START_REF] Deshpande | Independence is good: dependencybased histogram synopses for high-dimensional data[END_REF][START_REF] Getoor | Selectivity estimation using probabilistic models[END_REF][START_REF] Poosala | Improved histograms for selectivity estimation of range predicates[END_REF][START_REF] Tzoumas | Lightweight graphical models for selectivity estimation without independence assumptions[END_REF][START_REF] Tzoumas | Efficiently adapting graphical models for selectivity estimation[END_REF], (ii) run-time techniques [START_REF] Bruno | Continuous cloud-scale query optimization and processing[END_REF][START_REF] Kabra | Efficient mid-query re-optimization of sub-optimal query execution plans[END_REF][START_REF] Karanasos | Dynamically optimizing queries over large scale data platforms[END_REF][START_REF] Markl | Robust query processing through progressive optimization[END_REF][START_REF] Neumann | Taking the edge off cardinality estimation errors using incremental execution[END_REF] to monitor a query execution and trigger reoptimization of the plan when a sub-optimality is detected, and (iii) compile-time strategies [1-3, 9, 12] that permit the optimizer to generate an execution plan, being aware of the imprecision of used estimates.

Accurate cost estimates remain, though, very difficult as this requires a detailed and a prior knowledge about data (e.g., sizes of temporary relations) and run-time characteristics such as resource availability (e.g., system load). Run-time techniques are able to adapt an execution plan to changes in run-time conditions with a risk of an important cost-increase resulting from many possible adaptations of the plan. Compile-time strategies proposed to date suppose that it is often possible to find a single execution plan whose performance remains stable regardless of changes in the run-time conditions compared to the compiletime expectations of the run-time conditions. This assumption is not always valid. In some situations, especially in case of large uncertainty about run-time characteristics, find such a plan becomes hard to achieve. In this paper, we focus on this issue. We propose a compile-time strategy for identifying plans, each of which provides stable performance over a range of possible run-time values of error-prone parameters. Throughout this paper, these plans are said robust.

Our optimization method uses an interval of estimates for each uncertain parameter, rather than specifying estimates for single points. Such an interval fully quantifies estimation inaccuracy and is then used to generate robust plans. Note that a plan providing stable performance over the whole interval is a single robust plan. Otherwise, the interval is divided into sub-intervals so as to find execution plans, each of which is associated with the sub-interval within which the plan is robust. Our method relies on a probabilistic approach to decide which plan to choose to start the execution. The major contribution of our optimization method is to maximize the ability of a query optimizer to produce a robust execution plan in the presence of large estimation errors.

The rest of the paper is organized as follows: Sect. 2 presents the problem formulation. Section 3 details our contribution. The experimental evaluation results are highlighted in Sect. 4. Related work is overviewed in Sect. 5. We conclude and outline our future work in Sect. 6.

Problem Formulation

In this section, we start with the preliminaries. Then, we provide our problem definition.

Preliminaries

Motivated by the difficulty of providing precise estimates needed for costing query plans as well as the complexity of cost models, researchers focused their efforts on introducing new optimization algorithms. Their aim is to avoid significant performance regression caused by the use of erroneous estimates. Researches on this purpose fall into two main approaches [START_REF] Moumen | Estimation error-aware query optimization: an overview[END_REF]. A first approach, called Single Point-based Optimization [START_REF] Bruno | Continuous cloud-scale query optimization and processing[END_REF][START_REF] Kabra | Efficient mid-query re-optimization of sub-optimal query execution plans[END_REF][START_REF] Karanasos | Dynamically optimizing queries over large scale data platforms[END_REF][START_REF] Neumann | Taking the edge off cardinality estimation errors using incremental execution[END_REF] consists in monitoring a plan execution so as to detect estimation errors and a resulting sub-optimalty. This latter is corrected by interrupting the current execution and re-optimizing the remainder of the plan using up-to-date statistics. At each invocation, the optimizer considers the used estimates as though they were completely precise and accurate. It uses specific estimate for each parameter. The generated plan is thus the best plan for specific run-time conditions. The ability of methods relying on this approach to accurately collect statistics is limited [START_REF] Babu | Proactive re-optimization[END_REF]. Consequently, when re-optimizing, the optimizer may use new erroneous estimates. This may result in several plan re-optimization and so performance regression.

While Single Point-based Optimization uses exclusively single points for estimates ignoring possible estimation errors, a conceptually different approach called Multi Point-based Optimization was introduced. Besides to providing a solution to estimation errors, this approach avoids performance regression due to several re-optimizations of a plan. Contrary to the first approach which reacts after an estimation error is detected, Multi Point-based Optimization aims to predict plan sub-optimalities and anticipate the reaction to this. The methods proposed as part of this approach consider the possibility of estimation errors at the optimization phase. They produce plans that are likely to perform reasonably well in many run-time conditions. These methods [1-3, 9,14] aim at preventing rather than correcting. The key concept of these methods is the use of intervals of estimates, which models the estimation inaccuracy. In the literature, there are different techniques for computing such intervals. For instance, [START_REF] Chaudhuri | Estimating progress of long running SQL queries[END_REF] uses strict upper and lower bounds, [START_REF] Babu | Proactive re-optimization[END_REF][START_REF] Kabra | Efficient mid-query re-optimization of sub-optimal query execution plans[END_REF] model estimation uncertainty by means of discrete buckets that depend on the way the estimate was derived, etc. Once computed, the interval of estimates is used by the optimizer to generate an execution plan that is likely to provide stable performance within this interval.

Problem Definition

Existing methods proposed as part of the Multi Point-based Optimization approach suppose that it is always feasible to find a single robust plan within an interval of estimates. We believe that this assumption is not always valid. When the interval of estimates is large, it becomes difficult to find a plan generating stable performance over the whole interval. Execution plans may be robust at only some points of the interval. In the remainder of this paper, we adopt the following definition for a robust plan: let V e be an estimate of an error-prone parameter, let I be an interval of estimates around V e exhibiting the uncertainty about the estimate of this parameter. Let P best be the best plan for a specific value V i in I. Finally, let λ be a (user-defined) cost-increase threshold (expressed in percentage). A plan P alt is robust with respect to estimation errors if:

∀ V i ∈ I, cost(P alt ) cost(P best ) ≤ 1 + λ 100 (1)
For instance, if users tolerate a minor cost increase (λ) of at most 20 %, the cost of P alt is at most 1, 2 times the cost of the best plan.

Generation of a Robust Query Execution Plan

In this section, we detail our method called Identification of Robust Plans (IRP), which is part of the Multi Point-based Optimization approach. The key concept in our work is the uncertainty of estimates used by a query optimizer to choose an appropriate execution plan along with the difficulty to find a single robust execution plan when the estimation uncertainty is large. We present below an example that underlines our motivations before detailing our method.

A Motivating Example

We first study the case wherein the size of only one input-relation for a join operation is error-prone. then, we extend it to the general case. Best plan selection for this query requires accurate estimate of selectivity of the predicates C.country = 'France' and C.city = 'Paris'. However, even with the existence of histograms on attributes C.country and C.city, the optimizer can not maintain multi-dimensional histograms for all possible combinations of attributes [START_REF] Poosala | Selectivity estimation without the attribute value independence assumption[END_REF]. It may so assume independence to compute the joint selectivity of the two predicates. This assumption may lead to large estimation errors while costing plans due to an eventual correlation between the predicates. To avoid sub-optimal plan choice, resulting from these errors, we consider σ(C), which is the result of C.country = 'France' and C.city = 'Paris', as error-prone. We define an interval of estimates around σ(C), denoted I. This interval is then used to select an appropriate execution plan. In this process, one of the following cases may occur: (i) there is a single plan that is robust at all points of I, (ii) there are several plans, each of which is robust at only some points of I. Existing multi point-based optimization methods assume that the first case is often feasible, that is to say a plan providing stable performance within an interval of estimates can be founded. This assumption is not always valid. Consider the scenario of Example, suppose that there is an index on an attribute of the relation O. Through repeated invocations of a query optimizer, plans labelled "Plan1", "Plan2" and "Plan3" (Cf. Fig. 1) are enumerated as possible execution plans for Q.

Based on a cost model, a query optimizer estimates the costs of these plans with respect of variation of σ(C) so as to determine the execution plan that offers robust performance within the interval of estimates. This plan must respect robustness definition presented in Sect. 1. Assume that the tolerated cost-increase (λ) is about 20 %. This value is chosen based on the works of [START_REF] Abhirama | On the stability of plan costs and the costs of plan stability[END_REF][START_REF] Babu | Proactive re-optimization[END_REF]. Figure 2 plots the plans' costs with respect to variations of σ(C) in MB. In this Figure, we observe that for λ = 20 %, none of plans P1, P2 and P3 is robust within I. This example highlights the necessity to divide the interval of estimates into sub-intervals and to associate a robust plan with each sub-interval. An important question concerns the choice of only one plan to start the execution. A solution could be to determine the sub-interval covering the most possible run-time values and choose the plan associated with this sub-interval to execute the query.

Robust Optimization Method

The above mentioned discussion motivates the necessity of incorporating estimation uncertainty in the query optimization process. In order to design and develop such an optimization method, it is suitable to offer first a method for one-join operation. This method constitutes the building block for a robust execution of a multi-join query. In this regard, we present a method that consists of two main modules: (1) Identification of Robust Plans, and (2) Selection of an Execution Plan. We will examine them in more detail in the subsections below.

Identification of Robust Plans: IRP is a compile-time strategy for identifying robust plans. It relies on intervals of estimates to model the estimation uncertainty. Such intervals are used to select the plan that minimizes a potential sub-optimality resulting from possible estimation errors. To conduct our experiments we use the method in [START_REF] Babu | Proactive re-optimization[END_REF] to compute these intervals.

Let Q = Join(T, R1) be a query to join T and R1, where T is a temporary relation and R1 is a base relation. The size of T is denoted |T|. The point estimate of |T| is denoted T est . Let us assume that the interval of estimates around T est is defined, i.e., I = [L, U], where L and U are the lower and the upper bound of the interval. Let S be a set of possible execution plans for Q. This module consists in determining -for each plan P in S-the interval I p within which P is robust (Cf. [START_REF] Moumen | Handling estimation inaccuracy in query optimization[END_REF]). Calculate I p may be converted into a numerical solving problem. We vary T est in I and compute the lower bound of I p by solving the inequality:

Cost(P, T est , R1 val ) ≤ (1 + λ 100 ) × CostBestP lan(S, T est , R1 val ) (2)
T est is considered as the variable of the inequality. We choose then the minimum root to be the lower bound of I p . R1 val refers to the size of the base relation R1.

CostBestP lan(S, T est , R1 val ) returns the cost of the best plan in S for T est and R1 val while Cost(P, T est , R1 val ) returns the execution cost of P. Similarly, the upper bound is determined as the minimum root of the inequality below:

(1 + λ 100 ) × CostBestP lan(S, T est , R1 val ) < Cost(P, T est , R1 val ) (3)
Due to space limitation, this algorithm is described in greater detail in [START_REF] Moumen | Handling estimation inaccuracy in query optimization[END_REF]. The robustness of a plan is checked at different points in the interval. To avoid a large computational complexity, these points are computed based on the secant method, which is very effective and can be extended to n-parameters space [START_REF] Papakonstantinou | Origin and evolution of the secant method in one dimension[END_REF].

Selection of an Execution Plan: After identifying robust plans, only one plan should be selected to start the query execution. This plan is chosen based on a probabilistic approach. We propose to compute, for each plan, its probability prob(P ) to handle run-time variation of estimates. The greater is the probability the higher is the likelihood of the plan to minimize sub-optimality. We process estimates as random variables and compute prob(P ) as:

prob(P ) = length of the robustness range associated with P length of the interval of estimates I (4)

The plan with the higher probability is chosen to start the execution. When two plans have equal probabilities, the plan that maximizes the worst-case performance is selected. The study of this issue is available in [START_REF] Moumen | Handling estimation inaccuracy in query optimization[END_REF].

Extension to Multiple Parameters. So far, we have assumed that the size of only one join input-relation is error-prone. This approach can be generalized to the multi parameter case. In this case, the size of each relation is modelled by an interval of estimates. The intersection of these intervals forms a bounding box. We compute -for each plan-a robustness box rather than a robustness range. In addition, the plan associated with the robustness box covering the most space of uncertainty is chosen to start the execution. Notwithstanding these changes, the basic mechanism of the IRP algorithm is similar to the first case. This algorithm can be found in detail in [START_REF] Moumen | Handling estimation inaccuracy in query optimization[END_REF].

In this section we describe the experimental evaluation of our optimization method, termed IRP. We compare IRP with a method that relies on the single point-based optimization approach [START_REF] Selinger | Access path selection in a relational database management system[END_REF] (termed TRAD) and with RIO [START_REF] Babu | Proactive re-optimization[END_REF]. RIO is a method using the multi point-based optimization approach. We study the behaviours of these methods with respect to error in estimates. We consider that an estimation uncertainty may be high, medium or low. We conducted our experiments using a simulation model that we describe below.

Simulation Model

To perform our experiments, we used a query builder and a simulator. The simulator includes the simulated optimization method and a meta-base. The simulated method consists of two main modules: (1) Query Optimizer, and

(2) Query Executor. The meta-base includes information describing the runtime environment (e.g., CPU performance) as well as information about data (e.g., sizes of base relations). The dataset used in the experiments is shown in Table 1. In the next subsections, we present the results of our experiments. First, we study the case wherein only one input-relation for a join is prone to an estimation error. Second, we extend our experiments to the case wherein both inputsrelations are prone to estimation errors. During our experiments, we consider that the cost-increase threshold for robustness condition is 20 %.

Experimental Results

For this experiment, we use a set of 100 queries which we call SQ. Queries in SQ include only one join operation and verify all, the followings conditions: (i) One of the inputs relations is a base relation, denoted R1, and (ii) One of the inputs relations is a temporary relation, denoted T and is resulting from a selection operation on a base relation named R2. The following query Q ′ is a sample of queries in SQ:

Q ′ = select * f rom R1, R2 W here R1.a = R2.b and R2.c < V 1 and R2.d > V 2
Q ′ can be represented as Join(R1,T), where T is the result of "select * from R2 Where R2.c < V1 and R2.d > V2". Estimates of the temporary relations sizes while costing execution plans for queries in SQ, may be erroneous. This is due to eventual correlations between the selection predicates. For each query, the uncertainty about |T| is modelled by an interval of estimates. To calculate such an interval, we use the method proposed in [START_REF] Babu | Proactive re-optimization[END_REF]. We consider three uncertainty levels: high, medium, and low. Note that a high uncertainty in estimates involves a large interval of estimates. This interval is then used by RIO and IRP to generate a robust query execution plan. As for TRAD, it relies on a single-point estimate of |T|, i.e., T est , to select an execution plan expected to be the best.

Impact of Estimation Errors on Execution Times:

The first experiment consists in assessing the impact of estimation errors on the execution time of each method. Figure 3 shows the variation of the execution time of plans produced by TRAD, RIO and IRP for queries in SQ. We vary the error between the estimate of the temporary relation size and its actual value. This is repeated for each query in SQ. Figure 3 also shows the execution time of the best plan.

The execution time for a method is computed as the median of the execution times of all queries in SQ by this method. Error in estimates plotted on the x-axis is calculated as ( |T actual | |T estimate | -1) [START_REF] Babu | Proactive re-optimization[END_REF]. A positive error indicates an underestimate while a negative error indicates an overestimate of the actual run-time value compared to the compile-time estimated value. Figure 3 shows that the performance of TRAD remains acceptable when the error on |T|, is very low. However, when the error becomes large, i.e., greater than 2, we observe a significant increase in the execution times of plans produced by TRAD. Indeed, TRAD selects an execution plan whose performance is heavily dependent on the accuracy of compile-time estimates. This plan is optimal for only the single-point estimate of |T|. Plans chosen by TRAD are very sensitive to estimation errors.

Figure 3 shows that RIO generates better performance compared with TRAD. However, the performance of RIO may deteriorate. Indeed, when RIO does not find a single robust plan within the interval of estimates of |T|, it behaves like TRAD. It produces a plan expected to be optimal for the compiletime estimate of |T|. Unlike RIO, IRP remains based on multi-point estimates. It generated an execution plan that provides stable performances within a subinterval of the interval of estimates. Using a sub-interval of estimates rather than a single-point estimate for |T| allows to IRP to produce plans whose execution times are usually more stable compared with RIO and TRAD. We also notice in Fig. 3 that when the uncertainty is low, the performance of TRAD and IRP becomes close. This is because when the interval of estimates is narrow, it becomes more feasible for RIO to find a plan that is robust within an interval.

Impact of Estimation Errors on the Consistency of Methods: The consistency of a method refers to its ability to cope with estimation errors and/or changes in run-time conditions compared to compile-time expectation of runtime conditions. A method is said highly consistent if its performance does not degrade significantly in the presence of estimation errors [START_REF] Wiener | Benchmarking query executionrobustness[END_REF]. To measure the consistency of TRAD, RIO and IRP, we compute the variance of performance of each method and compare it to the variance in case of best performance. Note that the consistency is inversely proportional to the variance [START_REF] Wiener | Benchmarking query executionrobustness[END_REF]. To achieve this experiment, we use the same set of queries previously used, i.e., SQ. The results of this evaluation are shown in Fig. 4.

As we can see Fig. 4, the variances of RIO and IRP are close when the estimation uncertainty is low. However, when the uncertainty is large (high or medium), the gap between the variances of methods increase. A high variance means a significant dispersion of execution times. Figure 4 demonstrates that plans generated by IRP are more stable than those generated by RIO. This figure also proves that estimation errors have a pronounced impact on the consistency of TRAD. This figure confirms the evaluation results previously obtained.

When Both Inputs-Relations are Prone to Estimation Errors. We performed more experiments under the assumption that both join-inputs relations, denoted T1 and T2, are prone to estimation errors. As RIO assumes that at least one of the inputs-relations is a base relation [START_REF] Babu | Proactive re-optimization[END_REF], we only compared our method with TRAD. The experiments are done using the same dataset (Cf. Table 1) as previously. Unsurprisingly, the experimental results confirm the results obtained in the first case. IRP generates execution plans that provide stable performance in the presence of estimation errors. Always because of space limitation, more details of these experiments and figures can be found in [START_REF] Moumen | Handling estimation inaccuracy in query optimization[END_REF].

Related Work

A variety of optimization strategies have been proposed in the literature to identify robust plans. [START_REF] Yin | Robust query optimization methods with respect to estimation errors: a survey[END_REF] overviews these works. In this section, we compare our proposal with the most closely related prior research, i.e., [START_REF] Babu | Proactive re-optimization[END_REF][START_REF] Hulgeri | Parametric query optimization for linear and piecewise linear cost functions[END_REF][START_REF] Markl | Robust query processing through progressive optimization[END_REF]. Similarly to this paper, these methods address the problem of query optimization due to the uncertainty in estimates. These methods make use of intervals to manage estimation uncertainty. These intervals are then used by the optimizer to pick an appropriate execution plan. However, our work defers from these works on several aspects. In the initial optimization phase of Rio [START_REF] Babu | Proactive re-optimization[END_REF], if the plan chosen by the optimizer at the lower and the upper bounds of the interval is the same as that chosen for the single-point estimate, then the plan is assumed robust within the whole interval. In our method, we adopt a different way to check the robustness of a plan. We verify the robustness of a plan at different points in the interval. These points are determined using our modified secant method, which provides reduced computation complexity and precise results. In addition, Rio assumes that at least one of the join inputs-relations is a base relation. We extend this by considering the case wherein both relations are prone to estimation errors.

Among previous related research, the work by Markl et al. [START_REF] Markl | Robust query processing through progressive optimization[END_REF]. In [START_REF] Markl | Robust query processing through progressive optimization[END_REF], and later in [START_REF] Bizarro | Progressive parametric query optimization[END_REF], validity ranges are computed for each sub-plan of a query execution plan. The best plan is first chosen based on single-point estimates. The upper and lower bounds wherein the plan remains the best plan are then computed. These methods aim for optimal performance while IRP aims for robustness. Robust plans choices are especially important to safely process queries when the uncertainty about estimates is large.

The use of intervals may seem similar to the principle of parametric optimization [START_REF] Cole | Optimization of dynamic query evaluation plans[END_REF][START_REF] Hulgeri | Parametric query optimization for linear and piecewise linear cost functions[END_REF] where different plans are generated for different intervals of the optimization parameters. The main limitation of this approach is the large number of plans to generate, store and compare at the optimization phase. We reduce this complexity by computing robustness ranges. We accept a minor cost-increase that reduces the number of plans generated. In addition, parametric optimization is particularly attractive in the case of queries that are compiled once and executed several times, possibly with minor modifications of parameters. Unlike our work, its objective being to avoid compiling multiple instances of the same query, but not to ensure robustness against estimation errors.

Conclusion and Future Work

This paper proposes an optimization strategy to handle uncertainty in compiletime estimates. Uncertainty is modelled by means of intervals of estimates. These intervals are then used to identify robust plans. We characterize a plan as robust if its cost remains stable and acceptable in case of estimation errors. Our method relies on a probabilistic approach to select the plan by which to start the execution. The experiments show that the proposed strategy may improves the ability of a query optimizer to generated a robust execution plan, especially in the presence of large estimation errors.

The proposed method performs in a uniprocessor environment. As future work, we plan to extend it to a multiprocessor environment. It would be interesting to study the importance of the parallelism degree choices over the identification of a robust query execution plan.

Example.

  Consider the query Q = select * from customer as C, order as O where C.customerId = O.customerId and C.country = 'France' and C.city = 'Paris'.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Possible execution plans for the query Q = σ(C) ⊲⊳ O

Fig. 3 .

 3 Fig. 3. Variation of execution times with respect to errors on |T|

Fig. 4 .

 4 Fig. 4. Variance of execution times with respect to errors on |T|

Table 1 .

 1 Summary of dataset used in the experiments

	Parameter	Value	Parameter	Value
	Buffer size	400 MB	CPU performance	100 000 MIPS
	Disk bandwidth	100 MB/s	Average disk latency 2 ms
	Size of a page on disk 4 KB	Size of a record	1-3 KB
	Size of a relation	100-1000 MB Size of an attribute 10-500 Bytes

We only focus on the Cost-based Query Optimizers.


Damla Oguz
email: damlaoguz@iyte.edu.tr

Shaoyi Yin
email: yin@irit.fr

Abdelkader Hameurlain
email: hameurlain@irit.fr

Belgin Ergenc
email: belginergenc@iyte.edu.tr

Oguz Dikenelli
email: oguz.dikenelli@ege.edu.tr

Adaptive Join Operator for Federated Queries over Linked Data Endpoints

Keywords: Distributed query processing, Linked data, Query federation, Join methods, Adaptive query optimization

Traditional static query optimization is not adequate for query federation over linked data endpoints due to unpredictable data arrival rates and missing statistics. In this paper, we propose an adaptive join operator for federated query processing which can change the join method during the execution. Our approach always begins with symmetric hash join in order to produce the first result tuple as soon as possible and changes the join method as bind join when it estimates that bind join is more efficient than symmetric hash join for the rest of the process. We compare our approach with symmetric hash join and bind join. Performance evaluation shows that our approach provides optimal response time and has the adaptation ability to the different data arrival rates.

Introduction

Linked data, which is a way of publishing and connecting structured data on the web, provides connected distributed data across the web. In other words, linked data creates a global data space on the web. Link traversal and query federation are the two approaches for querying this space on the distributed data sources. Link traversal [START_REF] Hartig | Executing SPARQL queries over the web of linked data[END_REF] finds the related data sources during the query execution whereas query federation [START_REF] Görlitz | Federated data management and query optimization for linked open data[END_REF] selects the related data sources before the execution. In short, link traversal has the disadvantage of not guaranteeing complete results. For this reason, we turn our attention to query federation.

Query federation divides the query into subqueries and distributes them to the SPARQL endpoints of the selected data sources. The intermediate results from the data sources are aggregated and the final results are generated. These processes are employed via a federated query engine whose objective is to minimize the response time and the completion time. Response time refers to the time to receive the first result tuple whereas completion time refers to the time to receive all the result tuples. Response time and completion time include communication time, I/O time and CPU time. Since the communication time dominates the other costs, the main objective can be stated as to minimize the communication cost. Schwarte et al. [START_REF] Schwarte | FedX: optimization techniques for federated query processing on linked data[END_REF] use heuristics in query optimization whereas Quilitz and Leser [START_REF] Quilitz | Querying distributed RDF data sources with SPARQL[END_REF], Gortlitz and Staab [START_REF] Görlitz | SPLENDID: SPARQL endpoint federation exploiting VOID descriptions[END_REF] and Wang et al. [START_REF] Wang | LHD: optimising linked data query processing using parallelisation[END_REF] concentrate on static optimization which produces an execution plan at query compilation time and uses statistics to estimate the cardinality of the intermediate results. However, federated query processing is done on the distributed data sources on the web which causes unpredictable data arrival rates. In addition, most of the statistics are missing or unreliable. For these reasons, we think that adaptive query optimization [START_REF] Deshpande | Adaptive query processing[END_REF] is a need in this unpredictable environment. There are only two engines ANAPSID [START_REF] Acosta | ANAPSID: an adaptive query processing engine for SPARQL endpoints[END_REF] and ADERIS [START_REF] Lynden | Adaptive integration of distributed semantic web data[END_REF][START_REF] Lynden | ADERIS: an adaptive query processor for joining federated SPARQL endpoints[END_REF] which consider adaptive query optimization for query federation. Acosta et al. [START_REF] Acosta | ANAPSID: an adaptive query processing engine for SPARQL endpoints[END_REF] propose a non-blocking join method based on symmetric hash join [START_REF] Wilschut | Dataflow query execution in a parallel mainmemory environment[END_REF] and Xjoin [START_REF] Urhan | XJoin: a reactively-scheduled pipelined join operator[END_REF] whereas Lynden et al. [START_REF] Lynden | ADERIS: an adaptive query processor for joining federated SPARQL endpoints[END_REF] propose a cost model for dynamically changing the join order. To the best of our knowledge, there is not any study that exploits an adaptive join operator that aims to reduce both response time and completion time.

As mentioned earlier, communication time has the highest effect on overall cost and therefore join method has an important role in query optimization. However, there is not any study which changes the join method during the execution according to the data arrival rates. In this study, we propose an adaptive join operator for federated query processing on linked data which can change the join method during the execution by using adaptive query optimization. Performance evaluation shows that our proposal has both the advantage of optimal response time and the adaptation ability to the different data arrival rates. By this adaptation ability, completion time is minimized as well.

The rest of the paper is organized as follows: Sect. 2 introduces our approach for both single join queries and multi-join queries. Section 3 points out the results of our performance evaluation. Section 4 presents a brief survey of query optimization methods in relational databases and query federation over linked data. Finally, we conclude the paper and give remarks for the future work in Sect. 5.

Proposed Adaptive Join Operator

Bind join [START_REF] Haas | Optimizing queries across diverse data sources[END_REF] passes the bindings of the intermediate results of the outer relation to the inner relation in order to filter the result set and is substantially efficient when the intermediate results are small. Symmetric hash join [START_REF] Wilschut | Dataflow query execution in a parallel mainmemory environment[END_REF] maintains a hash table for each relation. Thus, symmetric hash join is a non-blocking join method which produces the first result tuple as early as possible. Equations 1 and 2 [START_REF] Quilitz | Querying distributed RDF data sources with SPARQL[END_REF] are the cost functions of bind join and symmetric hash join respectively, where R1 and R2 are relations, card(R) is the number of tuples in R, c t is the transfer cost for receiving one result tuple, and c r is the transfer cost for sending a SPARQL query. R2 ′ is the relation with the bindings of R1. card(R2 ′ ) is equal to card(R1⋊ ⋉R2) when we assume that the common attribute values are unique. Equation 2 is used for nested loop join in [START_REF] Quilitz | Querying distributed RDF data sources with SPARQL[END_REF]. However, the cost functions of nested loop join and symmetric hash join are the same when only communication time is considered.

cost(R1 ⋊ ⋉ BJ R2) = card(R1) • c t + card(R1) • c r + card(R2 ′ ) • c t (1) cost(R1 ⋊ ⋉ SHJ R2) = card(R1) • c t + card(R2) • c t + 2 • c r (2)
Deciding the join method by using a cost model before the query execution has some problems. The join cardinality, card(R1⋊ ⋉R2), and the data arrival rates of relations are unknown before the query execution. Using bind join can cause response time problem if the data arrival rate of the first relation is slow. On the other hand, symmetric hash join can produce the first result tuple as soon as there is a match between R1 and R2, without waiting for all tuples of R1 to arrive. However, if R2 is very large while join cardinality is low, the query completion time of symmetric hash join can be longer than the completion time of bind join. We notice that, the data arrival rates of relations are known after a short time of execution. So, the remaining completion time can be estimated. For these reasons, we propose to set the join method as symmetric hash join in the beginning and to use cost functions after having information about the data arrival rates of endpoints. We decide whether to change the join method as bind join according to the cost estimations. In order to learn the cardinalities, we send count queries in the beginning of the execution. As mentioned before, the communication time dominates the I/O time and CPU time. So the cost of count queries is negligible. In brief, our approach is based on the idea of changing the join method during the query execution according to the data arrival rates.

Adaptive Join Operator for Single Join Queries

Adaptive join operator for single join queries is depicted in Algorithm 1. Firstly, we send count queries to the endpoints of datasets R1 and R2 in order to learn their cardinalities. We always begin with symmetric hash join. During the execution, if all the tuples from one dataset arrive and the tuples from the other dataset continue to arrive, we estimate the remaining time of continuing with symmetric hash join and switching to bind join. We decide the join method according to these cost estimations. If we switch to bind join, we emit the duplicate results of symmetric hash join and bind join. The join cardinality estimation formula and the remaining time estimation formulas will be presented in the following subsections.

Join Cardinality and Remaining Time Estimations. In this subsection, we introduce our join cardinality estimation formula and remaining time estimation formulas for symmetric hash join and bind join. We use the estimated join cardinality in order to estimate the remaining times. Equation 3 is our join cardinality estimation formula where |R i ⋊ ⋉R j arrived | is the cardinality of R i ⋊ ⋉R j arrived , |R j | is the cardinality of R j , and |R j arrived | is the cardinality of arrived tuples of R j . We use this formula in order to calculate the estimated cardinality of R i ⋊ ⋉R j when all the tuples of R i arrive. We expect that there is a directional proportion between the join cardinality and number of tuples of R j .

JoinCardinality estimation = |R i ⋊ ⋉R j arrived | • |R j | |R j arrived | (3)
As stated earlier, when all the tuples of R i arrive, the algorithm estimates the remaining time if adaptive join operator continues with symmetric hash join and the remaining time if it changes the join method as bind join. We have an idea about the data arrival rate of R j during the execution, so the estimation is possible. Equation 4shows the estimated remaining time if adaptive join operator continues with symmetric hash join where ERT SHJ is the estimated remaining time if it continues with symmetric hash join, |R j | is the cardinality of R j , |R j arrived | is the cardinality of arrived tuples of R j , and t Rj arrived is the time for |R j arrived | tuples to arrive.

ERT SHJ = (|R j |-|R j arrived |) • t Rj arrived |R j arrived | (4)
Equation 5 shows the estimated remaining time, ERT BJ , if the algorithm switches to bind join where |R i | is the cardinality of R i , t SQ is the time for sending one query to a SPARQL endpoint (≈ t R j arrived |R j arrived | ), |JoinCardinality estimation | is the estimated cardinality of R i ⋊ ⋉R j , |R j arrived | is the cardinality of arrived tuples of R j , and t Rj arrived is the time for |R j arrived | tuples to arrive. The estimated remaining time for bind join includes sending all tuples of R i to the endpoint of R j and the retrieving time of R i ⋊ ⋉R j from the endpoint of R j .

ERT BJ = (|R i | • t SQ ) + |JoinCardinality estimation | • t Rj arrived |R j arrived | (5)

Adaptive Join Operator for Multi-join Queries

Different from the single join queries, we use multi-way symmetric hash join [START_REF] Viglas | Maximizing the output rate of multiway join queries over streaming information sources[END_REF] in the beginning. The algorithm for multi-join queries is depicted in Algorithm 2. When all tuples from a relation arrive, called R i , the algorithm estimates the remaining time if adaptive join operator switches to bind join for each relation which has a common attribute with R i . The algorithm chooses the relation with minimum estimated bind join cost, called R j , and compares the estimated remaining time if it changes the join method as bind join for R i ⋊ ⋉R j with the estimated remaining time if the operator continues with multi-way symmetric hash join for all relations. The above procedure is repeated every time a relation is completely received.

Algorithm 2. Adaptive Join Operator for Multi-join Queries Join Cardinality Estimation and Remaining Time Estimations. We use the same formula to calculate the join cardinality estimation for single join queries and multi-join queries. Thus, we use Eq. 3 for join cardinality estimation for multi-join queries as well. We need this estimation in order to calculate the estimated remaining time if adaptive join operator switches to bind join or if the algorithm continues with multi-way symmetric hash join. Equation 6shows the estimated remaining time if adaptive join operator uses bind join for R i and R j , and uses multi-way symmetric hash join for the other relations which are involved in the query. |R i | is the cardinality of R i , t SQ is the time for sending one query to the SPARQL endpoint containing R j (≈ t R j arrived |R j arrived | ), |R i ⋊ ⋉R j | is the estimated cardinality of R i ⋊ ⋉R j , |R j arrived | is the cardinality of arrived tuples of R j , t Rj arrived is the time for |R j arrived| tuples to arrive, ERT rest is the estimated remaining time for the rest of other relations to arrive and it is calculated by using Eq. 7, where k ∈ (1, ..., n) and k = i and k = j. Lastly, Eq. 7 shows the estimated remaining time if adaptive join operator continues with multi-way symmetric hash join. Completion time is equal to the maximum completion time of the relations which compose the query.

1 S ←-{R 1 , R 2 , R 3 , ..., R n } 2 M IN ERT BJ ←-∞ 3 BJ Candidate ←-Φ 4 Start M SHJ(S)
ERT BJ R ij = max (|R i | • t SQ + |R i ⋊ ⋉R j | • t Rj arrived |R j arrived | ); ERT rest (6)
ERT M SHJ = max (|R k | -|R k arrived |) • t Rk arrived |R k arrived | where k ∈ (1, ..., n) (7)
3 Performance Evaluation

In this section, we present the evaluation results on the performances of symmetric hash join/multi-way symmetric hash join, bind join and adaptive join operator for single join queries and for multi-join queries. The reason of comparing our proposal with symmetric hash join and bind join is as follows. Bind join is the most popular join method in query federation engines and symmetric hash join provides efficient response time by being a non-blocking join method [START_REF] Oguz | Federated query processing on linked data: a qualitative survey and open challenges[END_REF]. As stated in the previous sections, the goal of the query optimization in query federation is to minimize the response time and the completion time. For this reason, we use response time and completion time as the evaluation metrics. Query cost in distributed environment is mainly defined by communication cost. In order to simulate the real network conditions and consider only the communication cost, we conducted our experiments in the network simulator ns-3 1 . We assume that the size of all queries is the same and each result tuple is considered to have the same size, as well. Each query size is accepted as 500 bytes whereas each result tuple size is employed as 250 bytes. Each count query size is assumed as 750 bytes and the message size is set to 100 tuples. Each selectivity factor is 0.5/ max(cardinality of R1, cardinality of R2) [START_REF] Shekita | Multi-join optimization for symmetric multiprocessors[END_REF]. We set the low, medium and high cardinality as 1000 tuples, 5000 tuples and 10000 tuples respectively.

1 https://www.nsnam.org/.

Performance Evaluation for Single Join Queries

In this subsection, we compare adaptive join operator (AJO) with symmetric hash join (SHJ) and bind join (BJ) in two cases. We aim to show the impact of data sizes in the first case whereas we focus on the effect of different data arrival rates in the second case.

Impact of Data Sizes. The behaviors of the SHJ, BJ and AJO are analyzed when the data arrival rates of both endpoints are fixed to 0.5 Mbps and the delays to 10 ms while the data sizes of R1 and R2 are changed. In order to analyze all conditions, we evaluated the response time and the completion time when the data sizes of R1 and R2 are low-low (LL); low-medium (LM); low-high (LH); medium-low (ML); medium-medium (MM); medium-high (MH); high-low (HL); high-medium (HM) and high-high (HH) respectively.

As Fig. 1a shows, BJ has the worst response time for all conditions whereas SHJ and AJO behave similar to each other. As the data sizes of R1 increases, the response time of BJ increases as well due to waiting for the arrival of all results of R1 and sending them to the endpoint of R2. On the other hand, SHJ and AJO can generate the first result tuple as soon as there is a match between R1 and R2, without waiting for all tuples of R1 to arrive. As shown in Fig. 1b, the completion time of BJ is shorter than others when the cardinality of R1 is low and the cardinality of R2 is medium or high. On the other hand, SHJ and AJO perform better than BJ in seven of nine conditions. AJO's completion time is the best when the cardinality of R1 is medium or high and the cardinality of R2 is low. Also, AJO's completion time is faster than SHJ's when the cardinality of R1 is low and the cardinality of R2 is medium or high.

The speedup2 values between AJO and SHJ can be seen in Fig. 1c. Although they have almost the same response time for all cases, the completion time of AJO is 3 times as fast compared to SHJ when one of the relation's cardinality is high and the other one's is low. As shown in Fig. 1d, AJO can provide speedup in response time from 5.9 times to 45.5 times compared to BJ. AJO also provides speedup in completion time up to 6 times except two cases.

Impact of Data Arrival Rates. In this case, we fixed the data arrival rate of R1 to 2 Mbps and changed the data arrival rate of R2. We conducted the simulations for two different cardinality options: (i) low cardinality of R1 and high cardinality of R2; (ii) high cardinality of R1 and low cardinality of R2.

Low Cardinality of R1 and High Cardinality of R2. As Fig. 2a shows, the response time of BJ is always longer than SHJ and AJO. The gap between the response times of BJ and the others increases when the data arrival rate of R2 gets slower. As shown in Fig. 2b, the completion time of BJ is better than As shown in Fig. 3b, the completion times of SHJ and AJO are shorter than the completion time of BJ in all of the conditions because the first relation's cardinality is high. AJO performs better than SHJ in all the cases. Compared to SHJ, AJO has almost the same response time, however the speedup in completion time varies from 1.4 times to 2.2 times as shown in Fig. 3c. Compared to BJ, AJO improves both the response time and the completion time as illustrated in Fig. 3d. The speedup in response time increases from 11 times to 34.3 times while the speedup in completion time varies from 2.8 to 6.2 times.

Performance Evaluation for Multi-Join Queries

In this subsection, we compare AJO with multi-way symmetric hash join (MSHJ) and BJ when there are three relations in the query. A query example that we use in our experiments is shown below. R1 (service1) and R2 (service2) have a common attribute, ?student, R2 and R3 (service3) have a common attribute, ?course.

SELECT ?student ?level ?course ?instructorName WHERE { SERVICE <:service1> { ?student :name :studentName . ?student :level ?level . } SERVICE <:service2> { ?student :enroll ?course . } SERVICE <:service3> { ?course :instructor ?instructorName . } } Impact of Data Sizes. We fixed the data arrival rates of all relations to 0.5 Mbps and the delays to 10 ms. We conducted our experiments when the data sizes of R1, R2, R3 are low-low-high (LLH); low-medium-high (LMH); and lowhigh-high (LHH).

As Fig. 4a shows, the response times of MSHJ and AJO are almost the same whereas BJ's response time is substantially slower. BJ's completion time is the fastest as illustrated in Fig. 4b, because the first relation's cardinality is low. However, AJO's completion time is much better than MSHJ and close to BJ's. BJ's both response time and completion time would increase, if the first relation's cardinality were medium or high.

As shown in Fig. 4c, compared to MSHJ, AJO has almost the same response time, however it can provide speedup in completion time up to 2.3 times. Speedup values between AJO and BJ can be seen in Fig. 4d Compared to BJ, AJO degrades completion time up to 0.85 times, however it can improve the response time up to 5.75 times.

Impact of Data Arrival Rates. In order to show the impact of data arrival rates on MSHJ, BJ and AJO, we fixed the data arrival rates of R1 and R3 to 2 Mbps and changed the data arrival rate of R2. We conducted the simulations for two different cardinality options: (i) low cardinality of R1, high cardinality of R2, and low cardinality of R3 (LHL); (ii) low cardinality of R1, high cardinality of R2 and R3 (LHH).

Low Cardinality of R1, High Cardinality of R2, Low Cardinality of R3.

Related Work

Adaptive query optimization [START_REF] Deshpande | Adaptive query processing[END_REF] responds to the unforeseen variations of runtime environment to provide a better response time or more efficient CPU utilization. In our concept, the run-time environment is on the web and the main objective is to minimize the response time and the completion time. Thus, adaptive query optimization is a need to manage the changing conditions of the web. Although, adaptive query optimization is a new research area for linked data, it has been studied in detail in relational databases. Evolutionary methods which provide inter-operator adaptation, focus on generating plans that can be switched during execution according to delays or estimation errors. Query scrambling [START_REF] Amsaleg | Dynamic query operator scheduling for wide-area remote access[END_REF], mid-query re-optimization [START_REF] Kabra | Efficient mid-query re-optimization of sub-optimal query execution plans[END_REF], Tukwilla/ECA rules [START_REF] Ives | An adaptive query execution system for data integration[END_REF], progressive query optimization [START_REF] Markl | Robust query processing through progressive optimization[END_REF][START_REF] Kache | POP/FED: progressive query optimization for federated queries in DB2[END_REF][START_REF] Han | Progressive optimization in a shared-nothing parallel database[END_REF] and proactive re-optimization [START_REF] Babu | Proactive re-optimization[END_REF] are some known examples of evolutionary methods. On the other hand, revolutionary methods provide intra-operator adaptation. First group of intra-operator methods are adaptive operators like double hash join [START_REF] Ives | An adaptive query execution system for data integration[END_REF], XJoin [START_REF] Urhan | XJoin: a reactively-scheduled pipelined join operator[END_REF] and mobile join [START_REF] Arcangeli | Mobile agent based selfadaptive join for wide-area distributed query processing[END_REF][START_REF] Ozakar | Mobile join operators for restricted sources[END_REF], where the operator itself is able to adapt its way of execution according to variations encountered during its execution. Second group of intra-operator methods optimize the query processing in tuple level [START_REF] Avnur | Eddies: continuously adaptive query processing[END_REF][START_REF] Raman | Using state modules for adaptive query processing[END_REF][START_REF] Deshpande | An initial study of overheads of eddies[END_REF][START_REF] Deshpande | Lifting the burden of history from adaptive query processing[END_REF][START_REF] Bizarro | Content-based routing: different plans for different data[END_REF][START_REF] Zhou | An adaptable distributed query processing architecture[END_REF].

Another work for distributed database environment is also quite relevant to our work. Khan et al. [START_REF] Khan | An adaptive probe-based technique to optimize join queries in distributed internet databases[END_REF] propose an adaptive probing mechanism to have statistics about the data and choose the optimal execution plan during query execution. Compared to our work, the probe phase of their method delays the response time since the first result tuple is generated before the end of probing and decision for adaptability.

When we look at the adaptive methods of query federation engines on linked data, we see only two adaptive methods, intra-operator adaptivity of ANAP-SID [START_REF] Acosta | ANAPSID: an adaptive query processing engine for SPARQL endpoints[END_REF] and inter-operator adaptivity of ADERIS [START_REF] Lynden | ADERIS: an adaptive query processor for joining federated SPARQL endpoints[END_REF]. ANAPSID focuses on the problem of bursty data traffic and endpoint unavailability. In order to overcome these problems, ANAPSID implements a non-blocking join method which is based on symmetric hash join [START_REF] Wilschut | Dataflow query execution in a parallel mainmemory environment[END_REF] and XJoin [START_REF] Urhan | XJoin: a reactively-scheduled pipelined join operator[END_REF]. The proposed method continues to produce new results when one of the endpoints becomes blocked. ADERIS generates predicate tables for each predicate which cover the related subjects and objects of that predicate. The first version of ADERIS [START_REF] Lynden | Adaptive integration of distributed semantic web data[END_REF] joins two predicate tables as they become complete while the other predicate tables are being generated. In the second version, Lynden et al. [START_REF] Lynden | ADERIS: an adaptive query processor for joining federated SPARQL endpoints[END_REF] propose an adaptive cost model to determine the join order. In other words, ADERIS uses adaptive query optimization by changing the join order during the execution. In addition to these studies, Basca and Bernstein [START_REF] Basca | Avalanche: putting the spirit of the web back into semantic web querying[END_REF] propose a technique which gathers statistics on the fly before query execution. It produces only the first k results. In addition, Verborgh et al. [START_REF] Verborgh | Querying datasets on the web with high availability[END_REF] and Acosta et al. [START_REF] Acosta | Networks of linked data eddies: an adaptive web query processing engine for RDF data[END_REF] focus on adaptive query optimization for triple pattern fragments. However, triple pattern fragments are beyond the scope of this paper.

Intra-operator adaptivity of ANAPSID and inter-operator adaptivity of ADERIS have showed that adaptive query optimization is well suited to unpredictable characteristics of linked data environment. Although they provide adaptive solutions for query federation, none of them use adaptive query optimization in order to change the join method during the execution according to the data arrival rates to minimize both response time and completion time at the same time.

In this paper, we presented an adaptive join operator for single join queries and multi-join queries which aims to minimize both response time and completion time. It begins with symmetric hash join in order to provide optimal response time and changes the join method to bind join when it decides that bind join is more efficient than symmetric hash join for the rest of the query.

The results of the performance evaluation have shown the efficiency of the proposed adaptive join operator. It has almost the same response time with symmetric hash join and multi-way symmetric hash join, but it provides faster completion time. Compared to bind join, adaptive join operator performs substantially better with respect to the response time and can also improve the completion time. Bind join can provide slightly better completion time than adaptive join operator when the first relation's cardinality is low.

In conclusion, adaptive join operator provides both optimal response time and completion time for single join queries and multi-join queries. It performs quite well both in fixed and different data arrival rates. We plan to make experiments with more joins. We are also motivated to consider the case where a relation is distributed over multiple sources.

Algorithm 1 . 8 ERT 9 ERT

 189 Adaptive Join Operator for Single Join Queries 1 |R1| ←-cardinality of R1 received f rom the COU N T query 2 |R2| ←-cardinality of R2 received f rom the COU N T query 3 |R1 arrived | ←-cardinality of arrived R1 tuples 4 |R2 arrived | ←-cardinality of arrived R2 tuples 5 Set JOIN method as Symmetric Hash Join (SHJ) 6 while (|R1 arrived | < |R1| or |R2 arrived | < |R2|) do 7 if (|R1 arrived | == |R1| and |R2 arrived | < |R2| or |R2 arrived | == |R2| and |R1 arrived | < |R1|) then SHJ ←-estimated remaining time if continued using SHJ BJ ←-estimated remaining time if switched to Bind Join (BJ) 10 if (ERT SHJ > ERT BJ ) then 11 Set JOIN method as BJ 12 Emit the duplicate results of SHJ and BJ 13 end 14 end 15 end

Fig. 1 .

 1 Fig. 1. Data arrival rates of R1 and R2 are fixed

Fig. 2 .Fig. 3 .

 23 Fig. 2. Data sizes of R1 and R2 are fixed with card(R1) ≪ card(R2)

  Figure 5a. shows that BJ performs worser response time than MSHJ and AJO in this case as well. As can be seen from Fig. 5b, BJ's completion time is faster than MSHJ because the first relation's cardinality is low. On the other hand, AJO performs the best in seven of nine cases due to having the adaptation ability. Compared to MSHJ, AJO has almost the same response time but it can provide speedup in completion time up to 3.4 times as shown in Fig. 5c. Compared

Fig. 4 .Fig. 5 .

 45 Fig. 4. Data arrival rates of R1, R2 and R3 are fixed

Fig. 6 .

 6 Fig. 6. Data sizes of R1, R2 and R3 are fixed with card(R1) ≪ card(R2) = card(R3)

Speedup of x compared to y (response time) = response time of y / response time of x Speedup of x compared to y (completion time) = completion time of y / completion time of x.

Acknowledgment. This work is partially supported by The Scientific and Technological Research Council of Turkey (TUBITAK).


Aldo Gonzalez-Lorenzo

Alexandra Bac

Jean-Luc Mari

Pedro Real

Two Measures for the Homology Groups of Binary Volumes

Given a binary object (2D or 3D), its Betti numbers characterize the number of holes in each dimension. They are obtained algebraically, and even though they are perfectly defined, there is no unique way to display these holes. We propose two geometric measures for the holes, which are uniquely defined and try to compensate the loss of geometric information during the homology computation: the thickness and the breadth. They are obtained by filtering the information of the persistent homology computation of a filtration defined through the signed distance transform of the binary object.

Introduction

Homology computation is a very useful tool for the classification and the understanding of binary objects in a rigorous way. It provides a class of descriptors summarizing the basic structure of the considered shape.

A binary object is a set X ⊂ Z d together with a connectivity relation. We will assume through this paper that X is a volume (d = 3) and the elements of X will be called voxels. However, the generalization to higher dimensions is direct.

Roughly speaking, homology deals with the "holes" of an object. Holes can be classified by dimensions: 0-holes correspond to connected components, 1-holes to tunnels or handles and 2-holes to cavities. When computing homology, we usually expect to find the number of these holes (called the Betti numbers) and a representative of each hole (called representative cycle of a homology generator). Nevertheless, the homology computation works at an abstract level (the chain complex) which ignores the embedding of the object. Thus, the geometry of the object is in some way neglected.

Moreover, holes are difficult to visualize. We can know how many they are, but not where they are. This is due to the fact that in homology computation, a choice for determining a linearly independent set of holes must be done. This is something difficult to apprehend: for instance, we remind that a cube with its interior and faces removed (as depicted in Fig. 1) contains five 1-holes instead of six.

The aim of this paper is to endow Betti numbers with an additional information containing a geometric interpretation. We define two measures-thickness and breadth-which, unlike homology generators, are uniquely determined by the object and can be used as concise topology descriptors. They are obtained through the persistent homology of the filtration induced by the signed distance transform of the volume.

Previous efforts have been made to combine homology and geometry. We cite herein some works that are related to our problem. Erickson and Whittlesey founded an algorithm in [START_REF] Erickson | Greedy optimal homotopy and homology generators[END_REF] that computes the shortest base for the first homology group for oriented 2-manifolds. Dey et al. [START_REF] Dey | An efficient computation of handle and tunnel loops via Reeb graphs[END_REF] developed a similar work, but also classifying the 1-holes into tunnels and handles. Chen and Freedman [CF10] measured the 1-holes of a complex by the "length" of the homology generators and they also gave an algorithm to compute the smallest set of homology generators. Zomorodian and Carlsson introduced the localized homology in [START_REF] Zomorodian | Localized homology[END_REF], which allows to locate each homology class in a subset of a given cover. This cover, or collection of subcomplexes whose union contains the complex, successfully give a geometric sense to the Betti numbers.

Contributions

We define two geometric measures that enrich the Betti numbers of a binary volume. They are uniquely defined up to a choice of connectivity relation and distance. They can be computed through a distance transform and persistent homology, so it has matrix multiplication complexity over the number of voxels in the bounding box of the volume. These measures can be considered as pairs of numbers associated to each homology generator but also visualized as threedimensional balls on the volume.

Preliminaries

Cubical Complexes and Homology

Cubical Complex -This section is derived from [KMM04]. For a deeper understanding of these concepts, the reader can refer to it. An elementary interval is an interval of the form [k, k + 1] or a degenerate interval [k, k], where k ∈ Z. An elementary cube in R n is the Cartesian product of n elementary intervals, and the number of non-degenerate intervals in this product is its dimension. An elementary cube of dimension q will be called q-cube.

Given two elementary cubes σ and τ , we say that σ is a face of τ if σ ⊂ τ . It is a primary face if the difference of their dimensions is 1. Similarly, σ is a coface of τ if σ ⊃ τ . A cubical complex is a set of elementary cubes with all of their faces. The boundary of an elementary cube is the collection of its primary faces.

Chain Complex -A chain complex (C * , d * ) is a sequence of groups C 0 , C 1 , . . . (called chain groups) and homomorphisms d 1 : C 1 → C 0 , d 2 : C 2 → C 1 , . . . (called differential or boundary operators) such that d q-1 d q = 0, ∀q > 0.
Given a cubical complex, we define its chain complex as follows:

-C q is the free group generated by the q-cubes of the complex; -d q gives the "algebraic" boundary, which is the linear operator that maps every q-cube to the sum of its primary faces.

The elements of the chain group C q , which are formal sums of q-cubes with coefficients in Z 2 , are called q-chains. They can be seen as sets of cubes of the same dimension.

Homology Groups -A q-chain x is a cycle if d q (x) = 0, and a boundary if x = d q+1 (y) for some (q+1)-chain y. By the property d q-1 d q = 0, every boundary is a cycle, but the reverse is not true: a cycle which is not a boundary contains a "hole". The q-th homology group of the chain complex (C * , d * ) contains the qdimensional "holes": H(C) q = ker(d q )/im(d q+1 ). This set is a finitely generated group, so there is a "base" typically formed by the holes of the cubical complex. Since our ring of coefficients is Z 2 , this group is isomorphic to Z βq and β q is the q-th Betti number.

Cubical complex associated to a binary volume -Given a binary volume, we can define two different associated cubical complexes encoding the 6 or the 26connectivity relation.

-Primal associated cubical complex (26-connectivity): every voxel

x = (x 1 , x 2 , x 3 ) generates the 3-cube [x 1 , x 1 + 1] × [x 2 , x 2 + 1] × [x 3 , x 3 + 1]
and all its faces. -Dual associated cubical complex (6-connectivity): let us first adapt the notion of clique to our context. A d-clique is a maximal (in the sense of inclusion) set of voxels such that their intersection is a d-cube. First, for every voxel (in fact 3-clique) x = (x 1 , x 2 , x 3 ) of the volume, we add the 0-cube

σ = [x 1 ] × [x 2 ] × [x 3 ].
Then, for every d-clique (d < 3) in the volume, we add to the cubical complex a (3 -d)-cube such that its vertices are the voxels of the d-clique.

These cubical complexes can be defined for any dimension. Figure 2 illustrates both complexes.

Fig. 2. Left: a binary volume. Center: its primal associated cubical complex. Right: its dual cubical complex

Persistent Homology

This section introduces the persistent homology. A more rigorous presentation can be found in [START_REF] Edelsbrunner | Persistent homology -a survey[END_REF] and the references therein.

A filtration is a finite (or countable) sequence of nested cubical complexes

X 1 ⊂ X 2 ⊂ • • • X n .
It can also be described by a function f on the final complex X n , which assigns to each q-cube the first index at which it appears in the complex. Since it is a sequence of cubical complexes, a cube cannot appear strictly before its faces, so the function f must verify

f (σ) ≤ f (τ ), ∀σ ⊂ τ (1)
Therefore, a function f : X → R defined over a cubical complex is a filtration function if its image is a finite (or countable) set and if it satisfies Eq. ( 1). Given such a function, its filtration is the sequence

F f (X) = {X i } n i=0 , where a 0 < a 1 < • • • < a n are the images of f and X i = f -1 (]-∞, a i ]).
As illustrated in Fig. 3, the homology groups of the complex can evolve as "time" goes on. The persistence diagram [EH08, p. 3] records these changes: a q-hole being born in X i and dying (or vanishing) in X j is represented in the persistence diagram as the point (i, j). This is also called a P -interval in [START_REF] Zomorodian | Computing persistent homology[END_REF]. A homology generator of X n , which never dies, is represented by the point (i, ∞). The reader can find some persistence diagrams in Sect. 4. Persistent homology can also be visualized in terms of barcodes [START_REF] Ghrist | Barcodes: The persistent topology of data[END_REF], where each point (i, j) is represented as an interval in the real line.

We can assign a pair of cubes (σ i , σ j ) to each P -interval (i, j). The first cube creates the hole (e.g., a point in a new connected component or the edge that closes a handle) while the second one merges the hole into the set of boundaries (e.g., the edge that connects two connected components, or the square that fills a handle). The reader could try to find these pairs of cubes in the filtration described in Fig. 3.

There has been an extensive research in the computation of persistent homology. An algorithm in matrix multiplication time was introduced in [START_REF] Milosavljević | Zigzag persistent homology in matrix multiplication time[END_REF]. The algorithms present in [START_REF] Zomorodian | Computing persistent homology[END_REF][START_REF] Mischaikow | Morse theory for filtrations and efficient computation of persistent homology[END_REF] have cubical worst-time complexity, but they seem to behave better in practice. An algorithm adapted for cubical complexes was developed in [START_REF] Wagner | Efficient computation of persistent homology for cubical data[END_REF].

X 1 X 2 X 3 X 4
Fig. 3. A filtration. X1: there are two 0-holes (connected components). X2: one 0-hole dies. X3: a 1-hole is born. X3: that 1-hole dies.

Note that in this article we do not use Čech, Vietoris-Rips nor Alpha complexes, as it is usually done in the persistent homology literature. The filtrations considered are based on a function defined over a cubical complex.

Distance Transform

Given a binary volume X ⊂ Z 3 , its distance transform DT X is the map that sends every voxel x ∈ X to DT X (x) = min y∈Z 3 \X d(x, y). It can be seen as the radius of the maximal ball centered at x and contained in X. Note that we must consider one specific distance for the volume: L p metrics such as the Manhattan distance (L 1 ), the Euclidean distance (L 2 ) or the chessboard distance (L ∞ ); distances based on chamfer masks [START_REF] Montanari | A method for obtaining skeletons using a quasi-Euclidean distance[END_REF][START_REF] Borgefors | Distance transformations in arbitrary dimensions[END_REF] or sequences of chamfer masks [MDKC00,NE09], etc.

There exist linear time algorithms for computing the Euclidean distance on nD binary objects [BGKW95,Hir96,MRH00,MQR03].

We can then consider the signed distance transform, which maps every voxel x ∈ X to -DT X (x) and x / ∈ X to DT Z 3 \X (x).

3 The Two Measures

Motivation

The main motivation for this work comes from the desire of comparing binary volumes obtained from real acquisition of complex structures. Using mere Betti numbers for this objective can be ineffective, so we thought of enhancing this basic homological information by defining two geometry-aware measures for the holes.

In the following we give an intuitive introduction to the two new measures. We consider two binary images which are repeatedly eroded and dilated respectively, and we comment what happens to their homology groups. Then we figure out how we can treat this problem with persistent homology.

When we erode the image in Fig. 4-(a), we observe that a 1-hole disappears (Fig. 4-(b)), a 0-hole is created (Fig. 4-(c)) and a 0-hole disappears (Fig. 4-(d)). Thanks to persistent homology, we can record these events. Given a binary volume

X ⊂ [0, m 1 ] × [0, m 2 ] × [0, m 3 ] ⊂ Z 3 , we build the associated primal (or dual) cubical complex K of the bounding box [0, m 1 ] × [0, m 2 ] × [0, m 3 ].
Then we compute a filtration function f associated to the signed distance transform of X: the 3-cubes (0-cubes) are mapped to the value of their associated voxels (cf. Sect. 2.1). The image of the rest of the cubes is coherently assigned in order to produce a filtration, that is, each q-cube, for 0 ≤ q ≤ 2 (1 ≤ q ≤ 3), takes the minimum (maximum) value of its 3-dimensional cofaces (0-dimensional faces).

Let a 0 < a 1 < • • • < a i = 0 < • • • < a n be the different values of f over the volume. Thus, we can consider the filtration F f (K):

X 0 = f -1 (]-∞, a 0 ]) ⊂ • • • ⊂ X ⊂ • • • ⊂ X n = f -1 (]-∞, a n ])
Let us now see how the previously described phenomena are encoded in the persistent homology of the filtration F f (K). Note that the eroded images are now seen in reversed time:

-Fig. 4-(b): a 1-hole is born in negative time (1b-); -Fig. 4-(c): a 0-hole dies in negative time (0d-); -Fig. 4-(d): a 0-hole is born in negative time (0b-); -Fig. 4-(f): a 1-hole is born in positive time (1b+); -Fig. 4-(g): a 0-hole dies in positive time (0d+); -Fig. 4-(h): a 1-hole dies in positive time (1d+); Since we are interested in the homology groups of the given volume, we only consider the persistent intervals that start at negative time and finish at positive time. We can give an intuitive and physical interpretation to those events. 0b-A 0-hole being born at time t 0 < 0 means that the maximal ball included in that connected component has radius -t 0 ; 0d+ A 0-hole dying at time t 0 > 0 means that the shortest distance between that connected component and any other is 2 • t 0 ; 1b-A 1-hole being born at time t 0 < 0 means that -t 0 is the smallest radius needed for a ball included in X that, once removed, breaks or vanishes that hole; 1d+ A 1-hole dying at time t 0 > 0 means that the maximal ball that can pass through that hole has radius t 0 ; 2b-Same as 1b-; 2d+ A 2-hole dying at time t 0 > 0 means that the maximal ball that can fit inside that hole has radius t 0 ;

Thus, for q = 1, 2, the time t at which a q-hole is born can be seen as the thickness of the hole, or how far it is from being destructible. We will call it thickness. Also, the time t at which a q-hole dies can be interpreted as a kind of size or breadth. We choose this second term, since the size of a 2-hole is better understood as the volume it covers or the area of its boundary. These two terms are not suitable for dimension 0, so we use the terms breadth (again) and separability respectively.

Definitions

Let X ⊂ [0, m 1 ] × [0, m 2 ] × [0, m 3 ] ⊂ Z 3 be a binary volume and d : Z 3 → R + a distance. Consider the signed distance transform sDT X (x) = -min{d(x, y) : y / ∈ X} , x ∈ X min{d(x, y) : y ∈ X} , x / ∈ X
Depending on which connectivity relation we use for the volume, we build its associated cubical complex K (cf. Sect. 2.1) and the filtration function f X induced by sDT X (cf. Sect. 3.1).

The thickness and breadth of the q-holes of X are the pairs {(-i k , j k )} βq k=1 , where {(i k , j k )} βq k=1 are the P -intervals of the filtration f X such that i k < 0 and j k > 0 for all 1 ≤ k ≤ β q . We can represent these pairs as points in R 2 in the thickness-breadth diagram.

The final step of the filtration is the full cubical complex associated to the bounding box of the volume. If the volume is not empty, as the bounding box has one connected component there exists a P -interval (-i, ∞) of dimension 0. We will represent this thickness-breadth pair as (-i, -1) in the thicknessbreadth diagram. As a consequence, a volume has β 0 -1 separation values. This is coherent with its interpretation, as there are only n -1 shortest distances between n objects.

Note that the thickness-breadth pairs are uniquely defined for the filtration and they only depend on the connectivity relation of the volume and the distance considered.

Visualization

The breadth and thickness values of a volume can be visualized in terms of balls, as it was suggested in Sect. 3.1. Given a thickness-breadth pair (i, j) with its (non-unique) associated pair of cubes (σ, τ ) (cf. Sec. 2.2), we can also assign a pair of voxels (p, q) to them. For the primal (dual) associated cubical complex, according to its construction (cf. Sect 2.1), we choose any coface of dimension 3 (face of dimension 0) with the same image under f for each cube and we take its associated voxel in the original volume. We call these voxels, which are not unique, v(i) and v(j).

Therefore, for each hole we can visualize its thickness by the ball centered at v(i) with radius i, and similarly for its breadth. Figure 5 illustrates this procedure.

Results

Our implementation for computing the breadth and the thickness uses the DGtal library [DGt] for the distance transform and the Perseus software [Nan] for the persistent homology. In order to obtain the centers of the balls, we developed a specific software. The following volumes were voxelized with the Binvox software [START_REF] Min | 3D mesh voxelizer[END_REF][START_REF] Nooruddin | Simplification and repair of polygonal models using volumetric techniques[END_REF].

Figure 6 shows some examples of thickness-breadth diagrams. For each binary volume, we show the diagram containing the thickness-breadth pairs of the homology groups H 0 (red circles), H 1 (green triangles) and H 2 (blue squares). Note that we represent the pairs (i, ∞), associated to the "broadest" connected component of the volume, as (i, -1).

We can appreciate the fractal structure of the Menger sponge after three iterations in its diagram. There are only three possible values for the breadth and the thickness: (1, 3 0 +1

2 ), (1, 3 1 +1 2 ) and (1, 3 3 +1 2 ). For the lamp [START_REF] Reynolds | Radiant blossom[END_REF], we can easily recognize a lot of similar holes and a bigger one, which traverses the volume along the z-axis. The small 2-hole follows from a discretization error. The diagram of the Colosseum volume [START_REF] Gaspard | Roman colosseum completley detailed see the world[END_REF] presents a regular shape. All the 1-holes (i.e., the doors) have similar measures, except for one which has greater thickness. It corresponds to the ground floor concentric corridor.

Figure 7 illustrates the pertinence of the visualization described in Sect. 3.3. More examples are available on [GL].

Conclusion and Future Work

This paper introduces a concise and rigorous geometrical and topological information for binary volumes that extends the Betti numbers. This could be used for a statistical analysis of the volume or a better understanding of its topological features.

An interesting issue that should be addressed in the near future is the stability of this definition. Are the breadth and thickness stable under small perturbations of the volume? How much do these values change when we consider different connectivity relations or distances?

In addition, it seems that the intersection of the thickness and breadth balls with the volume could provide a heuristic for computing geometry-aware homology and cohomology generators.

Fig. 1 .

 1 Fig. 1. There are only five 1-holes in this object, and there is no natural way to state where they are.

Fig. 4 .

 4 Fig. 4. Two images being eroded and dilated. We can notice a change in its homology at every step.

Fig. 5 .

 5 Fig. 5. Example of visualization of the thickness and the breadth through balls. Top: a binary image (a) with the balls of H0 (b) and H1 (c). Bottom: a binary volume (d) which contains two chained volumetric tori, its breadth (e) and its thickness balls (f) of dimension 0 and 1.

Fig. 6 .

 6 Fig. 6. Left: three binary volumes. Right: their thickness-breadth diagrams. 0-holes are represented by red circles, 1-holes by green triangles and 2-holes by blue squares.

Fig. 7 .

 7 Fig. 7. Examples of thickness (red) and breadth (green) balls. Top: Fertility volume, available by AIM@SHAPE with the support of M. Couprie. Bottom: Menger sponge, available on [GL].


Kunal Suri
email: kunal.suri@cea.frarnaudcuccuruarnaud.cuccuru@cea.fr

Arnaud Cuccuru

Juan Cadavid
email: juan.cadavid@cea.fr

Sébastien Gérard

Walid Gaaloul
email: walid.gaaloul@telecom-sudparis.eu

Samir Tata
email: samir.tata@telecom-sudparis.eu

Sebastien Gerard
email: sebastien.gerard@cea.fr

Model-based development of

come

Approach

CONTACT INFORMATION

 Separation between the model-based behavior layer and system firmware  Simulation of the system using standardized models (verification)

 Execution of the system (robot) using API calls via executing already verified models Research Objectives