AlgFLWR


1   /*
2    * This file belongs to the XQuark distribution.
3    * Copyright (C) 2003 Universite de Versailles Saint-Quentin.
4    * Copyright (C) 2003 XQuark Group.
5    * 
6    * This program is free software; you can redistribute it and/or
7    * modify it under the terms of the GNU Lesser General Public
8    * License as published by the Free Software Foundation; either
9    * version 2.1 of the License, or (at your option) any later version.
10   * 
11   * This program is distributed in the hope that it will be useful,
12   * but WITHOUT ANY WARRANTY; without even the implied warranty of
13   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14   * Lesser General Public License for more details.
15   * 
16   * You should have received a copy of the GNU Lesser General Public
17   * License along with this program; if not, write to the Free Software
18   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307.
19   * You can also get it at http://www.gnu.org/licenses/lgpl.html
20   * 
21   * For more information on this software, see http://www.xquark.org.
22   */
23  
24  package org.xquark.mediator.algebra;
25  
26  import java.util.*;
27  
28  import org.xquark.mediator.decomposer.*;
29  import org.xquark.mediator.plan.*;
30  import org.xquark.mediator.runtime.MediatorException;
31  import org.xquark.xquery.normalize.GetBoundVariablesVisitor;
32  import org.xquark.xquery.parser.*;
33  import org.xquark.xquery.parser.hinttree.HintTree;
34  import org.xquark.xquery.parser.primitivefunctions.fnfunctions.FunctionCOLLECTION;
35  import org.xquark.xquery.parser.util.Constants;
36  
37  /**
38   * Represent a node where nodes or leaves can fix to it. Before atomization a DepMem binds only DepSource and DepVar. After atomization, a DepMem binds only DepVar.
39   *  
40   */
41  public class AlgFLWR extends Algebra {
42      // **********************************************************************
43      // * VERSIONING
44      // **********************************************************************
45      private static final String   RCSRevision = "$Revision: 1.27 $";
46  
47      private static final String   RCSName = "$Name:  $";
48  
49      // **********************************************************************
50      // * CLASS VARIABLES
51      // **********************************************************************
52      private ArrayList subDepFLWRs = null;
53  
54      private AlgFLWR parentDepFLWR = null;
55  
56      //private ArrayList variables = null;
57      private boolean monoSource = false;
58  
59      protected Set sources = null;
60  
61      protected HintTree hinttree = null;
62  
63      // telling if information has already been computed
64      boolean hasInformation = false;
65  
66      // telling whether the subelements are done with nested loop
67      int subhandling = -1;
68  
69      // relation between variables in where expression
70      VariableDependencies vardependencies = null;
71  
72      //  private HashMap varVarWhereMap = null;
73      //  private ArrayList allExprWhereList = null;
74      //  private ArrayList complexExprWhereList = null;
75      // maps for ordering purposes
76      private HashMap varOrderMap = null;
77  
78      private HashMap orderVarMap = null;
79  
80      private ArrayList complexExprOrderList = null;
81  
82      private ArrayList varOrderList = null;
83  
84      private ArrayList varReOrderList = null;
85  
86      private ArrayList varHintList = null;
87  
88      // for compulsery hint
89      private boolean hasCompulseryMerge = false;
90  
91      private boolean hasCompulseryNested = false;
92  
93      private IsolateWhereVisitor isolateVisitor = null;
94  
95      // ******************************************************************
96      // * INITIALIZATION
97      // ******************************************************************
98      /**
99       * 
100      * @param typevisitor
101      * @param expression
102      * @param depmanager
103      */
104     public AlgFLWR(XQueryExpression expression, Variable var, AlgebraManager depmanager, boolean islet) throws MediatorException {
105         super(expression, var, depmanager, islet);
106         // set HintTree
107         hinttree = ((FLWRExpression) expression).getHintTree();
108         // fill var lists
109         fillVarLists();
110     }
111 
112     // ******************************************************************
113     // * GET/SET METHODS
114     // ******************************************************************
115     public void setDependency(AlgFLWR parentDepFLWR) {
116         if (this.parentDepFLWR != null)
117             this.parentDepFLWR.getDependencyList().remove(this);
118         this.parentDepFLWR = parentDepFLWR;
119         ArrayList tmpList = parentDepFLWR.getDependencyList();
120         if (tmpList == null) {
121             tmpList = new ArrayList();
122             tmpList.add(this);
123             parentDepFLWR.setDependencyList(tmpList);
124         } else if (!tmpList.contains(this))
125             tmpList.add(this);
126     }
127 
128     public ArrayList getDependencyList() {
129         return subDepFLWRs;
130     }
131 
132     public void setDependencyList(ArrayList subDepFLWRs) {
133         this.subDepFLWRs = subDepFLWRs;
134     }
135 
136     public boolean isRootQDB() {
137         return (parentDepFLWR == null && parent == null);
138     }
139 
140     public boolean isQDB() {
141         return (isRootQDB() || parent == null);
142     }
143 
144     public boolean isMonoSource() {
145         return monoSource;
146     }
147 
148     public void setMonoSource(boolean monoSource) {
149         this.monoSource = monoSource;
150     }
151 
152     public HintTree getHintTree() {
153         return hinttree;
154     }
155 
156     public void setHintTree(HintTree hinttree) {
157         this.hinttree = hinttree;
158     }
159 
160     public int getSubHandling() {
161         return subhandling;
162     }
163 
164     public void setSubHandling(int subhandling) {
165         this.subhandling = subhandling;
166     }
167 
168     public boolean hasCompulseryMerge() {
169         return hasCompulseryMerge;
170     }
171 
172     public boolean hasCompulseryNested() {
173         return hasCompulseryNested;
174     }
175 
176     public void updateVarDependencyList(ArrayList dependVars) {
177         if (parentDepFLWR == null || dependVars == null || dependVars.isEmpty())
178             return;
179         for (int i = 0; i < dependVars.size(); i++) {
180             Variable tmpvar = (Variable) dependVars.get(i);
181             if (!((FLWRExpression) parentDepFLWR.getExpression()).getVariables().contains(tmpvar))
182                 getParentDepFLWR().addDependSourceVariable(tmpvar);
183             else
184                 dependVars.remove(tmpvar);
185         }
186         if (!dependVars.isEmpty())
187             getParentDepFLWR().updateVarDependencyList(dependVars);
188     }
189 
190     private AtomizeWhereVisitor awvisitor = null;
191 
192     private void computeVarOrderList() throws MediatorException {
193         ArrayList orders = ((FLWRExpression) expression).getOrderBy();
194         if (orders != null) {
195             varOrderList = new ArrayList(orders.size());
196             complexExprOrderList = new ArrayList(1);
197             orderVarMap = new HashMap();
198             varOrderMap = new HashMap();
199             GetBoundVariablesVisitor gbvv = new GetBoundVariablesVisitor(true, false);
200             for (int i = 0; i < orders.size(); i++) {
201                 XQueryExpression orderExpr = (XQueryExpression) orders.get(i);
202                 //              if (orderExpr.getOrder(0) == Constants.PLACE_ORDER)
203                 //                  continue;
204                 gbvv.reset();
205                 try {
206                     orderExpr.accept(gbvv);
207                 } catch (XQueryException e) {
208                     throw new MediatorException("Could not extract variables from expression : " + orderExpr, e);
209                 }
210                 ArrayList tmpList = gbvv.getAllVariables();
211                 orderVarMap.put(orderExpr, tmpList);
212                 if (tmpList.size() > 1) {
213                     complexExprOrderList.add(orderExpr);
214                     if (varOrderList != null && !varOrderList.containsAll(tmpList))
215                         varOrderList = null;
216                     ArrayList tmpOrders = (ArrayList) varOrderMap.get(tmpList);
217                     if (tmpOrders == null) {
218                         tmpOrders = new ArrayList(1);
219                         varOrderMap.put(tmpList, tmpOrders);
220                     }
221                     tmpOrders.add(orderExpr);
222                 } else {
223                     Variable tmpVar = (Variable) tmpList.get(0);
224                     if (((FLWRExpression) expression).getVariables().contains(tmpVar)) {
225                         int pos = varOrderList.indexOf(tmpVar);
226                         if (pos >= 0 && pos != varOrderList.size() - 1)
227                             varOrderList = null;
228                         else if (pos == -1)
229                             varOrderList.add(tmpVar);
230                         ArrayList tmpOrders = (ArrayList) varOrderMap.get(tmpVar);
231                         if (tmpOrders == null) {
232                             tmpOrders = new ArrayList(1);
233                             varOrderMap.put(tmpVar, tmpOrders);
234                         }
235                         tmpOrders.add(orderExpr);
236                     }
237                 }
238             }
239             if (complexExprOrderList.isEmpty())
240                 complexExprOrderList = null;
241         }
242     }
243 
244     /*
245      * private void updateVarListWithDependencies(ArrayList varlist) { updateVarListWithDependencies(varlist, null, false); }
246      */
247     private void updateVarListWithDependencies(ArrayList varlist, ArrayList rangelist, boolean reorder) {
248         if (varlist == null || varlist.isEmpty())
249             return;
250         int i = 0;
251         while (i < varlist.size()) {
252             Variable tmpVari = (Variable) varlist.get(i);
253             Algebra tmpNode = algManager.getMapNode(tmpVari);
254             if (tmpNode != null) {
255                 ArrayList tmpList = tmpNode.getVarsDependingOn();
256                 if (tmpList != null) {
257                     for (int j = 0; j < tmpList.size(); j++) {
258                         Variable tmpVarj = (Variable) tmpList.get(j);
259                         if (rangelist != null && !rangelist.contains(tmpVarj))
260                             continue;
261                         int posj = varlist.indexOf(tmpVarj);
262                         if (posj > i) {
263                             varlist.remove(tmpVarj);
264                             varlist.add(i, tmpVarj);
265                             if (reorder) {
266                                 if (!varReOrderList.contains(tmpVari))
267                                     varReOrderList.add(tmpVari);
268                                 if (!varReOrderList.contains(tmpVarj))
269                                     varReOrderList.add(tmpVarj);
270                             }
271                             i--;
272                             break;
273                         } else if (posj == -1) {
274                             varlist.add(i, tmpVarj);
275                             i--;
276                             break;
277                         }
278                     }
279                 }
280             }
281             i++;
282         }
283     }
284 
285     private void verifyVarOrderList() {
286         if (varOrderList == null) {
287             varOrderList = ((FLWRExpression) expression).getVariables();
288             if (((FLWRExpression) expression).getOrderBy() != null)
289                 varReOrderList = ((FLWRExpression) expression).getVariables();
290         } else {
291             varReOrderList = new ArrayList();
292             // manage depending on variables
293             int i = 0;
294             while (i < varOrderList.size()) {
295                 Variable tmpVari = (Variable) varOrderList.get(i);
296                 Algebra tmpNode = algManager.getMapNode(tmpVari);
297                 ArrayList tmpList = tmpNode.getVarsDependingOn();
298                 if (tmpList != null) {
299                     for (int j = 0; j < tmpList.size(); j++) {
300                         Variable tmpVarj = (Variable) tmpList.get(j);
301                         int posj = varOrderList.indexOf(tmpVarj);
302                         if (posj > i) {
303                             varOrderList.remove(tmpVarj);
304                             varOrderList.add(i, tmpVarj);
305                             if (!varReOrderList.contains(tmpVari))
306                                 varReOrderList.add(tmpVari);
307                             if (!varReOrderList.contains(tmpVarj))
308                                 varReOrderList.add(tmpVarj);
309                             i--;
310                             break;
311                         } else if (posj == -1) {
312                             varOrderList.add(i, tmpVarj);
313                             i--;
314                             break;
315                         }
316                     }
317                 }
318                 i++;
319             }
320             if (varReOrderList.isEmpty())
321                 varReOrderList = null;
322             // manage other variables
323             ArrayList varlist = ((FLWRExpression) expression).getVariables();
324             if (varOrderList.size() < varlist.size()) {
325                 for (i = 0; i < varlist.size(); i++) {
326                     if (!varOrderList.contains(varlist.get(i))) {
327                         varOrderList.add(varlist.get(i));
328                     }
329                 }
330             }
331         }
332     }
333 
334     private void fillList(ArrayList varlist, ArrayList allvars) {
335         if (varlist.containsAll(allvars))
336             return;
337         for (int i = 0; i < allvars.size(); i++) {
338             if (!varlist.contains(allvars.get(i))) {
339                 varlist.add(allvars.get(i));
340             }
341         }
342     }
343 
344     /*
345      * private boolean verifyHintTree(HintTree hinttree) { return verifyHintTree(hinttree, new ArrayList()); } private boolean verifyHintTree(HintTree hinttree, ArrayList hintVarList) { if (hinttree == null) return false; if (hinttree.getType() == HintTree.NESTED_LOOP_TYPE) { if (hinttree.getLeftHint() instanceof HintTree) { if (!verifyHintTree((HintTree) hinttree.getLeftHint(), hintVarList)) return false; } if (hinttree.getLeftHint() instanceof Variable) { hintVarList.add(hinttree.getLeftHint()); } if (hinttree.getRightHint() instanceof HintTree) { if (!verifyHintTree((HintTree) hinttree.getRightHint(), hintVarList)) return false; } if (hinttree.getRightHint() instanceof Variable) { hintVarList.add(hinttree.getRightHint()); } } else if (hinttree.getType() == HintTree.MERGE_TYPE) { ArrayList tmplistleft = (ArrayList) hintVarList.clone(); if (hinttree.getLeftHint() instanceof HintTree) { if (!verifyHintTree((HintTree) hinttree.getLeftHint(), tmplistleft)) return false;
346      * tmplistleft.removeAll(hintVarList); } ArrayList tmplistright = (ArrayList) hintVarList.clone(); if (hinttree.getRightHint() instanceof HintTree) { if (!verifyHintTree((HintTree) hinttree.getRightHint(), tmplistright)) return false; tmplistright.removeAll(hintVarList); } hintVarList.addAll(tmplistleft); hintVarList.addAll(tmplistright); if (hinttree.getLeftHint() instanceof Variable) { hintVarList.add(hinttree.getLeftHint()); } if (hinttree.getRightHint() instanceof Variable) { hintVarList.add(hinttree.getRightHint()); } } return true; }
347      */
348 
349     private boolean verifyVarHintList() {
350         if (varHintList == null)
351             return false;
352         ArrayList vars = ((FLWRExpression) expression).getVariables();
353         // verifying all variables of the hint tree are declared in flwr
354         if (!vars.containsAll(varHintList))
355             return false;
356         // verifying that all variables are used only once
357         for (int i = 0; i < varHintList.size(); i++) {
358             if (varHintList.lastIndexOf(varHintList.get(i)) != i)
359                 return false;
360         }
361         // get all variables in vars but not in varlist
362         ArrayList remainvars = (ArrayList) vars.clone();
363         remainvars.removeAll(varHintList);
364         if (!remainvars.isEmpty()) {
365             updateVarListWithDependencies(remainvars, remainvars, false);
366         }
367         // verifying that variables in hint are bound to DepNodeSource on collections
368         for (int i = 0; i < varHintList.size(); i++) {
369             Variable vari = (Variable) vars.get(i);
370             if (vari.getBindingType() != Constants.FOR_BINDINGTYPE)
371                 return false;
372             XQueryExpression expri = vari.getExpression();
373             if (expri instanceof LocatedExpression)
374                 expri = ((LocatedExpression) expri).getExpression();
375             if (!(expri instanceof FunctionCOLLECTION))
376                 return false;
377         }
378 
379         /*
380          * // verifying that all variables of the flwr are used in the hint tree for (int i = 0; i < vars.size(); i++) { Variable vari = (Variable) vars.get(i); if (vari.getBindingType() == Constants.FOR_BINDINGTYPE && !varHintList.contains(vari)) return false; // for now no let if (vari.getBindingType() == Constants.LET_BINDINGTYPE) return false; // if (vari.getBindingType() == Constants.LET_BINDINGTYPE && varHintList.contains(vari)) // return false; }
381          */
382         return true;
383     }
384 
385     private boolean updateVarHintList(HintTree hinttree) {
386         if (hinttree == null)
387             return false;
388         ArrayList vars = ((FLWRExpression) expression).getVariables();
389         /*
390          * Object obj = hinttree.getLeftHint(); if (obj instanceof HintTree) updateVarListWithDependencies(((HintTree)obj).getVarList(),vars,false); obj = hinttree.getRightHint(); if (obj instanceof HintTree) updateVarListWithDependencies(((HintTree)obj).getVarList(),vars,false);
391          */
392         updateVarListWithDependencies(hinttree.getVarList(), vars, false);
393         return true;
394     }
395 
396     private void compeReOrdering(boolean hasMerge, ArrayList varList) {
397         if (hasMerge)
398             //varReOrderList = (ArrayList) hint.getVarList().clone();
399             varReOrderList = (ArrayList) ((FLWRExpression) expression).getVariables().clone();
400         else {
401             if (varOrderList == null || varOrderList.isEmpty())
402                 return;
403             ArrayList tmplist = (ArrayList) ((FLWRExpression) expression).getVariables().clone();
404             tmplist.removeAll(varList);
405             tmplist.addAll(0, varList);
406             if (varReOrderList == null)
407                 varReOrderList = new ArrayList();
408             else
409                 varReOrderList.clear();
410             int pos = -1;
411             for (int j = 0; j < tmplist.size(); j++) {
412                 Variable tmpVarj = (Variable) tmplist.get(j);
413                 int posj = varOrderList.indexOf(tmpVarj);
414                 if (posj > pos)
415                     pos = posj;
416                 else
417                     for (int i = 0; i < tmplist.size(); i++) {
418                         Variable tmpVari = (Variable) tmplist.get(i);
419                         if (!varReOrderList.contains(tmpVari))
420                             varReOrderList.add(tmpVari);
421                     }
422             }
423             if (varReOrderList.isEmpty())
424                 varReOrderList = null;
425         }
426     }
427 
428     /*
429      * private boolean computeVarHintList(HintTree hinttree) { if (hinttree == null) return false; Object obj = hinttree.getLeftHint(); if (obj instanceof Variable) { if (varHintList.contains(obj)) return false; else varHintList.add(obj); } else computeVarHintList((HintTree) obj); obj = hinttree.getRightHint(); if (obj instanceof Variable) { if (varHintList.contains(obj)) return false; else varHintList.add(obj); } else computeVarHintList((HintTree) obj); return true; }
430      */
431 
432     public void makeInformation() throws MediatorException {
433         if (hasInformation)
434             return;
435         hasInformation = true;
436         // verify that all children have only one variable
437         if (!isMonoSource()) {
438             if (algChildren != null) {
439                 for (int i = 0; i < algChildren.size(); i++)
440                     if (((Algebra) algChildren.get(i)).getVariables().size() != 1)
441                         throw new MediatorException("Found DepNode of more than one variable as child of DepFLWR");
442             }
443         } else {
444             if (hinttree != null) {
445                 if (hinttree.getOuterType() != HintTree.NO_TYPE)
446                     hinttree.setType(HintTree.NO_TYPE);
447             }
448         }
449         // gather information on joins if any (where clause)
450 
451         XQueryExpression wexpr = ((FLWRExpression) expression).getWhereClause();
452         if (wexpr != null) {
453             vardependencies = new VariableDependencies(wexpr);
454             //          if (awvisitor == null)
455             //              awvisitor = new AtomizeWhereVisitor();
456             //          try {
457             //              wexpr.accept(awvisitor);
458             //          } catch (XQueryException e) {
459             //              throw new MediatorException("Could not atomize where clause : " + wexpr, e);
460             //          }
461             //          varVarWhereMap = awvisitor.getVarVarMap();
462             //          allExprWhereList = awvisitor.getAllExprList();
463             //          complexExprWhereList = awvisitor.getComplexExprList();
464         }
465         // gather inforamtion on hint tree if any
466         if (hinttree != null && hinttree.getType() != HintTree.NO_TYPE) {
467             varHintList = hinttree.getVarList();
468             if (updateVarHintList(hinttree)) {
469                 if (verifyVarHintList()) {
470                 } else {
471                     hinttree = null;
472                 }
473             } else {
474                 hinttree = null;
475             }
476         }
477         computeVarOrderList();
478         if (hinttree != null)
479             compeReOrdering(hinttree.hasMerge(), hinttree.getVarList());
480         else
481             compeReOrdering(algManager.getPlan().getDefaultSubHandling() == HintTree.MERGE_TYPE, ((FLWRExpression) expression).getVariables());
482     }
483 
484     public XQueryExpression getWhereClause() {
485         return ((FLWRExpression) expression).getWhereClause();
486     }
487 
488     public VariableDependencies getVarDependencies() {
489         return vardependencies;
490     }
491 
492     // ******************************************************************
493     // * CREATE EXECUTION PLAN
494     // ******************************************************************
495     // some documentation
496     /*
497      * for now hint tree only applies on FLWR expressions (not nested for now)
498      * 
499      * if (hint tree is correct) for now correct hint tree means that all (for) variables present in the FLWR expression are also present in the hint tree (let) variables are simply merged
500      * 
501      * if (hint tree is not present or hint tree is incorrect) variables are ordered in the following order first get the order implied by the order by clauses if any and if possible insert all depending on variables add all variables not in this list make list of variables to be reordered (because of dependencies)
502      */
503 
504     //##################################################################################################################################
505     //##################################################################################################################################
506     //##################################################################################################################################
507     private Operator createVarsOperator(ExecutionPlan plan, Operator operator, List varlist, List vars) throws MediatorException {
508         //##################################################################################################################################
509         //##################################################################################################################################
510         //##################################################################################################################################
511         for (int i = 0; i < vars.size(); i++) {
512             operator = createVarOperator(plan, operator, varlist, (Variable) vars.get(i));
513         }
514         return operator;
515     }
516 
517     //##################################################################################################################################
518     //##################################################################################################################################
519     //##################################################################################################################################
520     private Operator createVarOperator(ExecutionPlan plan, Operator operator, List varlist, Variable var) throws MediatorException {
521         //##################################################################################################################################
522         //##################################################################################################################################
523         //##################################################################################################################################
524         // getting child
525         Algebra depchildi = algManager.getMapNode(var);
526         XQueryExpression depchildiexpr = depchildi.getExpression();
527         //ArrayList varidependingon = (ArrayList) depchildi.getVarsDependingOn().clone();
528         Variable vari = (Variable) depchildi.getVariables().get(0);
529         if (!isMonoSource())
530             algManager.addVarToScope(vari);
531         else
532             algManager.addVarsToScope(depchildi.getVariables());
533         boolean isleti = depchildi.isLet();
534         varlist.add(vari);
535         //      if (log.isDebugEnabled()) {
536         //          log.debug("*********** DEPFLWR CHILD STUFF *************************");
537         //          log.debug("ClassName = " + depchildi.getClass().getName());
538         //          log.debug("is let = " + depchildi.isLet());
539         //          log.debug("depchildiexpr = " + depchildiexpr);
540         //          log.debugt("vari = " + vari);
541         //          log.debug("allVars = " + algManager.getScopeVariables());
542         //          log.debug("definition vars depending on = " + depchildi.getVarsDependingOn());
543         //          log.debug("where vars depending on = " + depchildi.getVarsWhereOn());
544         //          log.debug("vars referenced by = " + depchildi.getVarsReferencedBy());
545         //          log.debugt("children = " + depchildi.getChildren());
546         //          log.debug("var dependencies = " + vardependencies);
547         //          log.debug("---------------------------------------------------------");
548         //      }
549         // add where dependencies
550         if (vardependencies != null) {
551             ArrayList tmplist = vardependencies.getAllAssociatedVariables(vari);
552             if (tmplist != null) {
553                 for (int i = 0; i < tmplist.size(); i++) {
554                     Variable tmpvari = (Variable) tmplist.get(i);
555                     if (algManager.getScopeVariables().contains(tmpvari)) {
556                         if (depchildiexpr instanceof FLWRExpression && ((FLWRExpression) depchildiexpr).getVariables().contains(tmpvari)) {
557                             if (!depchildi.getVarsWhereOn().contains(tmpvari))
558                                 depchildi.getVarsWhereOn().add(tmpvari);
559                         } else {
560                             if (!depchildi.getVarsDependingOn().contains(tmpvari))
561                                 depchildi.getVarsDependingOn().add(tmpvari);
562                         }
563                     }
564 
565                 }
566             }
567         }
568         boolean doSort = false;
569         if (operator == null) {
570             if (depchildi instanceof AlgLocated || depchildi instanceof AlgVar || depchildi instanceof AlgArithFunction)
571                 //algebra = new AlgNotSource(plan,depchildi.getExpression(),var,depchildi.isLet(),depchildi.hasIdentifier());
572                 operator = new OpNotSource(plan, depchildi);
573             else
574                 operator = (Operator) depchildi.createOperator(plan);
575             doSort = true;
576         } else {
577             if (!depchildi.getDepends()) {
578                 Operator tmpOp = depchildi.createOperator(plan);
579                 // test if sort clause and not source -> then sort in place !!!
580                 if (!(depchildi instanceof AlgSource) && varOrderMap != null) {
581                     ArrayList orders = (ArrayList) varOrderMap.get(vari);
582                     if (orders != null)
583                         tmpOp = new OpSort(plan, tmpOp, orders);
584                 }
585                 if (isleti) {
586                     operator = new OpMerge(plan, depchildiexpr, operator, tmpOp);
587                 } else {
588                     operator = new OpCartesian(plan, depchildiexpr, operator, tmpOp);
589                 }
590             } else { // varidependingon is not empty
591                 if (depchildi instanceof AlgLocated || depchildi instanceof AlgVar || depchildi instanceof AlgArithFunction) {
592                     //algebra = new AlgSimpleMerge(plan, depchildiexpr, vari, algebra, depchildi.isLet());
593                     operator = new OpSimpleMerge(plan, depchildi, operator);
594                     doSort = true;
595                 } else if (depchildi instanceof AlgFunction && depchildi.getChildren() == null) {
596                     operator = new OpSimpleMerge(plan, depchildiexpr, vari, operator, depchildi.isLet());
597                     doSort = true;
598                 } else {
599                     Operator[] tmplist = new Operator[2];
600                     tmplist[0] = operator;
601                     Operator tmpOp = depchildi.createOperator(plan);
602                     // test if sort clause and not source -> then sort in place !!!
603                     if (!(depchildi instanceof AlgSource) && varOrderMap != null) {
604                         ArrayList orders = (ArrayList) varOrderMap.get(vari);
605                         if (orders != null)
606                             tmpOp = new OpSort(plan, tmpOp, orders);
607                     }
608                     tmpOp.setDepends(depchildi);
609                     tmplist[1] = tmpOp;
610                     operator = new OpSubQuery(plan, depchildiexpr, tmplist, true, false);
611                 }
612 
613             }
614         }
615         // handle restriction if any
616 
617         XQueryExpression tmpExpr = ((FLWRExpression) expression).getWhereClause();
618         if (tmpExpr != null) {
619             if (operator instanceof OpSource || operator instanceof OpSubQuery) {
620                 if (isolateVisitor == null)
621                     isolateVisitor = new IsolateWhereVisitor(algManager.getScopeVariables());
622                 else
623                     isolateVisitor.reset(algManager.getScopeVariables());
624                 isolateVisitor.putVar(true);
625                 try {
626                     tmpExpr.accept(isolateVisitor);
627                 } catch (XQueryException e) {
628                     throw new MediatorException("Can't isolate where expression : " + tmpExpr, e);
629                 }
630 
631                 tmpExpr = isolateVisitor.getIsolatedExpression();
632                 if (tmpExpr != null) {
633                     operator = operator.addCondition(plan, tmpExpr);
634                     //operator = new OpRestrict(plan, tmpExpr, operator);
635                 }
636                 ((FLWRExpression) expression).setWhereClause(isolateVisitor.getRemainingExpression());
637             } else {
638 
639                 if (isolateVisitor == null)
640                     isolateVisitor = new IsolateWhereVisitor(algManager.getScopeVariables());
641                 else
642                     isolateVisitor.reset(algManager.getScopeVariables());
643                 isolateVisitor.putVar(true);
644                 try {
645                     tmpExpr.accept(isolateVisitor);
646                 } catch (XQueryException e) {
647                     throw new MediatorException("Can't isolate where expression : " + tmpExpr, e);
648                 }
649 
650                 tmpExpr = isolateVisitor.getIsolatedExpression();
651                 if (tmpExpr != null) {
652                     operator = operator.addCondition(plan, tmpExpr);
653                     //algebra = new OpRestrict(plan, tmpExpr, algebra);
654                 }
655                 ((FLWRExpression) expression).setWhereClause(isolateVisitor.getRemainingExpression());
656 
657             }
658         }
659         // test if sort clause and not source -> then sort in place !!!
660         if (doSort && !(depchildi instanceof AlgSource) && varOrderMap != null) {
661             ArrayList orders = (ArrayList) varOrderMap.get(vari);
662             if (orders != null)
663                 operator = new OpSort(plan, operator, orders);
664         }
665         return operator;
666     }
667 
668     // utility
669     private boolean extractConditionsfromMap(VariableDependencies dep, List varListLeft, List varListRight, ArrayList leftExpressions, ArrayList rightExpressions, ArrayList mergeRestrictions, ArrayList otherRestrictions) {
670         boolean hasnoteq = false;
671         for (int il = 0; il < varListLeft.size(); il++) {
672             Variable leftvar = (Variable) varListLeft.get(il);
673             if (vardependencies != null) {
674                 HashMap tmpmap = vardependencies.getJoinMap(leftvar);
675                 if (tmpmap != null) {
676                     // there is at least something because of hint tree verification
677                     for (int ir = 0; ir < varListRight.size(); ir++) {
678                         Variable rightvar = (Variable) varListRight.get(ir);
679                         ArrayList tmplist = (ArrayList) tmpmap.get(rightvar);
680                         if (tmplist != null) {
681                             for (int i = 0; i < tmplist.size(); i++) {
682                                 XQueryExpression tmpexpr = (XQueryExpression) tmplist.get(i);
683                                 if (tmpexpr instanceof ListOpCompExpression) {
684                                     ListOpCompExpression listopcomp = (ListOpCompExpression) tmpexpr;
685                                     XQueryExpression expr1 = listopcomp.getExpression1();
686                                     XQueryExpression expr2 = listopcomp.getExpression2();
687                                     if ((expr1 instanceof LocatedExpression || expr1 instanceof Variable) && (expr2 instanceof LocatedExpression || expr2 instanceof Variable)) {
688                                         if (listopcomp.getOperator() == Constants.EQ_COMPOP) {
689                                             //if (((LocatedExpression) expr1).startsWith((Variable) rightvar) && ((LocatedExpression) expr2).startsWith((Variable) leftvar)) {
690                                             // change LARS 11/03/04
691                                             if (((expr1 instanceof LocatedExpression && ((LocatedExpression) expr1).startsWith(rightvar)) || expr1 == rightvar) && ((expr2 instanceof LocatedExpression && ((LocatedExpression) expr2).startsWith(leftvar)) || expr2 == leftvar)) {
692                                                 XQueryExpression bufexpr = expr2;
693                                                 try {
694                                                     listopcomp.setExpression2(expr1);
695                                                     listopcomp.setExpression1(bufexpr);
696                                                 } catch (XQueryException e) {
697                                                 }
698                                             }
699                                             if (hasnoteq) {
700                                                 leftExpressions.add(mergeRestrictions.size() - 1, listopcomp.getExpression1());
701                                                 rightExpressions.add(mergeRestrictions.size() - 1, listopcomp.getExpression2());
702                                                 mergeRestrictions.add(mergeRestrictions.size() - 1, listopcomp);
703                                             } else {
704                                                 leftExpressions.add(listopcomp.getExpression1());
705                                                 rightExpressions.add(listopcomp.getExpression2());
706                                                 mergeRestrictions.add(listopcomp);
707                                             }
708                                         } else if (!hasnoteq && (listopcomp.getOperator() == Constants.GEQ_COMPOP || listopcomp.getOperator() == Constants.GT_COMPOP || listopcomp.getOperator() == Constants.LEQ_COMPOP || listopcomp.getOperator() == Constants.LT_COMPOP)) {
709                                             hasnoteq = true;
710    &nb