Multi-tenant DBMSs are used by cloud providers for their Database-as-a-Service products. They could be single-node DBMSs installed in virtual machines, SQL-on-Hadoop systems or classic parallel relational DBMSs running on top of a shared-nothing or shared-disk architecture. For a cloud provider, it is interesting to measure these systems’ capability of dealing with multi-tenant workloads, i.e., taking advantage of the statistical multiplexing to obtain economic gain while being attractive by providing a good quality of service and a low bill to the tenants. In this paper, we present MTD-DS benchmark (with MTD for Multi-Tenant parallel DBMSs and DS for Decision Support). MTD-DS extends TPC-DS by adding a multi-tenant query workload generator, a performance Service Level Objectives generator, configurable Database-as-a-Service pricing models, and new metrics to measure the potential capability of a multi-tenant parallel DBMS in obtaining the best trade-off between the provider's benefit and the tenants’ satisfaction. Example experimental results have been produced to show the relevance and the feasibility of the MTD-DS benchmark.

A recent trend among major organisations is to release their datasets in the cloud over various Database-as-a-Service (DBaaS) providers’ premises, creating a use case for multi-cloud querying. As identified in the literature, middlewares with such capabilities should quote the monetary cost and the response time of the queries in order to gain the trust of their users, and also optimise the queries so as to avoid cost overruns and meet the quotations. Considering those requirements, this paper introduces an accurate cost model and an efficient execution plan search strategy for dealing with large-scale multi-cloud queries. The former is an ensemble learning stack leveraging online machine learning models, and the latter is a randomised method inspired by iterative improvement. We evaluated our middleware over simulated providers by using the Join Order Benchmark. Experiments showed that the cost model manages to correct the estimations from the providers. The randomised strategy can produce more efficiently execution plans that yield better performances and a lower monetary cost compared to an exhaustive approach from previous work.

The provision of public data through various Database-as-a-Service (DBaaS) providers has recently emerged as a significant trend, backed by major organisations. This paper introduces Nebula, a non-profit middleware providing multi-cloud querying capabilities by fully outsourcing its users' queries to the involved DBaaS providers. First, we propose a quoting procedure for those queries, whose need stems from the pay-per-query policy of the providers. Those quotations contain monetary cost and response time estimations, and are computed using provider-generated tenders. Then, we present an agent-based dynamic optimisation engine that orchestrates the outsourced execution of the queries. Agents within this engine cooperate in order to meet the quoted values. We evaluated Nebula over simulated providers by using the Join Order Benchmark (JOB). Experimental results showed Nebula's approach is, in most cases, more competitive in terms of monetary cost and response time than existing work in the multi-cloud DBMS literature.

In the cloud context, users are often called tenants. A cloud DBMS shared by many tenants is called a multi-tenant DBMS. The resource consolidation in such a DBMS allows the tenants to only pay for the resources that they consume, while providing the opportunity for the provider to increase its economic gain. For this, a Service Level Agreement (SLA) is usually established between the provider and a tenant. However, in the current systems, the SLA is often defined by the provider, while the tenant should agree with it before using the service. In addition, only the availability objective is described in the SLA, but not the performance objective. In this paper, an SLA negotiation framework is proposed, in which the provider and the tenant define the performance objective together in a fair way. To demonstrate the feasibility and the advantage of this framework, we evaluate its impact on query optimization. We formally define the problem by including the cost-efficiency aspect, we design a cost model and study the plan search space for this problem, we revise two search methods to adapt to the new context, and we propose a heuristic to solve the resource contention problem caused by concurrent queries of multiple tenants. We also conduct a performance evaluation to show that, our optimization approach (i.e., driven by the SLA) can be much more cost-effective than the traditional approach which always minimizes the query completion time.

Resource allocation is one of the principal stages of query processing in relational data grid systems. Specific characteristics of the data grid environment, such as dynamicity, heterogeneity and large scale, impose serious restrictions to the resource allocation process. Static resource allocation before the query execution may be far from optimal due to the dynamic changes of the system. One possible optimization is to adjust dynamically the allocation of resources during the query execution. Some methods of dynamic resource allocation have been proposed, however, most of them use centralized control mechanisms. In this study we argue that the decentralized approach meets better the requirements of the data grid systems. In this study we propose a decentralized method of dynamic resource allocation that is based on the mobile agent paradigm. We consider the participating nodes as autonomous and independent elements of the system, each of which can detect if it is overloaded and make the decision to react. Then we consider each relational operation as a mobile agent running on the allocated node, meaning that, it keeps track of its own status and can migrate to another node at any time. A two-level cooperation mechanism between such autonomous nodes and autonomous operations is described in detail. Performance evaluation proves the efficiency of the proposed method.

Grid systems become very popular during the last decade because of their rapidly increasing computational capabilities. On the other hand, the advances on different domains cause enormous increase in the scale of the manipulated data. This issue augments the importance of distributed query processing and causes researchers to port their underlying environment onto the grid systems. However the dynamicity, heterogeneity and large scale characteristics of grid systems pose new problems for the distributed query processing domain. Resource allocation for query processing in grid systems is one of these problems, which attracts many researchers' attention. In this paper, we propose a new resource allocation algorithm for one relational join operator in a query considering characteristics of the grid systems. We provide theoretical analyses of the proposed algorithm and we consolidate analyses with the simulations.

The purpose of this talk is to provide a comprehensive state of the art concerning the evolution of data management systems from uni-processor systems to large scale distributed systems. We focus our study on the query processing and optimization methods. For each environment, we recall their motivations and point out main characteristics of proposed methods, especially, the nature of decision-making (centralized or decentralized control for high level of scalability), adaptive level (intra-operator and/or inter-operator), impact of parallelism (partitioned and pipelined parallelism) and dynamicity (e.g. elasticity) of execution models.

Using Distributed Hash Tables (DHT) for resource discovery in large-scale systems generates considerable maintenance overhead. This not only increases the bandwidth consumption but also affect the routing efficiency. In this paper, we deal with resource discovery while minimizing maintenance overhead in hierarchical DHT systems. The considered resources are metadata describing the data sources. In our solution, only one gateway in one overlay is attached to the superior level overlay. It aims to reduce both lookup and maintenance costs while minimizing the overhead added to the system. We present a cost analysis for a resource discovery process and discuss capabilities of the proposed protocol to reduce the overhead of maintaining the overlay network. The analysis result proved that our design decrease significantly the maintenance costs in such systems especially when nodes frequently join/leave the system.

In Peer-to-Peer environments, the absence of a global schema makes locating data sources a real problem. Semantic and structural heterogeneity of local schemas prevent the localization phase to find relevant data sources for a given SQL query. Useless information obtained during this phase could not only lead to incorrect answers but also it is expensive in terms of resource consumption. In this paper, we propose a method integrating domain ontology into Chord protocol. This integration provides comprehensive data exchange while carrying out efficient data source localization. Before the localization phase, the terms of the given SQL query must be written according to the domain ontology which forms the only interface to interact between peers. Chord protocol is extended by Structure Indexes that describe the relation structures. The proposed method allows extended Chord protocol to select relevant data sources and to avoid useless information. We present simulation results showing the feasibility of our method and its benefits.

Since ten years, the Grid systems are hot research topics. Recently, the Grid systems open towards the management of heterogeneous and distributed data on a large-scale environment. The Grid data management raises new problems and presents real challenges: (i) resource discovery and allocation, (ii) query processing and optimization, (iii) monitoring services, (iv) replication and caching, (v) cost models, (vi) autonomic data management, and (vii) security. The main characteristics offered by these systems are: large scale (e.g. high numbers of data sources, and computing resources) and dynamicity of nodes (unstable system). The synergy and convergence of interests between Grid systems and agent systems have been clearly pointed out. To address some of the above problems, a complementary approach (with respect to web services and P2P techniques) based on mobile agents deserves to be explored. In this talk, we draw up a synthetic state of the art of using mobile agents to solve some fundamental problems of data management in grid systems (e.g. resource discovery and allocation, distributed query and optimization, monitoring services for query optimization, cost models). We point out the advantages of mobile agents and how they can help for decentralized control, and scaling.

Evaluation of distributed join queries often deals with an increasing data volume and low bandwidth in large scale environments. Several techniques were proposed to improve join performances. In this paper, we propose to use a new form of signatures, the algebraic signatures. We prove that these signatures combined to semi-join based join technique are very useful for reducing the communication cost in a distributed environment and focus in the semi-join based join operation. Semi-join based join is one of the most used techniques to decrease the communication cost on distributed architectures. We demonstrate that algebraic signatures are very useful to reduce significantly the amount of the data transfer between sites. Also, we have not any data decoding step in the site receiving these data. The performance study of our technique shows the reduction of the communication costs in the semi-join based join operation. Our technique can be deployed in large scale peer to peer or grid environments especially in a network with low bandwidth and strong latency.

This paper presents a compile-time placement method of mobile relational operators MROs in a large scale environment. MROs are self adaptive to changing runtime conditions by deciding their execution place if they discover compile-time estimation errors. Proposed placement methods tend to have a main drawback with MROs running over a large scale environment: their focus is on finding optimal performance depending on single-point estimation at compile-time, instead of optimal performance over an estimation interval. We propose: (i) to determine the migration space of a MRO including the sites on which the MRO is allowed to migrate during its execution, and (ii) to find the robust site which will allow acceptable response time in an estimation interval. Performance study shows that, with a risk of loosing around 6% in response time, it is possible to gain up to 300% with the proposed robust placement.

This paper presents briefly the aims and challenges addressed in the GGM (Grid for Geno-Medicine) project. The idea behind the project is to offer a software infrastructure able to analyze and discover links between distributed medical and genetic data.

Execution plans generated by traditional optimizers for large scale distributed queries can be sub-optimal because: the estimations are inaccurate, the data are unavailable and the execution environment is unstable. To deal with the sub-optimality, we propose to execute each relational operator of an execution plan by a mobile agent. A mobile agent can change its execution site in order to correct the sub-optimality. In this paper, we address the problem of choosing an execution site for a mobile agent among execution sites of the considered system. For this, we propose to integrate a cost model into the mobile agents. We define also the various interactions that might occur between a mobile agent and its execution site. The performance evaluation shows that the cost model embedded in the agent allows to choose the most appropriate execution site

In this article, optimization of decision support queries is considered in the context of wide-area distributed databases. An original approach based on the “mobile agent” paradigm is proposed and evaluated. Agents’ autonomy and reactivity allow operators of the execution plan to adapt dynamically to estimation errors on relations and to evolutions in the state of the execution system, avoiding time overheads commonly associated with centralized monitoring. We present decentralized self-adaptive algorithms for dynamic optimization of join operators, and their implementations in Java using mobile agents. Then, we evaluate performance depending on error rate on statistical information on database, and on communication bandwidth and CPU frequency. The results show that the agent-based approach can lead to a significant reduction of response time and provide decision criteria for developing an effective migration policy.

In this paper, we present an extension of PSA strategy (Parallel Scheduling Algorithm ), to determine an appropriate mapping of operations onto physical processors, taking into account the interconnection network topology of a sharednothing architecture. Performance evaluation, which relies on two benchmarks shows the efficiency of PSA strategy by comparing to Static Right-Deep strategy and to Bushy Tree Scheduling strategy. The major contributions of this work are (i) the incorporation of the mapping process into PSA strategy and (ii) the PSA strategy which provides a good trade-off between response time minimization and throughput maximization. 1 Introduction The problem of ESQL [9] queries optimization for parallel execution is fundamental to obtain high performance and high data availability. One way to increase optimization capacity is to improve the efficiency of generating an optimal execution plan. The design of an ESQL queries Optimizer may be decomposed into three dimension...

In this paper, we propose a method to determine parallel scheduling for SQL query operations. The parallelization strategy consists in determining a parallel scheduling based on serial methods. The criteria for operations scheduling is based on deadlines and consideration of the number of processors. Performance evaluation shows the efficiency of each type of parallelism (intra-operation and inter-operation) as a function of the number of processors.