Java > Open Source Codes > org > xquark > extractor > mysql > MysqlRemoveSubQueries


1 /*
2  * This file belongs to the XQuark distribution.
3  * Copyright (C) 2003 Universite de Versailles Saint-Quentin.
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this program; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307.
18  * You can also get it at http://www.gnu.org/licenses/lgpl.html
19  *
20  * For more information on this software, see http://www.xquark.org.
21  */
22
23 package org.xquark.extractor.mysql;
24
25 import java.util.*;
26
27 import org.xquark.extractor.algebra.*;
28 import org.xquark.extractor.algebra.Constants;
29 import org.xquark.extractor.common.*;
30 import org.xquark.extractor.runtime.IDProvider;
31
32 /**
33  * This visitor rewrites SQL queries so that nested subqueries in SELECT or
34  * WHERE are transformed into piped LEFT OUTER JOINS ...GROUP BY... HAVING.
35  *
36  * This visitor
37  * Rules pipe :
38  *
39  * 1st step :
40  *
41  * Scan predicates (in restrictions and joins) for aggregates and set operators
42  * (IN, ANY, EXIST, NOT EXIST) and pull up them as "SELECT in SELECT".
43  *
44  * 2nd step :
45  *
46  * "SELECT in SELECT" are rewritten as "LEFT OUTER JOIN...GROUP BY... HAVING"
47  */
48 public class MysqlRemoveSubQueries extends DefaultCompleteVisitor {
49
50     private static final String RCSRevision = "$Revision: 1.26 $";
51     private static final String RCSName = "$Name: $";
52
53     protected Expression _rewrittenQuery;
54     protected Mapper _topMapper; // keep the original because making a new one may be dangerous (original expressions do not always exist...)
55 protected FindQuerySignatureVisitor _keyNodesFinder = new FindQuerySignatureVisitor();
56     protected SplitPredicateVisitor _splitVisitor = null; // initialized on demand
57 protected RemoveAggregateFunctionVisitor _removeAggrVisitor = null; // initialized on demand
58 protected RenameAttributeExpressionVisitor _renameVisitor = null;
59     protected ForeignAttributeGrabber _foreignAttributeGrabber = null;
60     protected AttributeGrabber _attributeGrabber = null;
61     protected RestrictionVisitor _restrictionVisitor = new RestrictionVisitor();
62     protected AddKeys _addKeysVisitor = new AddKeys();
63     protected Stack _subQueryStack = new Stack();
64     protected IDProvider _attIDProvider = null;
65     protected IDProvider _relIDProvider = null;
66
67     public MysqlRemoveSubQueries(IDProvider attIDProvider, IDProvider relIDProvider) {
68         _attIDProvider = attIDProvider;
69         _relIDProvider = relIDProvider;
70     }
71
72     public void reinit(Expression query) {
73         _rewrittenQuery = query;
74         _topMapper = query.getMapper();
75     }
76
77     public Expression getRewrittenQuery() {
78         return _rewrittenQuery;
79     }
80
81     public void setRewrittenQuery(SubQueryNode query) {
82         switch (query._type) {
83             case SubQueryNode.TYPE_MAIN :
84                  ((Expression) query._query).setMapper(_topMapper);
85                 if (query._referringNode == null)
86                     _rewrittenQuery = (Expression) query._query;
87                 else
88                     _rewrittenQuery = query._referringNode;
89                 break;
90             case SubQueryNode.TYPE_FROM :
91                 // subquery was rewritten : connect as the original operand because
92 // FROM subqueries are not refernced from their parent subquery
93 if (query._renamedQuery == null)
94                      ((UnaryOperator) query._referringNode).setOperand((Expression) query._query);
95                 break;
96             default :
97                 }
98         // UC11: What to do with independant aggregation ? A cartesian product on a temp table ?
99 }
100
101     public void visit(UnOpProject arg) {
102         //Trace.enter(this, "visit(UnOpProject arg)", arg);
103 browseProjection(arg, SubQueryNode.CONTEXT_PROJECT);
104         //Trace.exit(this, "visit(UnOpProject arg)", arg);
105 }
106
107     public void visit(UnOpAggregate arg) {
108         //Trace.enter(this, "visit(UnOpProject arg)", arg);
109 browseProjection(arg, SubQueryNode.CONTEXT_AGGR);
110         //Trace.exit(this, "visit(UnOpProject arg)", arg);
111 }
112
113     private void browseProjection(UnOpProject arg, byte context) {
114         SubQueryNode query = null;
115
116         SubQueryNode parentQuery = null;
117         if (_subQueryStack.isEmpty())
118             query = new SubQueryNode(arg);
119         else {
120             parentQuery = (SubQueryNode) _subQueryStack.peek();
121             /* a subquery must have been already created */
122             if (parentQuery.getType() == SubQueryNode.TYPE_PREDICATE_EXIST)
123                 query = (SubQueryNode) _subQueryStack.peek();
124             else
125                 query = new SubQueryNode(arg, context);
126         }
127
128         if (query != null)
129             query.setBrowsingStep(SubQueryNode.STEP_OPERAND);
130
131         arg.getOperand().accept(this);
132
133         if (query != null)
134             query.setBrowsingStep(SubQueryNode.STEP_ITEMS);
135
136         List list = arg.getParameterList();
137         if (null != list) {
138             for (int i = 0; i < list.size(); i++) {
139                 query.setCurrent((Expression) list.get(i));
140                 query.getCurrent().accept(this);
141             }
142         }
143
144         if (query != parentQuery)
145             setRewrittenQuery(query.rewrite());
146     }
147
148     public void visit(UnOpRestrict arg) {
149         //Trace.enter(this, "visit(UnOpRestrict arg)", arg);
150 SubQueryNode query = (SubQueryNode) _subQueryStack.peek();
151
152         query.setBrowsingStep(SubQueryNode.STEP_PREDICATES);
153         List list = arg.getPredicateList();
154         if (null != list) {
155             for (int i = 0; i < list.size(); i++) {
156                 query.setCurrent((Expression) list.get(i));
157                 query.getCurrent().accept(this);
158             }
159         }
160
161         query.setBrowsingStep(SubQueryNode.STEP_OPERAND);
162         arg.getOperand().accept(this);
163
164         //Trace.exit(this, "visit(UnOpRestrict arg)", arg);
165 }
166
167     public void visit(Join arg) {
168         //Trace.enter(this, "visit(Join arg)", arg);
169 SubQueryNode query = (SubQueryNode) _subQueryStack.peek();
170
171         query.setBrowsingStep(SubQueryNode.STEP_PREDICATES);
172         List list = arg.getPredicateList();
173         if (null != list) {
174             for (int i = 0; i < list.size(); i++) {
175                 query.setCurrent((Expression) list.get(i));
176                 query.getCurrent().accept(this);
177             }
178         }
179
180         query.setBrowsingStep(SubQueryNode.STEP_OPERAND);
181         list = arg.getOperandList();
182         if (null != list) {
183             for (int i = 0; i < list.size(); i++) {
184                 query.setCurrent((Expression) list.get(i));
185                 query.getCurrent().accept(this);
186             }
187         }
188
189         //Trace.exit(this, "visit(Join arg)", arg);
190 }
191
192     public void visit(BinOpCompareAny arg) {
193         if (!(arg.getRightOperand() instanceof LitList)) {
194             SubQueryNode query = new SubQueryNode((Relation) arg.getRightOperand(), SubQueryNode.CONTEXT_ANY);
195             super.visit((BinaryAtomicOp) arg);
196             query.rewrite();
197         }
198         // else do not rewrite ANY will be generated as a IN(constant list)
199 }
200
201     public void visit(UnOpExists arg) {
202         SubQueryNode query = new SubQueryNode((Relation) arg.getOperand(), SubQueryNode.CONTEXT_EXIST);
203         super.visit((UnaryAtomicOp) arg);
204         query.rewrite();
205     }
206
207     /**
208      * 2nd step of rewriting:
209      * 1. Detects aggregations in projection.
210      * 2. Aggregations are the browsed to detect those based on the same relation
211      * (table or restriction on the same table) and grouped following this criteria.
212      * 3. Redundant aggregation from the same relation items are removed preserving
213      * original mapping.
214      * 4. Remaining relations in projection (nested aggreagations) are then
215      * transformed into a outer join and a groupby.
216      * 5. Outer join predicates (out of join predicates) are splitted in two: predicates
217      * containing references to aggregates aliases are moved into a new restriction nodes
218      * set above group by node, becoming a having close.
219      * @param arg
220      */
221     /**
222      * 1st step of rewriting:
223      * 1. Detects aggregations and assimilated in restrictions. During this process
224      * '= ANY' (i.e. IN which do not exist in algebra) predicates are processed like
225      * EXIST. Predicates involving the aggregates and COUNT(*) > 0 (or = 0 if a NOT
226      * is involved) are gathered for the HAVING clause.
227      * 2. Aggregations and assimilated are renamed and pulled up to the surrounding
228      * projection keeping. Join predicates not involving outer relation columns
229      * should be kept in the predicate of outer relation (multi-level nesting).
230      * 3. 2nd step is then piped because of depth-first trasversal of algebra
231      * tree.
232      * @param expr the restriction node browsed
233      * @param predicateList the list of expressions that will be scanned for
234      * aggregations
235      */
236
237     protected SubQueryNode transformSubquery(SubQueryNode query) {
238         //
239 return query;
240     }
241     /**
242      * Creates "flatened" outer join tree for a correlated aggregation.
243      * @param mainRelation the outer relation to join
244      * @param subRelation the subquery relation without the projection
245      * @param projectiontAttributes attributes that will be retrieved with the
246      * aggregation. The aggregations aliases will be added to this list in order
247      * to retrieve data in the next surrounding outer join.
248      * @param groupByList attribute that will be used for grouping
249      * @return A relation with no aliasing performed.
250      * @throws CloneNotSupportedException
251      */
252     protected RenameRelation createOuterJoin(Expression mainRelation, List newRelationPredicates, InnerRelationInfo subQuery, boolean distinct, boolean mainIsAggregate) {
253
254         //Trace.enter(this, "createOuterJoin(...)");
255
256         /* Build new relation */
257         Expression retRelation = null;
258         if (subQuery._keys == null) { // main relation is a DummyTable
259 retRelation = subQuery._relation;
260             if (newRelationPredicates == null)
261                 newRelationPredicates = subQuery._predicates;
262             else
263                 newRelationPredicates.addAll(subQuery._predicates);
264         } else if (subQuery._predicates.isEmpty()) { // create a standard join instead // TODO: uncorrelated aggregates should be removed before
265 if (mainRelation instanceof Join) { // In the case main relation is already a join
266 Join join = (Join) mainRelation;
267                 if (subQuery._relation instanceof Join) {
268                     Join subJoin = (Join) subQuery._relation;
269                     join.addOperandList(subJoin.getOperandList());
270                     join.addPredicateList(subJoin.getPredicateList());
271                 } else {
272                     join.addOperand(subQuery._relation);
273                 }
274                 retRelation = mainRelation;
275             } else {
276                 if (subQuery._relation instanceof Join) {
277                     Join join = (Join) subQuery._relation;
278                     join.addOperand(mainRelation);
279                     retRelation = join;
280                 } else {
281                     List operands = new ArrayList(2);
282                     operands.add(mainRelation);
283                     operands.add(subQuery._relation);
284                     retRelation = new Join(operands, Collections.EMPTY_LIST);
285                 }
286             }
287         } else {
288             if (subQuery._relation instanceof Join) {
289                 // when subquery is a join, the outer join can be replaced by
290 // a join when having predicate is (count() > 0) since it gets
291 // rid of
292 boolean canUseAJoin = false;
293                 if (subQuery._havingClauses != null) {
294                     Expression predicate = (Expression) subQuery._havingClauses.get(0);
295                     if (predicate instanceof BinOpCompare) {
296                         BinOpCompare comp = (BinOpCompare) predicate;
297                         if (comp.getRightOperand() instanceof LitInteger) {
298                             canUseAJoin = ((LitInteger) comp.getRightOperand()).getValue().intValue() == 0 && comp.getOperator() == Constants.GT_COMPOP && comp.getLeftOperand() instanceof FunAggregate && ((FunAggregate) comp.getLeftOperand()).getOperator() == FunAggregate.COUNT;
299                         } else if (comp.getLeftOperand() instanceof LitInteger) {
300                             canUseAJoin = ((LitInteger) comp.getLeftOperand()).getValue().intValue() == 0 && comp.getOperator() == Constants.LT_COMPOP && comp.getRightOperand() instanceof FunAggregate && ((FunAggregate) comp.getRightOperand()).getOperator() == FunAggregate.COUNT;
301                         }
302                     }
303                 }
304                 if (canUseAJoin) {
305                     Join join = (Join) subQuery._relation;
306                     if (mainRelation instanceof Join) {
307                         join.addOperandList(((Join) mainRelation).getOperandList());
308                         join.addPredicateList(((Join) mainRelation).getPredicateList()); // QUESTION: not already grabbed ?
309 } else
310                         join.addOperand(mainRelation);
311                     join.addPredicateList(subQuery._predicates);
312                     retRelation = join;
313                 } else
314                     throw new SqlWrapperException(MessageLibrary.getMessage("T_N_SUP_QUERY", "MySQL: joins in inner query"));
315                 // NOTE : MySQL requires an ON clause for each OUTER JOIN and it
316 // is not always possible to separate join predicates from outer
317 // join predicates (for instance when predicates are in OR expressions).
318 // Moreover, associativity rules for joins cannot always be controlled.
319
320                 // TODO: produce a simple join with all predicates and outer relation
321 // keys and pipe it (temp table) in an outer join with the external
322 // relation (possibly a join).
323 } else // Piping joins (if any) and OJ in this order does not pose a problem
324 retRelation = new BinOpOuterJoin(mainRelation, subQuery._relation, Constants.LEFT_OUTER_JOIN, subQuery._predicates);
325         }
326
327         // NOTE: As MySQL support predicate (out of join predicates) in ON clause (and its better
328 // semantically because predicate in WHERE could remove OUTER JOIN result "null tuples") all
329 // predicates (join an not) are put in ON
330
331         /* Pull up both predicates from main relation (first Outer join only since it's piped after) */
332         if (newRelationPredicates != null)
333             retRelation = new UnOpRestrict(retRelation, newRelationPredicates);
334
335         /* create a groupby node using PK + result columns(not necessary if a PK ? Pas d'erreur en tout cas avec MySQL) */
336         if (subQuery._keys != null)
337             retRelation = new UnOpGroup(retRelation, subQuery._keys);
338
339         /* Create a having clause for aggregates in where */
340         if (subQuery._havingClauses != null && !subQuery._havingClauses.isEmpty())
341             retRelation = new UnOpRestrict(retRelation, subQuery._havingClauses, true);
342
343         /* create projection node(s) */
344         if (mainIsAggregate) {
345             // in this case, create 2 projections (temp table) to avoid aggregates to interfere
346 // first projection must contain all second's item but without aggregate
347 // Clone the remaining projection attribute for the second projection
348 List proj2Items = null;
349             /* create the outer join projection (first) */
350             UnOpProject proj1 = null;
351             if (subQuery.hasAggregate())
352                 proj1 = new UnOpAggregate(retRelation, subQuery._items, distinct, _attIDProvider);
353             else
354                 proj1 = new UnOpProject(retRelation, subQuery._items, distinct, _attIDProvider);
355
356             RenameRelation rel1 = new RenameRelation(proj1, _relIDProvider);
357
358             proj2Items = processAggregateItems(proj1, rel1);
359
360             /* A second projection is piped to avoid aggregation "collision" */
361             // 2nd projection creation
362 retRelation = new UnOpAggregate(rel1, proj2Items, false, _attIDProvider);
363         } else {
364             /* create the outer join projection */
365             retRelation = new UnOpAggregate(retRelation, subQuery._items, distinct, _attIDProvider);
366         }
367         subQuery._alias.setOperand(retRelation);
368
369         //Trace.exit(this, "createOuterJoin(...)");
370 return subQuery._alias;
371     }
372
373     private List processAggregateItems(UnOpProject proj1, RenameRelation rel1) {
374         List aggrItemList = proj1.getItemList();
375
376         // remove aggregation items and collect aggregate function parameters
377 if (_removeAggrVisitor == null)
378             _removeAggrVisitor = new RemoveAggregateFunctionVisitor();
379         else
380             _removeAggrVisitor.reinit();
381
382         List aggrItems = new ArrayList();
383         ListIterator lit = aggrItemList.listIterator();
384         Expression item = null;
385         while (lit.hasNext()) {
386             item = (Expression) lit.next();
387             _removeAggrVisitor.newItem();
388             item.accept(_removeAggrVisitor);
389             if (_removeAggrVisitor.aggregateFound()) {
390                 lit.remove();
391                 aggrItems.add(item);
392             }
393         }
394
395         // Clone the remaining projection attribute for the second projection
396 List proj2Items = null;
397         try {
398             proj2Items = AlgebraTools.clone(aggrItemList);
399         } catch (CloneNotSupportedException e) {
400             throw new InternalErrorException(MessageLibrary.getMessage("IE_ERR", "Could not clone item list"));
401         }
402
403         /* browse the collected items to insert them in the projections and
404          * substitue the alias in the initial item */
405         Iterator it = _removeAggrVisitor.getCollectedItems().iterator();
406         FunAggregate funAggr = null;
407         AttributeExpression att = null;
408
409         while (it.hasNext()) {
410             item = (Expression) it.next();
411             funAggr = (FunAggregate) item.getFather(); // save the parent before it is changed
412 item = proj1.addItem(item); // can be substituted with an alias if conflict
413 att = new AttributeExpression(rel1, item.getName());
414             att.setUnderlyingExpr(item);
415             funAggr.setOperand(att); // set the potential alias for aggregate function
416 }
417
418         proj2Items.addAll(aggrItems);
419
420         return proj2Items;
421     }
422
423     /**
424      * Pick out all remaining predicates (join predicates have been removed) on
425      * an outer join.
426      * @param tree outer join to browse
427      * @return a list of predicates.
428      */
429     protected List pickOutPredicates(Expression tree, boolean blockOnProject) {
430         //Trace.enter(this, "pickOutPredicates(Expression tree)", tree);
431 List retVal = new ArrayList();
432
433         /* find out UnOpRestrict nodes */
434         List joinPredicateList = new ArrayList();
435         _restrictionVisitor.reinit(true, blockOnProject);
436         tree.accept(_restrictionVisitor);
437         List restrictionList = _restrictionVisitor.getRestrictions();
438
439         /* browse found nodes */
440         UnOpRestrict restrict = null;
441         Join join = null;
442         Set vti = null;
443
444         Expression expr;
445         for (int i = 0; i < restrictionList.size(); i++) {
446             expr = (Expression) restrictionList.get(i);
447
448             if (expr instanceof UnOpRestrict) {
449                 restrict = (UnOpRestrict) expr;
450                 retVal.addAll(restrict.getPredicateList());
451                 /* Remove the restriction node if possible and compact potential piled relation alias*/
452                 Expression father = restrict.getFather();
453                 if (father != null)
454                     father.replaceChild(restrict, restrict.getOperand());
455             } else if (expr instanceof Join) {
456                 join = (Join) expr;
457                 if (join.getPredicateList() != null) {
458                     retVal.addAll(join.getPredicateList());
459                     join.getPredicateList().clear();
460                 }
461             } else
462                 Debug.nyi("pickOutPredicates(Expression tree)");
463         }
464
465         //Trace.exit(this, "pickOutPredicates(Expression tree)", tree);
466 return retVal;
467     }
468
469     /**
470      * Find out in a list of items or predicates any Subquery and build a corresponding
471      * temporary structure to store them in a list waiting for the next step of
472      * rewriting.
473      * @param exprList the list of items or predicates to be scanned. Matching items
474      * are removed from the list.
475      * @param subQueries the initial list of subquery expressions.
476      * @param isPredicate flag allowing to know if a having clause must be generated
477      * @return the subquery list augmented with newly detected.
478      */
479
480     protected class SubQueryNode {
481         /* context of discovery */
482         public static final byte CONTEXT_PROJECT = 0;
483         public static final byte CONTEXT_AGGR = 1;
484         public static final byte CONTEXT_ANY = 2;
485         public static final byte CONTEXT_EXIST = 3;
486
487         /* subquery types */
488         public static final byte TYPE_MAIN = 0;
489         public static final byte TYPE_SELECT_AGGR = 1;
490         public static final byte TYPE_PREDICATE_AGGR = 2;
491         public static final byte TYPE_PREDICATE_EXIST = 3;
492         public static final byte TYPE_PREDICATE_ANY = 4;
493         public static final byte TYPE_FROM = 5; // not processed here
494
495         /* browsing step */
496         public static final byte STEP_NONE = 0;
497         public static final byte STEP_ITEMS = 1;
498         public static final byte STEP_PREDICATES = 2;
499         public static final byte STEP_OPERAND = 3;
500         public static final byte STEP_DONE = 4;
501
502         public byte _type = TYPE_MAIN;
503
504         public byte _browsingStep = STEP_NONE;
505
506         /** The current expression being browsed : used to set son's anchor */
507         private Expression _current;
508
509         /**
510          * Base expression. Predicate if predicate subquery.
511          */
512         private Expression _anchor = null;
513
514         /**
515          * the Rename surrounding subquery.
516          */
517         private UnaryOperator _renamedQuery = null;
518
519         /**
520          * The parent node of subquery expression (exception made of Rename).
521          */
522         private Expression _referringNode = null;
523
524         /**
525          * The subquery.
526          */
527         private Relation _query = null;
528
529         /**
530          * SubQueryNode.
531          */
532         private List _subQueryList = new ArrayList();
533
534         public SubQueryNode(Expression mainQuery) {
535             _type = TYPE_MAIN;
536             _query = (UnaryAlgebra) mainQuery;
537             _referringNode = mainQuery.getFather();
538
539             // add subquery to stack
540 _subQueryStack.push(this);
541         }
542
543         /* parentQuery not null */
544         public SubQueryNode(Relation root, byte context) {
545             SubQueryNode parentQuery = (SubQueryNode) _subQueryStack.peek();
546
547             _anchor = parentQuery.getCurrent();
548             Expression subQuery = (Expression) root;
549             _referringNode = subQuery.getFather();
550
551             /* set members according to context */
552             switch (context) {
553                 case CONTEXT_PROJECT :
554                     /* set type */
555                     // by default we consider that a simple projection is either root, either in from
556 _type = TYPE_FROM; // nothing performed
557 // rename may be parent
558 _query = root;
559                     if (_referringNode instanceof RenameRelation) {
560                         _renamedQuery = (UnaryOperator) subQuery.getFather();
561                         _referringNode = _renamedQuery.getFather();
562                     }
563
564                     break;
565
566                 case CONTEXT_AGGR :
567                     /* set type */
568                     switch (parentQuery.getBrowsingStep()) {
569                         case STEP_ITEMS :
570                             _type = TYPE_SELECT_AGGR;
571                             _renamedQuery = (UnaryOperator) _referringNode;
572                             _referringNode = _renamedQuery.getFather();
573                             // assume there is always a RenameItem
574 break;
575                         case STEP_PREDICATES :
576                             _type = TYPE_PREDICATE_AGGR; // nothing performed
577 break;
578                         default :
579                             _type = TYPE_FROM; // nothing performed
580 }
581                     // rename may be parent
582 _query = root;
583
584                     break;
585
586                 case CONTEXT_ANY :
587                     /* set type */
588                     _type = TYPE_PREDICATE_ANY;
589                     // rename may be itself
590 if (root instanceof RenameRelation) {
591                         _renamedQuery = (UnaryOperator) subQuery;
592                         _query = (UnaryAlgebra) ((RenameRelation) root).getOperand();
593                     } else
594                         _query = root;
595
596                     break;
597                 case CONTEXT_EXIST :
598                     /* set type */
599                     _type = TYPE_PREDICATE_EXIST;
600                     // rename may be itself
601 if (root instanceof RenameRelation) {
602                         _renamedQuery = (UnaryOperator) subQuery;
603                         _query = (UnaryAlgebra) ((RenameRelation) root).getOperand();
604                     } else
605                         _query = root;
606                     break;
607
608                 default :
609                     break;
610             }
611
612             // create an alias if missing
613 if (_referringNode == null) {
614                 switch (_type) {
615                     case TYPE_PREDICATE_ANY :
616                     case TYPE_PREDICATE_EXIST :
617                     case TYPE_FROM :
618                         _referringNode = new RenameRelation((Expression) _query, _relIDProvider);
619                         break;
620
621                     default :
622                         Debug.nyi("Aggregates should have surrounding RenameItem.");
623                 }
624             }
625
626             // canonize subquery
627 canonize();
628
629             // add subquery to parent if to be rewritten
630 if (_type != TYPE_FROM)
631                 parentQuery.addSubQuery(this);
632
633             // add subquery to stack
634 _subQueryStack.push(this);
635         }
636
637         /**
638          *
639          */
640         private void canonize() {
641
642             /**
643              * ANY (i.e. IN) predicate subquery processing. Transform it in a EXIST
644              * by adding a join predicate to the subquery then pipe the EXIST process.
645              */
646             switch (_type) {
647                 case TYPE_PREDICATE_ANY :
648                     /* transform this BinOpCompareAny in an 'homothetic' BinOpCompare with
649                      * on the one hand, the simple attribute expression and the other the
650                      * attribute expression of the subquery (remove the projection) as
651                      * operands and add this as a new subquery predicate
652                      */
653                     // by convention left operand is the scalar and right the subquery
654 UnOpProject subQueryProjection = (UnOpProject) _query;
655                     BinOpCompareAny original = (BinOpCompareAny) _referringNode;
656                     Expression scalarExpr1 = original.getLeftOperand(); // can be a constant
657
658                     Expression attExpr2 = (Expression) subQueryProjection.getItemList().get(0);
659                     if (attExpr2 instanceof RenameItem)
660                         attExpr2 = ((RenameItem)attExpr2).getOperand();
661                     BinOpCompare newPredicate = new BinOpCompare(original.getOperator(), scalarExpr1, attExpr2);
662
663                     /* the referred attribute field (used by exist processing) */
664                     Set refAtts = new HashSet();
665                     if (scalarExpr1 instanceof AttributeExpression)
666                         refAtts.add(scalarExpr1);
667                     if (_attributeGrabber == null)
668                         _attributeGrabber = new AttributeGrabber();
669                     else
670                         _attributeGrabber.reinit();
671                     attExpr2.accept(_attributeGrabber);
672                     refAtts.add(_attributeGrabber.getAttributeExpression());
673                     newPredicate.setReferredAttributes(refAtts);
674
675                     /* Find the restriction, join or create it if missing and add the predicate */
676                     _keyNodesFinder.reinit();
677                     subQueryProjection.accept(_keyNodesFinder);
678                     PredicateHolder restrict = _keyNodesFinder.getRestriction();
679                     if (restrict == null) { // insert a restriction node
680 Expression relation = _keyNodesFinder.getRelation();
681                         relation.getFather().replaceChild(relation, new UnOpRestrict(relation, newPredicate));
682                     } else {
683                         restrict.addPredicate(newPredicate);
684                     }
685
686                     /* Modify this node */
687                     _type = TYPE_PREDICATE_EXIST;
688                     _query = (Relation) subQueryProjection.getOperand();
689                     _referringNode = new UnOpExists((Expression) _query); // used later to fetch "not"
690 break;
691
692                 case TYPE_PREDICATE_EXIST :
693                     /* remove Potential UnOpNot */
694                     // TODO: check. in fact we consider that normalization prevent NOT(NOT EXISTS())
695 if (_anchor instanceof UnOpNot) {
696                         UnOpExists exists = (UnOpExists) _referringNode;
697                         // Note : could check UnOpNot's operand is exist...
698 //_anchor.getFather().replaceChild(exists); // _anchor is kept for predicate removal
699 exists.setNot(exists.getNot() ? false : true);
700                     }
701
702                     /* remove useless projection (should not happen ?) */
703                     if (_query instanceof UnOpProject) {
704                         UnOpProject project = (UnOpProject) _query;
705                         _query = (Relation) project.getOperand();
706                         if (_referringNode != null)
707                             _referringNode.replaceChild(project, (Expression) _query);
708                         else if (_renamedQuery != null)
709                             _renamedQuery.setOperand((Expression) _query);
710                     }
711                     break;
712
713                 default :
714                     }
715         }
716
717         public SubQueryNode rewrite() {
718
719             // process dummy queries without subqueries but with a predicate (which MySQL does not handle)
720 // introduces an UnaryAlgebra chain on a RenameRelation which carries out at generation time
721 if (_subQueryList.isEmpty()) {
722                 _keyNodesFinder.reinit();
723                 ((Expression) _query).accept(_keyNodesFinder);
724
725                 if (_keyNodesFinder.getRestriction() instanceof UnOpRestrict) {
726                     UnOpRestrict restrict = (UnOpRestrict) _keyNodesFinder.getRestriction();
727                     if (_keyNodesFinder.getRelation() instanceof DummyTable) {
728                         /* clone the project to put it in the inner relation */
729                         UnOpProject innerProject = null;
730                         try {
731                             innerProject = (UnOpProject) _keyNodesFinder.getProjection().clone();
732                         } catch (CloneNotSupportedException ex) {
733                             throw new SqlWrapperException(ex.getMessage(), ex);
734                         }
735
736                         /* create a rename for the inner relation */
737                         RenameRelation rename = new RenameRelation(innerProject, _relIDProvider);
738
739                         /* insert the new sequence of nodes above the dummy table */
740                         DummyTable dummy = (DummyTable) _keyNodesFinder.getRelation();
741                         dummy.getFather().replaceChild(dummy, rename);
742                         innerProject.setOperand(dummy);
743                     }
744                 }
745             } else { // process rewritting of this relation with one level of subquery
746 ListIterator it = _subQueryList.listIterator();
747                 SubQueryNode subQuery = null, lastSubQuery = null;
748                 InnerRelationInfo relation = null;
749                 List subRelations = new ArrayList();
750                 List aggrPairs = null;
751                 List aggrItems = null; // gather removed aggregate items to add them in potential piped queries (4B)
752
753                 /* remove subqueries before complex EXIST rewritting that browses predicates */
754                 // NOTE : do it now not to interfere with tree algebra iteration !!!
755 while (it.hasNext()) {
756                     subQuery = (SubQueryNode) it.next();
757
758                     switch (subQuery.getType()) {
759                         case TYPE_SELECT_AGGR :
760                              ((UnOpProject) subQuery._anchor.getFather()).removeItem(subQuery._anchor);
761                             if (aggrItems == null)
762                                 aggrItems = new ArrayList();
763                             aggrItems.add(subQuery._anchor);
764                             break;
765
766                         case TYPE_PREDICATE_AGGR :
767                             if (lastSubQuery != null && subQuery._anchor == lastSubQuery._anchor) {
768                                 if (aggrPairs == null)
769                                     aggrPairs = new ArrayList();
770                                 it.remove();
771                                 it.previous();
772                                 it.remove();
773                                 aggrPairs.add(new AggregatePair(lastSubQuery, subQuery));
774                             }
775                             /* remove predicate from outer relation */
776                              ((PredicateHolder) subQuery._anchor.getFather()).removePredicate(subQuery._anchor);
777                             break;
778
779                         case TYPE_PREDICATE_ANY : // normally canonization should have remove it
780 case TYPE_PREDICATE_EXIST :
781                             if (subQuery._anchor instanceof BinOpBoolean && ((BinOpBoolean) subQuery._anchor).getOperator() == Constants.OR)
782                                 throw new SqlWrapperException(MessageLibrary.getMessage("T_N_SUP_QUERY", "MySQL: multiple existential predicates in OR predicate"));
783
784                             /* remove predicate from outer relation */
785                              ((PredicateHolder) subQuery._anchor.getFather()).removePredicate(subQuery._anchor);
786                             break;
787
788                         default :
789                             }
790                     lastSubQuery = subQuery;
791                 }
792
793                 /* get information for outer join creation */
794                 boolean distinct = false, mainIsAggregate = _query instanceof UnOpAggregate;
795                 UnOpProject projection = null;
796                 Expression mainRelation = (Expression) _query;
797                 if (_query instanceof UnOpProject) { // may be a restriction if we are in an Exist (select *)
798 projection = (UnOpProject) _query;
799                     distinct = projection.getDistinct();
800                     mainRelation = ((UnaryOperator) mainRelation).getOperand();
801                 }
802
803                 // (4B) Transform predicate aggregates subqueries that are on the
804 // same predicate.
805 // Add a piped query (temp table) holding predicates and process
806 // aggregates in the query like 'select' instead of "predicate"
807 // aggregates
808 AggregatePair aggrPair = null;
809                 RenameRelation queryAlias = null;
810                 if (aggrPairs != null && projection != null) {
811                     // insert a duplicate of project and add a restrict
812 queryAlias = new RenameRelation((Expression) _query, _relIDProvider);
813                     BinaryOperator predicate = null;
814                     UnOpRestrict restrict = new UnOpRestrict(queryAlias);
815                     UnOpProject proj = null;
816                     try {
817                         proj = new UnOpProject(restrict, AlgebraTools.clone(projection.getItemList()), distinct, _attIDProvider); // clone beacause or renaming
818 } catch (CloneNotSupportedException e) {
819                         throw new InternalErrorException(MessageLibrary.getMessage("IE_ERR", "Could not clone item list"));
820                     }
821
822                     InnerRelationInfo in1, in2;
823
824                     for (int i = 0; i < aggrPairs.size(); i++) {
825                         aggrPair = (AggregatePair) aggrPairs.get(i);
826                         // change the type of subquery to SELECT_AGGR
827 aggrPair.subQuery1._renamedQuery = new RenameItem((Expression) aggrPair.subQuery1._query, _attIDProvider);
828                         in1 = processSelectAggr(aggrPair.subQuery1);
829                         subRelations.add(in1);
830                         aggrPair.subQuery2._renamedQuery = new RenameItem((Expression) aggrPair.subQuery2._query, _attIDProvider);
831                         in2 = processSelectAggr(aggrPair.subQuery2);
832                         subRelations.add(in2);
833
834                         // insert a duplicate of project and add a restrict
835 predicate = (BinaryOperator) aggrPair.subQuery1._anchor;
836                         // NOTE : order is based only on the fact that visitor scours left operant 1st...
837 AttributeExpression att1 = null, att2 = null;
838                         att1 = new AttributeExpression(queryAlias, aggrPair.subQuery1._renamedQuery.getName());
839                         att1.setUnderlyingExpr((Expression) in1._aggrItems.get(0));
840                         predicate.setLeftOperand(att1);
841
842                         att2 = new AttributeExpression(queryAlias, aggrPair.subQuery2._renamedQuery.getName());
843                         att2.setUnderlyingExpr((Expression) in2._aggrItems.get(0));
844                         predicate.setRightOperand(att2);
845                         restrict.addPredicate(predicate);
846                     }
847
848                     //rename attributes because an encapsulated query was created
849 if (_renameVisitor == null)
850                         _renameVisitor = new RenameAttributeExpressionVisitor();
851                     _renameVisitor.reinit(queryAlias);
852                     proj.accept(_renameVisitor);
853
854                     // add removed aggregation items (attribute expressions)
855 RenameItem ri = null;
856                     AttributeExpression ae = null;
857                     for (int i = 0; i < aggrItems.size(); i++) {
858                         ri = (RenameItem) aggrItems.get(i);
859                         ae = new AttributeExpression(queryAlias, ri.getName());
860                         ae.setUnderlyingExpr((Expression) ((UnOpAggregate) ri.getOperand()).getItemList().get(0));
861                         proj.addItem(ae);
862                     }
863
864                     _query = proj;
865                 }
866
867                 // Grab subqueries parts
868 Iterator it2 = _subQueryList.iterator();
869                 while (it2.hasNext()) {
870                     subQuery = (SubQueryNode) it2.next();
871
872                     switch (subQuery.getType()) {
873                         case TYPE_PREDICATE_AGGR :
874                             relation = processPredicateAggr(subQuery);
875                             break;
876                         case TYPE_PREDICATE_EXIST :
877                             relation = processExist(subQuery);
878                             // the project node may have been added by exist rewriting
879 if (_query instanceof UnOpProject)
880                                 projection = (UnOpProject) _query;
881                             break;
882                         case TYPE_SELECT_AGGR :
883                             relation = processSelectAggr(subQuery);
884                             break;
885
886                         default :
887                             throw new InternalErrorException(MessageLibrary.getMessage("IE_ERR", "The subquery type " + subQuery.getType() + " should not occur at such a stage of rewritting."));
888                     }
889                     subRelations.add(relation);
890                 }
891
892                 /* Optimization: limit the number of potential OUTER joins by grouping identical relations */
893                 subRelations = partitionSubQueriesByRelation(subRelations);
894
895                 /* find out PK and other parameters for outer join creation*/
896                 // Note: performed on relation and not root projection because
897 // the visitor add keys to items
898 _addKeysVisitor.reinit();
899                 mainRelation.accept(_addKeysVisitor);
900                 List keys = ((Relation) mainRelation).getKeys();
901
902                 /* Build item list for all subqueries */
903                 buildItemLists(subRelations, projection.getItemList(), ((Relation) mainRelation).visibleTableInstances(), keys, _referringNode instanceof UnOpSort ? (UnOpSort) _referringNode : null);
904
905                 /* Create a subtree(containing UnOpAggregate and UnOpgroup) for each aggregation */
906                 RenameRelation outerJoin = null;
907
908                 for (int i = 0; i < subRelations.size(); i++) {
909                     relation = (InnerRelationInfo) subRelations.get(i);
910
911                     /* Builds 1st outer join with all projection columns */
912                     if (i == 0) {
913                         /* Collect main relation predicates (put filtering the lowest possible) */
914                         List mainRelationPredicates = pickOutPredicates(mainRelation, true);
915                         if (mainRelation instanceof UnOpRestrict)
916                             mainRelation = ((UnOpRestrict) mainRelation).getOperand(); // pickOutPredicates could not remove it on top
917
918                         outerJoin = createOuterJoin(mainRelation, mainRelationPredicates, relation, distinct, mainIsAggregate);
919                     } else
920                         outerJoin = createOuterJoin(outerJoin, null, relation, distinct, mainIsAggregate);
921                 }
922
923                 if (queryAlias == null)
924                     _query = (Relation) outerJoin.getOperand();
925                 else
926                     queryAlias.setOperand(outerJoin.getOperand());
927             }
928
929             // remove from stack
930 _subQueryStack.pop();
931
932             //connect the original variable for reconstruction if topmost
933 if (_subQueryStack.isEmpty()) {
934                 if (_referringNode != null) {
935                     ((UnaryOperator) _referringNode).setOperand((Expression) _query);
936                 } else if (_renamedQuery != null) {
937                     _renamedQuery.setOperand((Expression) _query);
938                 }
939             }
940
941             return this;
942         }
943
944         private void buildItemLists(List subRelations, List mainRelationItems, Set mainRelations, List keys, UnOpSort mainSort) {
945             InnerRelationInfo relation;
946
947             // First pass: from bottom to top to cumulate return attributes
948 relation = (InnerRelationInfo) subRelations.get(0);
949             relation._items = mainRelationItems;
950
951             InnerRelationInfo underRelation = null;
952             for (int i = 1; i < subRelations.size(); i++) {
953                 relation = (InnerRelationInfo) subRelations.get(i);
954                 underRelation = (InnerRelationInfo) subRelations.get(i - 1);
955                 relation._items = new ArrayList();
956                 try {
957                     AlgebraTools.cloneCopyExpressionsWithoutDoubles(underRelation._items, relation._items);
958                     AlgebraTools.cloneCopyExpressionsWithoutDoubles(underRelation._aggrItems, relation._items);
959                 } catch (CloneNotSupportedException e) {
960                     throw new InternalErrorException(MessageLibrary.getMessage("IE_ERR", "Could not clone item lists"));
961                 }
962             }
963
964             // Second pass: from top to bottom to cumulate implicit attributes
965 // (and order by, and having) and rename relation
966
967             // create a rename for the top relation
968 relation = (InnerRelationInfo) subRelations.get(subRelations.size() - 1);
969             relation._alias = new RenameRelation(_relIDProvider);
970             relation._keys = keys;
971
972             for (int i = subRelations.size() - 1; i > 0; i--) {
973                 relation = (InnerRelationInfo) subRelations.get(i);
974                 underRelation = (InnerRelationInfo) subRelations.get(i - 1);
975
976                 // Find Attribute expressions that are not related to subquery
977 if (_foreignAttributeGrabber == null)
978                     _foreignAttributeGrabber = new ForeignAttributeGrabber();
979
980                 Collection vti = ((Relation) relation._relation).visibleTableInstances();
981                 _foreignAttributeGrabber.reinit(vti);
982                 AlgebraTools.applyVisitorOnCollection(_foreignAttributeGrabber, relation._havingClauses);
983                 AlgebraTools.applyVisitorOnCollection(_foreignAttributeGrabber, relation._predicates);
984                 if (mainSort != null) // Consider the main query sort (only 1st time)
985 AlgebraTools.applyVisitorOnCollection(_foreignAttributeGrabber, mainSort.getSortSpecificationList());
986
987                 // Copy these attributes and keys to the lower level // TODO: remove doubles
988 try {
989                     AlgebraTools.cloneCopyExpressionsWithoutDoubles(_foreignAttributeGrabber.getAttributeList(), underRelation._items);
990                     AlgebraTools.cloneCopyExpressionsWithoutDoubles(keys, underRelation._items);
991                     underRelation._keys = AlgebraTools.clone(relation._keys);
992                 } catch (CloneNotSupportedException e) {
993                     throw new InternalErrorException(MessageLibrary.getMessage("IE_ERR", "Could not clone item lists"));
994                 }
995
996                 // Create the rename at the lower level and rename items on lists at the upper one
997 if (_renameVisitor == null)
998                     _renameVisitor = new RenameAttributeExpressionVisitor();
999
1000                underRelation._alias = new RenameRelation(_relIDProvider);
1001                _renameVisitor.reinit(vti, underRelation._alias, true, true);
1002
1003                // rename the main query sort (only 1st time)
1004 if (mainSort != null) {
1005                    AlgebraTools.applyVisitorOnCollection(_renameVisitor, mainSort.getSortSpecificationList());
1006                    mainSort = null; // watchguard
1007 }
1008                AlgebraTools.applyVisitorOnCollection(_renameVisitor, relation._keys, false);
1009                AlgebraTools.applyVisitorOnCollection(_renameVisitor, relation._items, false); // this one removes aggregates
1010 AlgebraTools.applyVisitorOnCollection(_renameVisitor, relation._predicates, false);
1011                AlgebraTools.applyVisitorOnCollection(_renameVisitor, relation._havingClauses, false);
1012
1013                // Add current's level aggregates
1014 relation._items.addAll(relation._aggrItems);
1015            }
1016            // Add bottom's level aggregates
1017 relation = (InnerRelationInfo) subRelations.get(0);
1018            relation._items.addAll(relation._aggrItems);
1019        }
1020
1021        private InnerRelationInfo processSelectAggr(SubQueryNode subQuery) {
1022            /* connect to the original XQuery expr */ // Assuming there is only one
1023 List itemList = ((UnOpAggregate) subQuery._query).getItemList();
1024            RenameItem item = (RenameItem) itemList.get(0);
1025            item.setName(subQuery._renamedQuery.getName());
1026            subQuery._renamedQuery.setOperand(item.getOperand());
1027
1028            return new InnerRelationInfo(itemList, ((UnOpAggregate) subQuery._query).getOperand());
1029        }
1030
1031        private InnerRelationInfo processExist(SubQueryNode subQuery) {
1032
1033            Set outerTables = _query.visibleTableInstances();
1034            List projectAttributes = new ArrayList();
1035
1036            /* EXTERNAL/OUTER JOIN PREDICATES
1037             * Browse main query predicates to find external join predicates with
1038             * the outer table in order to add outer table attributes to
1039             * projection (do it first not to interfere with the possible
1040             * introduction of a join that may add predicates too)
1041             */
1042            PredicateHolder holder = (PredicateHolder) subQuery._anchor.getFather();
1043            Iterator it = holder.getPredicateList().iterator(), it2 = null;
1044            Expression predicate = null;
1045            AttributeExpression att = null, outerAtt = null;
1046            int nbOatt = 0, i = 0;
1047
1048            while (it.hasNext()) {
1049                predicate = (Expression) it.next();
1050                it2 = predicate.getReferredAttributes().iterator();
1051                outerAtt = null;
1052                i = nbOatt = 0;
1053                while (it2.hasNext()) {
1054                    att = (AttributeExpression) it2.next();
1055                    i++;
1056                    if (outerTables.contains(att.getTableInstance())) {
1057                        nbOatt++;
1058                        outerAtt = att;
1059                    }
1060                }
1061
1062                try {
1063                    if (i == 2 && nbOatt == 1)
1064                        projectAttributes.add(outerAtt.clone());
1065                } catch (CloneNotSupportedException ex) {
1066                    throw new SqlWrapperException(ex.getMessage(), ex);
1067                }
1068            }
1069
1070            /* EXTERNAL/INNER JOIN PREDICATES
1071            /* gather external conditions without removing them */
1072            ExternalJoinInfo sortInfo = sortSubQueryPredicates((Expression) subQuery._query, outerTables);
1073
1074            /* Piped Exists: add external table in the current exist (if foreign
1075             * , i.e. external, tables where found in subquery predicates)
1076             * in order to apply piping exist rewriting basic rule */
1077            if (!sortInfo._externalTables.isEmpty()) {
1078                if (_type != TYPE_PREDICATE_EXIST)
1079                    throw new InternalErrorException(MessageLibrary.getMessage("IE_ERR", "External join predicate should not occur out of exist subquery"));
1080
1081                // find external attribute expression and clone the referred table, and create a new alias
1082 List renamedExternalTables = null;
1083
1084                try {
1085                    renamedExternalTables = AlgebraTools.clone(sortInfo._externalTables);
1086                } catch (CloneNotSupportedException ex) {
1087                    throw new SqlWrapperException(ex.getMessage(), ex);
1088                }
1089
1090                // Change table aliases
1091 RenameRelation rTable = null, oTable = null;
1092                List keys = null;
1093                AttributeExpression rAtt = null, oAtt;
1094
1095                int len = renamedExternalTables.size();
1096                RenameAttributeExpressionVisitor renameVisitor = new RenameAttributeExpressionVisitor();
1097
1098                /* insert a restriction node for external join */
1099                if (!(_query instanceof UnOpRestrict))
1100                    _query = new UnOpRestrict((Expression) _query, new ArrayList());
1101
1102                for (i = 0; i < len; i++) {
1103                    oTable = (RenameRelation) sortInfo._externalTables.get(i);
1104                    rTable = (RenameRelation) renamedExternalTables.get(i);
1105                    rTable.setName(_relIDProvider);
1106
1107                    // get PK or equivalent
1108 keys = oTable.getKeys();
1109                    if (keys == null) {
1110                        _addKeysVisitor.reinit();
1111                        oTable.accept(_addKeysVisitor);
1112                        keys = oTable.getKeys(); // returns a list of attribute expressions without table part
1113 }
1114
1115                    /* Browse keys to build projection and join predicates */
1116                    it = keys.iterator();
1117                    Object o;
1118                    while (it.hasNext()) {
1119                        o = it.next();
1120                        if (o instanceof RenameItem)
1121                            oAtt = (AttributeExpression) ((RenameItem) o).getOperand();
1122                        else
1123                            oAtt = (AttributeExpression) o;
1124                        oAtt.setTableInstance(oTable);
1125                        rAtt = new AttributeExpression(rTable, oAtt.getName());
1126                        rAtt.setUnderlyingExpr(oAtt.getUnderlyinExpr());
1127                        projectAttributes.add(rAtt);
1128                        // 2 different attribute expressions for projection and predicates
1129 // must be created in case of late renaming (temporary table)
1130 rAtt = new AttributeExpression(rTable, oAtt.getName());
1131                        rAtt.setUnderlyingExpr(oAtt.getUnderlyinExpr());
1132                        ((UnOpRestrict) _query).addPredicate(new BinOpCompare(Constants.EQ_COMPOP, rAtt, oAtt));
1133                    }
1134
1135                    /* Replace external table by the added one into external join predicates */
1136                    renameVisitor.reinit(new ArrayList(Collections.singletonList(oTable)), rTable);
1137                    AlgebraTools.applyVisitorOnCollection(renameVisitor, sortInfo._externalJoinPredicates, false);
1138                }
1139
1140                /* add an artificial natural join (using keys) for these tables */
1141                Expression outerTable = (Expression) outerTables.iterator().next();
1142                Join join = null;
1143                if (outerTable.getFather() instanceof Join) {
1144                    join = (Join) outerTable.getFather();
1145                } else {
1146                    renamedExternalTables.add(outerTable); // Must be one if no join
1147 join = new Join();
1148                    outerTable.getFather().replaceChild(outerTable, join);
1149                }
1150                join.addOperandList(renamedExternalTables);
1151            }
1152
1153            // add a projection with external joins attributes involved (in order to keep only needed columns...)
1154 if (!projectAttributes.isEmpty()) {
1155                UnOpProject project = null;
1156                if (_query instanceof UnOpProject)
1157                    project = (UnOpProject) _query;
1158                else
1159                    project = new UnOpProject((Expression) _query, _attIDProvider);
1160                _referringNode.replaceChild((Expression) _query, project);
1161                _query = project;
1162                project.addItemList(projectAttributes);
1163            }
1164
1165            /* build the having predicate */
1166            AttributeExpression innerTupleRepresentative = null;
1167            try {
1168                innerTupleRepresentative = (AttributeExpression) findNonNullAttribute(subQuery._query.providedTableInstances()).clone();
1169            } catch (CloneNotSupportedException ex) {
1170                throw new SqlWrapperException(ex.getMessage(), ex);
1171            }
1172
1173            BinOpCompare having = new BinOpCompare(((UnOpExists) subQuery._referringNode).getNot() ? Constants.EQ_COMPOP : Constants.GT_COMPOP, new FunAggregate(FunAggregate.COUNT, innerTupleRepresentative,
1174                // TODO: in fact should be a list but FunAggregate is an UnaryOperator
1175 false), new LitInteger(0));
1176
1177            /* remove predicate from outer relation */
1178             ((PredicateHolder) subQuery._anchor.getFather()).removePredicate(subQuery._anchor);
1179
1180            return new InnerRelationInfo((Expression) subQuery._query, new ArrayList(Collections.singletonList(having)));
1181        }
1182
1183        /**
1184         * @param subQuery
1185         * @return
1186         */
1187        private InnerRelationInfo processPredicateAggr(SubQueryNode subQuery) {
1188            /* Replace subquery by an alias in the predicate */
1189            Expression aggr = ((RenameItem) ((UnOpAggregate) subQuery._query).getItemList().get(0)).getOperand();
1190            // must be only one in a predicate
1191 subQuery._referringNode.replaceChild((Expression) subQuery._query, aggr);
1192
1193            return new InnerRelationInfo(((UnOpAggregate) subQuery._query).getOperand(), new ArrayList(Collections.singletonList(subQuery._anchor)));
1194        }
1195
1196        /**
1197         * Create a partition between aggregations based on incoming relation and not
1198         * aggregation itself and merge subqueries. The alias kept is the surrounding
1199         * one if the aggreagtion has one item (in case it is referenced).
1200         * @param aggregationList
1201         * @return a list of {@link AggregatingExpression}.
1202         */
1203        private List partitionSubQueriesByRelation(List subQueryList) {
1204            ArrayList ret = new ArrayList();
1205
1206            int size;
1207            Iterator it = subQueryList.iterator();
1208            InnerRelationInfo sub1, sub2;
1209            int i;
1210
1211            /* partitions and merge in a single pass */
1212            while (it.hasNext()) {
1213                size = ret.size(); // sentinel for expression storage
1214 sub1 = (InnerRelationInfo) it.next();
1215
1216                /* browse existing partitions to find a match for unsorted */
1217                for (i = 0; i < size; i++) {
1218                    sub2 = (InnerRelationInfo) ret.get(i);
1219                    if (sub2.merge(sub1))
1220                        break;
1221                }
1222                /* no equivalent relation already encountered */
1223                if (i == size) {
1224                    ret.add(sub1);
1225                }
1226            }
1227            return ret;
1228        }
1229
1230        public byte getBrowsingStep() {
1231            return _browsingStep;
1232        }
1233
1234        public byte getType() {
1235            return _type;
1236        }
1237
1238        public void setType(byte type) {
1239            _type = type;
1240        }
1241
1242        public void setBrowsingStep(byte b) {
1243            _browsingStep = b;
1244        }
1245
1246        public void addSubQuery(SubQueryNode subQuery) {
1247            _subQueryList.add(subQuery);
1248        }
1249
1250        public Expression getCurrent() {
1251            return _current;
1252        }
1253
1254        public void setCurrent(Expression _current) {
1255            this._current = _current;
1256        }
1257    }
1258
1259    protected class InnerRelationInfo {
1260        private boolean _hasAggregate = false; // add originally aggregate items
1261 public List _aggrItems = null; // will be used to cumulate items when piping OJs
1262 public List _items = null; // will be used to cumulate items when piping OJs
1263 public Expression _relation = null;
1264        public List _havingClauses = null;
1265        public List _predicates = null; // used for building the outer join predicate (all are put in the ON clause)
1266 public List _keys = null;
1267        public RenameRelation _alias = null;
1268
1269        public InnerRelationInfo(List items, Expression relation) {
1270            this(relation, items, null);
1271            _hasAggregate = true;
1272        }
1273
1274        public InnerRelationInfo(Expression relation, List havingClauses) {
1275            this(relation, new ArrayList(), havingClauses);
1276        }
1277
1278        private InnerRelationInfo(Expression relation, List items, List havingClauses) {
1279            _aggrItems = items;
1280            _havingClauses = havingClauses;
1281            prepare(relation); // after setting other fields
1282 removeStarCounts();
1283        }
1284
1285        public boolean hasAggregate() {
1286            return _hasAggregate;
1287        }
1288
1289        /**
1290         * Predicates are picked up and relation may be renamed if needed.
1291         * Subqueries are unconditionnaly renamed because of potential splitting
1292         * in multiple Sql statements with temporary tables or views. Renaming,
1293         * considering the SQL generating algorithm, would be uneasy.
1294         * @param relation
1295         * @return
1296         */
1297        private void prepare(Expression relation) {
1298            /* Pick up predicate and remove restriction nodes carrying them */
1299            _predicates = pickOutPredicates(relation, false);
1300            // visitor could not remove the top node and multiple node may be piled
1301 while (relation instanceof UnOpRestrict && !(((UnOpRestrict) relation).getOperand() instanceof UnOpGroup)) // the top node may be a having not to be discarded
1302 relation = ((UnOpRestrict) relation).getOperand();
1303
1304            rename(relation);
1305        }
1306
1307        private void removeStarCounts() {
1308            if (_aggrItems != null) {
1309                FunAggregate aggrFunc = null;
1310                AttributeExpression tupleRepresentative = null;
1311                for (int i = 0; i < _aggrItems.size(); i++) {
1312                    aggrFunc = (FunAggregate) ((RenameItem) _aggrItems.get(i)).getOperand();
1313                    if (aggrFunc.getOperator() == FunAggregate.COUNT && !(aggrFunc.getOperand() instanceof AttributeExpression)) {
1314                        if (tupleRepresentative == null)
1315                            tupleRepresentative = (AttributeExpression) findNonNullAttribute(((Relation) _relation).providedTableInstances());
1316                        //.clone();
1317 aggrFunc.setOperand(tupleRepresentative);
1318                    }
1319                }
1320            }
1321        }
1322
1323        public void rename(Expression relation) {
1324
1325            if (relation instanceof RenameRelation || relation instanceof Join) // no need to rename relation
1326 _relation = relation;
1327            else {
1328                _relation = new RenameRelation(relation, _relIDProvider);
1329
1330                /* Prepare rename visitor */
1331                if (_renameVisitor == null)
1332                    _renameVisitor = new RenameAttributeExpressionVisitor();
1333                _renameVisitor.reinit(((Relation) relation).visibleTableInstances(), (RenameRelation) _relation);
1334
1335                /* Rename items */
1336                if (_aggrItems != null)
1337                    AlgebraTools.applyVisitorOnCollection(_renameVisitor, _aggrItems, false);
1338
1339                /* Rename predicates */
1340                if (_predicates != null)
1341                    AlgebraTools.applyVisitorOnCollection(_renameVisitor, _predicates, false);
1342
1343                /* Rename havings */
1344                if (_havingClauses != null)
1345                    AlgebraTools.applyVisitorOnCollection(_renameVisitor, _havingClauses, false);
1346            }
1347        }
1348
1349        /* If relation clauses are identical, items and havings are merged to produce one relation */
1350        public boolean merge(InnerRelationInfo merged) {
1351            if (_relation.deepEquals(merged._relation) // relation are the same
1352 && AlgebraTools.areExprListEquivalent(_predicates, merged._predicates)) {
1353
1354                /* Prepare rename visitor */ // TODO : in fact both members can be joins. Deeps equals should return a map between relations to allow renaming
1355 RenameRelation rename = (RenameRelation) ((Relation) _relation).providedTableInstances().iterator().next();
1356                if (_renameVisitor == null)
1357                    _renameVisitor = new RenameAttributeExpressionVisitor();
1358                _renameVisitor.reinit(((Relation) merged._relation).providedTableInstances(), rename);
1359
1360                /* merge aggregates */
1361                if (merged._aggrItems != null) {
1362                    /* Rename items */
1363                    AlgebraTools.applyVisitorOnCollection(_renameVisitor, merged._aggrItems, false);
1364                    if (_aggrItems == null)
1365                        _aggrItems = merged._aggrItems;
1366                    else
1367                        _aggrItems.addAll(merged._aggrItems);
1368                }
1369                /* Compare and merge havings */
1370                if (merged._havingClauses != null) {
1371                    if (_havingClauses == null)
1372                        _havingClauses = merged._havingClauses;
1373                    else if (!AlgebraTools.areExprListEquivalent(_havingClauses, merged._havingClauses)) {
1374                        // create new one cause they are final singletons...
1375 _havingClauses = new ArrayList(_havingClauses);
1376                        AlgebraTools.applyVisitorOnCollection(_renameVisitor, merged._havingClauses, false);
1377                        _havingClauses.addAll(merged._havingClauses);
1378                    }
1379                }
1380                return true;
1381            } else
1382                return false;
1383        }
1384    }
1385
1386    /**
1387     * this class scans(by means of simple scan) a algebre tree and find out key
1388     * nodes of the query (does not browse subqueries).
1389     */
1390
1391    protected class FindQuerySignatureVisitor extends DefaultSimpleVisitor {
1392        private static final String RCSRevision = "$Revision: 1.26 $";
1393        private static final String RCSName = "$Name: $";
1394
1395        private UnOpProject project = null;
1396        private PredicateHolder restrict = null;
1397        private Expression relation = null; // relation if no restriction found
1398
1399        public FindQuerySignatureVisitor() {
1400        }
1401
1402        public void reinit() {
1403            project = null;
1404            restrict = null;
1405            relation = null;
1406        }
1407
1408        public UnOpProject getProjection() {
1409            return project;
1410        }
1411
1412        public PredicateHolder getRestriction() {
1413            return restrict;
1414        }
1415
1416        public Expression getRelation() {
1417            return relation;
1418        }
1419
1420        public void visit(UnOpProject arg) {
1421            super.visit((UnaryOperator) arg);
1422            project = arg;
1423        }
1424
1425        public void visit(UnOpRestrict arg) {
1426            super.visit((UnaryOperator) arg);
1427            restrict = arg;
1428        }
1429
1430        public void visit(Join arg) {
1431            restrict = arg;
1432            relation = arg;
1433        }
1434
1435        public void visit(Table arg) {
1436            relation = arg;
1437        }
1438
1439        public void visit(DummyTable arg) {
1440            relation = arg;
1441        }
1442
1443        public void visit(BinaryAlgebra arg) {
1444            relation = arg;
1445        }
1446
1447        public void visit(BinOpOuterJoin arg) {
1448            relation = arg;
1449        }
1450    }
1451
1452    protected class RemoveAggregateFunctionVisitor extends DefaultSimpleVisitor {
1453        private static final String RCSRevision = "$Revision: 1.26 $";
1454        private static final String RCSName = "$Name: $";
1455
1456        private List _collectedItems = new ArrayList();
1457        private boolean _aggrFound = false;
1458
1459        public void reinit() {
1460            _collectedItems.clear();
1461            _aggrFound = false;
1462        }
1463
1464        public List getCollectedItems() {
1465            return _collectedItems;
1466        }
1467
1468        public boolean aggregateFound() {
1469            return _aggrFound;
1470        }
1471
1472        public void newItem() {
1473            _aggrFound = false;
1474        }
1475
1476        public void visit(FunAggregate arg) {
1477            super.visit(arg);
1478            _aggrFound = true;
1479            _collectedItems.add(arg.getOperand());
1480        }
1481    }
1482
1483    protected ExternalJoinInfo sortSubQueryPredicates(Expression subQuery, Set outerTables) {
1484        //Trace.enter(this, "sortSubQueryPredicates()", subQuery);
1485
1486        ExternalJoinInfo ret = new ExternalJoinInfo();
1487
1488        /* find out UnOpRestrict nodes */
1489        _restrictionVisitor.reinit();
1490        subQuery.accept(_restrictionVisitor);
1491        List restrictionList = _restrictionVisitor.getRestrictions();
1492
1493        /* browse found nodes */
1494        List predicateList = null;
1495
1496        Set innerTables = ((Relation) subQuery).visibleTableInstances();
1497        // TODO: if does not exist : generate a view with automatic numbering...
1498
1499        for (int i = 0; i < restrictionList.size(); i++) {
1500            Expression expr = (Expression) restrictionList.get(i);
1501            predicateList = ((PredicateHolder) expr).getPredicateList();
1502
1503            /* Split: join predicates may be intermingled NO THEY AREN'T ?*/ // TODO: to it at algebra generation time
1504 predicateList = splitPredicateList(predicateList);
1505
1506            Expression predicate = null;
1507            Set allTables = null;
1508            Iterator it = predicateList.iterator();
1509
1510            while (it.hasNext()) {
1511                predicate = (Expression) it.next();
1512                // get all referred tables
1513 allTables = predicate.getReferredTableInstances();
1514                // a copy is performed by the method
1515
1516                // remove all inner tables: if empty simple predicates (ignored)
1517 allTables.removeAll(innerTables);
1518                allTables.removeAll(outerTables);
1519
1520                // external join predicate
1521 if (!allTables.isEmpty()) {
1522                    ret._externalTables.addAll(allTables);
1523                    ret._externalJoinPredicates.add(predicate);
1524                }
1525            }
1526        }
1527
1528        //Trace.exit(this, "sortSubQueryPredicates()", subQuery);
1529 return ret;
1530    }
1531
1532    protected class ExternalJoinInfo {
1533        public List _externalTables = new ArrayList();
1534        public List _externalJoinPredicates = new ArrayList();
1535    }
1536
1537    protected class AggregatePair {
1538        public SubQueryNode subQuery1 = null;
1539        public SubQueryNode subQuery2 = null;
1540        public AggregatePair(SubQueryNode subQuery1, SubQueryNode subQuery2) {
1541            this.subQuery1 = subQuery1;
1542            this.subQuery2 = subQuery2;
1543        }
1544    }
1545
1546    /**
1547     * @param innerTables
1548     * @return
1549     */
1550    private AttributeExpression findNonNullAttribute(Set relations) {
1551
1552        Iterator it = relations.iterator(), itColumns;
1553        AttributeExpression attExp = null;
1554
1555        while (it.hasNext() && attExp == null) {
1556            attExp = ((Relation) it.next()).findNonNullAttribute();
1557        }
1558
1559        Debug.assertTrue(attExp != null, "Impossible to rewrite query because all relation attributes are nullable.");
1560
1561        return attExp;
1562    }
1563
1564    /**
1565     * @param predicateList
1566     * @return
1567     */
1568    private List splitPredicateList(List predicateList) {
1569        int len = predicateList.size();
1570
1571        if (_splitVisitor == null)
1572            _splitVisitor = new SplitPredicateVisitor();
1573        else
1574            _splitVisitor.reinit();
1575
1576        AlgebraTools.applyVisitorOnCollection(_splitVisitor, predicateList);
1577
1578        return _splitVisitor.getPredicateList();
1579    }
1580
1581    protected class SplitPredicateVisitor extends DefaultAlgebraVisitor {
1582        private static final String RCSRevision = "$Revision: 1.26 $";
1583        private static final String RCSName = "$Name: $";
1584
1585        private List _predicates = null;
1586
1587        public SplitPredicateVisitor() {
1588            reinit();
1589        }
1590
1591        public void reinit() {
1592            _predicates = new ArrayList();
1593        }
1594
1595        public List getPredicateList() {
1596            return _predicates;
1597        }
1598
1599        public void visit(BinOpBoolean arg) {
1600            // perform recursion only on cascaded BinOpBoolean "AND"
1601 if (arg.getOperator() == Constants.AND) {
1602                arg.getLeftOperand().accept(this);
1603                arg.getRightOperand().accept(this);
1604            } else
1605                _predicates.add(arg);
1606        }
1607
1608        public void visit(Expression arg) {
1609            // not a Binary boolean AND operator: gather the predicate as is
1610 _predicates.add(arg);
1611        }
1612    }
1613
1614    protected class ForeignAttributeGrabber extends DefaultCompleteVisitor {
1615
1616        private List attList = new ArrayList();
1617        private Collection _relations;
1618
1619        public void reinit(Collection renameRelations) {
1620            _relations = renameRelations;
1621            attList.clear();
1622        }
1623
1624        public List getAttributeList() {
1625            return attList;
1626        }
1627
1628        public void visit(AttributeExpression arg) {
1629            if (!_relations.contains(arg.getTableInstance()))
1630                attList.add(arg);
1631        }
1632    }
1633    
1634    protected class AttributeGrabber extends DefaultSimpleVisitor {
1635
1636        private AttributeExpression att = null;
1637
1638        public void reinit() {att = null;}
1639
1640        public AttributeExpression getAttributeExpression() {
1641            return att;
1642        }
1643
1644        public void visit(AttributeExpression arg) {
1645            att = arg;
1646        }
1647    }
1648
1649}
1650

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags