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          &n