Arnaud WOLF†, Kento GOTO†, and Motomichi TOYAMA†† † ††Department of Information and Computer Science, Keio University Hiyoshi 3–14–1, Kouhoku-ku, Yokohama-shi, Kanagawa, 223–8522 Japan E-mail: †{arnaud,goto}@db.ics.keio.ac.jp, ††toyama@ics.keio.ac.jp Abstract  SuperSQL is an extension of SQL that automatically formats data retrieved from the database into various kinds of application data as an output of a query. Output formats include, but are not limited to, HTML, HTML5, XML and PDF. SuperSQL continuously evolves to support current emerging technologies particularly related to web development. Current developments lead us to identify improvement points and remodel the de- sign of the SuperSQL architecture. Specifically, the current implementation includes useless cartesian product that significantly slows down the execution of the queries, because all the tables are retrieved together, while we could actually retrieve them independently from each other. This paper proposes an optimizer by query decomposition based on a full reducer algorithm. Key words   Data retrieval, query optimization, SuperSQL, query language
Introduction
1.
SuperSQL is an extension of SQL that enables to gener- ate various kinds of application data directly as a result of a query.  Its syntax is similar to SQL with additional format- ting capabilities.  Possible application data output formats include HTML, PDF, XML, XLS, Ajax, etc.  The current main usage of this language is the generation of websites or web applications, with the advantage not having to use any other language that would require more programming skills. A sample of SuperSQL query with its resulting webpage is shown in Figure 1. If many features enabling a richer and more flexible utili- sation of SuperSQL have been developed recently, SuperSQL also faces important performance issues.  More specifically, the structure in the compiler that is responsible of data re- trieval roughly generate the SQL query by gathering all the involved tables within it. This causes the generation of very big intermediate tables, slowing down the execution time. Our current work consists in developing an optimizer that will split the original SQL query into several SQL queries by using query decomposition, in order to reduce the size of the intermediate tables. Our query decomposition model itself is based on the concept of full reducers, an old optimization technique often used in distributed databases. The outline of this paper is as follow. In part 2, we introduce an simple experience highlighting the performance issues of SuperSQL. In part 3, we introduce more in details Super- SQL, in term of architecture and data representation.  In part 4, we introduce the current optimizer implementation and part 5 is the conclusion.
2.   Performance issues in SuperSQL
A very simple experiment shows the performance issues of the current implementation. The experience is based on the following query: GENERATE HTML [p.name]!, [s.name]! FROM professor p, student s WHERE p.dept = 'ICS' AND s.dept = 'ICS' This query writes in an HTML file both lists of professors and students from the department ICS. While varying the size of both tables professor and student, we executed the above query and collected the execution time.  For a given size, we also executed the query that writes only the list of professors, and the one that writes only the list of students, and compare the sum of execution time of those queries to the one of the original query. The results are shown in Fig- ure 2. The results clearly shows that the original query induces a behaviour that is far from the expected trend, namely, the sum of the trends of the individual queries. This lead us to understand that we should manage to change the behaviour of the SuperSQL compiler, in order it to split the retrieval of the two tables.
SuperSQL inner architecture and pro-
3.
cess
As specified in the introduction, the syntax of SuperSQL is very similar to SQL. However, in addition, the user also has to specify how he wants the data to be organised in the generated output file. The structure of a SuperSQL query is the same as the one of a SQL query, except that the SELECT clause is replaced by another structure. A SuperSQL query always starts by GENERATE "format", where "format" is the desired format of the output file, and is followed by the Target Form Expression (TFE) clause, whose role is to organised the future data into a tree structure. We call the remaining part of the query the SQL clause. The structure derived from the TFE clause is called the schema. Figure 3 shows the architecture of the SuperSQL compiler. The SuperSQL is first parsed, and two parts are extracted, the schema (from the TFE clause), and components, namely the table names, predicates and so on. The components are sent to the SQL query maker that generates the SQL query aimed at retrieving the data. The extracted data are then sent to the data constructor, that organises the data ac- cordingly to the schema. Then the code generator gener- ates the output files. TFE's semantic is based on operators. The two main oper- ators are the connectors and the repeaters. Connectors are used to connect the data within a specific dimension. Espe- cially, in case of HTML files, there are three dimensions: the horizontal dimension represented by a comma (","), the ver- tical dimension by an exclamation point ("!") and the link dimension by a percent symbol ("%"). The repeaters, symbolised by a pair of brackets ("[]"), con- nects the components written inside it in its associated di- mension, and will unroll all the tuples of the corresponding relation. From this semantic, a tree structure, called the TFE tree, representing the hierarchy of the future retrieved data, is derived.  Figure 4 shows an example of query and its tree structure. GENERATE HTML [ a.name, [b.name]!, [c.name]! ]! FROM A a, B b, C c If two components are not embedded within the same re- peaters, they are called independent, that is, they don't form a tuple together. In case of our example, b and c are independent, but a and b or a and c are not independent. Therefore, a branch of the TFE tree is the largest type of set of components that are all dependent each other In the current implementation, the SQL query maker derives the SQL queries just from the components issued from the SQL clause. It doesn't use the schema. The SQL clause, containing FROM clause, WHERE clause and so on, is just copied in the final SQL query, and the SELECT clause gath- ers all the desired attributes.  For instance, the SuperSQL query in Figure 4 leads to the following SQL query:
SELECT a.name, b.name, c.name
FROM A a, B b, C c
The result of executing this query is the cartesian product between the tables A, B and C, which can be a very huge table.  However, the desired organisation specified by the schema doesn't expresses a cartesian product, because ta- bles B and C are here independent. To be more concrete, if each tables contains 30 tuples, the size of the intermediate table can reach almost 4000 tuples, while the size of the array in the output file would not overcome 30 rows. Therefore, a post-process is performed in order to remove useless tuples and get the final structure. If the intermediate table retrieved from the cartesian prod- uct is very huge, the retrieval and the post-process operations cause huge overhead. Thus, the purpose of the optimizer we are developing is to reduce the size of this intermediate tables by splitting the SQL query into several SQL queries involv- ing only tables that are dependent each other considering the schema. The tree structure used in the optimizer described in this pa- per is derived from the TFE tree above. For our optimizer, we just need to know the tables in themselves, and not neces- sarily the attributes (at least, not at this stage). Therefore, our tree structure is similar to the above one, except that we replace each component by its table's name, and remove the duplicates in each node. Moreover, in case a table appears more than one time in a branch, we only keep its uppermost occurence in the branch. Figure 5 shows the modified tree of the example in Figure 4.
Optimizer based on query decomposi-
4.
tion and full reducer
4.1   Principle of query decomposition
In this section, we introduce the general principle of query decomposition we designed under the logic of SuperSQL. The inputs and outputs of the query decomposition process are specified in Figure 6. The input is a SQL query from where
we extract a set of tables and an algebraic extraction from the FROM clause, and a predicate from the WHERE clause. The purpose of query decomposition is to find a partition of the set of branches that optimizes the data retrieval, and for this partition, to find the appropriate set of algebraic expres- sions F and the set of predicates P satisfying the constraint equation (1). Equation (1) expresses that the result obtained for each branch from each partition should be equivalent to the projection on this branch of the result obtained from the original query.
Vi ∈ [1, m], ∀B ∈ Bi, πb(σpi (Fi (Bi))) ≡ πb(σp(F(B))

4.2   Principle of full reduction
Let us Pa be a given partition of B. In many cases, it is possible to retrieve all the sets from Pa with a unique query for each set. However, there are also many cases where it is not possible, because the expression F or the predicate P of the original query involves a dependance between some branches.  As for an example, let us consider the following query :
GENERATE HTML
[a.name]!, [b.name]!, [c.name]! FROM A a, B b, C c WHERE a.id = b.id AND b.reg = c.reg AND a.dept = "ICS" In case of this query, we have three branches, but the WHERE clause involves predicates between them.  There- fore, if we retrieve separately each of the three branches, we still need to check, afterward, if each tuple of each relation satisfies the condition with at least one tuple in the another relation. [2] designs an algorithm of full reduction destined to dis- tributed database systems.  In a distributed database system, a query may involve relations in different locations, and the data retrieved from each of those locations has to be gath- ered in a common place before being treated. Therefore, in order to avoid overhead due to intersite communication, it can be desired to reduce the size of data from each location before joining them. In case of the above example, if A, B and C are stored in different locations, it could be useful to first select, for instance, only the tuples of A that satisfies the predicate with at least one tuple of B, before actually performing the join. [2] introduces a technique to reduce as much as possible the size of relations by performing what they call a full-reducer sequence, applicable on simple queries (involving only inner joins and no special algebraic operators). It consists on the following steps. At first, given a sql query q, we construct a graph Gq = {R, E}, where R is a set of relations, and E a set of pairs of relations such as, for a pair ( R 1 , R 2 ) of R , q includes a binary predicate involving both R 1 and R 2 . We call this graph the query graph of q. The second step is to perform a recursive sequence of up- dates, called full reducer, that reduces the size of the desired table by keeping only tuples that satisfies all the predicates with at least one tuple from other relations it is connected with. As this sequence is described in [2], we won't describe it in details here. An important point is that, according to [2], we can find a full reducer if and only if the query graph does not contain cycle, or namely, is a tree. [1] describes a way to reduce the size of relations even if the graph contains cycles, but it can- not be applied in the context of SuperSQL. As a matter of fact, in case of SuperSQL, the purpose is not to finally join the relations, but to retrieve the exact amount of informa¬ tion from each branch without joining it, and then we need a full reducer. And [2] proved that if the query graph of q contains cycle, it is impossible to find a full reducer for q. The solution of[1] enables only to partially reduce the size. In case of SuperSQL, the vertices of the query graph are not relations, but branches, and there is an edge between two branches if there exists a binary predicate involving tables from both branches. Building such a graph requires a pre- treatment on predicates that is described later. As an example, let us consider the above example. The three branches derived from this examples are B 1 = (A, a), B 2 = (B,b) and B3 = (C, c).  Figure 7 is an example of query tree under the context of SuperSQL, and Figure 8 is the full- reducer sequence that enables to retrieve the data from each branch. 4.3   Model and limitations of the optimizer The optimizer we are currently developing has two main limitations. The first one is that it can only be applied on Figure 7 Example of query tree 1. CREATE TABLE tmp1 as SELECT * FROM A WHERE dept = "ICS" 2. CREATE TABLE tmp2 as SELECT * FROM B 3. CREATE TABLE tmp3 as SELECT * FROM C 4. REMOVE FROM tmp2 b WHERE NOT EXISTS (SELECT * FROM tmp3 c WHERE c.reg = b.reg) 5. REMOVE FROM tmp1 a WHERE NOT EXISTS (SELECT* FROM tmp2 b WHERE b.id = a.id) 6. SELECT a name FROM tmp1 a 7. SELECT b.name FROM tmp2 b WHERE EXISTS (SELECT* FROM tmp1 a WHERE a.id = b.id) 8. SELECT c.name FROM tmp3 c WHERE EXISTS (SELECT* FROM tmp2 b WHERE b.reg = c.reg) Figure 8   The full reducer of above example queries that does not include complex operators, that is, queries that only involves inner joins in the FROM clause (e.g., no outer joins), no aggregates, and no HAVING clause in the WHERE clause. Especially, the generalisation on any FROM clause, even the one including outer joins, will be the object of near future works. The second one is about the predicate. We will see below that we need to factorize the predicate, in order to make the queries. If the factorization is not possible, then the optimization is also impossible. Considering those limitations, under the scope of the opti¬ mizer, a SuperSQL query can be defined with the following inputs: . a set of relations R. a set of branches B, with each element of B being a . subset of R. . a predicate P. Predicates are modeled as polynomials of elementary predi- cates. The + operator corresponds to OR and the × operator corresponds to AND.
pij's are called elementary predicates.  Namely, it is the predicates that are directly found in the WHERE clause, such as "a.id = b.id".  An elementary predicate can either be a unary predicate if it involves only one relation, or a binary predicate if it involves two relations.
The different steps of the optimization
4.4
In this section, we describe the different steps of the opti¬ mization performed by the optimizer we are developing. Pretreatment of branches 4. 4. 1 As mentioned in Figure 6, in order to be usable as an in- put of the query decomposition process, the set of branches should be disjoint. However, in general, it is far from be- ing the case. The tree represented in Figure 5 includes two branches: B1 = {(A, a), (B, b)} and B2 = {(A,a), (C,c)}, and the relation (A, a) is a common relation of the two branches. In order to make the branches distinct, we replace each com- mon relation of the two branches by relations with same name, but different aliases. As for the example, the two branches become B1 = {(A, a1), (B, b)} and B2 = {(A,a2), (C,c)}. Let us assume that the predicate P of this query is defined as being:
Then the alias in each of the elementary predicate is replaced by the alias of the specific branch, and a binary predicate specifying that the primary key of al and a2 should be equal is added.
where K A is the set of primary keys of A. The set of rela- tions having been duplicated like that is stored in prevision of data construction.
Pretreatment of predicates
4. 4. 2
As the vertices of the query graph are branches and not relations, we need to build it with predicates defined per branches, and not per relation. Thus, we need to extract those branches predicate from the predicate P'. However, in order to do that, we need to transform P' into a specific shape.
So the second step of the optimizer is to factorise the pred- icate P' in order it to fit with equation (5). The PB's are used in queries materializing each branches, and the P B B B B are used to build the query tree and perform the full reduc- tion. However, there may be some predicates that cannot be fac- torised as above. For instance, still considering the example of Figure 5, the predicate of the equation (6) cannot be fac- torised as above. In such a case, the optimization is stopped, and the original retrieval within a single query is performed.
In order to check if a predicate is factorisable, we extract all the elementary predicates of P and put it in the appro- priate monomial (the one involving its branch(es)), create a polynomial that is the product of all those monomial, and check the equality by identification. In case of the predicate of equation (6), for instance, the inequality (7) shows that
4. 4. 3 The query graph and the management of cycles If the factorisation succeeded, the PBBB's are used in or- der to build the query graph, that is, if for a pair of branch (B, B'), there is a predicate P B , B ′ , the branches B and B' are connected together in the graph. Then the optimizer checks if the graph contains cycles or not. If the graph does contain cycles, the partition is re- jected. However, unlike the case of factorisation failure, the opimization does not stop completely.  Rather, we extract from the graph a cycle base (a set of set of vertices of the graphs, each of them representing a cycle, and such as every cycles of the graph are combination of those cycles). Then we change the partition Pa in order to eliminate all the cy- cles of the base, that is, by joining all the branches in a cycle together. Figure 9 shows an example of case including cycles.
4.5 Data retrieval
When a query graph without cycles is obtained, the full reduction sequence can be performed, as it is described in above section. Then the queries are generated and executed in the appropriate order, and the result sets are extracted. At this stage, an simple but fundamental step has to be per- formed.  The query graph is built on either a binary predicate connects two branches or not. However, even if there is no binary predicates connecting two branches, there is still a dependence between them, because under the limitation of this optimizer, we assume that only inner joins connects the relations. Figure 10 illustrates a case where we need to perform an additional treatment. As a matter of fact, in this case, the branch B4 is not connected to any other branch. Therefore, all the data of B4 is retrieved without going through any full- reducer sequence. However, if any branch among B1, B2 or B3 issues an empty set, in order the constraint equation 1 to be satisfied, the final result set of B4 should also be empty. Thus, the check of emptiness is an compulsory operation to perform after the retrieval. In a general case, the checking B4 Figure 10   Example of case where emptiness check is necessary of emptiness has to be perform in order to ensure that the emptiness of the result set of one connected component of the query graph causes the emptiness of all the other con¬ nected components of the graph.
4.6   Data construction
The last step of the process is data construction. In this stage, the data is finally organised in a tree structure cor¬ responding to the schema. Figure 11 shows an example of output structure of the data constructor. The output structure includes a sub-structure called tuple tree. A tuple tree is a list of elements that are either data or another list of tuple tree. The root of the final structure is a single tuple tree, containing only the list of tuple trees for each root of the schema. The data are input in the structure branch after branch. For a given branch, data are input tuple after tuple. For the in- sertion of a given tuple, the structure is traversed recursively considering the schema. When considering a given node of the tree, the existence of a tuple tree containing the values of the given tuple is checked. Then if necessary, a new tuple tree containing those values is created. The same process is applied recursively to the subtrees of this tuple tree. As this step requires to manipulate the entire set of data retrieved from the database, the smaller the intermediate tables are, the faster the execution is. The optimizer stands on a heuristic: we assume that the more the original query is divided, the faster the execution is.  As a matter of fact, the decomposition necessarily leads to smaller intermediate tables. The weak point of this heuristic is that the data retrieval, with materialization and multi- ple update during full reduction, may cause some important overhead. However, our assumption stands on the hypothe- sis that users of SuperSQL don't often write queries with a great number of branches, or with complex predicates. Therefore, we assume that the query graph won't cause long full-reduction chains, and that the overhead due to the data retrieval will be compensated by the gain on performance on data-construction. All those assertions will be verified on near future works.
Conclusion and future works
5.
In order to face the issues of performance due to unde- sirable cartesian product during the data retrieval, we de- signed an optimizer based on query decomposition and full- reduction. Figure 12 shows the flowgraph of all the steps of
optimization.
We adapted the full-reduction principle widely used in dis- tributed database for the purpose of SuperSQL. The devel- oped optimizer has limitations concerning the complexity of queries, and currently accepts only queries excluding outer joins, having clause and aggregates. The optimizer has not been properly evaluated yet, but the evaluation of this lim- ited version is the next stage of our work.  The evaluation will include, the evaluation of gain of performances provided by the optimizer, the measurement of the overhead brought by the optimization ourselves, and the validity of our heuris- tic, that is, considering that users mostly writes queries that tends to be executed more efficiently with our optimizer. Near future works will also involves the generalisation of the query decomposition model to algebraic expressions includ- ing outer joins, that will strongly rely on the notion of in- dependence.  This step requires deeper thinkings related to relational algebra.