NestedLoopJoinPlan


1   package com.daffodilwoods.daffodildb.server.sql99.dql.plan.table;
2   
3   import com.daffodilwoods.daffodildb.client.*;
4   import com.daffodilwoods.daffodildb.server.serversystem.*;
5   import com.daffodilwoods.daffodildb.server.sql99.common.*;
6   import com.daffodilwoods.daffodildb.server.sql99.dql.common.*;
7   import com.daffodilwoods.daffodildb.server.sql99.dql.iterator.*;
8   import com.daffodilwoods.daffodildb.server.sql99.dql.iterator.table.*;
9   import com.daffodilwoods.daffodildb.server.sql99.dql.plan.*;
10  import com.daffodilwoods.daffodildb.server.sql99.dql.plan.condition.*;
11  import com.daffodilwoods.daffodildb.server.sql99.expression.booleanvalueexpression.*;
12  import com.daffodilwoods.daffodildb.server.sql99.utils.*;
13  import com.daffodilwoods.database.resource.*;
14  import com.daffodilwoods.database.sqlinitiator.*;
15  import com.daffodilwoods.daffodildb.server.datadictionarysystem._ReferencedConstraintCharacteristics;
16  import com.daffodilwoods.database.utility.P;
17  import com.daffodilwoods.daffodildb.server.sql99.dql.iterator.condition.NonIndexedFilterIterator;
18  
19  /**
20   *
21   * <p>Title: NestedLoopJoinIterator</p>
22   * <p>Description:
23   * This class represents the cartesian of array of TablePlans. It provides the
24   * functionality of obtaining resultset. The resultset returned for NestedLoop
25   * will contain as many rows as equivalent to multiplication of rows obtained
26   * from each plan.
27   *  </p>
28   * <p>Copyright: Copyright (c) 2003</p>
29   * <p>Company: Daffodil S/W Ltd.</p>
30   * @author SelectTeam
31   * @version 1.0
32   */
33  
34  public class NestedLoopJoinPlan extends PlanAbstract {
35  
36     /**
37      * Represents the way of execution for condition which is solvable above the
38      * join level.
39      */
40  
41     private Object   conditionMappingArray[][];
42  
43     /**
44      * Represents the way of execution for condition which is solvable above the
45      * join level and order is not needed.
46      */
47  
48     private Object   conditionMappingArrayWithoutOrder[][];
49  
50     /**
51      * boolean variable to indicate whether cost is calculated for this plan or
52      * not.
53      */
54  
55     private boolean costCalculated;
56  
57  
58     private _Reference[] underlyingRef;
59  
60     public NestedLoopJoinPlan(_TablePlan[] tablePlans0) throws DException {
61        childPlans = tablePlans0;
62        initializeTableDetails();
63     }
64  
65     /**
66      * Constructor with remainingCondition and tablePlans is called from TemporaryMerge.
67      * @param tablePlans0
68      * @param condition0
69      */
70  
71     public NestedLoopJoinPlan(_TablePlan[] tablePlans0, booleanvalueexpression condition0) throws DException {
72        this(tablePlans0);
73        remainingCondition = condition0;
74     }
75  
76     public NestedLoopJoinPlan(_TablePlan[] tablePlans0, booleanvalueexpression condition0,_Reference[] underlyingRef0 ) throws DException {
77        this(tablePlans0);
78        remainingCondition = condition0;
79        underlyingRef=underlyingRef0;
80     }
81  
82  
83     /**
84      * Returns the type of this plan.
85      * @return
86      * @throws DException
87      */
88  
89     public int getType() throws DException {
90        return TableExpressionConstants.NESTEDLOOPJOINPLAN;
91     }
92  
93     /**
94      * Calculates the cost by multiplying the cost of underlying plans. Also the
95      * cost of condition(if any) is added into resultant cost. This condition will
96      * be evaluated on the cartesian of resultset of underlying plan.
97      * @return
98      * @throws DException
99      */
100 
101    public double getCost(_ServerSession session) throws DException {
102       costCalculated = true;
103       double cost = 1;
104       for (int i = 0; i < childPlans.length; i++) {
105          cost *= childPlans[i].getCost(session);
106       }
107 
108       return remainingCondition == null ?
109           cost :
110           cost + remainingCondition.getCost(getRowCountWithoutCondition(session), false);
111    }
112 
113 
114    /**
115     * Calculates the cost by multiplying the cost of underlying plans. Also the
116     * cost of passed condition and remaninig condition(if any) is added into
117     * resultant cost. This condition will be evaluated on the cartesian of
118     * resultset of underlying plan.
119     * @param session
120     * @param conditionArg
121     * @param estimatedRows
122     * @return
123     * @throws DException
124     */
125 
126    public double getCost(_ServerSession session, booleanvalueexpression conditionArg, long estimatedRows) throws DException {
127       double cost = 1;
128       for (int i = 0; i < childPlans.length; i++) {
129          cost *= childPlans[i].getCost(session);
130       }
131       return remainingCondition == null ?
132           cost + conditionArg.getCost(getRowCountWithoutCondition(session), false)
133           : cost + changeConditionMappingArray(conditionArg, true).getCost(getRowCountWithoutCondition(session), false);
134    }
135 
136    /**
137     * This method returns the estimated number of rows that results from
138     * cartesian of underlying plan.
139     * @param serverSession
140     * @return
141     * @throws DException
142     */
143 
144    private long getRowCountWithoutCondition(_ServerSession serverSession) throws DException {
145       long rowCount = 1;
146       for (int i = 0; i < childPlans.length; i++) {
147          rowCount *= childPlans[i].getRowCount(serverSession);
148       }
149       return rowCount;
150    }
151 
152    /**
153     * This method is used to obtain the resultset for this plan. Firstly,
154     * cartesian resultset is formed on underlying resultsets. Then if any
155     * condition is present, then filtered resultset is formed on cartesian
156     * resultset.
157     * @param session
158     * @return
159     * @throws DException
160     */
161 
162    public _Iterator execute(_ServerSession session) throws DException {
163      if (!costCalculated) {
164          getCost(session);
165       }
166       _Iterator[] iterArray = new _Iterator[childPlans.length];
167       for (int i = 0; i < iterArray.length; i++) {
168          iterArray[i] = childPlans[i].execute(session);
169 
170       }
171       NestedLoopJoinIterator nestedLoopJoinIterator = new NestedLoopJoinIterator(iterArray);
172       if( underlyingRef != null ){
173         _Iterator itr = getNonIndexedFilteredIteratorWithSubQuery(nestedLoopJoinIterator,session,remainingCondition);
174         itr.setSpecificUnderlyingReferences(getUnderLyingReferencesForAllUnderLyingRefPassed());
175         return itr;
176       }
177       _Iterator iter= remainingCondition == null ?nestedLoopJoinIterator :getNonIndexedFilteredIterator(nestedLoopJoinIterator, session, remainingCondition);
178       return iter;
179    }
180 
181    /**
182     * Returns the order present in underlying plans, by concating them.
183     * @return
184     * @throws DException
185     */
186 
187    public _Order getOrder() throws DException {
188       SelectOrder selectOrder = null;
189       for (int i = 0; i < childPlans.length; i++) {
190          _Order order = childPlans[i].getOrder();
191          selectOrder = (SelectOrder) GeneralPurposeStaticClass.getJoinOrdered(selectOrder, order);
192       }
193       return selectOrder;
194    }
195 
196    /**
197     * This method is used to obtain the resultset based on the passed condition.
198     * Firstly, cartesian resultset is formed on underlying resultsets. Then if
199     * any condition is present, then that condition is anded with passed
200     * condition and filtered resultset is formed with remaining condition and
201     * passed condition on cartesian resultset.
202     * @param session
203     * @param conditionArg
204     * @return
205     * @throws DException
206     */
207 
208    public _Iterator execute(_ServerSession session, booleanvalueexpression conditionArg) throws DException {
209       _Iterator[] iterArray = new _Iterator[childPlans.length];
210       for (int i = 0; i < iterArray.length; i++) {
211          iterArray[i] = childPlans[i].execute(session);
212       }
213       NestedLoopJoinIterator nestedLoopJoinIterator = new NestedLoopJoinIterator(iterArray);
214       booleanvalueexpression conditionFromWhichCostIsCalculated =remainingCondition == null ? conditionArg : searchCostCaluledFrom(conditionArg, true);
215 
216       _Iterator iter3=getNonIndexedFilteredIterator(nestedLoopJoinIterator, session, conditionFromWhichCostIsCalculated);
217       iter3.setSpecificUnderlyingReferences(getUnderLyingReferencesForAllUnderLyingRefPassed());
218       return iter3;
219    }
220 
221    public String   toString() {
222       StringBuffer   sBuffer = new StringBuffer  ("NESTEDLOOPJOINPLAN");
223       for (int i = 0; i < childPlans.length; i++) {
224          sBuffer.append("[");
225          sBuffer.append(childPlans[i].toString());
226          sBuffer.append("]");
227       }
228       return sBuffer.toString();
229    }
230 
231    /**
232     * Serches the condition for the passed condition in appropriate mapping
233     * decided by boolean variable.
234     * @param conditionArg
235     * @param order
236     * @return
237     * @throws DException
238     */
239 
240    private booleanvalueexpression searchCostCaluledFrom(booleanvalueexpression conditionArg, boolean order) throws DException {
241       Object  [][] actualArray =
242           order ?
243           conditionMappingArray :
244           conditionMappingArrayWithoutOrder;
245 
246       for (int i = 0; i < actualArray.length; i++) {
247          if (actualArray[i][0].hashCode() == conditionArg.hashCode()) {
248             return (booleanvalueexpression) actualArray[i][1];
249          }
250       }
251       throw new DException("DSE3527", new Object  [] {conditionArg.toString()});
252    }
253 
254    /**
255     * This method is used to change the appropriate mapping based on whether
256     * order is taken into the consideration or not (decided by boolean
257     * variable). The anding of passed condition and remaining condition is put
258     * against passed condition in the mapping.
259     * @param conditionArg
260     * @param order
261     * @return
262     * @throws DException
263     */
264 
265    private booleanvalueexpression changeConditionMappingArray(booleanvalueexpression conditionArg, boolean order) throws DException {
266       Object  [][] srcArray = null;
267       booleanvalueexpression bve = null;
268       if (order) {
269          if (conditionMappingArray == null) {
270             conditionMappingArray = new Object  [0][0];
271          }
272          srcArray = conditionMappingArray;
273       } else {
274          if (conditionMappingArrayWithoutOrder == null) {
275             conditionMappingArrayWithoutOrder = new Object  [0][0];
276          }
277          srcArray = conditionMappingArrayWithoutOrder;
278       }
279       Object  [][] tempConditionMappingArray = new Object  [srcArray.length + 1][];
280       System.arraycopy(srcArray, 0, tempConditionMappingArray, 0, srcArray.length);
281       if (order) {
282          conditionMappingArray = tempConditionMappingArray;
283          conditionMappingArray[conditionMappingArray.length - 1] = new Object  [2];
284          conditionMappingArray[conditionMappingArray.length - 1][0] = conditionArg;
285          bve = BVEPlanMerger.addAndConditions(remainingCondition, conditionArg);
286          conditionMappingArray[conditionMappingArray.length - 1][1] = bve;
287       } else {
288          conditionMappingArrayWithoutOrder = tempConditionMappingArray;
289          conditionMappingArrayWithoutOrder[conditionMappingArrayWithoutOrder.length - 1] = new Object  [2];
290          conditionMappingArrayWithoutOrder[conditionMappingArrayWithoutOrder.length - 1][0] = conditionArg;
291          bve = (booleanvalueexpression) BVEPlanMerger.addAndConditions(remainingCondition, conditionArg);
292          conditionMappingArrayWithoutOrder[conditionMappingArrayWithoutOrder.length - 1][1] = bve;
293       }
294       return bve;
295    }
296 
297    public String   getVerifier() throws DException {
298       StringBuffer   sBuffer = new StringBuffer  ();
299       inc();
300       sBuffer.append(tabW("[ NESTED_LOOP_JOIN_PLAN ]"));
301       for (int i = 0; i < childPlans.length; i++) {
302          sBuffer.append("\n" + childPlans[i].getVerifier());
303       }
304       inc();
305       sBuffer.append(tab( ("[Condition = " + remainingCondition + "]")));
306       dec();
307       sBuffer.append(tab("[/ NESTED_LOOP_JOIN_PLAN ]"));
308       dec();
309       return sBuffer.toString();
310    }
311 
312    /**
313     * It is required when join condition belongs to this plan. If order is
314     * present in underlying plans and also if joincondition belongs to
315     * consecutive plan then join plan is formed for them, otherwise passed
316     * condition is solved on the cartesian.
317     * If order is not present then join relation is merged between two plans to
318     * which it belongs. And the resultant plan replaces the execution plan of
319     * both tables involved in join condition.
320     * @param joinRelation
321     * @throws DException
322     */
323 
324    public void merge(_JoinRelation joinRelation) throws DException {
325       if (getOrder() != null) {
326          mergeInSimpleCase(joinRelation);
327       } else {
328          TableDetails joinRelationTableDetails[] = joinRelation.getTableDetails();
329          if (joinRelationTableDetails.length != 2) {
330             throw new DException("DSENEW", new Object  [] {""});
331          }
332          int[] positionOfJoinRelation = getTablePlanPostions(joinRelationTableDetails);
333          childPlans = mergingOfJoinRelation(childPlans[positionOfJoinRelation[0]], childPlans[positionOfJoinRelation[1]], joinRelation, joinRelation.getTableDetails(), null, childPlans);
334          if (childPlans == null) {
335             Thread.dumpStack();
336          }
337       }
338    }
339 
340    /**
341     * It is required when join condition belong to this plan and If order is
342     * present in underlying plans. Now if joincondition belongs to
343     * consecutive plan then
344     * join plan is formed for them, otherwise passed condition is solved on the
345     * cartesian.
346     * @param joinRelation
347     * @throws DException
348     */
349 
350    private void mergeInSimpleCase(_JoinRelation joinRelation) throws DException {
351       TableDetails[] tableDetailsJR = joinRelation.getTableDetails();
352       int[] ind = getTablePlansIfConditionTablesAtZeroDistance(tableDetailsJR);
353       if (ind != null) { // joinRelation tables are at zero distance
354          int i = ind[0];
355          if (ind.length == 2) {
356             _TablePlan[] temp = new _TablePlan[childPlans.length - 1];
357             System.arraycopy(childPlans, 0, temp, 0, i);
358             temp[i] = new TwoTableJoinPlan(childPlans[i], childPlans[i + 1], joinRelation.getCondition());
359             System.arraycopy(childPlans, i + 2, temp, i + 1, childPlans.length - ind[1] - 1);
360             childPlans = temp;
361             if (childPlans == null) {
362                Thread.dumpStack();
363             }
364          } else {
365             childPlans[i].merge(joinRelation);
366          }
367       } else { // joinRelation tables are not at zero distance
368          remainingCondition = BVEPlanMerger.addAndConditions(remainingCondition, joinRelation.getCondition());
369          return;
370       }
371    }
372 
373    /**
374     * Returns an array of int containing indexes of given TableDetails, if
375     * present in the global childPlans array otherwise null.
376     * The given TableDetails belongs to a JoinRelation;
377     * @param tableDetailsJR
378     * @return
379     * @throws DException
380     */
381    private int[] getTablePlanPostions(TableDetails[] tableDetailsJR) throws DException {
382       int[] pos = new int[tableDetailsJR.length];
383       for (int i = 0, k = 0; i < tableDetailsJR.length; i++) {
384          for (int j = 0; j < childPlans.length; j++) {
385             if (childPlans[j].ifExists(tableDetailsJR[i])) {
386                pos[k++] = j;
387             }
388          }
389       }
390       return pos;
391    }
392 
393    /**
394     * Returns the indexes of tables in plans, when they are at cosecutive
395     * position.
396     * @param tableDetailsJR
397     * @return
398     * @throws DException
399     */
400 
401    private int[] getTablePlansIfConditionTablesAtZeroDistance(TableDetails[] tableDetailsJR) throws DException {
402       int[] pos = getTablePlanPostions(tableDetailsJR);
403       if (pos[1] - pos[0] == 0) {
404          return new int[] {pos[0]};
405       }
406       if (pos[1] - pos[0] == 1) {
407          return pos;
408       }
409       return null;
410    }
411 
412    /**
413     * Returns the plan for Nested Loop.
414     * @return
415     * @throws DException
416     */
417 
418    public _QueryPlan getQueryPlan() throws DException {
419       int length = childPlans.length;
420       _QueryPlan[] cplans = new _QueryPlan[length];
421       for (int i = 0; i < length; i++) {
422          cplans[i] = childPlans[i].getQueryPlan();
423       }
424       String   condition2 = remainingCondition == null ? null : ("" + remainingCondition);
425       return new QueryPlan("NestedLoopJoinPlan", cplans, condition2, null);
426    }
427 
428    /**
429     * Returns all the children plans.
430     * @return
431     * @throws DException
432     */
433 
434    public _TablePlan[] getChildTablePlans() throws DException {
435       return new _TablePlan[] {this};
436    }
437 
438    protected void updateMapping(int[] mappingPositions, _TablePlan tablePlan) throws DException {
439    }
440 
441    /**
442     * This method is used to remove the cover of unExecutable plans like
443     * OrderSequencePlan and TemporaryMergePlan.
444     * @return
445     * @throws DException
446     */
447 
448    public _TablePlan joinMissingLink() throws DException {
449       if (childPlans.length == 1) {
450          childPlans[0] = childPlans[0].joinMissingLink();
451          return childPlans[0];
452       } else {
453          return super.joinMissingLink();
454       }
455    }
456 
457    /**
458     * The following methods are same as corresponding counterparts getCost
459     * methods, but with a difference that order is not considered in underlying
460     * resultsets.
461     */
462 
463    public double getCostWithoutOrder(_ServerSession session) throws DException {
464       double cost = 1;
465       for (int i = 0; i < childPlans.length; i++) {
466          cost *= childPlans[i].getCostWithoutOrder(session);
467       }
468       return remainingCondition == null ?
469           cost :
470           cost + remainingCondition.getCost(getRowCountWithoutCondition(session), false);
471    }
472 
473    public double getCostWithoutOrder(_ServerSession session, booleanvalueexpression conditionArg, long estimatedRowCount) throws DException {
474       double cost = 1;
475       for (int i = 0; i < childPlans.length; i++) {
476          cost *= childPlans[i].getCostWithoutOrder(session);
477 
478       }
479       long rowCounts = getRowCountWithoutCondition(session);
480       return Double.MAX_VALUE / 2;
481    }
482 
483    /**
484     * The following methods are same as corresponding counterparts execute
485     * methods, but with a difference that order is not considered in underlying
486     * resultsets.
487     */
488 
489    public _Iterator executeWithoutOrder(_ServerSession session) throws DException {
490       _Iterator[] iterArray = new _Iterator[childPlans.length];
491       for (int i = 0; i < iterArray.length; i++) {
492          iterArray[i] = childPlans[i].executeWithoutOrder(session);
493       }
494       NestedLoopJoinIterator nestedLoopJoinIterator = new NestedLoopJoinIterator(iterArray);
495       if (remainingCondition == null) {
496          return nestedLoopJoinIterator;
497       }
498       _Iterator iter3=getNonIndexedFilteredIterator(nestedLoopJoinIterator, session, remainingCondition);
499       iter3.setSpecificUnderlyingReferences(getUnderLyingReferencesForAllUnderLyingRefPassed());
500       return iter3;
501    }
502 
503    public _Iterator executeWithOutOrder(_ServerSession session, booleanvalueexpression conditionArg) throws DException {
504       _Iterator[] iterArray = new _Iterator[childPlans.length];
505       iterArray[0] = childPlans[0].execute(session, conditionArg);
506       for (int i = 1; i < iterArray.length; i++) {
507          iterArray[i] = childPlans[i].executeWithoutOrder(session);
508       }
509       NestedLoopJoinIterator nestedLoopJoinIterator = new NestedLoopJoinIterator(iterArray);
510       booleanvalueexpression conditionFromWhichCostIsCalculated = remainingCondition == null ? conditionArg : searchCostCaluledFrom(conditionArg, false);
511       _Iterator iter=getNonIndexedFilteredIterator(nestedLoopJoinIterator, session, conditionFromWhichCostIsCalculated);
512       iter.setSpecificUnderlyingReferences(getUnderLyingReferencesForAllUnderLyingRefPassed());
513       return iter;
514    }
515 
516    private _Reference[] getUnderLyingReferencesForAllUnderLyingRefPassed() throws DException{
517      return GeneralPurposeStaticClass.getUnderLyingReferencesOnly(underlyingRef,getTableDetails());
518    }
519 
520 
521 }
522
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags