KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > xquark > extractor > algebra > RemoveNestedAggregation


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.algebra;
24
25 import java.util.*;
26
27 import org.xquark.extractor.common.Debug;
28 import org.xquark.extractor.common.SqlWrapperException;
29 import org.xquark.extractor.progress.SimplifyOuterJoinVisitor;
30 import org.xquark.extractor.runtime.IDProvider;
31
32 /**
33  *
34  * To change the template for this generated type comment go to
35  * Window>Preferences>Java>Code Generation>Code and Comments
36  */
37 public class RemoveNestedAggregation extends DefaultCompleteVisitor {
38
39     protected Map _vt = new HashMap();
40     protected AggregationVisitor _aggregationVisitor = new AggregationVisitor();
41     protected RestrictionVisitor _restrictionVisitor = new RestrictionVisitor();
42     protected AddKeys _addKeysVisitor = new AddKeys();
43     protected IDProvider _attIDProvider = null;
44     protected IDProvider _relIDProvider = null;
45
46     public RemoveNestedAggregation(IDProvider attIDProvider, IDProvider relIDProvider) {
47         _attIDProvider = attIDProvider;
48         _relIDProvider = relIDProvider;
49     }
50
51     /**
52      * if this UnOpProject contains nested aggregation, transform the nested
53      * aggregations into a outer join and a groupby.
54      * @param arg
55      */
56     public void visit(UnOpProject arg) {
57         //Trace.enter(this, "visit(UnOpProject arg)", arg);
58 super.visit((UnaryAlgebra) arg);
59         if (arg instanceof UnOpProject && !(arg instanceof UnOpAggregate)) {
60             List aggregationList = findAggregations(arg.getItemList());
61
62             /** TODO
63              * The aggregations contained in this project might have common
64              * base relations. In this case , several aggregation based on a same
65              * relation should by put in one aggregation.
66              * example :
67              * SELECT i.itemno ,
68              * (select max(b.bid) from bids b where b.itemno = i.itemno),
69              * (select count(b.bid) from bids b where b.itemno = i.itemno)
70              * from items i;
71              * In the above query , two nested aggregations should be put in one
72              * subquery :
73              * SELECT i.itemno ,
74              * (select max(b.bid) , count(b.bid) from bids b where b.itemno = i.itemno)
75              * from items i;
76              */
77
78             if (aggregationList != null && !aggregationList.isEmpty()) {
79                 try {
80                     /* find out main relation */
81                     Expression mainRelation = arg.getOperand();
82
83                     if (true /** TODO mainRelation is a complex algebra tree */
84                         ) {
85                         // mainRelation = new UnOpStore(mainRelation);
86 // mainRelation = new RenameRelation(mainRelation, getRelationName(9));
87 }
88
89                     /* Create a subtree (containing UnOpAggregate and UnOpgroup) for each aggregation */
90                     List groupbyList = new ArrayList();
91                     Expression groupby = null;
92                     AggregatingExpression aggrExpr = null;
93                     List predicateList = null;
94                     for (int i = 0; i < aggregationList.size(); i++) {
95                         aggrExpr = (AggregatingExpression) aggregationList.get(i);
96
97                         /* added for optimization */
98                         Expression translation = (Expression) _vt.get(aggrExpr._aggregation);
99                         if (translation != null) {
100                             aggrExpr._referringNode.replaceChild(aggrExpr._aggregation, translation);
101                             continue;
102                         }
103
104                         predicateList = pickOutJoinPredicates(aggrExpr._aggregation);
105
106                         Set tiSet = aggrExpr._aggregatedExpr.getReferredTableInstances();
107                         Debug.assertTrue(null != tiSet && !tiSet.isEmpty(), "null != tiSet && !tiSet.isEmpty()");
108                         boolean localExpression = aggrExpr._aggregation.visibleTableInstances().containsAll(tiSet);
109
110                         if ((predicateList != null && !predicateList.isEmpty()) || !localExpression) {
111                             groupby = createGroupby(mainRelation, aggrExpr, predicateList);
112                             groupbyList.add(groupby);
113                         } else {
114                             /* the aggregation is a constant */
115                             TempValue tempValue = new TempValue(aggrExpr._aggregation);
116                             aggrExpr._referringNode.replaceChild(aggrExpr._aggregation, tempValue);
117                         }
118                     }
119
120                     if (!groupbyList.isEmpty()) {
121                         /* add keys to mainRelation, this keys are needed to outer join
122                         * mainRelation and groupby that will be created later.
123                         */
124                         _addKeysVisitor.reinit();
125                         mainRelation.accept(_addKeysVisitor);
126                         List keys = ((Relation) mainRelation).getKeys();
127                         RenameRelation renameRelation = null;
128                         predicateList = null;
129
130                         BinOpOuterJoin outerJoin = null;
131                         for (int i = 0; i < groupbyList.size(); i++) {
132
133                             renameRelation = (RenameRelation) groupbyList.get(i);
134                             predicateList = createJoinPredicateList(keys, renameRelation);
135                             if (i == 0)
136                                 outerJoin = new BinOpOuterJoin(mainRelation, renameRelation, Constants.LEFT_OUTER_JOIN, predicateList);
137                             else
138                                 outerJoin = new BinOpOuterJoin(outerJoin, renameRelation, Constants.LEFT_OUTER_JOIN, predicateList);
139                         }
140
141                         arg.setOperand(outerJoin);
142                         SimplifyOuterJoinVisitor visitor = new SimplifyOuterJoinVisitor(_attIDProvider, _relIDProvider);
143                         outerJoin.accept(visitor);
144                     }
145                 } catch (CloneNotSupportedException JavaDoc ex) {
146                     throw new SqlWrapperException(ex.getMessage(), ex);
147                 }
148             }
149         }
150         //Trace.exit(this, "visit(UnOpProject arg)", arg);
151 }
152
153     public void visit(UnOpRestrict arg) {
154         //Trace.enter(this, "visit(UnOpRestrict arg)", arg);
155 super.visit((UnaryAlgebra) arg);
156
157         List aggregationList = findAggregations(arg.getPredicateList());
158
159         if (null != aggregationList && !aggregationList.isEmpty()) {
160             try {
161                 /* find out main relation */
162                 Expression mainRelation = arg.getOperand();
163
164                 /* Create a subtree(containning UnOpAggregate and UnOpgroup) for each aggregation */
165                 List groupbyList = new ArrayList();
166                 Expression groupby = null;
167                 AggregatingExpression aggrExpr = null;
168                 List predicateList = null;
169                 for (int i = 0; i < aggregationList.size(); i++) {
170                     aggrExpr = (AggregatingExpression) aggregationList.get(i);
171
172                     /* added for optimization */
173                     Expression translation = (Expression) _vt.get(aggrExpr._aggregation);
174                     if (null != translation) {
175                         aggrExpr._referringNode.replaceChild(aggrExpr._aggregation, translation);
176                         continue;
177                     }
178
179                     predicateList = pickOutJoinPredicates(aggrExpr._aggregation);
180
181                     Set tiSet = aggrExpr._aggregatedExpr.getReferredTableInstances();
182                     Debug.assertTrue(null != tiSet && !tiSet.isEmpty(), "null != tiSet && !tiSet.isEmpty()");
183                     boolean localExpression = aggrExpr._aggregation.visibleTableInstances().containsAll(tiSet);
184
185                     if ((null != predicateList && !predicateList.isEmpty()) || !localExpression) {
186                         groupby = createGroupby(mainRelation, aggrExpr, predicateList);
187                         groupbyList.add(groupby);
188                     } else {
189                         /* the aggregation is a constant */
190                         TempValue tempValue = new TempValue(aggrExpr._aggregation);
191                         aggrExpr._referringNode.replaceChild(aggrExpr._aggregation, tempValue);
192                     }
193                 }
194
195                 if (!groupbyList.isEmpty()) {
196                     /* add keys to mainRelation, this keys are needed to outer join
197                     * mainRelation and groupby that will be created later.
198                     */
199                     _addKeysVisitor.reinit();
200                     mainRelation.accept(_addKeysVisitor);
201                     List keys = ((Relation) mainRelation).getKeys();
202                     RenameRelation renameRelation = null;
203                     predicateList = null;
204
205                     BinOpOuterJoin outerJoin = null;
206                     for (int i = 0; i < groupbyList.size(); i++) {
207                         renameRelation = (RenameRelation) groupbyList.get(i);
208                         predicateList = createJoinPredicateList(keys, renameRelation);
209                         if (0 == i) {
210                             outerJoin = new BinOpOuterJoin(mainRelation, renameRelation, Constants.LEFT_OUTER_JOIN, predicateList);
211                         } else {
212                             outerJoin = new BinOpOuterJoin(outerJoin, renameRelation, Constants.LEFT_OUTER_JOIN, predicateList);
213                         }
214                     }
215
216                     arg.setOperand(outerJoin);
217                     SimplifyOuterJoinVisitor visitor = new SimplifyOuterJoinVisitor(_attIDProvider, _relIDProvider);
218                     outerJoin.accept(visitor);
219                 }
220             } catch (CloneNotSupportedException JavaDoc ex) {
221                 throw new SqlWrapperException(ex.getMessage(), ex);
222             }
223         }
224         //Trace.exit(this, "visit(UnOpRestrict arg)", arg);
225 }
226     public void visit(Join arg) {
227         //Trace.enter(this, "visit(Join arg)", arg);
228 super.visit(arg);
229
230         List aggregationList = findAggregations(arg.getPredicateList());
231
232         if (null != aggregationList && !aggregationList.isEmpty()) {
233             try {
234                 /* find out main relation */
235                 Expression mainRelation = arg;
236                 Expression father = arg.getFather();
237
238                 /* Create a subtree(containning UnOpAggregate and UnOpgroup) for each aggregation */
239                 List groupbyList = new ArrayList();
240                 Expression groupby = null;
241                 AggregatingExpression aggrExpr = null;
242                 List predicateList = null;
243                 for (int i = 0; i < aggregationList.size(); i++) {
244                     aggrExpr = (AggregatingExpression) aggregationList.get(i);
245
246                     /* added for optimization */
247                     Expression translation = (Expression) _vt.get(aggrExpr._aggregation);
248                     if (null != translation) {
249                         aggrExpr._referringNode.replaceChild(aggrExpr._aggregation, translation);
250                         continue;
251                     }
252
253                     arg.removePredicate(aggrExpr._root);
254
255                     predicateList = pickOutJoinPredicates(aggrExpr._aggregation);
256
257                     Set tiSet = aggrExpr._aggregatedExpr.getReferredTableInstances();
258                     Debug.assertTrue(null != tiSet && !tiSet.isEmpty(), "null != tiSet && !tiSet.isEmpty()");
259                     boolean localExpression = aggrExpr._aggregation.visibleTableInstances().containsAll(tiSet);
260
261                     if ((null != predicateList && !predicateList.isEmpty()) || !localExpression) {
262                         groupby = createGroupby(mainRelation, aggrExpr, predicateList);
263                         groupbyList.add(groupby);
264                     } else {
265                         /* the aggregation is a constant */
266                         TempValue tempValue = new TempValue(aggrExpr._aggregation);
267                         aggrExpr._referringNode.replaceChild(aggrExpr._aggregation, tempValue);
268                     }
269                 }
270
271                 if (!groupbyList.isEmpty()) {
272                     /* add keys to mainRelation, this keys are needed to outer join
273                     * mainRelation and groupby that will be created later.
274                     */
275                     _addKeysVisitor.reinit();
276                     mainRelation.accept(_addKeysVisitor);
277                     List keys = ((Relation) mainRelation).getKeys();
278                     RenameRelation renameRelation = null;
279                     predicateList = null;
280
281                     BinOpOuterJoin outerJoin = null;
282                     for (int i = 0; i < groupbyList.size(); i++) {
283                         renameRelation = (RenameRelation) groupbyList.get(i);
284                         predicateList = createJoinPredicateList(keys, renameRelation);
285                         if (0 == i) {
286                             outerJoin = new BinOpOuterJoin(mainRelation, renameRelation, Constants.LEFT_OUTER_JOIN, predicateList);
287                         } else {
288                             outerJoin = new BinOpOuterJoin(outerJoin, renameRelation, Constants.LEFT_OUTER_JOIN, predicateList);
289                         }
290                     }
291
292                     List list = new ArrayList();
293                     for (int i = 0; i < aggregationList.size(); i++) {
294                         list.add(((AggregatingExpression) aggregationList.get(i))._root);
295                     }
296                     UnOpRestrict restrict = new UnOpRestrict(outerJoin, list);
297                     restrict.setOperand(outerJoin);
298
299                     father.replaceChild(arg, restrict);
300
301                     SimplifyOuterJoinVisitor visitor = new SimplifyOuterJoinVisitor(_attIDProvider, _relIDProvider);
302                     outerJoin.accept(visitor);
303                 }
304             } catch (CloneNotSupportedException JavaDoc ex) {
305                 throw new SqlWrapperException(ex.getMessage(), ex);
306             }
307         }
308         //Trace.exit(this, "visit(Join arg)", arg);
309 }
310
311     /**
312      * This function
313      * 1. create a goupby subtree for an UnOpAggregate
314      * 2. update itemList in <code>project<code>
315      *
316      */
317     protected RenameRelation createGroupby(Expression mainRelation, AggregatingExpression aggregatingExpr, List joinPredicateList) throws CloneNotSupportedException JavaDoc {
318         //Trace.enter(this, "createGroupby(...)");
319 RenameRelation retVal = null;
320
321         mainRelation = (Expression) mainRelation.clone();
322         UnOpAggregate aggregation = aggregatingExpr._aggregation;
323
324         /* create a join node */
325         Join join = new Join();
326         join.addOperand(mainRelation);
327         join.addOperand(aggregation.getOperand());
328         join.setPredicateList(joinPredicateList);
329
330         /* create a groupby node */
331         _addKeysVisitor.reinit();
332         mainRelation.accept(_addKeysVisitor);
333         List keysOfMainRelation = ((Relation) mainRelation).getKeys();
334         List clonedList = AlgebraTools.clone(keysOfMainRelation);
335         UnOpGroup group = new UnOpGroup(join, clonedList);
336
337         /* create aggregation node */
338         UnOpAggregate newAggregation = new UnOpAggregate(_attIDProvider);
339         newAggregation.setOperand(group);
340         newAggregation.addItem((Expression) ((Expression) aggregation.getItemList().get(0)).clone());
341         newAggregation.setOrginalXExpr(aggregation.getOrginalXExpr());
342
343         _addKeysVisitor.reinit();
344         newAggregation.accept(_addKeysVisitor);
345
346         retVal = new RenameRelation(newAggregation, _relIDProvider);
347
348         /* modify the referencing node */
349         Expression aggregatedAttribute = (Expression) aggregation.getItemList().get(0);
350         AttributeExpression correspondingAttribut = new AttributeExpression(retVal, aggregatedAttribute.getName());
351         correspondingAttribut.setUnderlyingExpr(aggregatedAttribute);
352         aggregatingExpr._referringNode.replaceChild(aggregatingExpr._aggregation, correspondingAttribut);
353
354         /* todo added for optimization */
355         RenameRelation ti = retVal;
356         RenameItem aggr = (RenameItem) aggregation.getItemList().get(0);
357         AttributeExpression translation = new AttributeExpression(ti, aggr.getName());
358         translation.setUnderlyingExpr(aggr);
359         _vt.put(aggregatingExpr._aggregation, translation);
360
361         //Trace.exit(this, "createGroupby(...)");
362 return retVal;
363     }
364
365     protected List createJoinPredicateList(List keys, RenameRelation renameRelation) throws CloneNotSupportedException JavaDoc {
366         //Trace.enter(this, "createJoinPredicateList(List keys, RenameRelation renameRelation)");
367 List retVal = new ArrayList();
368
369         keys = AlgebraTools.clone(keys);
370         AttributeExpression keyItem = null;
371
372         _addKeysVisitor.reinit();
373         renameRelation.accept(_addKeysVisitor);
374         List keysInAggregation = AlgebraTools.clone(renameRelation.getKeys());
375         AttributeExpression keyInAggregation = null;
376
377         for (int i = 0; i < keys.size(); i++) {
378             keyItem = (AttributeExpression) keysInAggregation.get(i);
379             keyInAggregation = (AttributeExpression) keys.get(i);
380             retVal.add(new BinOpCompare(Constants.EQ_COMPOP, keyItem, keyInAggregation));
381         }
382
383         //Trace.exit(this, "createJoinPredicateList(List keys, RenameRelation renameRelation)");
384 return retVal;
385     }
386
387     /**
388      * Browse a tree for {@link UnOpRestrict} and {@link Join} nodes and pick out
389      * predicates referencing tables that are not in scope.
390      * @param tree an expression.
391      * @return a list of predicate expressions.
392      */
393     protected List pickOutJoinPredicates(Expression tree) {
394         //Trace.enter(this, "pickOutJoinPredicats(Expression tree)", tree);
395 List retVal = new ArrayList();
396
397         /* find out UnOpRestrict nodes */
398         List joinPredicateList = new ArrayList();
399         _restrictionVisitor.reinit();
400         tree.accept(_restrictionVisitor);
401         List restrictionList = _restrictionVisitor.getRestrictions();
402
403         /* browse found nodes */
404         UnOpRestrict restrict = null;
405         Set vti = null;
406         List predicateList = null;
407
408         for (int i = 0; i < restrictionList.size(); i++) {
409             Expression expr = (Expression) restrictionList.get(i);
410
411             vti = ((Relation) expr).visibleTableInstances();
412             if (expr instanceof PredicateHolder) {
413                 predicateList = ((PredicateHolder) expr).getPredicateList();
414             } else {
415                 Debug.nyi("pickOutJoinPredicats(Expression tree)");
416             }
417
418             Expression predicate = null;
419             Set rti = null;
420             for (int j = predicateList.size() - 1; j >= 0; j--) { // reverse order removes index problems caused by removal
421 predicate = (Expression) predicateList.get(j);
422                 rti = predicate.getReferredTableInstances();
423                 if (!vti.containsAll(rti)) { /** @todo vti = null */
424                     retVal.add(predicate);
425                     ((PredicateHolder) expr).removePredicate(predicate);
426                 }
427             }
428         }
429
430         //Trace.exit(this, "pickOutJoinPredicats(Expression tree)", tree);
431 return retVal;
432     }
433
434     /**
435      * Find out if this project node contains aggregation in its itemList
436      * @return a list of AggregatingExpression
437      *
438      */
439     protected List findAggregations(List exprList) {
440         //Trace.enter(this, "List findAggregations(List exprList)");
441 List retVal = new ArrayList();
442
443         Expression expr = null;
444         AggregatingExpression aggrExpr = null;
445
446         if (null != exprList) {
447             int size = exprList.size();
448             for (int i = 0; i < size; i++) {
449                 expr = (Expression) exprList.get(i);
450                 _aggregationVisitor.reinit();
451                 expr.accept(_aggregationVisitor);
452                 if (_aggregationVisitor.isAggregation()) {
453
454                     aggrExpr = new AggregatingExpression(expr, _aggregationVisitor.getAggregation().getFather(), _aggregationVisitor.getAggregation(), _aggregationVisitor.getAggregatedExpression());
455                     retVal.add(aggrExpr);
456                 }
457             }
458         }
459
460         //Trace.exit(this, "List findAggregations(List exprList)");
461 return retVal;
462     }
463
464     /**
465      * An AggregatingExpression may be a simple aggregation, (i.e. <code>select
466      * max(col1) from table1 where predicate1 <code>) or expression built on top
467      * of a simple aggregation(i.e. <code> 2 * select max(col1) from table1
468      * where predicate1 <code>). In this later case, AggregatingExpression indicates
469      * important node in the tree.
470      */
471     protected class AggregatingExpression {
472
473         /**
474          * Constructor.
475          * @param root base expression that was scanned to find an aggregation.
476          * Typically an item or a predicate.
477          * @param referringNode The parent node of aggregation expression. Generally
478          * a RenameItem node. But may be another operator (2*select(max)).
479          * @param aggregation The aggregation expression (may not be an aggregation
480          * function).
481          * @param aggregatedExpr The argument of aggregation function.
482          */
483         public AggregatingExpression(Expression root, Expression referringNode, UnOpAggregate aggregation, Expression aggregatedExpr) {
484             _root = root;
485             _referringNode = referringNode;
486             _aggregation = aggregation;
487             _aggregatedExpr = aggregatedExpr;
488         }
489
490         /**
491          * Base expression.
492          */
493         public Expression _root = null;
494
495         /**
496          * The parent node of aggregation expression.
497          */
498         public Expression _referringNode = null;
499
500         /**
501          * The aggregation expression.
502          */
503         public UnOpAggregate _aggregation = null;
504
505         /**
506          * the argument of aggregation function.
507          */
508         public Expression _aggregatedExpr = null;
509     }
510
511     /**
512      * this class scan a algebra tree and determine whether it is an aggregation
513      */
514     protected class AggregationVisitor extends DefaultSimpleVisitor {
515         private static final String JavaDoc RCSRevision = "$Revision: 1.8 $";
516         private static final String JavaDoc RCSName = "$Name: $";
517
518         private UnOpAggregate _aggregation = null;
519
520         public AggregationVisitor() {
521         }
522
523         public void reinit() {
524             _aggregation = null;
525         }
526
527         public boolean isAggregation() {
528             return null != _aggregation;
529         }
530
531         public UnOpAggregate getAggregation() {
532             return _aggregation;
533         }
534
535         public Expression getAggregatedExpression() {
536             Expression retVal = null;
537             Expression item = (Expression) _aggregation.getItemList().get(0);
538             if (item instanceof RenameItem) {
539                 item = ((RenameItem) item).getOperand();
540             }
541
542             Debug.assertTrue(item instanceof FunAggregate, "item instanceof FunAggregate");
543
544             FunAggregate funAggregate = (FunAggregate) item;
545             retVal = funAggregate.getOperand();
546             return retVal;
547         }
548
549         public void visit(UnaryAlgebra arg) {
550         }
551
552         public void visit(BinaryAlgebra arg) {
553         }
554
555         public void visit(Join arg) {
556         }
557
558         public void visit(UnOpAggregate arg) {
559             _aggregation = arg;
560         }
561     }
562
563 }
564
Popular Tags