Numerous databases marketed as SQL-on-Hadoop,
NewSQL [
Even in a single organization, it is common to nd multiple databases that exhibit high variety. Often applications require integrated access to those databases. It is di cult to write optimized software that retrieves data from multiple such databases, given the di erent data models, di erent query syntaxes and the (often subtly) di erent query semantics. This problem has been recognized for many decades in the database community. It is now accentuated, as a plethora of di erent and specialized databases nds its place in the enterprise. For example, the problem happens whenever an enterprise adopts a fast and scalable NoSQL database to capture its users' activity on its web site (web log) and then builds applications that need integrated access to the web log data stored in the NoSQL database and also to data in its existing SQL databases.
Mediator systems had been proposed in the 90s in order
to provide integrated query access to multiple heterogeneous
databases, including databases with di erent query
capabilities. Polystores provide similar functionality [
Suppose the client issues the federated query Q, which nds the average temperature reported by any reliably functioning sensor in a speci c lat-long bounding box, where a sensor is deemed reliable only if none of its measurements are outside the range 40 F to 140 F. The query can be rewritten into the following plan, which includes PostgreSQL and MongoDB subqueries that are e cient and compatible with the limited query capabilities of MongoDB.1 Plan 1: (qQ1 s:id!n@id pQ2) s:id!1@id pQ3
The plan rst issues to PostgreSQL the query Q1, which nds the ids (s.id) of the sensors in the bounding box. Then, for each id, the parameter-passing semijoin operator issues to MongoDB repeated queries Q2, each time instantiating the parameter @id of Q2 with another id from the result of Q1. The queries Q2 test whether the identi ed sensor is reliable. If the sensor quali es, the particular sensor from Q1 appears in the output of the semijoin. Finally, the parameter-passing join issues to MongoDB repeated queries Q3 that nd the average of the temperature measurements for each quali ed sensor. Notice that if MongoDB had the capability to support nested queries, it would have been possible to issue a single MongoDB query for each id as opposed to two queries. Therefore the rewriting is aware of source capabilities. Finally, the coord to state() function, which inputs coordinates and outputs the name of the corresponding state, is executed in the middleware level.
Plan 1 is one of the many possible plans that one may consider. For example, another plan, say Plan 2, could have issued a query Q1' that fetches to the middleware all the sensors, regardless of whether they are in the bounding box 1In the interest of simplicity we simplify some aspects of the plan. will not become a general purpose mediator, but rather will become federators specializing to a few particular sources.
Client SELECT coord_to_state(s.lat, s.lng), AVG(m.temp) AS avg_temp FROM sensors AS s JOIN measurements AS m ON s.id = m.sid WHERE (s.lat>32.6 AND s.lat<32.9 AND s.lng>-117.0 AND s.lng<-117.3) AND NOT EXISTS (SELECT 1 FROM measurements AS me
WHERE me.sid=s.id AND (me.temp>140 OR me.temp<-40)) GROUP BY s.id, s.lat, s.lng Q FORWARD Middleware
SQL++ Query Processor SQL++ Virtual Database
V2 V1
Q1 SELECT s.id,s.lat,s.lng FROM sensors WHERE ( s.lat>32.6 AND s.lat<32.9 AND s.lng>-117.0 AND s.lng<-117.3) or not. Consequently, the bounding box selection would happen at the middleware level and then Plan 2 could proceed with the parameter-passing semijoin and join of Plan 1. However, one can easily tell that Plan 2 is not competitive since the capabilities of Postgres guarantee that one is always better o executing this kind of selection conditions at the Postgres source. Even in the absence of statistics and a cost estimator, a mediator should characterize Plan 2 as non-competitive and worthless of further consideration.
Nevertheless, in general, there are multiple competitive plans, i.e., plans that one needs source statistics and a cost estimator to tell which one is the expected best. For example, if it were the case that the vast majority of sensors are unreliable (i.e., if only a few sensors passed the conditions > 40 and < 140), then it could made sense to execute a Plan 3 that rst issues a MongoDB query to nd the unreliable sensors, then checks on Postgres whether they are in the wanted bounding box and then nds the average tempratures. One needs statistics and a cost estimator to tell which one of Plan 1 or Plan 3 is better. Therefore they are both competitive.
We de ne the rewriting problem as follows: Given a client query Q, nd all competitive candidate plans that are nontrivially di erent. By requiring non-trivial di erence, we eliminate the possibility of having multiple candidates that are super cial variations of each other. For example, supercially di erent plans can be created by, say, creating two versions of a plan, where the two versions use di erent, yet result-equivalent and performance-equivalent source queries.
In this paper we assume that the optimal plan is found in a sequence of two modules. The rst module is the rewriter: It inputs the client query and it outputs candidate competitive rewritings. The second module is the cost optimizer: It inputs the competitive candidate rewritings, assigns a cost to each one of them and chooses the plan with the minimum cost. In contrast, many query processors generally mix rewriting and cost optimization, hence pruning the search space and/or e ciently exploring the space. (By \space" we refer to the space of candidate rewritings.) The simpler, modular architecture of this paper splits the rewriter from the cost optimizer, primarily for presentation reasons: We show that rewriting poses challenging problems, even if not mixed with cost estimation and pruning.2
The rewriting problem is now more relevant and more challenging than it was in the past, since we now face unprecented variety in the capabilities of sources. This paper presents the past techniques and architectures for query rewriting, argues that continued work is needed in order to become practically viable in the present environment and provides corresponding directions. Notice that \practical viability" means being able to develop mediators where the number of lines of code (LOC) grows ideally sublinearly or, in the worst case, linearly in the number of involved sources. Given the number of possible di erent sources, any superlinear growth of LOC all but guarantees that such system 2Furthermore, it is an open question, to be judged in realworld deployments, whether pruning of the search space is a signi cant feature in mediators and polystores. In relational database optimizers, where rewriting, estimation and pruning are mixed, n-way joins e ectively prohibited architectures where all equivalent plans (join orders) would be explicit produced, as their number would generally be exponential in n. In contrast, the number of competitive plans may rarely be huge, therefore demoting the importance of mixing rewriting and optimization. sensors: {{ {id:1, lat:32.8, lng:-117.1}, {id:2, lat:32.7, lng:-117.2} }}
SQL Wrapper measurements: [ {sid:1, temp:200, msg:"calib. err."}, {sid:2, temp:70.1}, {sid:2, temp:70.2} ]
MongoDB Wrapper sensors: id lat lng 1 32.8 -117.1 2 32.7 -117.2 measurements: [ {sid: 1, temp: 200, msg:"calib. err."}, {sid: 2, temp: 70.1}, {sid: 2, temp: 70.2} ]
MongoDB
The prior example made clear that knowledge of the query capabilities of the sources is essential in the rewriting problem. To further isolate the point that requires capabilities awareness, during the rewriting process, we further modularize the rewriting module into two sub-modules. The split decouples rewriting aspects that pertain to fundamental capability di erences (e.g., can a source do nested conditions or not?) from rewriting aspects that are a translation across super cial syntactic di erences (e.g., a source can do nested conditions but it expresses them in its own, non-SQL dialect).
Architecturally, we enable this split by formally specifying
the syntax and semantics of SQL++ [
Q2 db.measurements .aggregate( {$match: {$and: [ {sid: @id}, {$or: [ {temp: {$gt: 140}}, {temp: {$lt: -40}} ]}]}}, {$limit: 1}) PostgreSQL
Q3
db.measurements
.aggregate(
{$match:{sid:@id}},
{$group: {
_id: "$sid",
avg: {$avg:"$temp"}
}})
pabilities of the sources, the more precise statement is that
each virtual view can answer a subset of SQL++ queries,
according to the source capabilities. For example, the
virtual view of MongoDB can be queried with SQL++ but such
SQL++ cannot have nested conditions. The important
differentiating aspect of SQL++ is that its syntax includes
con guration ags. For each database system, we set the
ags to di erent values, typically to describe whether the
database system supports the corresponding part of the
language. For example, a con guration ag represents whether
the nested conditions part of the syntax is allowed. When
we describe a Postgres database this ag will be true. In a
MongoDB it will be false. While [
There are also additional ags that describe subtle semantic di erences. For example, equality in SQL and equality in MongoDB have subtly di erent semantics in the case of nulls and absent attributes. Appropriate con guration ags classify these di erences among the sources. In the case of the equality problem, appropriate rewriting rules will then translate an equality under SQL's con guraton ag, into an equality under MongoDB's ag.
By appropriate choices of con guration options, the
SQL++ semantics morph into the semantics of other
SQL+JSON databases. The short paper [
A simple and easy-to-implement algebra-based
architecture adds the capabilities-based rewriting as a very last step
in otherwise conventional rewriting [
Such architecture is a relatively obvious and simple
incremental improvement over conventional query processors.
The bad news is that in the era of high variety there cannot
be a uniform set of conventions for the format of the
sourceagnostic plans. Ideally the source agnostic plans would have
4 An earlier, extended version [
We exemplify next a very common, albeit not the only one, problem pattern that argues for the non-existence of \ideal" source agnostic plans. Consider two algebraic operators f and g that can be swapped, i.e., f (g(:) = g(f (:). Assume that the source-agnostic plan for a client query q is Expession A1: o1(f (g(e2)))
By virtue of the equivalence of f (g(:)) and g(f (:)), one can see that the rewriter could have also produced the sourceagnostic Expession A2 o1(g(f (e2))) instead of Expession A1. In the absence of knowledge of the capabilities of the unerlying sources, it is impossible to choose between A1 and A2. The inability to choose can eventually lead to suboptimal plans, because the decomposers will detect suboptimal subexpressions. For example, in the discussed problem pattern, consider two alternate source capability situations. In both situations e2 should be executed at a source s, while o1 can only be executed in the middleware. In the rst situation, g can also be executed at the source s, along with o2, while f cannot be executed at s. In the second situation, it is vice versa: f can be executed at s, along with o2, while g cannot. It is easy to see that the rst situation produces an optimal plan if the source-agnostic plan is the Expession A1. The second situation produces an optimal plan when the source agnostic plan is the Expession A2.
In e ect, there is not a one-size- ts-all source agnostic plan. In the absence thereof, one may argue for a seemingly simple x: First produce all possible source agnostic plans. For example, whenever faced with operators that can be swapped produce a plan for each swapping. Then let decomposers work on each source agnostic plan. Unfortunately, this is not a scalable solution since the number of source agnostic plans would be huge.
Instead, FORWARD supports a capability-aware rewriting stage that is aware of the capabilities ags and performs rewritings with the goal of maximizing the subexpressions that can be pushed to a source. According to this architecture, it does not matter whether the source agnostic phase produces Expession A1 or Expession A2. Let us, for example, assume that it produces Expession A1, while g cannot be pushed to the source but f can. The capability-aware rewriting phase will inspect operators above e2 and see if they can be pushed down along with e2. Since f is such an operator, the rewriting will transform f (g(e2)) into g(f (e2)), hence preparing the ground for the decomposer. 4.
A number of works tackled the problem of answering
queries using sources with limited query capabilities as if
it were an extension of the well-studied problem of
answering queries using views. Namely, [
By expanding the containsconditions(id) of Line 2 with Line 4 and then with Line 3 we derive that one supported (parameterized) view is view(doc) :- document(id, doc), contains(id, w1), w1=?, contains(id, w2), w2=?
By replacing the parameters ? with constants we have
conventional views/queries. Other language extensions [
While theoretically strong, these works did not turn out
as-is into industrial processors, despite their authors
founding two mediator companies in the early 00s (Nimble,
subsequently acquired by Actuate; and Enosys Software,
subsequently acquired by BEA Aqualogic). A key reason for
their non-adoption is the relatively low variety requirements
of the early 00s. Hence it was su cient to follow variants
of Garlic's [
Nevertheless, their ability to describe the sets of supported queries and the fact they o ered completeness guarantee, invites drawing ideas from them in the current era of high variability. How can we bring such descriptive power into an algebraic setting?
We do not discuss cost optimization and polystore
design [