JoinNode


1   /*
2   
3      Derby - Class org.apache.derby.impl.sql.compile.JoinNode
4   
5      Licensed to the Apache Software Foundation (ASF) under one or more
6      contributor license agreements.  See the NOTICE file distributed with
7      this work for additional information regarding copyright ownership.
8      The ASF licenses this file to you under the Apache License, Version 2.0
9      (the "License"); you may not use this file except in compliance with
10     the License.  You may obtain a copy of the License at
11  
12        http://www.apache.org/licenses/LICENSE-2.0
13  
14     Unless required by applicable law or agreed to in writing, software
15     distributed under the License is distributed on an "AS IS" BASIS,
16     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17     See the License for the specific language governing permissions and
18     limitations under the License.
19  
20   */
21  
22  package org.apache.derby.impl.sql.compile;
23  
24  import org.apache.derby.iapi.services.context.ContextManager;
25  
26  import org.apache.derby.iapi.services.compiler.MethodBuilder;
27  
28  import org.apache.derby.iapi.services.sanity.SanityManager;
29  
30  import org.apache.derby.iapi.error.StandardException;
31  
32  import org.apache.derby.iapi.sql.compile.Optimizable;
33  import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
34  import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
35  import org.apache.derby.iapi.sql.compile.Optimizer;
36  import org.apache.derby.iapi.sql.compile.Visitable;
37  import org.apache.derby.iapi.sql.compile.Visitor;
38  import org.apache.derby.iapi.sql.compile.CostEstimate;
39  import org.apache.derby.iapi.sql.compile.RowOrdering;
40  import org.apache.derby.iapi.sql.compile.C_NodeTypes;
41  
42  import org.apache.derby.iapi.sql.dictionary.DataDictionary;
43  import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
44  import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
45  
46  import org.apache.derby.iapi.types.TypeId;
47  import org.apache.derby.iapi.types.DataTypeDescriptor;
48  
49  import org.apache.derby.iapi.reference.SQLState;
50  import org.apache.derby.iapi.reference.ClassName;
51  
52  import org.apache.derby.iapi.sql.Activation;
53  import org.apache.derby.iapi.sql.ResultSet;
54  
55  import org.apache.derby.iapi.store.access.TransactionController;
56  
57  import org.apache.derby.iapi.services.loader.GeneratedMethod;
58  
59  import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
60  
61  import org.apache.derby.iapi.util.JBitSet;
62  import org.apache.derby.iapi.util.PropertyUtil;
63  import org.apache.derby.iapi.services.classfile.VMOpcode;
64  
65  import java.util.Properties  ;
66  import java.util.Vector  ;
67  
68  /**
69   * A JoinNode represents a join result set for either of the basic DML
70   * operations: SELECT and INSERT.  For INSERT - SELECT, any of the
71   * fields in a JoinNode can be used (the JoinNode represents
72   * the (join) SELECT statement in the INSERT - SELECT).  For INSERT,
73   * the resultColumns in the selectList will contain the names of the columns
74   * being inserted into or updated.
75   *
76   * @author Jeff Lichtman
77   */
78  
79  public class JoinNode extends TableOperatorNode
80  {
81      /* Join semantics */
82      public static final int INNERJOIN = 1;
83      public static final int CROSSJOIN = 2;
84      public static final int LEFTOUTERJOIN = 3;
85      public static final int RIGHTOUTERJOIN = 4;
86      public static final int FULLOUTERJOIN = 5;
87      public static final int UNIONJOIN = 6;
88  
89      private boolean optimized;
90  
91      private PredicateList leftPredicateList;
92      private PredicateList rightPredicateList;
93  
94      protected boolean flattenableJoin = true;
95      Vector                aggregateVector;
96      SubqueryList        subqueryList;
97      ValueNode           joinClause;
98      boolean             joinClauseNormalized;
99      PredicateList       joinPredicates;
100     ResultColumnList    usingClause;
101     //User provided optimizer overrides
102     Properties   joinOrderStrategyProperties;
103 
104 
105     /**
106      * Initializer for a JoinNode.
107      *
108      * @param leftResult    The ResultSetNode on the left side of this join
109      * @param rightResult   The ResultSetNode on the right side of this join
110      * @param onClause      The ON clause
111      * @param usingClause   The USING clause
112      * @param selectList    The result column list for the join
113      * @param tableProperties   Properties list associated with the table
114      * @param joinOrderStrategyProperties   User provided optimizer overrides
115      *
116      * @exception StandardException     Thrown on error
117      */
118     public void init(
119                     Object   leftResult,
120                     Object   rightResult,
121                     Object   onClause,
122                     Object   usingClause,
123                     Object   selectList,
124                     Object   tableProperties,
125                     Object   joinOrderStrategyProperties)
126             throws StandardException
127     {
128         super.init(leftResult, rightResult, tableProperties);
129         resultColumns = (ResultColumnList) selectList;
130         joinClause = (ValueNode) onClause;
131         joinClauseNormalized = false;
132         this.usingClause = (ResultColumnList) usingClause;
133         this.joinOrderStrategyProperties = (Properties  )joinOrderStrategyProperties;
134 
135         /* JoinNodes can be generated in the parser or at the end of optimization.
136          * Those generated in the parser do not have resultColumns yet.
137          */
138         if (resultColumns != null)
139         {
140             /* A longer term assertion */
141             if (SanityManager.DEBUG)
142             {
143                 SanityManager.ASSERT((leftResultSet.getReferencedTableMap() != null &&
144                                       rightResultSet.getReferencedTableMap() != null) ||
145                                      (leftResultSet.getReferencedTableMap() == null &&
146                                       rightResultSet.getReferencedTableMap() == null),
147                     "left and right referencedTableMaps are expected to either both be non-null or both be null");
148             }
149 
150             /* Build the referenced table map (left || right) */
151             if (leftResultSet.getReferencedTableMap() != null)
152             {
153                 referencedTableMap = (JBitSet) leftResultSet.getReferencedTableMap().clone();
154                 referencedTableMap.or((JBitSet) rightResultSet.getReferencedTableMap());
155             }
156         }
157         joinPredicates = (PredicateList) getNodeFactory().getNode(
158                                             C_NodeTypes.PREDICATE_LIST,
159                                             getContextManager());
160     }
161 
162     /*
163      *  Optimizable interface
164      */
165 
166     /**
167      * @see org.apache.derby.iapi.sql.compile.Optimizable#optimizeIt
168      *
169      * @exception StandardException     Thrown on error
170      */
171     public CostEstimate optimizeIt(
172                             Optimizer optimizer,
173                             OptimizablePredicateList predList,
174                             CostEstimate outerCost,
175                             RowOrdering rowOrdering)
176             throws StandardException
177     {
178         optimizer.trace(Optimizer.CALLING_ON_JOIN_NODE, 0, 0, 0.0, null);
179 
180         // It's possible that a call to optimize the left/right will cause
181         // a new "truly the best" plan to be stored in the underlying base
182         // tables.  If that happens and then we decide to skip that plan
183         // (which we might do if the call to "considerCost()" below decides
184         // the current path is infeasible or not the best) we need to be
185         // able to revert back to the "truly the best" plans that we had
186         // saved before we got here.  So with this next call we save the
187         // current plans using "this" node as the key.  If needed, we'll
188         // then make the call to revert the plans in OptimizerImpl's
189         // getNextDecoratedPermutation() method.
190         updateBestPlanMap(ADD_PLAN, this);
191 
192         /*
193         ** RESOLVE: Most types of Optimizables only implement estimateCost(),
194         ** and leave it up to optimizeIt() in FromTable to figure out the
195         ** total cost of the join.  For joins, though, we want to figure out
196         ** the best plan for the join knowing how many outer rows there are -
197         ** it could affect the join strategy significantly.  So we implement
198         ** optimizeIt() here, which overrides the optimizeIt() in FromTable.
199         ** This assumes that the join strategy for which this join node is
200         ** the inner table is a nested loop join, which will not be a valid
201         ** assumption when we implement other strategies like materialization
202         ** (hash join can work only on base tables).
203         */
204 
205         /* RESOLVE - Need to figure out how to really optimize this node. */
206 
207         // RESOLVE: NEED TO SET ROW ORDERING OF SOURCES IN THE ROW ORDERING
208         // THAT WAS PASSED IN.
209         leftResultSet = optimizeSource(
210                             optimizer,
211                             leftResultSet,
212                             getLeftPredicateList(),
213                             outerCost);
214 
215         /* Move all joinPredicates down to the right.
216          * RESOLVE - When we consider the reverse join order then
217          * we will have to pull them back up and then push them
218          * down to the other side when considering the reverse
219          * join order.
220          * RESOLVE - This logic needs to be looked at when we
221          * implement full outer join.
222          */
223         // Walk joinPredicates backwards due to possible deletes
224         for (int index = joinPredicates.size() - 1; index >= 0; index --)
225         {
226             JBitSet   curBitSet;
227             Predicate predicate;
228 
229             predicate = (Predicate) joinPredicates.elementAt(index);
230             if (! predicate.getPushable())
231             {
232                 continue;
233             }
234             joinPredicates.removeElementAt(index);
235             getRightPredicateList().addElement(predicate);
236         }
237 
238         rightResultSet = optimizeSource(
239                             optimizer,
240                             rightResultSet,
241                             getRightPredicateList(),
242                             leftResultSet.getCostEstimate());
243 
244         costEstimate = getCostEstimate(optimizer);
245 
246         /*
247         ** We add the costs for the inner and outer table, but the number
248         ** of rows is that for the inner table only.
249         */
250         costEstimate.setCost(
251             leftResultSet.getCostEstimate().getEstimatedCost() +
252             rightResultSet.getCostEstimate().getEstimatedCost(),
253             rightResultSet.getCostEstimate().rowCount(),
254             rightResultSet.getCostEstimate().rowCount());
255 
256         /*
257         ** Some types of joins (e.g. outer joins) will return a different
258         ** number of rows than is predicted by optimizeIt() in JoinNode.
259         ** So, adjust this value now. This method does nothing for most
260         ** join types.
261         */
262         adjustNumberOfRowsReturned(costEstimate);
263 
264         /*
265         ** Get the cost of this result set in the context of the whole plan.
266         */
267         getCurrentAccessPath().
268             getJoinStrategy().
269                 estimateCost(
270                             this,
271                             predList,
272                             (ConglomerateDescriptor) null,
273                             outerCost,
274                             optimizer,
275                             costEstimate
276                             );
277 
278         optimizer.considerCost(this, predList, costEstimate, outerCost);
279 
280         /* Optimize subqueries only once, no matter how many times we're called */
281         if ( (! optimized) && (subqueryList != null))
282         {
283             /* RESOLVE - Need to figure out how to really optimize this node.
284             * Also need to figure out the pushing of the joinClause.
285             */
286             subqueryList.optimize(optimizer.getDataDictionary(),
287                                     costEstimate.rowCount());
288             subqueryList.modifyAccessPaths();
289         }
290 
291         optimized = true;
292 
293         return costEstimate;
294     }
295 
296     /**
297      * @see Optimizable#pushOptPredicate
298      *
299      * @exception StandardException     Thrown on error
300      */
301 
302     public boolean pushOptPredicate(OptimizablePredicate optimizablePredicate)
303             throws StandardException
304     {
305         if (SanityManager.DEBUG)
306         {
307             SanityManager.ASSERT(optimizablePredicate instanceof Predicate,
308                 "optimizablePredicate expected to be instanceof Predicate");
309             SanityManager.ASSERT(! optimizablePredicate.hasSubquery() &&
310                                  ! optimizablePredicate.hasMethodCall(),
311                 "optimizablePredicate either has a subquery or a method call");
312         }
313 
314         /* Add the matching predicate to the joinPredicates */
315         joinPredicates.addPredicate((Predicate) optimizablePredicate);
316 
317         /* Remap all of the ColumnReferences to point to the
318          * source of the values.
319          */
320         RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
321         ((Predicate) optimizablePredicate).getAndNode().accept(rcrv);
322 
323         return true;
324     }
325 
326     /**
327      * @see Optimizable#modifyAccessPath
328      *
329      * @exception StandardException     Thrown on error
330      */
331     public Optimizable modifyAccessPath(JBitSet outerTables) throws StandardException
332     {
333         super.modifyAccessPath(outerTables);
334 
335         /* By the time we're done here, both the left and right
336          * predicate lists should be empty because we pushed everything
337          * down.
338          */
339         if (SanityManager.DEBUG)
340         {
341             if (getLeftPredicateList().size() != 0)
342             {
343                 SanityManager.THROWASSERT(
344                     "getLeftPredicateList().size() expected to be 0, not " +
345                     getLeftPredicateList().size());
346             }
347             if (getRightPredicateList().size() != 0)
348             {
349                 SanityManager.THROWASSERT(
350                     "getRightPredicateList().size() expected to be 0, not " +
351                     getRightPredicateList().size());
352             }
353         }
354 
355         return this;
356     }
357 
358 
359     /**
360      *  Some types of joins (e.g. outer joins) will return a different
361      *  number of rows than is predicted by optimizeIt() in JoinNode.
362      *  So, adjust this value now. This method does nothing for most
363      *  join types.
364      */
365     protected void adjustNumberOfRowsReturned(CostEstimate costEstimate)
366     {
367     }
368 
369     /**
370      * Return a ResultColumnList with all of the columns in this table.
371      * (Used in expanding '*'s.)
372      * NOTE: Since this method is for expanding a "*" in the SELECT list,
373      * ResultColumn.expression will be a ColumnReference.
374      *
375      * @param allTableName      The qualifier on the "*"
376      *
377      * @return ResultColumnList List of result columns from this table.
378      *
379      * @exception StandardException     Thrown on error
380      */
381     public ResultColumnList getAllResultColumns(TableName allTableName)
382             throws StandardException
383     {
384         /* We need special processing when there is a USING clause.
385          * The resulting table will be the join columns from
386          * the outer table followed by the non-join columns from 
387          * left side plus the non-join columns from the right side.
388          */
389         if (usingClause == null)
390         {
391             return getAllResultColumnsNoUsing(allTableName);
392         }
393 
394         /* Get the logical left side of the join.
395          * This is where the join columns come from.
396          * (For RIGHT OUTER JOIN, the left is the right
397          * and the right is the left and the JOIN is the NIOJ).
398          */
399         ResultSetNode   logicalLeftRS = getLogicalLeftResultSet();
400 
401         // Get the join columns
402         ResultColumnList joinRCL = logicalLeftRS.getAllResultColumns(
403                                         null).
404                                             getJoinColumns(usingClause);
405 
406         // Get the left and right RCLs
407         ResultColumnList leftRCL = leftResultSet.getAllResultColumns(allTableName); 
408         ResultColumnList rightRCL = rightResultSet.getAllResultColumns(allTableName); 
409 
410         /* Chop the join columns out of the both left and right.
411          * Thanks to the ANSI committee, the join columns 
412          * do not belong to either table.
413          */
414         if (leftRCL != null)
415         {
416             leftRCL.removeJoinColumns(usingClause);
417         }
418         if (rightRCL != null)
419         {
420             rightRCL.removeJoinColumns(usingClause);
421         }
422 
423         /* If allTableName is null, then we want to return the splicing
424          * of the join columns followed by the non-join columns from
425          * the left followed by the non-join columns from the right.
426          * If not, then at most 1 side should match.
427          * NOTE: We need to make sure that the RC's VirtualColumnIds
428          * are correct (1 .. size).
429          */
430         if (leftRCL == null)
431         {
432             rightRCL.resetVirtualColumnIds();
433             return rightRCL;
434         }
435         else if (rightRCL == null)
436         {
437             leftRCL.resetVirtualColumnIds();
438             return leftRCL;
439         }
440         else
441         {
442             /* Both sides are non-null.  This should only happen
443              * if allTableName is null.
444              */
445             if (SanityManager.DEBUG)
446             {
447                 if (allTableName != null)
448                 {
449                     SanityManager.THROWASSERT(
450                         "allTableName (" + allTableName + 
451                         ") expected to be null");
452                 }
453             }
454             joinRCL.destructiveAppend(leftRCL);
455             joinRCL.destructiveAppend(rightRCL);
456             joinRCL.resetVirtualColumnIds();
457             return joinRCL;
458         }
459     }
460 
461     /**
462      * Return a ResultColumnList with all of the columns in this table.
463      * (Used in expanding '*'s.)
464      * NOTE: Since this method is for expanding a "*" in the SELECT list,
465      * ResultColumn.expression will be a ColumnReference.
466      * NOTE: This method is handles the case when there is no USING clause.
467      * The caller handles the case when there is a USING clause.
468      *
469      * @param allTableName      The qualifier on the "*"
470      *
471      * @return ResultColumnList List of result columns from this table.
472      *
473      * @exception StandardException     Thrown on error
474      */
475     private ResultColumnList getAllResultColumnsNoUsing(TableName allTableName)
476             throws StandardException
477     {
478         ResultColumnList leftRCL = leftResultSet.getAllResultColumns(allTableName); 
479         ResultColumnList rightRCL = rightResultSet.getAllResultColumns(allTableName); 
480         /* If allTableName is null, then we want to return the spliced
481          * left and right RCLs.  If not, then at most 1 side should match.
482          */
483         if (leftRCL == null)
484         {
485             return rightRCL;
486         }
487         else if (rightRCL == null)
488         {
489             return leftRCL;
490         }
491         else
492         {
493             /* Both sides are non-null.  This should only happen
494              * if allTableName is null.
495              */
496             if (SanityManager.DEBUG)
497             {
498                 if (allTableName != null)
499                 {
500                     SanityManager.THROWASSERT(
501                         "allTableName (" + allTableName + 
502                         ") expected to be null");
503                 }
504             }
505 
506             // Return a spliced copy of the 2 lists
507             ResultColumnList tempList =
508                                 (ResultColumnList) getNodeFactory().getNode(
509                                                 C_NodeTypes.RESULT_COLUMN_LIST,
510                                                 getContextManager());
511             tempList.nondestructiveAppend(leftRCL);
512             tempList.nondestructiveAppend(rightRCL);
513             return tempList;
514         }
515     }
516 
517     /**
518      * Try to find a ResultColumn in the table represented by this FromTable
519      * that matches the name in the given ColumnReference.
520      *
521      * @param columnReference   The columnReference whose name we're looking
522      *              for in the given table.
523      *
524      * @return  A ResultColumn whose expression is the ColumnNode
525      *          that matches the ColumnReference.
526      *      Returns null if there is no match.
527      *
528      * @exception StandardException     Thrown on error
529      */
530 
531     public ResultColumn getMatchingColumn(ColumnReference columnReference) throws StandardException
532     {
533         /* Get the logical left and right sides of the join.
534          * (For RIGHT OUTER JOIN, the left is the right
535          * and the right is the left and the JOIN is the NIOJ).
536          */
537         ResultSetNode   logicalLeftRS = getLogicalLeftResultSet();
538         ResultSetNode   logicalRightRS = getLogicalRightResultSet();
539         ResultColumn    leftRC = null;
540         ResultColumn    resultColumn = null;
541         ResultColumn    rightRC = null;
542         ResultColumn    usingRC = null;
543 
544         leftRC = logicalLeftRS.getMatchingColumn(columnReference);
545 
546         if (leftRC != null)
547         {
548             resultColumn = leftRC;
549 
550             /* Find out if the column is in the using clause */
551             if (usingClause != null)
552             {
553                 usingRC = usingClause.getResultColumn(leftRC.getName());
554             }
555         }
556 
557         /* We only search on the right if the column isn't in the
558          * USING clause.
559          */
560         if (usingRC == null)
561         {
562             rightRC = logicalRightRS.getMatchingColumn(columnReference);
563         }
564 
565         if (rightRC != null)
566         {
567             /* We must catch ambiguous column references for joins here,
568              * since FromList only checks for ambiguous references between
569              * nodes, not within a node.
570              */
571             if (leftRC != null)
572             {
573                 throw StandardException.newException(SQLState.LANG_AMBIGUOUS_COLUMN_NAME, 
574                          columnReference.getSQLColumnName());
575             }
576             resultColumn = rightRC;
577         }
578 
579         /* Insert will bind the underlying result sets which have
580          * tables twice. On the 2nd bind, resultColumns != null,
581          * we must return the RC from the JoinNode's RCL which is above
582          * the RC that we just found above.  (Otherwise, the source
583          * for the ColumnReference will be from the wrong ResultSet
584          * at generate().)
585          */
586         if (resultColumns != null)
587         {
588             int rclSize = resultColumns.size();
589             for (int index = 0; index < rclSize; index++)
590             {
591                 ResultColumn rc = (ResultColumn) resultColumns.elementAt(index);
592                 VirtualColumnNode vcn = (VirtualColumnNode) rc.getExpression();
593                 if (resultColumn == vcn.getSourceColumn())
594                 {
595                     resultColumn = rc;
596                     break;
597                 }
598             }
599         }
600 
601         return resultColumn;
602     }
603 
604     /**
605      * Bind the result columns of this ResultSetNode when there is no
606      * base table to bind them to.  This is useful for SELECT statements,
607      * where the result columns get their types from the expressions that
608      * live under them.
609      *
610      * @param fromListParam     FromList to use/append to.
611      *
612      * @exception StandardException     Thrown on error
613      */
614     public void bindResultColumns(FromList fromListParam)
615                     throws StandardException
616     {
617         super.bindResultColumns(fromListParam);
618 
619         /* Now we build our RCL */
620         buildRCL();
621 
622         /* We cannot bind the join clause until after we've bound our
623          * result columns. This is because the resultColumns from the
624          * children are propagated and merged to create our resultColumns
625          * in super.bindRCs().  If we bind the join clause prior to that
626          * call, then the ColumnReferences in the join clause will point
627          * to the children's RCLs at the time that they are bound, but
628          * will end up pointing above themselves, to our resultColumns,
629          * after the call to super.bindRCS().
630          */
631         deferredBindExpressions(fromListParam);
632     }
633 
634     /**
635      * Bind the result columns for this ResultSetNode to a base table.
636      * This is useful for INSERT and UPDATE statements, where the
637      * result columns get their types from the table being updated or
638      * inserted into.
639      * If a result column list is specified, then the verification that the 
640      * result column list does not contain any duplicates will be done when
641      * binding them by name.
642      *
643      * @param targetTableDescriptor The TableDescriptor for the table being
644      *              updated or inserted into
645      * @param targetColumnList  For INSERT statements, the user
646      *                  does not have to supply column
647      *                  names (for example, "insert into t
648      *                  values (1,2,3)".  When this
649      *                  parameter is null, it means that
650      *                  the user did not supply column
651      *                  names, and so the binding should
652      *                  be done based on order.  When it
653      *                  is not null, it means do the binding
654      *                  by name, not position.
655      * @param statement         Calling DMLStatementNode (Insert or Update)
656      * @param fromListParam     FromList to use/append to.
657      *
658      * @exception StandardException     Thrown on error
659      */
660 
661     public void bindResultColumns(TableDescriptor targetTableDescriptor,
662                     FromVTI targetVTI,
663                     ResultColumnList targetColumnList,
664                     DMLStatementNode statement,
665                     FromList fromListParam)
666                 throws StandardException
667     {
668         super.bindResultColumns(targetTableDescriptor,
669                                 targetVTI,
670                                 targetColumnList, statement, 
671                                 fromListParam);
672 
673         /* Now we build our RCL */
674         buildRCL();
675 
676         /* We cannot bind the join clause until after we've bound our
677          * result columns. This is because the resultColumns from the
678          * children are propagated and merged to create our resultColumns
679          * in super.bindRCs().  If we bind the join clause prior to that
680          * call, then the ColumnReferences in the join clause will point
681          * to the children's RCLs at the time that they are bound, but
682          * will end up pointing above themselves, to our resultColumns,
683          * after the call to super.bindRCS().
684          */
685         deferredBindExpressions(fromListParam);
686     }
687 
688     /**
689      * Build the RCL for this node.  We propagate the RCLs up from the
690      * children and splice them to form this node's RCL.
691      *
692      * @exception StandardException     Thrown on error
693      */
694 
695     private void buildRCL() throws StandardException
696     {
697         /* NOTE - we only need to build this list if it does not already 
698          * exist.  This can happen in the degenerate case of an insert
699          * select with a join expression in a derived table within the select.
700          */
701         if (resultColumns != null)
702         {
703             return;
704         }
705 
706         ResultColumnList leftRCL;
707         ResultColumnList rightRCL;
708         ResultColumnList tmpRCL;
709 
710         /* We get a shallow copy of the left's ResultColumnList and its 
711          * ResultColumns.  (Copy maintains ResultColumn.expression for now.)
712          */
713         resultColumns = leftResultSet.getResultColumns();
714         leftRCL = resultColumns.copyListAndObjects();
715         leftResultSet.setResultColumns(leftRCL);
716 
717         /* Replace ResultColumn.expression with new VirtualColumnNodes
718          * in the ProjectRestrictNode's ResultColumnList.  (VirtualColumnNodes include
719          * pointers to source ResultSetNode, this, and source ResultColumn.)
720          */
721         resultColumns.genVirtualColumnNodes(leftResultSet, leftRCL, false);
722 
723         /*
724         ** If this is a right outer join, we can get nulls on the left side,
725         ** so change the types of the left result set to be nullable.
726         */
727         if (this instanceof HalfOuterJoinNode && ((HalfOuterJoinNode)this).isRightOuterJoin())
728         {
729             resultColumns.setNullability(true);
730         }
731 
732         /* Now, repeat the process with the right's RCL */
733         tmpRCL = rightResultSet.getResultColumns();
734         rightRCL = tmpRCL.copyListAndObjects();
735         rightResultSet.setResultColumns(rightRCL);
736 
737         /* Replace ResultColumn.expression with new VirtualColumnNodes
738          * in the ProjectRestrictNode's ResultColumnList.  (VirtualColumnNodes include
739          * pointers to source ResultSetNode, this, and source ResultColumn.)
740          */
741         tmpRCL.genVirtualColumnNodes(rightResultSet, rightRCL, false);
742         tmpRCL.adjustVirtualColumnIds(resultColumns.size());
743 
744         /*
745         ** If this is a left outer join, we can get nulls on the right side,
746         ** so change the types of the right result set to be nullable.
747         */
748         if (this instanceof HalfOuterJoinNode && !((HalfOuterJoinNode)this).isRightOuterJoin())
749         {
750             tmpRCL.setNullability(true);
751         }
752         
753         /* Now we append the propagated RCL from the right to the one from
754          * the left and call it our own.
755          */
756         resultColumns.nondestructiveAppend(tmpRCL);
757     }
758 
759     private void deferredBindExpressions(FromList fromListParam)
760                 throws StandardException
761     {
762         /* Bind the expressions in the join clause */
763         subqueryList = (SubqueryList) getNodeFactory().getNode(
764                                             C_NodeTypes.SUBQUERY_LIST,
765                                             getContextManager());
766         aggregateVector = new Vector  ();
767 
768         /* ON clause */
769         if (joinClause != null)
770         {
771             /* Create a new fromList with only left and right children before
772              * binding the join clause. Valid column references in the join clause
773              * are limited to columns from the 2 tables being joined. This
774              * algorithm enforces that.
775              */
776             FromList    fromList = (FromList) getNodeFactory().getNode(
777                                     C_NodeTypes.FROM_LIST,
778                                     getNodeFactory().doJoinOrderOptimization(),
779                                     getContextManager());
780             fromList.addElement((FromTable) leftResultSet);
781             fromList.addElement((FromTable) rightResultSet);
782 
783             /* First bind with all tables in the from clause, to detect ambiguous
784              * references. Push the left and right children to the front of the
785              * fromListParam before binding the join clause.  (We will
786              * remove it before returning.)  Valid column references in
787              * the join clause are limited to columns from the 2 tables being
788              * joined
789              */
790             fromListParam.insertElementAt(rightResultSet, 0);
791             fromListParam.insertElementAt(leftResultSet, 0);
792             joinClause = joinClause.bindExpression(
793                                       fromListParam, subqueryList,
794                                       aggregateVector);
795 
796             /* Now bind with two tables being joined. If this raises column not found exception,
797              * then we have a reference to other tables in the from clause. Raise invalid
798              * ON clause error to match DB2.
799              */
800             try {
801                 joinClause = joinClause.bindExpression(
802                                       fromList, subqueryList,
803                                       aggregateVector);
804             } catch (StandardException se) {
805                 if (se.getSQLState().equals(SQLState.LANG_COLUMN_NOT_FOUND))
806                     throw StandardException.newException(SQLState.LANG_DB2_ON_CLAUSE_INVALID); 
807                 throw se;
808             }
809 
810             /* DB2 doesn't allow subquerries in the ON clause */
811             if (subqueryList.size() > 0)
812                 throw StandardException.newException(SQLState.LANG_DB2_ON_CLAUSE_INVALID); 
813             /*
814             ** We cannot have aggregates in the ON clause.
815             ** In the future, if we relax this, we'll need
816             ** to be able to pass the aggregateVector up
817             ** the tree.
818             */
819             if (aggregateVector.size() > 0)
820             {
821                 throw StandardException.newException(SQLState.LANG_NO_AGGREGATES_IN_ON_CLAUSE);
822             }
823 
824             fromListParam.removeElementAt(0);
825             fromListParam.removeElementAt(0);
826         }
827         /* USING clause */
828         else if (usingClause != null)
829         {
830             /* Build a join clause from the usingClause, using the
831              * exposed names in the left and right RSNs.
832              * For each column in the list, we generate 2 ColumnReferences,
833              * 1 for the left and 1 for the right.  We bind each of these
834              * to the appropriate side and build an equality predicate
835              * between the 2.  We bind the = and AND nodes by hand because
836              * we have to bind the ColumnReferences a side at a time.
837              * We need to bind the CRs a side at a time to ensure that
838              * we don't find an bogus ambiguous column reference. (Bug 377)
839              */
840             joinClause = (AndNode) getNodeFactory().getNode(
841                                                 C_NodeTypes.AND_NODE,
842                                                 null,
843                                                 null,
844                                                 getContextManager());
845             AndNode currAnd = (AndNode) joinClause;
846             ValueNode trueNode = (ValueNode) getNodeFactory().getNode(
847                                             C_NodeTypes.BOOLEAN_CONSTANT_NODE,
848                                             Boolean.TRUE,
849                                             getContextManager());
850 
851             int usingSize = usingClause.size();
852             for (int index = 0; index < usingSize; index++)
853             {
854                 BinaryComparisonOperatorNode equalsNode;
855                 ColumnReference leftCR;
856                 ColumnReference rightCR;
857                 ResultColumn    rc = (ResultColumn) usingClause.elementAt(index);
858 
859                 /* currAnd starts as first point of insertion (leftOperand == null)
860                  * and becomes last point of insertion.
861                  */
862                 if (currAnd.getLeftOperand() != null)
863                 {
864                     currAnd.setRightOperand(
865                         (AndNode) getNodeFactory().getNode(
866                                                 C_NodeTypes.AND_NODE,
867                                                 null,
868                                                 null,
869                                                 getContextManager()));
870                     currAnd = (AndNode) currAnd.getRightOperand();
871                 }
872 
873                 /* Create and bind the left CR */
874                 fromListParam.insertElementAt(leftResultSet, 0);
875                 leftCR = (ColumnReference) getNodeFactory().getNode(
876                             C_NodeTypes.COLUMN_REFERENCE,
877                             rc.getName(),
878                             ((FromTable) leftResultSet).getTableName(),
879                             getContextManager()); 
880                 leftCR = (ColumnReference) leftCR.bindExpression(
881                                       fromListParam, subqueryList,
882                                       aggregateVector);
883                 fromListParam.removeElementAt(0);
884 
885                 /* Create and bind the right CR */
886                 fromListParam.insertElementAt(rightResultSet, 0);
887                 rightCR = (ColumnReference) getNodeFactory().getNode(
888                             C_NodeTypes.COLUMN_REFERENCE,
889                             rc.getName(),
890                             ((FromTable) rightResultSet).getTableName(),
891                             getContextManager()); 
892                 rightCR = (ColumnReference) rightCR.bindExpression(
893                                       fromListParam, subqueryList,
894                                       aggregateVector);
895                 fromListParam.removeElementAt(0);
896 
897                 /* Create and insert the new = condition */
898                 equalsNode = (BinaryComparisonOperatorNode)
899                                 getNodeFactory().getNode(
900                                         C_NodeTypes.BINARY_EQUALS_OPERATOR_NODE,
901                                         leftCR,
902                                         rightCR,
903                                         getContextManager());
904                 equalsNode.bindComparisonOperator();
905 
906                 currAnd.setLeftOperand(equalsNode);
907                 /* The right deep chain of AndNodes ends in a BinaryTrueNode.
908                  * NOTE: We set it for every AndNode, even though we will
909                  * overwrite it if this is not the last column in the list,
910                  * because postBindFixup() expects both the AndNode to have
911                  * both the left and right operands.
912                  */
913                 currAnd.setRightOperand(trueNode);
914                 currAnd.postBindFixup();
915              }
916         }
917 
918         if (joinClause != null)
919         {
920             /* If joinClause is a parameter, (where ?), then we assume
921              * it will be a nullable boolean.
922              */
923             if (joinClause.requiresTypeFromContext())
924             {
925                 joinClause.setType(new DataTypeDescriptor(TypeId.BOOLEAN_ID, true));
926             }
927             
928             /*
929             ** Is the datatype of the JOIN clause BOOLEAN?
930             **
931             ** NOTE: This test is not necessary in SQL92 entry level, because
932             ** it is syntactically impossible to have a non-Boolean JOIN clause
933             ** in that level of the standard.  But we intend to extend the
934             ** language to allow Boolean user functions in the JOIN clause,
935             ** so we need to test for the error condition.
936             */
937             TypeId joinTypeId = joinClause.getTypeId();
938 
939             /* If the where clause is not a built-in type, then generate a bound 
940              * conversion tree to a built-in type.
941              */
942             if (joinTypeId.userType())
943             {
944                 joinClause = joinClause.genSQLJavaSQLTree();
945             }
946 
947             if (! joinClause.getTypeServices().getTypeId().equals(
948                     TypeId.BOOLEAN_ID))
949             {
950                 throw StandardException.newException(SQLState.LANG_NON_BOOLEAN_JOIN_CLAUSE, 
951                         joinClause.getTypeServices().getTypeId().getSQLTypeName()
952                         );
953             }
954         }
955     }
956 
957 
958     /** 
959      * Put a ProjectRestrictNode on top of each FromTable in the FromList.
960      * ColumnReferences must continue to point to the same ResultColumn, so
961      * that ResultColumn must percolate up to the new PRN.  However,
962      * that ResultColumn will point to a new expression, a VirtualColumnNode, 
963      * which points to the FromTable and the ResultColumn that is the source for
964      * the ColumnReference.  
965      * (The new PRN will have the original of the ResultColumnList and
966      * the ResultColumns from that list.  The FromTable will get shallow copies
967      * of the ResultColumnList and its ResultColumns.  ResultColumn.expression
968      * will remain at the FromTable, with the PRN getting a new 
969      * VirtualColumnNode for each ResultColumn.expression.)
970      * We then project out the non-referenced columns.  If there are no referenced
971      * columns, then the PRN's ResultColumnList will consist of a single ResultColumn
972      * whose expression is 1.
973      *
974      * @param numTables         Number of tables in the DML Statement
975      * @param gbl               The group by list, if any
976      * @param fromList          The from list, if any
977      *
978      * @return The generated ProjectRestrictNode atop the original FromTable.
979      *
980      * @exception StandardException     Thrown on error
981      */
982     public ResultSetNode preprocess(int numTables,
983                                     GroupByList gbl,
984                                     FromList fromList)
985                                 throws StandardException
986     {
987         ResultSetNode newTreeTop;
988         
989         newTreeTop = super.preprocess(numTables, gbl, fromList);
990 
991         /* Put the expression trees in conjunctive normal form.
992          * NOTE - This needs to occur before we preprocess the subqueries
993          * because the subquery transformations assume that any subquery operator 
994          * negation has already occurred.
995          */
996         if (joinClause != null)
997         {
998             normExpressions();
999 
1000            /* Preprocess any subqueries in the join clause */
1001            if (subqueryList != null)
1002            {
1003                /* RESOLVE - In order to flatten a subquery in
1004                 * the ON clause of an inner join we'd have to pass
1005                 * the various lists from the outer select through to
1006                 * ResultSetNode.preprocess() and overload
1007                 * normExpressions in HalfOuterJoinNode.  That's not
1008                 * worth the effort, so we say that the ON clause
1009                 * is not under a top level AND in normExpressions()
1010                 * to ensure that subqueries in the ON clause do not
1011                 * get flattened.  That allows us to pass empty lists
1012                 * to joinClause.preprocess() because we know that no
1013                 * flattening will take place. (Bug #1206)
1014                 */
1015                joinClause.preprocess(
1016                                numTables,
1017                                (FromList) getNodeFactory().getNode(
1018                                    C_NodeTypes.FROM_LIST,
1019                                    getNodeFactory().doJoinOrderOptimization(),
1020                                    getContextManager()),
1021                                (SubqueryList) getNodeFactory().getNode(
1022                                                    C_NodeTypes.SUBQUERY_LIST,
1023                                                    getContextManager()),
1024                                (PredicateList) getNodeFactory().getNode(
1025                                                    C_NodeTypes.PREDICATE_LIST,
1026                                                    getContextManager()));
1027            }
1028
1029            /* Pull apart the expression trees */
1030            joinPredicates.pullExpressions(numTables, joinClause);
1031            joinPredicates.categorize();
1032            joinClause = null;
1033        }
1034
1035        return newTreeTop;
1036    }
1037
1038    /**
1039     * Find the unreferenced result columns and project them out. This is used in pre-processing joins
1040     * that are not flattened into the where clause.
1041     */
1042    void projectResultColumns() throws StandardException
1043    {
1044        leftResultSet.projectResultColumns();
1045        rightResultSet.projectResultColumns();
1046        resultColumns.pullVirtualIsReferenced();
1047        super.projectResultColumns();
1048    }
1049    
1050    /** Put the expression trees in conjunctive normal form 
1051     *
1052     * @exception StandardException     Thrown on error
1053     */
1054    public void normExpressions()
1055                throws StandardException
1056    {
1057        if (joinClauseNormalized == true) return;
1058
1059        /* For each expression tree:
1060         *  o Eliminate NOTs (eliminateNots())
1061         *  o Ensure that there is an AndNode on top of every
1062         *    top level expression. (putAndsOnTop())
1063         *  o Finish the job (changeToCNF())
1064         */
1065        joinClause = joinClause.eliminateNots(false);
1066        if (SanityManager.DEBUG)
1067        {
1068            if (!(joinClause.verifyEliminateNots()) )
1069            {
1070                joinClause.treePrint();
1071                SanityManager.THROWASSERT(
1072                    "joinClause in invalid form: " + joinClause); 
1073            }
1074        }
1075        joinClause = joinClause.putAndsOnTop();
1076        if (SanityManager.DEBUG)
1077        {
1078            if (! ((joinClause instanceof AndNode) &&
1079                   (joinClause.verifyPutAndsOnTop())) )
1080            {
1081                joinClause.treePrint();
1082                SanityManager.THROWASSERT(
1083                    "joinClause in invalid form: " + joinClause); 
1084            }
1085        }
1086        /* RESOLVE - ON clause is temporarily "not under a top
1087         * top level AND" until we figure out how to deal with
1088         * subqueries in the ON clause. (Bug 1206)
1089         */
1090        joinClause = joinClause.changeToCNF(false);
1091        if (SanityManager.DEBUG)
1092        {
1093            if (! ((joinClause instanceof AndNode) &&
1094                   (joinClause.verifyChangeToCNF())) )
1095            {
1096                joinClause.treePrint();
1097                SanityManager.THROWASSERT(
1098                    "joinClause in invalid form: " + joinClause); 
1099            }
1100        }
1101
1102        joinClauseNormalized = true;
1103    }
1104
1105    /**
1106     * Push expressions down to the first ResultSetNode which can do expression
1107     * evaluation and has the same referenced table map.
1108     * RESOLVE - This means only pushing down single table expressions to
1109     * DistinctNodes today.  Once we have a better understanding of how
1110     * the optimizer will work, we can push down join clauses.
1111     *
1112     * @param outerPredicateList    The PredicateList from the outer RS.
1113     *
1114     * @exception StandardException     Thrown on error
1115     */
1116    public void pushExpressions(PredicateList outerPredicateList)
1117                    throws StandardException
1118    {
1119        FromTable       leftFromTable = (FromTable) leftResultSet;
1120        FromTable       rightFromTable = (FromTable) rightResultSet;
1121
1122        /* OuterJoinNodes are responsible for overriding this
1123         * method since they have different rules about where predicates
1124         * can be applied.
1125         */
1126        if (SanityManager.DEBUG)
1127        {
1128            if (this instanceof HalfOuterJoinNode)
1129            {
1130                SanityManager.THROWASSERT(
1131                    "JN.pushExpressions() not expected to be called for " +
1132                    getClass().getName());
1133            }
1134        }
1135
1136        /* We try to push "pushable" 
1137         * predicates to 1 of 3 places:
1138         *  o Predicates that only reference tables
1139         *    on the left are pushed to the leftPredicateList.
1140         *  o Predicates that only reference tables
1141         *    on the right are pushed to the rightPredicateList.
1142         *  o Predicates which reference tables on both
1143         *    sides (and no others) are pushed to 
1144         *    the joinPredicates and may be pushed down
1145         *    further during optimization.
1146         */
1147        // Left only
1148        pushExpressionsToLeft(outerPredicateList);
1149        leftFromTable.pushExpressions(getLeftPredicateList());
1150        // Right only
1151        pushExpressionsToRight(outerPredicateList);
1152        rightFromTable.pushExpressions(getRightPredicateList());
1153        // Join predicates
1154        grabJoinPredicates(outerPredicateList);
1155
1156        /* By the time we're done here, both the left and right
1157         * predicate lists should be empty because we pushed everything
1158         * down.
1159         */
1160        if (SanityManager.DEBUG)
1161        {
1162            if (getLeftPredicateList().size() != 0)
1163            {
1164                SanityManager.THROWASSERT(
1165                    "getLeftPredicateList().size() expected to be 0, not " +
1166                    getLeftPredicateList().size());
1167            }
1168            if (getRightPredicateList().size() != 0)
1169            {
1170                SanityManager.THROWASSERT(
1171                    "getRightPredicateList().size() expected to be 0, not " +
1172                    getRightPredicateList().size());
1173            }
1174        }
1175    }
1176
1177    protected void pushExpressionsToLeft(PredicateList outerPredicateList)
1178        throws StandardException
1179    {
1180        FromTable       leftFromTable = (FromTable) leftResultSet;
1181
1182        JBitSet     leftReferencedTableMap = leftFromTable.getReferencedTableMap();
1183
1184        /* Build a list of the single table predicates on left result set
1185         * that we can push down 
1186         */
1187        // Walk outerPredicateList backwards due to possible deletes
1188        for (int index = outerPredicateList.size() - 1; index >= 0; index --)
1189        {
1190            JBitSet   curBitSet;
1191            Predicate predicate;
1192
1193            predicate = (Predicate) outerPredicateList.elementAt(index);
1194            if (! predicate.getPushable())
1195            {
1196                continue;
1197            }
1198
1199            curBitSet = predicate.getReferencedSet();
1200            
1201            /* Do we have a match? */
1202            if (leftReferencedTableMap.contains(curBitSet))
1203            {
1204                /* Add the matching predicate to the push list */
1205                getLeftPredicateList().addPredicate(predicate);
1206
1207                /* Remap all of the ColumnReferences to point to the
1208                 * source of the values.
1209                 * The tree is something like:
1210                 *          PRN1
1211                 *            |
1212                 *           JN (this)
1213                 *         /    \
1214                 *      PRN2    PRN3
1215                 *        |       |
1216                 *      FBT1    FBT2
1217                 *
1218                 * The ColumnReferences start off pointing to the RCL off of
1219                 * PRN1.  For optimization, we want them to point to the
1220                 * RCL off of PRN2.  In order to do that, we remap them
1221                 * twice here.  If optimization pushes them down to the
1222                 * base table, it will remap them again.
1223                 */
1224                RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
1225                predicate.getAndNode().accept(rcrv);
1226                predicate.getAndNode().accept(rcrv);
1227
1228                /* Remove the matching predicate from the outer list */
1229                outerPredicateList.removeElementAt(index);
1230            }
1231        }
1232    }
1233
1234    private void pushExpressionsToRight(PredicateList outerPredicateList)
1235        throws StandardException
1236    {
1237        FromTable       rightFromTable = (FromTable) rightResultSet;
1238
1239        JBitSet     rightReferencedTableMap = rightFromTable.getReferencedTableMap();
1240
1241        /* Build a list of the single table predicates on right result set
1242         * that we can push down 
1243         */
1244        // Walk outerPredicateList backwards due to possible deletes
1245        for (int index = outerPredicateList.size() - 1; index >= 0; index --)
1246        {
1247            JBitSet   curBitSet;
1248            Predicate predicate;
1249
1250            predicate = (Predicate) outerPredicateList.elementAt(index);
1251            if (! predicate.getPushable())
1252            {
1253                continue;
1254            }
1255
1256            curBitSet = predicate.getReferencedSet();
1257            
1258            /* Do we have a match? */
1259            if (rightReferencedTableMap.contains(curBitSet))
1260            {
1261                /* Add the matching predicate to the push list */
1262                getRightPredicateList().addPredicate(predicate);
1263
1264                /* Remap all of the ColumnReferences to point to the
1265                 * source of the values.
1266                 * The tree is something like:
1267                 *          PRN1
1268                 *            |
1269                 *           JN (this)
1270                 *         /    \
1271                 *      PRN2    PRN3
1272                 *        |       |
1273                 *      FBT1    FBT2
1274                 *
1275                 * The ColumnReferences start off pointing to the RCL off of
1276                 * PRN1.  For optimization, we want them to point to the
1277                 * RCL off of PRN3.  In order to do that, we remap them
1278                 * twice here.  If optimization pushes them down to the
1279                 * base table, it will remap them again.
1280                 */
1281                RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
1282                predicate.getAndNode().accept(rcrv);
1283                predicate.getAndNode().accept(rcrv);
1284
1285                /* Remove the matching predicate from the outer list */
1286                outerPredicateList.removeElementAt(index);
1287            }
1288        }
1289    }
1290
1291    private void grabJoinPredicates(PredicateList outerPredicateList)
1292        throws StandardException
1293    {
1294        FromTable       leftFromTable = (FromTable) leftResultSet;
1295        FromTable       rightFromTable = (FromTable) rightResultSet;
1296
1297        JBitSet     leftReferencedTableMap = leftFromTable.getReferencedTableMap();
1298        JBitSet     rightReferencedTableMap = rightFromTable.getReferencedTableMap();
1299
1300        /* Build a list of the join predicates that we can push down */
1301        // Walk outerPredicateList backwards due to possible deletes
1302        for (int index = outerPredicateList.size() - 1; index >= 0; index --)
1303        {
1304            JBitSet   curBitSet;
1305            Predicate predicate;
1306
1307            predicate = (Predicate) outerPredicateList.elementAt(index);
1308            if (! predicate.getPushable())
1309            {
1310                continue;
1311            }
1312
1313            curBitSet = predicate.getReferencedSet();
1314            
1315            /* Do we have a match? */
1316            JBitSet innerBitSet = (JBitSet) rightReferencedTableMap.clone();
1317            innerBitSet.or(leftReferencedTableMap);
1318            if (innerBitSet.contains(curBitSet))
1319            {
1320                /* Add the matching predicate to the push list */
1321                joinPredicates.addPredicate(predicate);
1322
1323                /* Remap all of the ColumnReferences to point to the
1324                 * source of the values.
1325                 * The tree is something like:
1326                 *          PRN1
1327                 *            |
1328                 *           JN (this)
1329                 *         /    \
1330                 *      PRN2    PRN3
1331                 *        |       |
1332                 *      FBT1    FBT2
1333                 *
1334                 * The ColumnReferences start off pointing to the RCL off of
1335                 * PRN1.  For optimization, we want them to point to the
1336                 * RCL off of PRN2 or PRN3.  In order to do that, we remap them
1337                 * twice here.  If optimization pushes them down to the
1338                 * base table, it will remap them again.
1339                 */
1340                RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
1341                predicate.getAndNode().accept(rcrv);
1342                predicate.getAndNode().accept(rcrv);
1343
1344                /* Remove the matching predicate from the outer list */
1345                outerPredicateList.removeElementAt(index);
1346            }
1347        }
1348    }
1349
1350    /**
1351     * Flatten this JoinNode into the outer query block. The steps in
1352     * flattening are:
1353     *  o  Mark all ResultColumns as redundant, so that they are "skipped over"
1354     *     at generate().
1355     *  o  Append the joinPredicates to the outer list.
1356     *  o  Create a FromList from the tables being joined and return 
1357     *     that list so that the caller will merge the 2 lists 
1358     *
1359     * @param rcl               The RCL from the outer query
1360     * @param outerPList        PredicateList to append wherePredicates to.
1361     * @param sql               The SubqueryList from the outer query
1362     * @param gbl               The group by list, if any
1363     *
1364     * @return FromList     The fromList from the underlying SelectNode.
1365     *
1366     * @exception StandardException     Thrown on error
1367     */
1368    public FromList flatten(ResultColumnList rcl,
1369                            PredicateList outerPList,
1370                            SubqueryList sql,
1371                            GroupByList gbl)
1372
1373            throws StandardException
1374    {
1375        /* OuterJoinNodes should never get here.
1376         * (They can be transformed, but never
1377         * flattened directly.)
1378         */
1379        if (SanityManager.DEBUG)
1380        {
1381            if (this instanceof HalfOuterJoinNode)
1382            {
1383                SanityManager.THROWASSERT(
1384                    "JN.flatten() not expected to be called for " +
1385                    getClass().getName());
1386            }
1387        }
1388
1389        /* Build a new FromList composed of left and right children 
1390         * NOTE: We must call FL.addElement() instead of FL.addFromTable()
1391         * since there is no exposed name. (And even if there was,
1392         * we could care less about unique exposed name checking here.)
1393         */
1394        FromList    fromList = (FromList) getNodeFactory().getNode(
1395                                    C_NodeTypes.FROM_LIST,
1396                                    getNodeFactory().doJoinOrderOptimization(),
1397                                    getContextManager());
1398        fromList.addElement((FromTable) leftResultSet);
1399        fromList.addElement((FromTable) rightResultSet);
1400
1401        /* Mark our RCL as redundant */
1402        resultColumns.setRedundant();
1403
1404        /* Remap all ColumnReferences from the outer query to this node.
1405         * (We replace those ColumnReferences with clones of the matching
1406         * expression in the left and right's RCL.
1407         */
1408        rcl.remapColumnReferencesToExpressions();
1409        outerPList.remapColumnReferencesToExpressions();
1410        if (gbl != null)
1411        {
1412            gbl.remapColumnReferencesToExpressions();
1413        }
1414
1415        if (joinPredicates.size() > 0)
1416        {
1417            outerPList.destructiveAppend(joinPredicates);
1418        }
1419
1420        if (subqueryList != null && subqueryList.size() > 0)
1421        {
1422            sql.destructiveAppend(subqueryList);
1423        }
1424
1425        return fromList;
1426    }
1427
1428    /**
1429     * Currently we don't reordering any outer join w/ inner joins.
1430     */
1431    public boolean LOJ_reorderable(int numTables)
1432                throws StandardException
1433    {
1434        return false;
1435    }
1436
1437    /**
1438     * Transform any Outer Join into an Inner Join where applicable.
1439     * (Based on the existence of a null intolerant
1440     * predicate on the inner table.)
1441     *
1442     * @param predicateTree The predicate tree for the query block
1443     *
1444     * @return The new tree top (OuterJoin or InnerJoin).
1445     *
1446     * @exception StandardException     Thrown on error
1447     */
1448    public FromTable transformOuterJoins(ValueNode predicateTree, int numTables)
1449        throws StandardException
1450    {
1451        /* Can't flatten if no predicates in where clause. */
1452        if (predicateTree == null)
1453        {
1454            return this;
1455        }
1456
1457        /* See if left or right sides can be transformed */
1458        leftResultSet = ((FromTable) leftResultSet).transformOuterJoins(predicateTree, numTables);
1459        rightResultSet = ((FromTable) rightResultSet).transformOuterJoins(predicateTree, numTables);
1460
1461        return this;
1462    }
1463
1464    /**
1465     * For joins, the tree will be (nodes are left out if the clauses
1466     * are empty):
1467     *
1468     *      ProjectRestrictResultSet -- for the having and the select list
1469     *      SortResultSet -- for the group by list
1470     *      ProjectRestrictResultSet -- for the where and the select list (if no group or having)
1471     *      the result set for the fromList
1472     *
1473     *
1474     * @exception StandardException     Thrown on error
1475     */
1476    public void generate(ActivationClassBuilder acb,
1477                                MethodBuilder mb)
1478                            throws StandardException
1479    {
1480        generateCore(acb, mb, INNERJOIN, null, null);
1481    }
1482
1483    /**
1484     * Generate the code for a qualified join node.
1485     *
1486     * @exception StandardException     Thrown on error
1487     */
1488    public void generateCore(ActivationClassBuilder acb,
1489                                   MethodBuilder mb,
1490                                   int joinType) 
1491            throws StandardException
1492    {
1493        generateCore(acb, mb, joinType, joinClause, subqueryList);
1494    }
1495
1496    /**
1497     * Do the generation work for the join node hierarchy.
1498     *
1499     * @param acb           The ActivationClassBuilder
1500     * @param mb the method the code is to go into
1501     * @param joinType      The join type
1502     * @param joinClause    The join clause, if any
1503     * @param subquerys     The list of subqueries in the join clause, if any
1504     *
1505     * @exception StandardException     Thrown on error
1506     */
1507    protected void generateCore(ActivationClassBuilder acb,
1508                                      MethodBuilder mb,
1509                                      int joinType,
1510                                      ValueNode joinClause,
1511                                      SubqueryList subquerys)
1512            throws StandardException
1513    {
1514        /* Put the predicates back into the tree */
1515        if (joinPredicates != null)
1516        {
1517            joinClause = joinPredicates.restorePredicates();
1518            joinPredicates = null;
1519        }
1520
1521        /* Get the next ResultSet #, so that we can number this ResultSetNode, its
1522         * ResultColumnList and ResultSet.
1523         */
1524        assignResultSetNumber();
1525
1526        /* Set the point of attachment in all subqueries attached
1527         * to this node.
1528         */
1529        if (subquerys != null && subquerys.size() > 0)
1530        {
1531            subquerys.setPointOfAttachment(resultSetNumber);
1532        }
1533
1534        // build up the tree.
1535
1536        /* Generate the JoinResultSet */
1537        /* Nested loop and hash are the only join strategy currently supporteds.  
1538         * Right outer joins are transformed into left outer joins.
1539         */
1540        String            joinResultSetString;
1541
1542        if (joinType == LEFTOUTERJOIN)
1543        {
1544            joinResultSetString = 
1545                ((Optimizable) rightResultSet).getTrulyTheBestAccessPath().
1546                    getJoinStrategy().halfOuterJoinResultSetMethodName();
1547        }
1548        else
1549        {
1550            joinResultSetString = 
1551                ((Optimizable) rightResultSet).getTrulyTheBestAccessPath().
1552                    getJoinStrategy().joinResultSetMethodName();
1553        }
1554
1555        acb.pushGetResultSetFactoryExpression(mb);
1556        int nargs = getJoinArguments(acb, mb, joinClause);
1557        mb.callMethod(VMOpcode.INVOKEINTERFACE, (String  ) null, joinResultSetString, ClassName.NoPutResultSet, nargs);
1558    }
1559
1560    /**
1561     * Get the arguments to the join result set.
1562     *
1563     * @param acb   The ActivationClassBuilder for the class we're building.
1564     * @param mb the method the generated code is going into
1565     * @param joinClause    The join clause, if any
1566     *
1567     * @return  The array of arguments to the join result set
1568     *
1569     * @exception StandardException     Thrown on error
1570     */
1571    private int getJoinArguments(ActivationClassBuilder acb,
1572                                            MethodBuilder mb,
1573                                            ValueNode joinClause)
1574                            throws StandardException
1575    {
1576        int numArgs = getNumJoinArguments();
1577
1578        leftResultSet.generate(acb, mb); // arg 1
1579        mb.push(leftResultSet.resultColumns.size()); // arg 2
1580        rightResultSet.generate(acb, mb); // arg 3
1581        mb.push(rightResultSet.resultColumns.size()); // arg 4
1582
1583        // Get our final cost estimate based on child estimates.
1584        costEstimate = getFinalCostEstimate();
1585
1586        // for the join clause, we generate an exprFun
1587        // that evaluates the expression of the clause
1588        // against the current row of the child's result.
1589        // if the join clause is empty, we generate a function
1590        // that just returns true. (Performance tradeoff: have
1591        // this function for the empty join clause, or have
1592        // all non-empty join clauses check for a null at runtime).
1593
1594        // generate the function and initializer:
1595        // Note: Boolean lets us return nulls (boolean would not)
1596        // private Boolean exprN()
1597        // {
1598        //   return <<joinClause.generate(ps)>>;
1599        // }
1600        // static Method exprN = method pointer to exprN;
1601
1602        // if there is no join clause, we just pass a null Expression.
1603        if (joinClause == null)
1604        {
1605            mb.pushNull(ClassName.GeneratedMethod); // arg 5
1606        }
1607        else
1608        {
1609            // this sets up the method and the static field.
1610            // generates:
1611            //  Object userExprFun { }
1612            MethodBuilder userExprFun = acb.newUserExprFun();
1613
1614            // join clause knows it is returning its value;
1615
1616            /* generates:
1617             *    return <joinClause.generate(acb)>;
1618             * and adds it to userExprFun
1619             */
1620            joinClause.generate(acb, userExprFun);
1621            userExprFun.methodReturn();
1622
1623            // we are done modifying userExprFun, complete it.
1624            userExprFun.complete();
1625
1626            // join clause is used in the final result set as an access of the new static
1627            // field holding a reference to this new method.
1628            // generates:
1629            //  ActivationClass.userExprFun
1630            // which is the static field that "points" to the userExprFun
1631            // that evaluates the where clause.
1632            acb.pushMethodReference(mb, userExprFun); // arg 5
1633        }
1634
1635        mb.push(resultSetNumber); // arg 6
1636
1637        addOuterJoinArguments(acb, mb);
1638
1639        // Does right side return a single row
1640        oneRowRightSide(acb, mb);
1641
1642        // estimated row count
1643        mb.push(costEstimate.rowCount());
1644
1645        // estimated cost
1646        mb.push(costEstimate.getEstimatedCost());
1647
1648        //User may have supplied optimizer overrides in the sql
1649        //Pass them onto execute phase so it can be shown in 
1650        //run time statistics.
1651        if (joinOrderStrategyProperties != null)
1652            mb.push(PropertyUtil.sortProperties(joinOrderStrategyProperties));
1653        else
1654            mb.pushNull("java.lang.String");
1655
1656        return numArgs;
1657
1658    }
1659
1660    /**
1661     * @see ResultSetNode#getFinalCostEstimate
1662     *
1663     * Get the final CostEstimate for this JoinNode.
1664     *
1665     * @return  The final CostEstimate for this JoinNode, which is sum
1666     *  the costs for the inner and outer table.  The number of rows,
1667     *  though, is that for the inner table only.
1668     */
1669    public CostEstimate getFinalCostEstimate()
1670        throws StandardException
1671    {
1672        // If we already found it, just return it.
1673        if (finalCostEstimate != null)
1674            return finalCostEstimate;
1675
1676        CostEstimate leftCE = leftResultSet.getFinalCostEstimate();
1677        CostEstimate rightCE = rightResultSet.getFinalCostEstimate();
1678
1679        finalCostEstimate = getNewCostEstimate();
1680        finalCostEstimate.setCost(
1681            leftCE.getEstimatedCost() + rightCE.getEstimatedCost(),
1682            rightCE.rowCount(),
1683            rightCE.rowCount());
1684
1685        return finalCostEstimate;
1686    }
1687
1688    protected void oneRowRightSide(ActivationClassBuilder acb,
1689                                       MethodBuilder mb)
1690        throws StandardException
1691    {
1692        mb.push(rightResultSet.isOneRowResultSet());
1693        mb.push(rightResultSet.isNotExists());  //join is for NOT EXISTS
1694    }
1695
1696    /**
1697     * Return the number of arguments to the join result set.  This will
1698     * be overridden for other types of joins (for example, outer joins).
1699     */
1700    protected int getNumJoinArguments()
1701    {
1702        return 11;
1703    }
1704
1705    /**
1706     * Generate and add any arguments specifict to outer joins.
1707     * (Expected to be overriden, where appropriate, in subclasses.)
1708     *
1709     * @param acb       The ActivationClassBuilder
1710     * @param mb the method  the generated code is to go into
1711     *
1712     * return The number of args added
1713     *
1714     * @exception StandardException     Thrown on error
1715     */
1716     protected int addOuterJoinArguments(ActivationClassBuilder acb,
1717                                            MethodBuilder mb)
1718         throws StandardException
1719     {
1720         return 0;
1721     }
1722
1723    /** 
1724     * Convert the joinType to a string.
1725     *
1726     * @param joinType          The joinType as an int.
1727     *
1728     * @return String       The joinType as a String.
1729     */
1730    public static String   joinTypeToString(int joinType)
1731    {
1732        switch(joinType)
1733        {
1734            case INNERJOIN:
1735                return "INNER JOIN";
1736
1737            case CROSSJOIN:
1738                return "CROSS JOIN";
1739
1740            case LEFTOUTERJOIN:
1741                return "LEFT OUTER JOIN";
1742
1743            case RIGHTOUTERJOIN:
1744                return "RIGHT OUTER JOIN";
1745
1746            case FULLOUTERJOIN:
1747                return "FULL OUTER JOIN";
1748
1749            case UNIONJOIN:
1750                return "UNION JOIN";
1751
1752            default:
1753                if (SanityManager.DEBUG)
1754                {
1755                    SanityManager.ASSERT(false, "Unexpected joinType");
1756                }
1757                return null;
1758        }
1759    }
1760
1761    protected PredicateList getLeftPredicateList() throws StandardException
1762    {
1763        if (leftPredicateList == null)
1764            leftPredicateList = (PredicateList) getNodeFactory().getNode(
1765                                                    C_NodeTypes.PREDICATE_LIST,
1766                                                    getContextManager());
1767
1768        return leftPredicateList;
1769    }
1770
1771    protected PredicateList getRightPredicateList() throws StandardException
1772    {
1773        if (rightPredicateList == null)
1774            rightPredicateList = (PredicateList) getNodeFactory().getNode(
1775                                                    C_NodeTypes.PREDICATE_LIST,
1776                                                    getContextManager());
1777
1778        return rightPredicateList;
1779    }
1780
1781    /**
1782     * Get the lock mode for the target of an update statement
1783     * (a delete or update).  The update mode will always be row for
1784     * CurrentOfNodes.  It will be table if there is no where clause.
1785     *
1786     * @return  The lock mode
1787     */
1788    public int updateTargetLockMode()
1789    {
1790        /* Always use row locking if we have a join node.
1791         * We can only have a join node if there is a subquery that
1792         * got flattened, hence there is a restriction.
1793         */
1794        return TransactionController.MODE_RECORD;
1795    }
1796
1797    /**
1798     * Mark this node and its children as not being a flattenable join.
1799     */
1800    void notFlattenableJoin()
1801    {
1802        flattenableJoin = false;
1803        leftResultSet.notFlattenableJoin();
1804        rightResultSet.notFlattenableJoin();
1805    }
1806
1807    /**
1808     * Is this FromTable a JoinNode which can be flattened into 
1809     * the parents FromList.
1810     *
1811     * @return boolean      Whether or not this FromTable can be flattened.
1812     */
1813    public boolean isFlattenableJoinNode()
1814    {
1815        return flattenableJoin;
1816    }
1817
1818    /**
1819     * Return whether or not the underlying ResultSet tree
1820     * is ordered on the specified columns.
1821     * RESOLVE - This method currently only considers the outermost table 
1822     * of the query block.
1823     *
1824     * @param   crs                 The specified ColumnReference[]
1825     * @param   permuteOrdering     Whether or not the order of the CRs in the array can be permuted
1826     * @param   fbtVector           Vector that is to be filled with the FromBaseTable  
1827     *
1828     * @return  Whether the underlying ResultSet tree
1829     * is ordered on the specified column.
1830     *
1831     * @exception StandardException     Thrown on error
1832     */
1833    boolean isOrderedOn(ColumnReference[] crs, boolean permuteOrdering, Vector   fbtVector)
1834                throws StandardException
1835    {
1836        /* RESOLVE - easiest thing for now is to only consider the leftmost child */
1837        return leftResultSet.isOrderedOn(crs, permuteOrdering, fbtVector);
1838    }
1839
1840    /**
1841     * Prints the sub-nodes of this object.  See QueryTreeNode.java for
1842     * how tree printing is supposed to work.
1843     *
1844     * @param depth     The depth of this node in the tree
1845     */
1846
1847    public void printSubNodes(int depth)
1848    {
1849        if (SanityManager.DEBUG)
1850        {
1851            super.printSubNodes(depth);
1852
1853            if (subqueryList != null)
1854            {
1855                printLabel(depth, "subqueryList: ");
1856                subqueryList.treePrint(depth + 1);
1857            }
1858
1859            if (joinClause != null)
1860            {
1861                printLabel(depth, "joinClause: ");
1862                joinClause.treePrint(depth + 1);
1863            }
1864
1865            if (joinPredicates.size() != 0)
1866            {
1867                printLabel(depth, "joinPredicates: ");
1868                joinPredicates.treePrint(depth + 1);
1869            }
1870
1871            if (usingClause != null)
1872            {
1873                printLabel(depth, "usingClause: ");
1874                usingClause.treePrint(depth + 1);
1875            }
1876        }
1877    }
1878
1879    void setSubqueryList(SubqueryList subqueryList)
1880    {
1881        this.subqueryList = subqueryList;
1882    }
1883
1884    void setAggregateVector(Vector   aggregateVector)
1885    {
1886        this.aggregateVector = aggregateVector;
1887    }
1888
1889    /**
1890     * Return the logical left result set for this qualified
1891     * join node.
1892     * (For RIGHT OUTER JOIN, the left is the right
1893     * and the right is the left and the JOIN is the NIOJ).
1894     */
1895    ResultSetNode getLogicalLeftResultSet()
1896    {
1897        return leftResultSet;
1898    }
1899
1900    /**
1901     * Return the logical right result set for this qualified
1902     * join node.
1903     * (For RIGHT OUTER JOIN, the left is the right
1904     * and the right is the left and the JOIN is the NIOJ).
1905     */
1906    ResultSetNode getLogicalRightResultSet()
1907    {
1908        return rightResultSet;
1909    }
1910
1911    /**
1912     * Accept a visitor, and call v.visit()
1913     * on child nodes as necessary.  
1914     * 
1915     * @param v the visitor
1916     *
1917     * @exception StandardException on error
1918     */
1919    public Visitable accept(Visitor v) 
1920        throws StandardException
1921    {
1922        if (v.skipChildren(this))
1923        {
1924            return v.visit(this);
1925        }
1926
1927        Visitable returnNode = super.accept(v);
1928
1929        if (resultColumns != null && !v.stopTraversal())
1930        {
1931            resultColumns = (ResultColumnList)resultColumns.accept(v);
1932        }
1933
1934        if (joinClause != null && !v.stopTraversal())
1935        {
1936            joinClause = (ValueNode)joinClause.accept(v);
1937        }
1938
1939        if (usingClause != null && !v.stopTraversal())
1940        {
1941            usingClause = (ResultColumnList)usingClause.accept(v);
1942        }
1943
1944        return returnNode;
1945    }
1946
1947    // This method returns the table references in Join node, and this may be
1948    // needed for LOJ reordering.  For example, we may have the following query:
1949    //       (T JOIN S) LOJ (X LOJ Y) 
1950    // The top most LOJ may be a join betw T and X and thus we can reorder the
1951    // LOJs.  However, as of 10/2002, we don't reorder LOJ mixed with join.
1952    public JBitSet LOJgetReferencedTables(int numTables)
1953                throws StandardException
1954    {
1955        JBitSet map = new JBitSet(numTables);
1956
1957        map = (JBitSet) leftResultSet.LOJgetReferencedTables(numTables);
1958        if (map == null) return null;
1959        else map.or((JBitSet) rightResultSet.LOJgetReferencedTables(numTables));
1960
1961        return map;
1962    }
1963    
1964}
1965
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags