OptimizerImpl


1   /*
2   
3      Derby - Class org.apache.derby.impl.sql.compile.OptimizerImpl
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.sanity.SanityManager;
25  
26  import org.apache.derby.iapi.error.StandardException;
27  
28  import org.apache.derby.iapi.sql.compile.JoinStrategy;
29  import org.apache.derby.iapi.sql.compile.Optimizable;
30  import org.apache.derby.iapi.sql.compile.OptimizableList;
31  import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
32  import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
33  import org.apache.derby.iapi.sql.compile.Optimizer;
34  import org.apache.derby.iapi.sql.compile.CostEstimate;
35  import org.apache.derby.iapi.sql.compile.RequiredRowOrdering;
36  import org.apache.derby.iapi.sql.compile.RowOrdering;
37  import org.apache.derby.iapi.sql.compile.AccessPath;
38  
39  import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
40  
41  import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
42  import org.apache.derby.iapi.sql.dictionary.DataDictionary;
43  import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
44  
45  import org.apache.derby.catalog.IndexDescriptor;
46  import org.apache.derby.iapi.reference.SQLState;
47  
48  import org.apache.derby.iapi.util.JBitSet;
49  import org.apache.derby.iapi.util.StringUtil;
50  
51  import java.util.Properties  ;
52  import java.util.HashMap  ;
53  
54  /**
55   * This will be the Level 1 Optimizer.
56   * RESOLVE - it's a level 0 optimizer right now.
57   * Current State:
58   *  o  No costing services
59   *  o  We can only cost a derived table with a join once.
60   *  
61   * Optimizer uses OptimizableList to keep track of the best join order as it
62   * builds it.  For each available slot in the join order, we cost all of the
63   * Optimizables from that slot til the end of the OptimizableList.  Later,
64   * we will choose the best Optimizable for that slot and reorder the list
65   * accordingly.
66   * In order to do this, we probably need to move the temporary pushing and
67   * pulling of join clauses into Optimizer, since the logic will be different
68   * for other implementations.  (Of course, we're not pushing and pulling join
69   * clauses between permutations yet.)
70   */
71  
72  public class OptimizerImpl implements Optimizer 
73  {
74  
75      DataDictionary           dDictionary;
76      /* The number of tables in the query as a whole.  (Size of bit maps.) */
77      int                      numTablesInQuery;
78      /* The number of optimizables in the list to optimize */
79      int                      numOptimizables;
80  
81      /* Bit map of tables that have already been assigned to slots.
82       * Useful for pushing join clauses as slots are assigned.
83       */
84      protected JBitSet        assignedTableMap;
85      protected OptimizableList optimizableList;
86      OptimizablePredicateList predicateList;
87      JBitSet                  nonCorrelatedTableMap;
88  
89      protected int[]          proposedJoinOrder;
90      protected int[]                  bestJoinOrder;
91      protected int            joinPosition;
92      boolean                  desiredJoinOrderFound;
93  
94      /* This implements a state machine to jump start to a appearingly good join
95       * order, when the number of tables is high, and the optimization could take
96       * a long time.  A good start can prune better, and timeout sooner.  Otherwise,
97       * it may take forever to exhaust or timeout (see beetle 5870).  Basically after
98       * we jump, we walk the high part, then fall when we reach the peak, finally we
99       * walk the low part til where we jumped to.
100      */
101     private static final int NO_JUMP = 0;
102     private static final int READY_TO_JUMP = 1;
103     private static final int JUMPING = 2;
104     private static final int WALK_HIGH = 3;
105     private static final int WALK_LOW = 4;
106     private int              permuteState;
107     private int[]            firstLookOrder;
108 
109     private boolean          ruleBasedOptimization;
110 
111     private CostEstimateImpl outermostCostEstimate;
112     protected CostEstimateImpl currentCost;
113     protected CostEstimateImpl currentSortAvoidanceCost;
114     protected CostEstimateImpl bestCost;
115 
116     protected long           timeOptimizationStarted;
117     protected long           currentTime;
118     protected boolean        timeExceeded;
119     private boolean          noTimeout;
120     private boolean          useStatistics;
121     private int              tableLockThreshold;
122 
123     private JoinStrategy[]  joinStrategies;
124 
125     protected RequiredRowOrdering   requiredRowOrdering;
126 
127     private boolean          foundABestPlan;
128 
129     protected CostEstimate sortCost;
130 
131     private RowOrdering currentRowOrdering = new RowOrderingImpl();
132     private RowOrdering bestRowOrdering = new RowOrderingImpl();
133 
134     private boolean conglomerate_OneRowResultSet;
135 
136     // optimizer trace
137     protected boolean optimizerTrace;
138     protected boolean optimizerTraceHtml;
139 
140     // max memory use per table
141     protected int maxMemoryPerTable;
142 
143     // Whether or not we need to reload the best plan for an Optimizable
144     // when we "pull" it.  If the latest complete join order was the
145     // best one so far, then the Optimizable will already have the correct
146     // best plan loaded so we don't need to do the extra work.  But if
147     // the most recent join order was _not_ the best, then this flag tells
148     // us that we need to reload the best plan when pulling.
149     private boolean reloadBestPlan;
150 
151     // Set of optimizer->bestJoinOrder mappings used to keep track of which
152     // of this OptimizerImpl's "bestJoinOrder"s was the best with respect to a
153     // a specific outer query; the outer query is represented by an instance
154     // of Optimizer.  Each outer query could potentially have a different
155     // idea of what this OptimizerImpl's "best join order" is, so we have
156     // to keep track of them all.
157     private HashMap   savedJoinOrders;
158 
159     // Value used to figure out when/if we've timed out for this
160     // Optimizable.
161     protected double timeLimit;
162 
163     // Cost estimate for the final "best join order" that we chose--i.e.
164     // the one that's actually going to be generated.
165     CostEstimate finalCostEstimate;
166 
167     /* Status variables used for "jumping" to previous best join
168      * order when possible.  In particular, this helps when this
169      * optimizer corresponds to a subquery and we are trying to
170      * find out what the best join order is if we do a hash join
171      * with the subquery instead of a nested loop join.  In that
172      * case the previous best join order will have the best join
173      * order for a nested loop, so we want to start there when
174      * considering hash join because odds are that same join order
175      * will give us the best cost for hash join, as well.  We
176      * only try this, though, if neither the previous round of
177      * optimization nor this round relies on predicates that have
178      * been pushed down from above--because that's the scenario
179      * for which the best join order is likely to be same for
180      * consecutive rounds.
181      */
182     private boolean usingPredsPushedFromAbove;
183     private boolean bestJoinOrderUsedPredsFromAbove;
184 
185     protected  OptimizerImpl(OptimizableList optimizableList, 
186                   OptimizablePredicateList predicateList,
187                   DataDictionary dDictionary,
188                   boolean ruleBasedOptimization,
189                   boolean noTimeout,
190                   boolean useStatistics,
191                   int maxMemoryPerTable,
192                   JoinStrategy[] joinStrategies,
193                   int tableLockThreshold,
194                   RequiredRowOrdering requiredRowOrdering,
195                   int numTablesInQuery)
196         throws StandardException
197     {
198         if (SanityManager.DEBUG) {
199             SanityManager.ASSERT(optimizableList != null,
200                              "optimizableList is not expected to be null");
201         }
202 
203         outermostCostEstimate =  getNewCostEstimate(0.0d, 1.0d, 1.0d);
204 
205         currentCost = getNewCostEstimate(0.0d, 0.0d, 0.0d);
206 
207         currentSortAvoidanceCost = getNewCostEstimate(0.0d, 0.0d, 0.0d);
208 
209         bestCost = getNewCostEstimate(Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);
210 
211         // Verify that any Properties lists for user overrides are valid
212         optimizableList.verifyProperties(dDictionary);
213 
214         this.numTablesInQuery = numTablesInQuery;
215         numOptimizables = optimizableList.size();
216         proposedJoinOrder = new int[numOptimizables];
217         if (numTablesInQuery > 6)
218         {
219             permuteState = READY_TO_JUMP;
220             firstLookOrder = new int[numOptimizables];
221         }
222         else
223             permuteState = NO_JUMP;
224 
225         /* Mark all join positions as unused */
226         for (int i = 0; i < numOptimizables; i++)
227             proposedJoinOrder[i] = -1;
228 
229         bestJoinOrder = new int[numOptimizables];
230         joinPosition = -1;
231         this.optimizableList = optimizableList;
232         this.predicateList = predicateList;
233         this.dDictionary = dDictionary;
234         this.ruleBasedOptimization = ruleBasedOptimization;
235         this.noTimeout = noTimeout;
236         this.maxMemoryPerTable = maxMemoryPerTable;
237         this.joinStrategies = joinStrategies;
238         this.tableLockThreshold = tableLockThreshold;
239         this.requiredRowOrdering = requiredRowOrdering;
240         this.useStatistics = useStatistics;
241 
242         /* initialize variables for tracking permutations */
243         assignedTableMap = new JBitSet(numTablesInQuery);
244 
245         /*
246         ** Make a map of the non-correlated tables, which are the tables
247         ** in the list of Optimizables we're optimizing.  An reference
248         ** to a table that is not defined in the list of Optimizables
249         ** is presumed to be correlated.
250         */
251         nonCorrelatedTableMap = new JBitSet(numTablesInQuery);
252         for (int tabCtr = 0; tabCtr < numOptimizables; tabCtr++)
253         {
254             Optimizable curTable = optimizableList.getOptimizable(tabCtr);
255             nonCorrelatedTableMap.or(curTable.getReferencedTableMap());
256         }
257 
258         /* Get the time that optimization starts */
259         timeOptimizationStarted = System.currentTimeMillis();
260         reloadBestPlan = false;
261         savedJoinOrders = null;
262         timeLimit = Double.MAX_VALUE;
263 
264         usingPredsPushedFromAbove = false;
265         bestJoinOrderUsedPredsFromAbove = false;
266     }
267 
268     /**
269      * This method is called before every "round" of optimization, where
270      * we define a "round" to be the period between the last time a call to
271      * getOptimizer() (on either a ResultSetNode or an OptimizerFactory)
272      * returned _this_ OptimizerImpl and the time a call to this OptimizerImpl's
273      * getNextPermutation() method returns FALSE.  Any re-initialization
274      * of state that is required before each round should be done in this
275      * method.
276      */
277     public void prepForNextRound()
278     {
279         // We initialize reloadBestPlan to false so that if we end up
280         // pulling an Optimizable before we find a best join order
281         // (which can happen if there is no valid join order for this
282         // round) we won't inadvertently reload the best plans based
283         // on some previous round.
284         reloadBestPlan = false;
285 
286         /* Since we're preparing for a new round, we have to clear
287          * out the "bestCost" from the previous round to ensure that,
288          * when this round of optimizing is done, bestCost will hold
289          * the best cost estimate found _this_ round, if there was
290          * one.  If there was no best cost found (which can happen if
291          * there is no feasible join order) then bestCost will remain
292          * at Double.MAX_VALUE.  Then when outer queries check the
293          * cost and see that it is so high, they will reject whatever
294          * outer join order they're trying in favor of something that's
295          * actually valid (and therefore cheaper).
296          *
297          * Note that we do _not_ reset the "foundABestPlan" variable nor
298          * the "bestJoinOrder" array.  This is because it's possible that
299          * a "best join order" may not exist for the current round, in
300          * which case this OptimizerImpl must know whether or not it found
301          * a best join order in a previous round (foundABestPlan) and if
302          * so what the corresponding join order was (bestJoinOrder).  This
303          * information is required so that the correct query plan can be
304          * generated after optimization is complete, even if that best
305          * plan was not found in the most recent round.
306          */
307         bestCost = getNewCostEstimate(
308             Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);
309 
310         /* If we have predicates that were pushed down to this OptimizerImpl
311          * from an outer query, then we reset the timeout state to prepare for
312          * the next round of optimization.  Otherwise if we timed out during
313          * a previous round and then we get here for another round, we'll
314          * immediately "timeout" again before optimizing any of the Optimizables
315          * in our list.  This is okay if we don't have any predicates from
316          * outer queries because in that case the plan we find this round
317          * will be the same one we found in the previous round, in which
318          * case there's no point in resetting the timeout state and doing
319          * the work a second time.  But if we have predicates from an outer
320          * query, those predicates could help us find a much better plan
321          * this round than we did in previous rounds--so we reset the timeout
322          * state to ensure that we have a chance to consider plans that
323          * can take advantage of the pushed predicates.
324          */
325         usingPredsPushedFromAbove = false;
326         if ((predicateList != null) && (predicateList.size() > 0))
327         {
328             for (int i = predicateList.size() - 1; i >= 0; i--)
329             {
330                 // If the predicate is "scoped", then we know it was pushed
331                 // here from an outer query.
332                 if (((Predicate)predicateList.
333                     getOptPredicate(i)).isScopedForPush())
334                 {
335                     usingPredsPushedFromAbove = true;
336                     break;
337                 }
338             }
339         }
340 
341         if (usingPredsPushedFromAbove)
342         {
343             timeOptimizationStarted = System.currentTimeMillis();
344             timeExceeded = false;
345         }
346 
347         /* If user specified the optimizer override for a fixed
348          * join order, then desiredJoinOrderFound could be true
349          * when we get here.  We have to reset it to false in
350          * prep for the next round of optimization.  Otherwise
351          * we'd end up quitting the optimization before ever
352          * finding a plan for this round, and that could, among
353          * other things, lead to a never-ending optimization
354          * phase in certain situations.  DERBY-1866.
355          */
356         desiredJoinOrderFound = false;
357     }
358 
359     public int getMaxMemoryPerTable()
360     {
361         return maxMemoryPerTable;
362     }
363     
364     /**
365      * @see Optimizer#getNextPermutation
366      *
367      * @exception StandardException     Thrown on error
368      */
369     public boolean getNextPermutation()
370             throws StandardException
371     {
372         /* Don't get any permutations if there is nothing to optimize */
373         if (numOptimizables < 1)
374         {
375             if (optimizerTrace)
376             {
377                 trace(NO_TABLES, 0, 0, 0.0, null);
378             }
379 
380             endOfRoundCleanup();
381             return false;
382         }
383 
384         /* Make sure that all Optimizables init their access paths.
385          * (They wait until optimization since the access path
386          * references the optimizer.)
387          */
388         optimizableList.initAccessPaths(this);
389 
390         /*
391         ** Experiments show that optimization time only starts to
392         ** become a problem with seven tables, so only check for
393         ** too much time if there are more than seven tables.
394         ** Also, don't check for too much time if user has specified
395         ** no timeout.
396         */
397         if ( ( ! timeExceeded ) &&
398              (numTablesInQuery > 6)  &&
399              ( ! noTimeout) )
400         {
401             /*
402             ** Stop optimizing if the time spent optimizing is greater than
403             ** the current best cost.
404             */
405             currentTime = System.currentTimeMillis();
406             timeExceeded = (currentTime - timeOptimizationStarted) > timeLimit;
407 
408             if (optimizerTrace && timeExceeded)
409             {
410                 trace(TIME_EXCEEDED, 0, 0, 0.0, null);
411             }
412         }
413 
414         if (bestCost.isUninitialized() && foundABestPlan &&
415             ((!usingPredsPushedFromAbove && !bestJoinOrderUsedPredsFromAbove)
416                 || timeExceeded))
417         {
418             /* We can get here if this OptimizerImpl is for a subquery
419              * that timed out for a previous permutation of the outer
420              * query, but then the outer query itself did _not_ timeout.
421              * In that case we'll end up back here for another round of
422              * optimization, but our timeExceeded flag will be true.
423              * We don't want to reset all of the timeout state here
424              * because that could lead to redundant work (see comments
425              * in prepForNextRound()), but we also don't want to return
426              * without having a plan, because then we'd return an unfairly
427              * high "bestCost" value--i.e. Double.MAX_VALUE.  Note that
428              * we can't just revert back to whatever bestCost we had
429              * prior to this because that cost is for some previous
430              * permutation of the outer query--not the current permutation--
431              * and thus would be incorrect.  So instead we have to delay
432              * the timeout until we find a complete (and valid) join order,
433              * so that we can return a valid cost estimate.  Once we have
434              * a valid cost we'll then go through the timeout logic
435              * and stop optimizing.
436              * 
437              * All of that said, instead of just trying the first possible
438              * join order, we jump to the join order that gave us the best
439              * cost in previous rounds.  We know that such a join order exists
440              * because that's how our timeout value was set to begin with--so
441              * if there was no best join order, we never would have timed out
442              * and thus we wouldn't be here.
443              *
444              * We can also get here if we've already optimized the list
445              * of optimizables once (in a previous round of optimization)
446              * and now we're back to do it again.  If that's true AND
447              * we did *not* receive any predicates pushed from above AND
448              * the bestJoinOrder from the previous round did *not* depend
449              * on predicates pushed from above, then we'll jump to the
450              * previous join order and start there.  NOTE: if after jumping
451              * to the previous join order and calculating the cost we haven't
452              * timed out, we will continue looking at other join orders (as
453              * usual) until we exhaust them all or we time out.
454              */
455             if (permuteState != JUMPING)
456             {
457                 // By setting firstLookOrder to our target join order
458                 // and then setting our permuteState to JUMPING, we'll
459                 // jump to the target join order and get the cost.  That
460                 // cost will then be saved as bestCost, allowing us to
461                 // proceed with normal timeout logic.
462                 if (firstLookOrder == null)
463                     firstLookOrder = new int[numOptimizables];
464                 for (int i = 0; i < numOptimizables; i++)
465                     firstLookOrder[i] = bestJoinOrder[i];
466                 permuteState = JUMPING;
467 
468                 /* If we already assigned at least one position in the
469                  * join order when this happened (i.e. if joinPosition
470                  * is greater than *or equal* to zero; DERBY-1777), then 
471                  * reset the join order before jumping.  The call to
472                  * rewindJoinOrder() here will put joinPosition back
473                  * to 0.  But that said, we'll then end up incrementing
474                  * joinPosition before we start looking for the next
475                  * join order (see below), which means we need to set
476                  * it to -1 here so that it gets incremented to "0" and
477                  * then processing can continue as normal from there.  
478                  * Note: we don't need to set reloadBestPlan to true
479                  * here because we only get here if we have *not* found
480                  * a best plan yet.
481                  */
482                 if (joinPosition >= 0)
483                 {
484                     rewindJoinOrder();
485                     joinPosition = -1;
486                 }
487             }
488 
489             // Reset the timeExceeded flag so that we'll keep going
490             // until we find a complete join order.  NOTE: we intentionally
491             // do _not_ reset the timeOptimizationStarted value because we
492             // we want to go through this timeout logic for every
493             // permutation, to make sure we timeout as soon as we have
494             // our first complete join order.
495             timeExceeded = false;
496         }
497 
498         /*
499         ** Pick the next table in the join order, if there is an unused position
500         ** in the join order, and the current plan is less expensive than
501         ** the best plan so far, and the amount of time spent optimizing is
502         ** still less than the cost of the best plan so far, and a best
503         ** cost has been found in the current join position.  Otherwise,
504         ** just pick the next table in the current position.
505         */
506         boolean joinPosAdvanced = false;
507 
508         /* Determine if the current plan is still less expensive than
509          * the best plan so far.  If bestCost is uninitialized then
510          * we want to return false here; if we didn't, then in the (rare)
511          * case where the current cost is greater than Double.MAX_VALUE
512          * (esp. if it's Double.POSITIVE_INFINITY, which can occur
513          * for very deeply nested queries with long FromLists) we would
514          * give up on the current plan even though we didn't have a
515          * best plan yet, which would be wrong.  Also note: if we have
516          * a required row ordering then we might end up using the
517          * sort avoidance plan--but we don't know at this point
518          * which plan (sort avoidance or "normal") we're going to
519          * use, so we error on the side of caution and only short-
520          * circuit if both currentCost and currentSortAvoidanceCost
521          * (if the latter is applicable) are greater than bestCost.
522          */
523         boolean alreadyCostsMore =
524             !bestCost.isUninitialized() &&
525             (currentCost.compare(bestCost) > 0) &&
526             ((requiredRowOrdering == null) ||
527                 (currentSortAvoidanceCost.compare(bestCost) > 0));
528 
529         if ((joinPosition < (numOptimizables - 1)) &&
530             !alreadyCostsMore &&
531             ( ! timeExceeded )
532             )
533         {
534             /*
535             ** Are we either starting at the first join position (in which
536             ** case joinPosition will be -1), or has a best cost been found
537             ** in the current join position?  The latter case might not be
538             ** true if there is no feasible join order.
539             */
540             if ((joinPosition < 0) ||
541                 optimizableList.getOptimizable(
542                                             proposedJoinOrder[joinPosition]).
543                                 getBestAccessPath().getCostEstimate() != null)
544             {
545                 joinPosition++;
546                 joinPosAdvanced = true;
547 
548                 /*
549                 ** When adding a table to the join order, the best row
550                 ** row ordering for the outer tables becomes the starting
551                 ** point for the row ordering of the current table.
552                 */
553                 bestRowOrdering.copy(currentRowOrdering);
554             }
555         }
556         else
557         {
558             if (optimizerTrace)
559             {
560                 /*
561                 ** Not considered short-circuiting if all slots in join
562                 ** order are taken.
563                 */
564                 if (joinPosition < (numOptimizables - 1))
565                 {
566                     trace(SHORT_CIRCUITING, 0, 0, 0.0, null);
567                 }
568             }
569 
570             // If we short-circuited the current join order then we need
571             // to make sure that, when we start pulling optimizables to find
572             // a new join order, we reload the best plans for those
573             // optimizables as we pull them.  Otherwise we could end up
574             // generating a plan for an optimizable even though that plan
575             // was part of a short-circuited (and thus rejected) join
576             // order.
577             if (joinPosition < (numOptimizables - 1))
578                 reloadBestPlan = true;
579         }
580 
581         if (permuteState == JUMPING && !joinPosAdvanced && joinPosition >= 0)
582         {
583             //not feeling well in the middle of jump
584             // Note: we have to make sure we reload the best plans
585             // as we rewind since they may have been clobbered
586             // (as part of the current join order) before we gave
587             // up on jumping.
588             reloadBestPlan = true;
589             rewindJoinOrder();  //fall
590             permuteState = NO_JUMP;  //give up
591         }
592 
593         /*
594         ** The join position becomes < 0 when all the permutations have been
595         ** looked at.
596         */
597         while (joinPosition >= 0)
598         {
599             int nextOptimizable = 0;
600 
601             if (desiredJoinOrderFound || timeExceeded)
602             {
603                 /*
604                 ** If the desired join order has been found (which will happen
605                 ** if the user specifies a join order), pretend that there are
606                 ** no more optimizables at this join position.  This will cause
607                 ** us to back out of the current join order.
608                 **
609                 ** Also, don't look at any more join orders if we have taken
610                 ** too much time with this optimization.
611                 */
612                 nextOptimizable = numOptimizables;
613             }
614             else if (permuteState == JUMPING)  //still jumping
615             {
616                 /* We're "jumping" to a join order that puts the optimizables
617                 ** with the lowest estimated costs first (insofar as it
618                 ** is legal to do so).  The "firstLookOrder" array holds the
619                 ** ideal join order for position <joinPosition> up thru
620                 ** position <numOptimizables-1>.  So here, we look at the
621                 ** ideal optimizable to place at <joinPosition> and see if
622                 ** it's legal; if it is, then we're done.  Otherwise, we
623                 ** swap it with <numOptimizables-1> and see if that gives us
624                 ** a legal join order w.r.t <joinPosition>.  If not, then we
625                 ** swap it with <numOptimizables-2> and check, and if that
626                 ** fails, then we swap it with <numOptimizables-3>, and so
627                 ** on.  For example, assume we have 6 optimizables whose
628                 ** order from least expensive to most expensive is 2, 1, 4,
629                 ** 5, 3, 0.  Assume also that we've already verified the
630                 ** legality of the first two positions--i.e. that joinPosition
631                 ** is now "2". That means that "firstLookOrder" currently
632                 ** contains the following:
633                 **
634                 ** [ pos ]    0  1  2  3  4  5
635                 ** [ opt ]    2  1  4  5  3  0
636                 **
637                 ** Then at this point, we do the following:
638                 **
639                 **  -- Check to see if the ideal optimizable "4" is valid
640                 **     at its current position (2)
641                 **  -- If opt "4" is valid, then we're done; else we
642                 **     swap it with the value at position _5_:
643                 **
644                 ** [ pos ]    0  1  2  3  4  5
645                 ** [ opt ]    2  1  0  5  3  4
646                 **
647                 **  -- Check to see if optimizable "0" is valid at its
648                 **     new position (2).
649                 **  -- If opt "0" is valid, then we're done; else we
650                 **     put "0" back in its original position and swap
651                 **     the ideal optimizer ("4") with the value at
652                 **     position _4_:
653                 **
654                 ** [ pos ]    0  1  2  3  4  5
655                 ** [ opt ]    2  1  3  5  4  0
656                 **
657                 **  -- Check to see if optimizable "3" is valid at its
658                 **     new position (2).
659                 **  -- If opt "3" is valid, then we're done; else we
660                 **     put "3" back in its original position and swap
661                 **     the ideal optimizer ("4") with the value at
662                 **     position _3_:
663                 **
664                 ** [ pos ]    0  1  2  3  4  5
665                 ** [ opt ]    2  1  5  4  3  0
666                 **
667                 **  -- Check to see if optimizable "5" is valid at its
668                 **     new position (2).
669                 **  -- If opt "5" is valid, then we're done; else we've
670                 **     tried all the available optimizables and none
671                 **     of them are legal at position 2.  In this case,
672                 **     we give up on "JUMPING" and fall back to normal
673                 **     join-order processing.
674                 */
675 
676                 int idealOptimizable = firstLookOrder[joinPosition];
677                 nextOptimizable = idealOptimizable;
678                 int lookPos = numOptimizables;
679                 int lastSwappedOpt = -1;
680 
681                 Optimizable nextOpt;
682                 for (nextOpt = optimizableList.getOptimizable(nextOptimizable);
683                     !(nextOpt.legalJoinOrder(assignedTableMap));
684                     nextOpt = optimizableList.getOptimizable(nextOptimizable))
685                 {
686                     // Undo last swap, if we had one.
687                     if (lastSwappedOpt >= 0) {
688                         firstLookOrder[joinPosition] = idealOptimizable;
689                         firstLookOrder[lookPos] = lastSwappedOpt;
690                     }
691 
692                     if (lookPos > joinPosition + 1) {
693                     // we still have other possibilities; get the next
694                     // one by "swapping" it into the current position.
695                         lastSwappedOpt = firstLookOrder[--lookPos];
696                         firstLookOrder[joinPosition] = lastSwappedOpt;
697                         firstLookOrder[lookPos] = idealOptimizable;
698                         nextOptimizable = lastSwappedOpt;
699                     }
700                     else {
701                     // we went through all of the available optimizables
702                     // and none of them were legal in the current position;
703                     // so we give up and fall back to normal processing.
704                     // Note: we have to make sure we reload the best plans
705                     // as we rewind since they may have been clobbered
706                     // (as part of the current join order) before we got
707                     // here.
708                         if (joinPosition > 0) {
709                             joinPosition--;
710                             reloadBestPlan = true;
711                             rewindJoinOrder();
712                         }
713                         permuteState = NO_JUMP;
714                         break;
715                     }
716                 }
717 
718                 if (permuteState == NO_JUMP)
719                     continue;
720 
721                 if (joinPosition == numOptimizables - 1) {
722                 // we just set the final position within our
723                 // "firstLookOrder" join order; now go ahead
724                 // and search for the best join order, starting from
725                 // the join order stored in "firstLookOrder".  This
726                 // is called walking "high" because we're searching
727                 // the join orders that are at or "above" (after) the
728                 // order found in firstLookOrder.  Ex. if we had three
729                 // optimizables and firstLookOrder was [1 2 0], then
730                 // the "high" would be [1 2 0], [2 0 1] and [2 1 0];
731                 // the "low" would be [0 1 2], [0 2 1], and [1 0 2].
732                 // We walk the "high" first, then fall back and
733                 // walk the "low".
734                     permuteState = WALK_HIGH;
735                 }
736             }
737             else
738             {
739                 /* Find the next unused table at this join position */
740                 nextOptimizable = proposedJoinOrder[joinPosition] + 1;
741 
742                 for ( ; nextOptimizable < numOptimizables; nextOptimizable++)
743                 {
744                     boolean found = false;
745                     for (int posn = 0; posn < joinPosition; posn++)
746                     {
747                         /*
748                         ** Is this optimizable already somewhere
749                         ** in the join order?
750                         */
751                         if (proposedJoinOrder[posn] == nextOptimizable)
752                         {
753                             found = true;
754                             break;
755                         }
756                     }
757 
758                     /* Check to make sure that all of the next optimizable's
759                      * dependencies have been satisfied.
760                      */
761                     if (nextOptimizable < numOptimizables)
762                     {
763                         Optimizable nextOpt =
764                                 optimizableList.getOptimizable(nextOptimizable);
765                         if (! (nextOpt.legalJoinOrder(assignedTableMap)))
766                         {
767                             if (optimizerTrace)
768                             {
769                                 trace(SKIPPING_JOIN_ORDER, nextOptimizable, 0, 0.0, null);
770                             }
771 
772                             /*
773                             ** If this is a user specified join order then it is illegal.
774                             */
775                             if ( ! optimizableList.optimizeJoinOrder())
776                             {
777                                 if (optimizerTrace)
778                                 {
779                                     trace(ILLEGAL_USER_JOIN_ORDER, 0, 0, 0.0, null);
780                                 }
781 
782                                 throw StandardException.newException(SQLState.LANG_ILLEGAL_FORCED_JOIN_ORDER);
783                             }
784                             continue;
785                         }
786                     }
787 
788                     if (! found)
789                     {
790                         break;
791                     }
792                 }
793 
794             }
795 
796             /*
797             ** We are going to try an optimizable at the current join order
798             ** position.  Is there one already at that position?
799             */
800             if (proposedJoinOrder[joinPosition] >= 0)
801             {
802                 /*
803                 ** We are either going to try another table at the current
804                 ** join order position, or we have exhausted all the tables
805                 ** at the current join order position.  In either case, we
806                 ** need to pull the table at the current join order position
807                 ** and remove it from the join order.
808                 */
809                 Optimizable pullMe =
810                     optimizableList.getOptimizable(
811                                             proposedJoinOrder[joinPosition]);
812 
813                 /*
814                 ** Subtract the cost estimate of the optimizable being
815                 ** removed from the total cost estimate.
816                 **
817                 ** The total cost is the sum of all the costs, but the total
818                 ** number of rows is the number of rows returned by the
819                 ** innermost optimizable.
820                 */
821                 double prevRowCount;
822                 double prevSingleScanRowCount;
823                 int prevPosition = 0;
824                 if (joinPosition == 0)
825                 {
826                     prevRowCount = outermostCostEstimate.rowCount();
827                     prevSingleScanRowCount = outermostCostEstimate.singleScanRowCount();
828                 }
829                 else
830                 {
831                     prevPosition = proposedJoinOrder[joinPosition - 1];
832                     CostEstimate localCE = 
833                         optimizableList.
834                             getOptimizable(prevPosition).
835                                 getBestAccessPath().
836                                     getCostEstimate();
837                     prevRowCount = localCE.rowCount();
838                     prevSingleScanRowCount = localCE.singleScanRowCount();
839                 }
840 
841                 /*
842                 ** If there is no feasible join order, the cost estimate
843                 ** in the best access path may never have been set.
844                 ** In this case, do not subtract anything from the
845                 ** current cost, since nothing was added to the current
846                 ** cost.
847                 */
848                 double newCost = currentCost.getEstimatedCost();
849                 double pullCost = 0.0;
850                 CostEstimate pullCostEstimate =
851                                 pullMe.getBestAccessPath().getCostEstimate();
852                 if (pullCostEstimate != null)
853                 {
854                     pullCost = pullCostEstimate.getEstimatedCost();
855 
856                     newCost -= pullCost;
857 
858                     /*
859                     ** It's possible for newCost to go negative here due to
860                     ** loss of precision.
861                     */
862                     if (newCost < 0.0)
863                         newCost = 0.0;
864                 }
865 
866                 /* If we are choosing a new outer table, then
867                  * we rest the starting cost to the outermostCost.
868                  * (Thus avoiding any problems with floating point
869                  * accuracy and going negative.)
870                  */
871                 if (joinPosition == 0)
872                 {
873                     if (outermostCostEstimate != null)
874                     {
875                         newCost = outermostCostEstimate.getEstimatedCost();
876                     }
877                     else
878                     {
879                         newCost = 0.0;
880                     }
881                 }
882 
883                 currentCost.setCost(
884                     newCost,
885                     prevRowCount,
886                     prevSingleScanRowCount);
887                 
888                 /*
889                 ** Subtract from the sort avoidance cost if there is a
890                 ** required row ordering.
891                 **
892                 ** NOTE: It is not necessary here to check whether the
893                 ** best cost was ever set for the sort avoidance path,
894                 ** because it considerSortAvoidancePath() would not be
895                 ** set if there cost were not set.
896                 */
897                 if (requiredRowOrdering != null)
898                 {
899                     if (pullMe.considerSortAvoidancePath())
900                     {
901                         AccessPath ap = pullMe.getBestSortAvoidancePath();
902                         double     prevEstimatedCost = 0.0d;
903 
904                         /*
905                         ** Subtract the sort avoidance cost estimate of the
906                         ** optimizable being removed from the total sort
907                         ** avoidance cost estimate.
908                         **
909                         ** The total cost is the sum of all the costs, but the
910                         ** total number of rows is the number of rows returned
911                         ** by the innermost optimizable.
912                         */
913                         if (joinPosition == 0)
914                         {
915                             prevRowCount = outermostCostEstimate.rowCount();
916                             prevSingleScanRowCount = outermostCostEstimate.singleScanRowCount();
917                             /* If we are choosing a new outer table, then
918                              * we rest the starting cost to the outermostCost.
919                              * (Thus avoiding any problems with floating point
920                              * accuracy and going negative.)
921                              */
922                             prevEstimatedCost = outermostCostEstimate.getEstimatedCost();
923                         }
924                         else
925                         {
926                             CostEstimate localCE = 
927                                 optimizableList.
928                                     getOptimizable(prevPosition).
929                                         getBestSortAvoidancePath().
930                                             getCostEstimate();
931                             prevRowCount = localCE.rowCount();
932                             prevSingleScanRowCount = localCE.singleScanRowCount();
933                             prevEstimatedCost = currentSortAvoidanceCost.getEstimatedCost() -
934                                                     ap.getCostEstimate().getEstimatedCost();
935                         }
936 
937                         currentSortAvoidanceCost.setCost(
938                             prevEstimatedCost,
939                             prevRowCount,
940                             prevSingleScanRowCount);
941 
942                         /*
943                         ** Remove the table from the best row ordering.
944                         ** It should not be necessary to remove it from
945                         ** the current row ordering, because it is
946                         ** maintained as we step through the access paths
947                         ** for the current Optimizable.
948                         */
949                         bestRowOrdering.removeOptimizable(
950                                                     pullMe.getTableNumber());
951 
952                         /*
953                         ** When removing a table from the join order,
954                         ** the best row ordering for the remaining outer tables
955                         ** becomes the starting point for the row ordering of
956                         ** the current table.
957                         */
958                         bestRowOrdering.copy(currentRowOrdering);
959                     }
960                 }
961 
962                 /*
963                 ** Pull the predicates at from the optimizable and put
964                 ** them back in the predicate list.
965                 **
966                 ** NOTE: This is a little inefficient because it pulls the
967                 ** single-table predicates, which are guaranteed to always
968                 ** be pushed to the same optimizable.  We could make this
969                 ** leave the single-table predicates where they are.
970                 */
971                 pullMe.pullOptPredicates(predicateList);
972 
973                 /*
974                 ** When we pull an Optimizable we need to go through and
975                 ** load whatever best path we found for that Optimizable
976                 ** with respect to _this_ OptimizerImpl.  An Optimizable
977                 ** can have different "best paths" for different Optimizer
978                 ** Impls if there are subqueries beneath it; we need to make
979                 ** sure that when we pull it, it's holding the best path as
980                 ** as we determined it to be for _us_.
981                 **
982                 ** NOTE: We we only reload the best plan if it's necessary
983                 ** to do so--i.e. if the best plans aren't already loaded.
984                 ** The plans will already be loaded if the last complete
985                 ** join order we had was the best one so far, because that
986                 ** means we called "rememberAsBest" on every Optimizable
987                 ** in the list and, as part of that call, we will run through
988                 ** and set trulyTheBestAccessPath for the entire subtree.
989                 ** So if we haven't tried any other plans since then,
990                 ** we know that every Optimizable (and its subtree) already
991                 ** has the correct best plan loaded in its trulyTheBest
992                 ** path field.  It's good to skip the load in this case
993                 ** because 'reloading best plans' involves walking the
994                 ** entire subtree of _every_ Optimizable in the list, which
995                 ** can be expensive if there are deeply nested subqueries.
996                 */
997                 if (reloadBestPlan)
998                     pullMe.updateBestPlanMap(FromTable.LOAD_PLAN, this);
999 
1000                /* Mark current join position as unused */
1001                proposedJoinOrder[joinPosition] = -1;
1002            }
1003
1004            /* Have we exhausted all the optimizables at this join position? */
1005            if (nextOptimizable >= numOptimizables)
1006            {
1007                /*
1008                ** If we're not optimizing the join order, remember the first
1009                ** join order.
1010                */
1011                if ( ! optimizableList.optimizeJoinOrder())
1012                {
1013                    // Verify that the user specified a legal join order
1014                    if ( ! optimizableList.legalJoinOrder(numTablesInQuery))
1015                    {
1016                        if (optimizerTrace)
1017                        {
1018                            trace(ILLEGAL_USER_JOIN_ORDER, 0, 0, 0.0, null);
1019                        }
1020
1021                        throw StandardException.newException(SQLState.LANG_ILLEGAL_FORCED_JOIN_ORDER);
1022                    }
1023
1024                    if (optimizerTrace)
1025                    {
1026                        trace(USER_JOIN_ORDER_OPTIMIZED, 0, 0, 0.0, null);
1027                    }
1028
1029                    desiredJoinOrderFound = true;
1030                }
1031
1032                if (permuteState == READY_TO_JUMP && joinPosition > 0 && joinPosition == numOptimizables-1)
1033                {
1034                    permuteState = JUMPING;
1035
1036                    /* A simple heuristics is that the row count we got indicates a potentially
1037                     * good join order.  We'd like row count to get big as late as possible, so
1038                     * that less load is carried over.
1039                     */
1040                    double rc[] = new double[numOptimizables];
1041                    for (int i = 0; i < numOptimizables; i++)
1042                    {
1043                        firstLookOrder[i] = i;
1044                        CostEstimate ce = optimizableList.getOptimizable(i).
1045                                                getBestAccessPath().getCostEstimate();
1046                        if (ce == null)
1047                        {
1048                            permuteState = READY_TO_JUMP;  //come again?
1049                            break;
1050                        }
1051                        rc[i] = ce.singleScanRowCount();
1052                    }
1053                    if (permuteState == JUMPING)
1054                    {
1055                        boolean doIt = false;
1056                        int temp;
1057                        for (int i = 0; i < numOptimizables; i++)   //simple selection sort
1058                        {
1059                            int k = i;
1060                            for (int j = i+1; j < numOptimizables; j++)
1061                                if (rc[j] < rc[k])  k = j;
1062                            if (k != i)
1063                            {
1064                                rc[k] = rc[i];  //destroy the bridge
1065                                temp = firstLookOrder[i];
1066                                firstLookOrder[i] = firstLookOrder[k];
1067                                firstLookOrder[k] = temp;
1068                                doIt = true;
1069                            }
1070                        }
1071
1072                        if (doIt)
1073                        {
1074                            joinPosition--;
1075                            rewindJoinOrder();  //jump from ground
1076                            continue;
1077                        }
1078                        else permuteState = NO_JUMP;    //never
1079                    }
1080                }
1081
1082                /*
1083                ** We have exhausted all the optimizables at this level.
1084                ** Go back up one level.
1085                */
1086
1087                /* Go back up one join position */
1088                joinPosition--;
1089
1090                /* Clear the assigned table map for the previous position 
1091                 * NOTE: We need to do this here to for the dependency tracking
1092                 */
1093                if (joinPosition >= 0)
1094                {
1095                    Optimizable pullMe =
1096                        optimizableList.getOptimizable(
1097                                            proposedJoinOrder[joinPosition]);
1098
1099                    /*
1100                    ** Clear the bits from the table at this join position.
1101                    ** This depends on them having been set previously.
1102                    ** NOTE: We need to do this here to for the dependency tracking
1103                    */
1104                    assignedTableMap.xor(pullMe.getReferencedTableMap());
1105                }
1106
1107                if (joinPosition < 0 && permuteState == WALK_HIGH) //reached peak
1108                {
1109                    joinPosition = 0;   //reset, fall down the hill
1110                    permuteState = WALK_LOW;
1111                }
1112                continue;
1113            }
1114
1115            /*
1116            ** We have found another optimizable to try at this join position.
1117            */
1118            proposedJoinOrder[joinPosition] = nextOptimizable;
1119
1120            if (permuteState == WALK_LOW)
1121            {
1122                boolean finishedCycle = true;
1123                for (int i = 0; i < numOptimizables; i++)
1124                {
1125                    if (proposedJoinOrder[i] < firstLookOrder[i])
1126                    {
1127                        finishedCycle = false;
1128                        break;
1129                    }
1130                    else if (proposedJoinOrder[i] > firstLookOrder[i])  //done
1131                        break;
1132                }
1133                if (finishedCycle)
1134                {
1135                    // We just set proposedJoinOrder[joinPosition] above, so
1136                    // if we're done we need to put it back to -1 to indicate
1137                    // that it's an empty slot.  Then we rewind and pull any
1138                    // other Optimizables at positions < joinPosition.
1139                    // Note: we have to make sure we reload the best plans
1140                    // as we rewind since they may have been clobbered
1141                    // (as part of the current join order) before we got
1142                    // here.
1143                    proposedJoinOrder[joinPosition] = -1;
1144                    joinPosition--;
1145                    if (joinPosition >= 0)
1146                    {
1147                        reloadBestPlan = true;
1148                        rewindJoinOrder();
1149                        joinPosition = -1;
1150                    }
1151
1152                    permuteState = READY_TO_JUMP;
1153                    endOfRoundCleanup();
1154                    return false;
1155                }
1156            }
1157
1158            /* Re-init (clear out) the cost for the best access path
1159             * when placing a table.
1160             */
1161            optimizableList.getOptimizable(nextOptimizable).
1162                getBestAccessPath().setCostEstimate((CostEstimate) null);
1163
1164            /* Set the assigned table map to be exactly the tables
1165             * in the current join order. 
1166             */
1167            assignedTableMap.clearAll();
1168            for (int index = 0; index <= joinPosition; index++)
1169            {
1170                assignedTableMap.or(optimizableList.getOptimizable(proposedJoinOrder[index]).getReferencedTableMap());
1171            }
1172
1173            if (optimizerTrace)
1174            {
1175                trace(CONSIDERING_JOIN_ORDER, 0, 0, 0.0, null);
1176            }
1177
1178            Optimizable nextOpt =
1179                            optimizableList.getOptimizable(nextOptimizable);
1180
1181            nextOpt.startOptimizing(this, currentRowOrdering);
1182
1183            pushPredicates(
1184                optimizableList.getOptimizable(nextOptimizable),
1185                assignedTableMap);
1186
1187            return true;
1188        }
1189
1190        endOfRoundCleanup();
1191        return false;
1192    }
1193
1194    private void rewindJoinOrder()
1195        throws StandardException
1196    {
1197        for (; ; joinPosition--)
1198        {
1199            Optimizable pullMe =
1200                optimizableList.getOptimizable(
1201                                    proposedJoinOrder[joinPosition]);
1202            pullMe.pullOptPredicates(predicateList);
1203            if (reloadBestPlan)
1204                pullMe.updateBestPlanMap(FromTable.LOAD_PLAN, this);
1205            proposedJoinOrder[joinPosition] = -1;
1206            if (joinPosition == 0) break;
1207        }
1208        currentCost.setCost(0.0d, 0.0d, 0.0d);
1209        currentSortAvoidanceCost.setCost(0.0d, 0.0d, 0.0d);
1210        assignedTableMap.clearAll();
1211    }
1212
1213    /**
1214     * Do any work that needs to be done after the current round
1215     * of optimization has completed.  For now this just means walking
1216     * the subtrees for each optimizable and removing the "bestPlan"
1217     * that we saved (w.r.t to this OptimizerImpl) from all of the
1218     * nodes.  If we don't do this post-optimization cleanup we
1219     * can end up consuming a huge amount of memory for deeply-
1220     * nested queries, which can lead to OOM errors.  DERBY-1315.
1221     */
1222    private void endOfRoundCleanup()
1223        throws StandardException
1224    {
1225        for (int i = 0; i < numOptimizables; i++)
1226        {
1227            optimizableList.getOptimizable(i).
1228                updateBestPlanMap(FromTable.REMOVE_PLAN, this);
1229        }
1230    }
1231
1232    /*
1233    ** Push predicates from this optimizer's list to the given optimizable,
1234    ** as appropriate given the outer tables.
1235    **
1236    ** @param curTable  The Optimizable to push predicates down to
1237    ** @param outerTables   A bit map of outer tables
1238    **
1239    ** @exception StandardException     Thrown on error
1240    */
1241    void pushPredicates(Optimizable curTable, JBitSet outerTables)
1242            throws StandardException
1243    {
1244        /*
1245        ** Push optimizable clauses to current position in join order.
1246        **
1247        ** RESOLVE - We do not push predicates with subqueries not materializable.
1248        */
1249
1250        int                     numPreds        = predicateList.size();
1251        JBitSet                 predMap         = new JBitSet(numTablesInQuery);
1252        JBitSet                 curTableNums    = null;
1253        BaseTableNumbersVisitor btnVis          = null;
1254        boolean                 pushPredNow     = false;
1255        int                     tNum;
1256        Predicate               pred;
1257
1258        /* Walk the OptimizablePredicateList.  For each OptimizablePredicate,
1259         * see if it can be assigned to the Optimizable at the current join
1260         * position.
1261         *
1262         * NOTE - We walk the OPL backwards since we will hopefully be deleted
1263         * entries as we walk it.
1264         */
1265        for (int predCtr = numPreds - 1; predCtr >= 0; predCtr--)
1266        {
1267            pred = (Predicate)predicateList.getOptPredicate(predCtr);
1268
1269            /* Skip over non-pushable predicates */
1270            if (! isPushable(pred))
1271            {
1272                continue;
1273            }
1274                
1275            /* Make copy of referenced map so that we can do destructive
1276             * manipulation on the copy.
1277             */
1278            predMap.setTo(pred.getReferencedMap());
1279
1280            /* Clear bits representing those tables that have already been
1281             * assigned, except for the current table.  The outer table map
1282             * includes the current table, so if the predicate is ready to
1283             * be pushed, predMap will end up with no bits set.
1284             */
1285            for (int index = 0; index < predMap.size(); index++)
1286            {
1287                if (outerTables.get(index))
1288                {
1289                    predMap.clear(index);
1290                }
1291            }
1292
1293            /*
1294            ** Only consider non-correlated variables when deciding where
1295            ** to push predicates down to.
1296            */
1297            predMap.and(nonCorrelatedTableMap);
1298
1299            /* At this point what we've done is figure out what FromTables
1300             * the predicate references (using the predicate's "referenced
1301             * map") and then: 1) unset the table numbers for any FromTables
1302             * that have already been optimized, 2) unset the table number
1303             * for curTable, which we are about to optimize, and 3) cleared
1304             * out any remaining table numbers which do NOT directly
1305             * correspond to UN-optimized FromTables in this OptimizerImpl's
1306             * optimizableList.
1307             *
1308             * Note: the optimizables in this OptImpl's optimizableList are
1309             * called "non-correlated".
1310             *
1311             * So at this point predMap holds a list of tableNumbers which
1312             * correspond to "non-correlated" FromTables that are referenced
1313             * by the predicate but that have NOT yet been optimized.  If any
1314             * such FromTable exists then we canNOT push the predicate yet.  
1315             * We can only push the predicate if every FromTable that it
1316             * references either 1) has already been optimized, or 2) is
1317             * about to be optimized (i.e. the FromTable is curTable itself).
1318             * We can check for this condition by seeing if predMap is empty,
1319             * which is what the following line does.
1320             */
1321            pushPredNow = (predMap.getFirstSetBit() == -1);
1322
1323            /* If the predicate is scoped, there's more work to do. A
1324             * scoped predicate's "referenced map" may not be in sync
1325             * with its actual column references.  Or put another way,
1326             * the predicate's referenced map may not actually represent
1327             * the tables that are referenced by the predicate.  For
1328             * example, assume the query tree is something like:
1329             *
1330             *      SelectNode0
1331             *     (PRN0, PRN1)
1332             *       |     |
1333             *       T1 UnionNode
1334             *           /   |
1335             *         PRN2  PRN3
1336             *          |     |
1337             *  SelectNode1   SelectNode2
1338             *   (PRN4, PRN5)    (PRN6)
1339             *     |     |         |
1340             *     T2    T3        T4
1341             *
1342             * Assume further that we have an equijoin predicate between
1343             * T1 and the Union node, and that the column reference that
1344             * points to the Union ultimately maps to T3.  The predicate
1345             * will then be scoped to PRN2 and PRN3 and the newly-scoped
1346             * predicates will get passed to the optimizers for SelectNode1
1347             * and SelectNode2--which brings us here.  Assume for this
1348             * example that we're here for SelectNode1 and that "curTable"
1349             * is PRN4.  Since the predicate has been scoped to SelectNode1,
1350             * its referenced map will hold the table numbers for T1 and
1351             * PRN2--it will NOT hold the table number for PRN5, even
1352             * though PRN5 (T3) is the actual target for the predicate.
1353             * Given that, the above logic will determine that the predicate
1354             * should be pushed to curTable (PRN4)--but that's not correct.
1355             * We said at the start that the predicate ultimately maps to
1356             * T3--so we should NOT be pushing it to T2.  And hence the
1357             * need for some additional logic.  DERBY-1866.
1358             */
1359            if (pushPredNow && pred.isScopedForPush() && (numOptimizables > 1))
1360            {
1361                if (btnVis == null)
1362                {
1363                    curTableNums = new JBitSet(numTablesInQuery);
1364                    btnVis       = new BaseTableNumbersVisitor(curTableNums);
1365                }
1366
1367                /* What we want to do is find out if the scoped predicate
1368                 * is really supposed to be pushed to curTable.  We do
1369                 * that by getting the base table numbers referenced by
1370                 * curTable along with curTable's own table number.  Then
1371                 * we get the base table numbers referenced by the scoped
1372                 * predicate. If the two sets have at least one table
1373                 * number in common, then we know that the predicate
1374                 * should be pushed to curTable.  In the above example
1375                 * predMap will end up holding the base table number
1376                 * for T3, and thus this check will fail when curTable
1377                 * is PRN4 but will pass when it is PRN5, which is what
1378                 * we want.
1379                 */
1380                tNum = ((FromTable)curTable).getTableNumber();
1381                curTableNums.clearAll();
1382                btnVis.setTableMap(curTableNums);
1383                ((FromTable)curTable).accept(btnVis);
1384                if (tNum >= 0)
1385                    curTableNums.set(tNum);
1386
1387                btnVis.setTableMap(predMap);
1388                pred.accept(btnVis);
1389
1390                predMap.and(curTableNums);
1391                if ((predMap.getFirstSetBit() == -1))
1392                    pushPredNow = false;
1393            }
1394
1395            /*
1396            ** Finally, push the predicate down to the Optimizable at the
1397            ** end of the current proposed join order, if it can be evaluated
1398            ** there.
1399            */
1400            if (pushPredNow)
1401            {
1402                /* Push the predicate and remove it from the list */
1403                if (curTable.pushOptPredicate(pred))
1404                {
1405                    predicateList.removeOptPredicate(predCtr);
1406                }
1407            }
1408        }
1409    }
1410
1411    /**
1412     * @see Optimizer#getNextDecoratedPermutation
1413     *
1414     * @exception StandardException     Thrown on error
1415     */
1416    public boolean getNextDecoratedPermutation()
1417                throws StandardException
1418    {
1419        boolean     retval;
1420        Optimizable curOpt =
1421            optimizableList.getOptimizable(proposedJoinOrder[joinPosition]);
1422        double      originalRowCount = 0.0;
1423        
1424        // RESOLVE: Should we step through the different join strategies here?
1425
1426        /* Returns true until all access paths are exhausted */
1427        retval =  curOpt.nextAccessPath(this,
1428                                        (OptimizablePredicateList) null,
1429                                        currentRowOrdering);
1430
1431        // If the previous path that we considered for curOpt was _not_ the best
1432        // path for this round, then we need to revert back to whatever the
1433        // best plan for curOpt was this round.  Note that the cost estimate
1434        // for bestAccessPath could be null here if the last path that we
1435        // checked was the only one possible for this round.
1436        if ((curOpt.getBestAccessPath().getCostEstimate() != null) &&
1437            (curOpt.getCurrentAccessPath().getCostEstimate() != null))
1438        {
1439            // Note: we can't just check to see if bestCost is cheaper
1440            // than currentCost because it's possible that currentCost
1441            // is actually cheaper--but it may have been 'rejected' because
1442            // it would have required too much memory.  So we just check
1443            // to see if bestCost and currentCost are different.  If so
1444            // then we know that the most recent access path (represented
1445            // by "current" access path) was not the best.
1446            if (curOpt.getBestAccessPath().getCostEstimate().compare(
1447                curOpt.getCurrentAccessPath().getCostEstimate()) != 0)
1448            {
1449                curOpt.updateBestPlanMap(FromTable.LOAD_PLAN, curOpt);
1450            }
1451            else if (curOpt.getBestAccessPath().getCostEstimate().rowCount() <
1452                curOpt.getCurrentAccessPath().getCostEstimate().rowCount())
1453            {
1454                // If currentCost and bestCost have the same cost estimate
1455                // but currentCost has been rejected because of memory, we
1456                // still need to revert the plans.  In this case the row
1457                // count for currentCost will be greater than the row count
1458                // for bestCost, so that's what we just checked.
1459                curOpt.updateBestPlanMap(FromTable.LOAD_PLAN, curOpt);
1460            }
1461        }
1462
1463        /* If we needed to revert plans for curOpt, we just did it above.
1464         * So we no longer need to keep the previous best plan--and in fact,
1465         * keeping it can lead to extreme memory usage for very large
1466         * queries.  So delete the stored plan for curOpt. DERBY-1315.
1467         */
1468        curOpt.updateBestPlanMap(FromTable.REMOVE_PLAN, curOpt);
1469
1470        /*
1471        ** When all the access paths have been looked at, we know what the
1472        ** cheapest one is, so remember it.  Only do this if a cost estimate
1473        ** has been set for the best access path - one will not have been
1474        ** set if no feasible plan has been found.
1475        */
1476        CostEstimate ce = curOpt.getBestAccessPath().getCostEstimate();
1477        if ( ( ! retval ) && (ce != null))
1478        {
1479            /*
1480            ** Add the cost of the current optimizable to the total cost.
1481            ** The total cost is the sum of all the costs, but the total
1482            ** number of rows is the number of rows returned by the innermost
1483            ** optimizable.
1484            */
1485            currentCost.setCost(
1486                currentCost.getEstimatedCost() + ce.getEstimatedCost(),
1487                ce.rowCount(),
1488                ce.singleScanRowCount());
1489
1490            if (curOpt.considerSortAvoidancePath() &&
1491                requiredRowOrdering != null)
1492            {
1493                /* Add the cost for the sort avoidance path, if there is one */
1494                ce = curOpt.getBestSortAvoidancePath().getCostEstimate();
1495
1496                currentSortAvoidanceCost.setCost(
1497                    currentSortAvoidanceCost.getEstimatedCost() +
1498                        ce.getEstimatedCost(),
1499                    ce.rowCount(),
1500                    ce.singleScanRowCount());
1501            }
1502
1503            if (optimizerTrace)
1504            {
1505                trace(TOTAL_COST_NON_SA_PLAN, 0, 0, 0.0, null);
1506                if (curOpt.considerSortAvoidancePath())
1507                {
1508                    trace(TOTAL_COST_SA_PLAN, 0, 0, 0.0, null);
1509                }
1510            }
1511                
1512            /* Do we have a complete join order? */
1513            if ( joinPosition == (numOptimizables - 1) )
1514            {
1515                if (optimizerTrace)
1516                {
1517                    trace(COMPLETE_JOIN_ORDER, 0, 0, 0.0, null);
1518                }
1519
1520                /* Add cost of sorting to non-sort-avoidance cost */
1521                if (requiredRowOrdering != null)
1522                {
1523                    boolean gotSortCost = false;
1524
1525                    /* Only get the sort cost once */
1526                    if (sortCost == null)
1527                    {
1528                        sortCost = newCostEstimate();
1529                    }
1530                    /* requiredRowOrdering records if the bestCost so far is
1531                     * sort-needed or not, as done in rememberBestCost.  If
1532                     * the bestCost so far is sort-needed, and assume
1533                     * currentCost is also sort-needed, we want this comparison
1534                     * to be as accurate as possible.  Different plans may
1535                     * produce different estimated row count (eg., heap scan
1536                     * vs. index scan during a join), sometimes the difference
1537                     * could be very big.  However the actual row count should
1538                     * be only one value.  So when comparing these two plans,
1539                     * we want them to have the same sort cost.  We want to
1540                     * take the smaller row count, because a better estimation
1541                     * (eg. through index) would yield a smaller number.  We
1542                     * adjust the bestCost here if it had a bigger rowCount
1543                     * estimate.  The performance improvement of doing this
1544                     * sometimes is quite dramatic, eg. from 17 sec to 0.5 sec,
1545                     * see beetle 4353.
1546                     */
1547                    else if (requiredRowOrdering.getSortNeeded())
1548                    {
1549                        if (bestCost.rowCount() > currentCost.rowCount())
1550                        {
1551                            // adjust bestCost
1552                            requiredRowOrdering.estimateCost(
1553                                                    bestCost.rowCount(),
1554                                                    bestRowOrdering,
1555                                                    sortCost
1556                                                    );
1557                            double oldSortCost = sortCost.getEstimatedCost();
1558                            requiredRowOrdering.estimateCost(
1559                                                    currentCost.rowCount(),
1560                                                    bestRowOrdering,
1561                                                    sortCost
1562                                                    );
1563                            gotSortCost = true;
1564                            bestCost.setCost(bestCost.getEstimatedCost() -
1565                                            oldSortCost + 
1566                                            sortCost.getEstimatedCost(),
1567                                            sortCost.rowCount(),
1568                                            currentCost.singleScanRowCount());
1569                        }
1570                        else if (bestCost.rowCount() < currentCost.rowCount())
1571                        {
1572                            // adjust currentCost's rowCount
1573                            currentCost.setCost(currentCost.getEstimatedCost(),
1574                                                bestCost.rowCount(),
1575                                                currentCost.singleScanRowCount());
1576                        }
1577                    }
1578
1579                    /* This does not figure out if sorting is necessary, just
1580                     * an asumption that sort is needed; if the assumption is
1581                     * wrong, we'll look at sort-avoidance cost as well, later
1582                     */
1583                    if (! gotSortCost)
1584                    {
1585                        requiredRowOrdering.estimateCost(
1586                                                    currentCost.rowCount(),
1587                                                    bestRowOrdering,
1588                                                    sortCost
1589                                                    );
1590                    }
1591
1592                    originalRowCount = currentCost.rowCount();
1593
1594                    currentCost.setCost(currentCost.getEstimatedCost() +
1595                                        sortCost.getEstimatedCost(),
1596                                        sortCost.rowCount(),
1597                                        currentCost.singleScanRowCount()
1598                                        );
1599                    
1600                    if (optimizerTrace)
1601                    {
1602                        trace(COST_OF_SORTING, 0, 0, 0.0, null);
1603                        trace(TOTAL_COST_WITH_SORTING, 0, 0, 0.0, null);
1604                    }
1605                }
1606
1607                /*
1608                ** Is the cost of this join order lower than the best one we've
1609                ** found so far?
1610                **
1611                ** NOTE: If the user has specified a join order, it will be the
1612                ** only join order the optimizer considers, so it is OK to use
1613                ** costing to decide that it is the "best" join order.
1614                **
1615                ** For very deeply nested queries, it's possible that the optimizer
1616                ** will return an estimated cost of Double.INFINITY, which is
1617                ** greater than our uninitialized cost of Double.MAX_VALUE and
1618                ** thus the "compare" check below will return false.   So we have
1619                ** to check to see if bestCost is uninitialized and, if so, we
1620                ** save currentCost regardless of what value it is--because we
1621                ** haven't found anything better yet.
1622                **
1623                ** That said, it's also possible for bestCost to be infinity
1624                ** AND for current cost to be infinity, as well.  In that case
1625                ** we can't really tell much by comparing the two, so for lack
1626                ** of better alternative we look at the row counts.  See
1627                ** CostEstimateImpl.compare() for more.
1628                */
1629                if ((! foundABestPlan) ||
1630                    (currentCost.compare(bestCost) < 0) ||
1631                    bestCost.isUninitialized())
1632                {
1633                    rememberBestCost(currentCost, Optimizer.NORMAL_PLAN);
1634
1635                    // Since we just remembered all of the best plans,
1636                    // no need to reload them when pulling Optimizables
1637                    // from this join order.
1638                    reloadBestPlan = false;
1639                }
1640                else
1641                    reloadBestPlan = true;
1642
1643                /* Subtract cost of sorting from non-sort-avoidance cost */
1644                if (requiredRowOrdering != null)
1645                {
1646                    /*
1647                    ** The cost could go negative due to loss of precision.
1648                    */
1649                    double newCost = currentCost.getEstimatedCost() -
1650                                        sortCost.getEstimatedCost();
1651                    if (newCost < 0.0)
1652                        newCost = 0.0;
1653                    
1654                    currentCost.setCost(newCost,
1655                                        originalRowCount,
1656                                        currentCost.singleScanRowCount()
1657                                        );
1658                }
1659
1660                /*
1661                ** This may be the best sort-avoidance plan if there is a
1662                ** required row ordering, and we are to consider a sort
1663                ** avoidance path on the last Optimizable in the join order.
1664                */
1665                if (requiredRowOrdering != null &&
1666                    curOpt.considerSortAvoidancePath())
1667                {
1668                    if (requiredRowOrdering.sortRequired(bestRowOrdering) ==
1669                                    RequiredRowOrdering.NOTHING_REQUIRED)
1670                    {
1671                        if (optimizerTrace)
1672                        {
1673                            trace(CURRENT_PLAN_IS_SA_PLAN, 0, 0, 0.0, null);
1674                        }
1675
1676                        if ((currentSortAvoidanceCost.compare(bestCost) <= 0)
1677                            || bestCost.isUninitialized())
1678                        {
1679                            rememberBestCost(currentSortAvoidanceCost,
1680                                            Optimizer.SORT_AVOIDANCE_PLAN);
1681                        }
1682                    }
1683                }
1684            }
1685        }
1686
1687        return retval;
1688    }
1689
1690    /**
1691     * Is the cost of this join order lower than the best one we've
1692     * found so far?  If so, remember it.
1693     *
1694     * NOTE: If the user has specified a join order, it will be the
1695     * only join order the optimizer considers, so it is OK to use
1696     * costing to decide that it is the "best" join order.
1697     *  @exception StandardException    Thrown on error
1698     */
1699    private void rememberBestCost(CostEstimate currentCost, int planType)
1700        throws StandardException
1701    {
1702        foundABestPlan = true;
1703
1704        if (optimizerTrace)
1705        {
1706            trace(CHEAPEST_PLAN_SO_FAR, 0, 0, 0.0, null);
1707            trace(PLAN_TYPE, planType, 0, 0.0, null);
1708            trace(COST_OF_CHEAPEST_PLAN_SO_FAR, 0, 0, 0.0, null);
1709        }
1710
1711        /* Remember the current cost as best */
1712        bestCost.setCost(currentCost);
1713
1714        // Our time limit for optimizing this round is the time we think
1715        // it will take us to execute the best join order that we've 
1716        // found so far (across all rounds of optimizing).  In other words,
1717        // don't spend more time optimizing this OptimizerImpl than we think
1718        // it's going to take to execute the best plan.  So if we've just
1719        // found a new "best" join order, use that to update our time limit.
1720        if (bestCost.getEstimatedCost() < timeLimit)
1721            timeLimit = bestCost.getEstimatedCost();
1722
1723        /*
1724        ** Remember the current join order and access path
1725        ** selections as best.
1726        ** NOTE: We want the optimizer trace to print out in
1727        ** join order instead of in table number order, so
1728        ** we use 2 loops.
1729        */
1730        bestJoinOrderUsedPredsFromAbove = usingPredsPushedFromAbove;
1731        for (int i = 0; i < numOptimizables; i++)
1732        {
1733            bestJoinOrder[i] = proposedJoinOrder[i];
1734        }
1735        for (int i = 0; i < numOptimizables; i++)
1736        {
1737            optimizableList.getOptimizable(bestJoinOrder[i]).
1738                rememberAsBest(planType, this);
1739        }
1740
1741        /* Remember if a sort is not needed for this plan */
1742        if (requiredRowOrdering != null)
1743        {
1744            if (planType == Optimizer.SORT_AVOIDANCE_PLAN)
1745                requiredRowOrdering.sortNotNeeded();
1746            else
1747                requiredRowOrdering.sortNeeded();
1748        }
1749
1750        if (optimizerTrace)
1751        {
1752            if (requiredRowOrdering != null)
1753            {
1754                trace(SORT_NEEDED_FOR_ORDERING, planType, 0, 0.0, null);
1755            }
1756            trace(REMEMBERING_BEST_JOIN_ORDER, 0, 0, 0.0, null);
1757        }
1758    }
1759
1760    /**
1761     * @see org.apache.derby.iapi.sql.compile.Optimizer#costPermutation
1762     *
1763     * @exception StandardException     Thrown on error
1764     */
1765    public void costPermutation() throws StandardException
1766    {
1767        /*
1768        ** Get the cost of the outer plan so far.  This gives us the current
1769        ** estimated rows, ordering, etc.
1770        */
1771        CostEstimate outerCost;
1772        if (joinPosition == 0)
1773        {
1774            outerCost = outermostCostEstimate;
1775        }
1776        else
1777        {
1778            /*
1779            ** NOTE: This is somewhat problematic.  We assume here that the
1780            ** outer cost from the best access path for the outer table
1781            ** is OK to use even when costing the sort avoidance path for
1782            ** the inner table.  This is probably OK, since all we use
1783            ** from the outer cost is the row count.
1784            */
1785            outerCost =
1786                optimizableList.getOptimizable(
1787                    proposedJoinOrder[joinPosition - 1]).
1788                        getBestAccessPath().getCostEstimate();
1789        }
1790
1791        /* At this point outerCost should be non-null (DERBY-1777).
1792         * Do the assertion here so that we catch it right away;
1793         * otherwise we'd end up with an NPE somewhere further
1794         * down the tree and it'd be harder to figure out where
1795         * it came from.
1796         */
1797        if (SanityManager.DEBUG)
1798        {
1799            SanityManager.ASSERT(outerCost != null,
1800                "outerCost is not expected to be null");
1801        }
1802
1803        Optimizable optimizable = optimizableList.getOptimizable(proposedJoinOrder[joinPosition]);
1804
1805        /*
1806        ** Don't consider non-feasible join strategies.
1807        */
1808        if ( ! optimizable.feasibleJoinStrategy(predicateList, this))
1809        {
1810            return;
1811        }
1812
1813        /* Cost the optimizable at the current join position */
1814        optimizable.optimizeIt(this,
1815                               predicateList,
1816                               outerCost,
1817                               currentRowOrdering);
1818    }
1819
1820    /**
1821     * @see org.apache.derby.iapi.sql.compile.Optimizer#costOptimizable
1822     *
1823     * @exception StandardException     Thrown on error
1824     */
1825    public void costOptimizable(Optimizable optimizable,
1826                                TableDescriptor td, 
1827                                ConglomerateDescriptor cd,
1828                                OptimizablePredicateList predList,
1829                                CostEstimate outerCost)
1830            throws StandardException
1831    {
1832        /*
1833        ** Don't consider non-feasible join strategies.
1834        */
1835        if ( ! optimizable.feasibleJoinStrategy(predList, this))
1836        {
1837            return;
1838        }
1839
1840        /*
1841        ** Classify the predicates according to the given conglomerate.
1842        ** The predicates are classified as start keys, stop keys,
1843        ** qualifiers, and none-of-the-above.  They are also ordered
1844        ** to match the ordering of columns in keyed conglomerates (no
1845        ** ordering is done for heaps).
1846        */
1847        // if (predList != null)
1848        //  predList.classify(optimizable, cd);
1849
1850        if (ruleBasedOptimization)
1851        {
1852            ruleBasedCostOptimizable(optimizable,
1853                                        td,
1854                                        cd,
1855                                        predList,
1856                                        outerCost);
1857        }
1858        else
1859        {
1860            costBasedCostOptimizable(optimizable,
1861                                        td,
1862                                        cd,
1863                                        predList,
1864                                        outerCost);
1865        }
1866    }
1867
1868    /**
1869     * This method decides whether the given conglomerate descriptor is
1870     * cheapest based on rules, rather than based on cost estimates.
1871     * The rules are:
1872     *
1873     *      Covering matching indexes are preferred above all
1874     *      Non-covering matching indexes are next in order of preference
1875     *      Covering non-matching indexes are next in order of preference
1876     *      Heap scans are next in order of preference
1877     *      Non-covering, non-matching indexes are last in order of
1878     *      preference.
1879     *
1880     * In the current language architecture, there will always be a
1881     * heap, so a non-covering, non-matching index scan will never be
1882     * chosen.  However, the optimizer may see a non-covering, non-matching
1883     * index first, in which case it will choose it temporarily as the
1884     * best conglomerate seen so far.
1885     *
1886     * NOTE: This method sets the cost in the optimizable, even though it
1887     * doesn't use the cost to determine which access path to choose.  There
1888     * are two reasons for this: the cost might be needed to determine join
1889     * order, and the cost information is copied to the query plan.
1890     */
1891    private void ruleBasedCostOptimizable(Optimizable optimizable,
1892                                            TableDescriptor td,
1893                                            ConglomerateDescriptor cd,
1894                                            OptimizablePredicateList predList,
1895                                            CostEstimate outerCost)
1896                throws StandardException
1897    {
1898        /* CHOOSE BEST CONGLOMERATE HERE */
1899        ConglomerateDescriptor  conglomerateDescriptor = null;
1900        ConglomerateDescriptor  bestConglomerateDescriptor = null;
1901        AccessPath bestAp = optimizable.getBestAccessPath();
1902        int lockMode = optimizable.getCurrentAccessPath().getLockMode();
1903
1904
1905        /*
1906        ** If the current conglomerate better than the best so far?
1907        ** The pecking order is:
1908        **      o  covering index useful for predicates
1909        **          (if there are predicates)
1910        **      o  index useful for predicates (if there are predicates)
1911        **      o  covering index
1912        **      o  table scan
1913        */
1914
1915        /*
1916        ** If there is more than one conglomerate descriptor
1917        ** choose any index that is potentially useful.
1918        */
1919        if (predList != null &&
1920            predList.useful(optimizable, cd))
1921        {
1922            /*
1923            ** Do not let a non-covering matching index scan supplant a
1924            ** covering matching index scan.
1925            */
1926            boolean newCoveringIndex = optimizable.isCoveringIndex(cd);
1927            if ( ( ! bestAp.getCoveringIndexScan()) ||
1928                bestAp.getNonMatchingIndexScan() ||
1929                newCoveringIndex )
1930            {
1931                bestAp.setCostEstimate(
1932                    estimateTotalCost(
1933                                    predList,
1934                                    cd,
1935                                    outerCost,
1936                                    optimizable
1937                                    )
1938                                );
1939                bestAp.setConglomerateDescriptor(cd);
1940                bestAp.setNonMatchingIndexScan(false);
1941                bestAp.setCoveringIndexScan(newCoveringIndex);
1942
1943                bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode());
1944
1945                optimizable.rememberJoinStrategyAsBest(bestAp);
1946            }
1947
1948            return;
1949        }
1950
1951        /* Remember the "last" covering index.
1952         * NOTE - Since we don't have costing, we just go for the
1953         * last one since that's as good as any
1954         */
1955        if (optimizable.isCoveringIndex(cd))
1956        {
1957            bestAp.setCostEstimate(
1958                                estimateTotalCost(predList,
1959                                                    cd,
1960                                                    outerCost,
1961                                                    optimizable)
1962                                );
1963            bestAp.setConglomerateDescriptor(cd);
1964            bestAp.setNonMatchingIndexScan(true);
1965            bestAp.setCoveringIndexScan(true);
1966
1967            bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode());
1968
1969            optimizable.rememberJoinStrategyAsBest(bestAp);
1970            return;
1971        }
1972
1973        /*
1974        ** If this is the heap, and the best conglomerate so far is a
1975        ** non-covering, non-matching index scan, pick the heap.
1976        */
1977        if ( ( ! bestAp.getCoveringIndexScan()) &&
1978             bestAp.getNonMatchingIndexScan() &&
1979             ( ! cd.isIndex() )
1980           )
1981        {
1982            bestAp.setCostEstimate(
1983                                    estimateTotalCost(predList,
1984                                                        cd,
1985                                                        outerCost,
1986                                                        optimizable)
1987                                    );
1988
1989            bestAp.setConglomerateDescriptor(cd);
1990
1991            bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode());
1992
1993            optimizable.rememberJoinStrategyAsBest(bestAp);
1994
1995            /*
1996            ** No need to set non-matching index scan and covering
1997            ** index scan, as these are already correct.
1998            */
1999            return;
2000        }
2001
2002
2003        /*
2004        ** If all else fails, and no conglomerate has been picked yet,
2005        ** pick this one.
2006        */
2007        bestConglomerateDescriptor = bestAp.getConglomerateDescriptor();
2008        if (bestConglomerateDescriptor == null)
2009        {
2010            bestAp.setCostEstimate(
2011                                    estimateTotalCost(predList,
2012                                                        cd,
2013                                                        outerCost,
2014                                                        optimizable)
2015                                    );
2016
2017            bestAp.setConglomerateDescriptor(cd);
2018
2019            /*
2020            ** We have determined above that this index is neither covering
2021            ** nor matching.
2022            */
2023            bestAp.setCoveringIndexScan(false);
2024            bestAp.setNonMatchingIndexScan(cd.isIndex());
2025
2026            bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode());
2027
2028            optimizable.rememberJoinStrategyAsBest(bestAp);
2029        }
2030
2031        return;
2032    }
2033
2034    /**
2035     * This method decides whether the given conglomerate descriptor is
2036     * cheapest based on cost, rather than based on rules.  It compares
2037     * the cost of using the given ConglomerateDescriptor with the cost
2038     * of using the best ConglomerateDescriptor so far.
2039     */
2040    private void costBasedCostOptimizable(Optimizable optimizable,
2041                                            TableDescriptor td,
2042                                            ConglomerateDescriptor cd,
2043                                            OptimizablePredicateList predList,
2044                                            CostEstimate outerCost)
2045                throws StandardException
2046    {
2047        CostEstimate estimatedCost = estimateTotalCost(predList,
2048                                                        cd,
2049                                                        outerCost,
2050                                                        optimizable);
2051
2052        // Before considering the cost, make sure we set the optimizable's
2053        // "current" cost to be the one that we found.  Doing this allows
2054        // us to compare "current" with "best" later on to find out if
2055        // the "current" plan is also the "best" one this round--if it's
2056        // not then we'll have to revert back to whatever the best plan is.
2057        // That check is performed in getNextDecoratedPermutation() of
2058        // this class.
2059        optimizable.getCurrentAccessPath().setCostEstimate(estimatedCost);
2060
2061        /*
2062        ** Skip this access path if it takes too much memory.
2063        **
2064        ** NOTE: The default assumption here is that the number of rows in
2065        ** a single scan is the total number of rows divided by the number
2066        ** of outer rows.  The optimizable may over-ride this assumption.
2067        */
2068        // RESOLVE: The following call to memoryUsageOK does not behave
2069        // correctly if outerCost.rowCount() is POSITIVE_INFINITY; see
2070        // DERBY-1259.
2071        if( ! optimizable.memoryUsageOK( estimatedCost.rowCount() / outerCost.rowCount(), maxMemoryPerTable))
2072        {
2073            if (optimizerTrace)
2074            {
2075                trace(SKIPPING_DUE_TO_EXCESS_MEMORY, 0, 0, 0.0, null);
2076            }
2077            return;
2078        }
2079
2080        /* Pick the cheapest cost for this particular optimizable. */
2081        AccessPath ap = optimizable.getBestAccessPath();
2082        CostEstimate bestCostEstimate = ap.getCostEstimate();
2083
2084        if ((bestCostEstimate == null) ||
2085            bestCostEstimate.isUninitialized() ||
2086            (estimatedCost.compare(bestCostEstimate) < 0))
2087        {
2088            ap.setConglomerateDescriptor(cd);
2089            ap.setCostEstimate(estimatedCost);
2090            ap.setCoveringIndexScan(optimizable.isCoveringIndex(cd));
2091
2092            /*
2093            ** It's a non-matching index scan either if there is no
2094            ** predicate list, or nothing in the predicate list is useful
2095            ** for limiting the scan.
2096            */
2097            ap.setNonMatchingIndexScan(
2098                                    (predList == null) ||
2099                                    ( ! ( predList.useful(optimizable, cd) ) )
2100                                    );
2101            ap.setLockMode(optimizable.getCurrentAccessPath().getLockMode());
2102            optimizable.rememberJoinStrategyAsBest(ap);
2103        }
2104
2105        /*
2106        ** Keep track of the best sort-avoidance path if there is a
2107        ** required row ordering.
2108        */
2109        if (requiredRowOrdering != null)
2110        {
2111            /*
2112            ** The current optimizable can avoid a sort only if the
2113            ** outer one does, also (if there is an outer one).
2114            */
2115            if (joinPosition == 0 ||
2116                optimizableList.getOptimizable(
2117                                        proposedJoinOrder[joinPosition - 1]).
2118                                                considerSortAvoidancePath())
2119            {
2120                /*
2121                ** There is a required row ordering - does the proposed access
2122                ** path avoid a sort?
2123                */
2124                if (requiredRowOrdering.sortRequired(currentRowOrdering,
2125                                                        assignedTableMap)
2126                                        == RequiredRowOrdering.NOTHING_REQUIRED)
2127                {
2128                    ap = optimizable.getBestSortAvoidancePath();
2129                    bestCostEstimate = ap.getCostEstimate();
2130
2131                    /* Is this the cheapest sort-avoidance path? */
2132                    if ((bestCostEstimate == null) ||
2133                        bestCostEstimate.isUninitialized() ||
2134                        (estimatedCost.compare(bestCostEstimate) < 0))
2135                    {
2136                        ap.setConglomerateDescriptor(cd);
2137                        ap.setCostEstimate(estimatedCost);
2138                        ap.setCoveringIndexScan(
2139                                            optimizable.isCoveringIndex(cd));
2140
2141                        /*
2142                        ** It's a non-matching index scan either if there is no
2143                        ** predicate list, or nothing in the predicate list is
2144                        ** useful for limiting the scan.
2145                        */
2146                        ap.setNonMatchingIndexScan(
2147                                        (predList == null) ||
2148                                        ( ! (predList.useful(optimizable, cd)) )
2149                                        );
2150                        ap.setLockMode(
2151                            optimizable.getCurrentAccessPath().getLockMode());
2152                        optimizable.rememberJoinStrategyAsBest(ap);
2153                        optimizable.rememberSortAvoidancePath();
2154
2155                        /*
2156                        ** Remember the current row ordering as best
2157                        */
2158                        currentRowOrdering.copy(bestRowOrdering);
2159                    }
2160                }
2161            }
2162        }
2163    }
2164
2165    /**
2166     * This is the version of costOptimizable for non-base-tables.
2167     *
2168     * @see Optimizer#considerCost
2169     *
2170     * @exception StandardException     Thrown on error
2171     */
2172    public void considerCost(Optimizable optimizable,
2173                                OptimizablePredicateList predList,
2174                                CostEstimate estimatedCost,
2175                                CostEstimate outerCost)
2176            throws StandardException
2177    {
2178        /*
2179        ** Don't consider non-feasible join strategies.
2180        */
2181        if ( ! optimizable.feasibleJoinStrategy(predList, this))
2182        {
2183            return;
2184        }
2185
2186        // Before considering the cost, make sure we set the optimizable's
2187        // "current" cost to be the one that we received.  Doing this allows
2188        // us to compare "current" with "best" later on to find out if
2189        // the "current" plan is also the "best" one this round--if it's
2190        // not then we'll have to revert back to whatever the best plan is.
2191        // That check is performed in getNextDecoratedPermutation() of
2192        // this class.
2193        optimizable.getCurrentAccessPath().setCostEstimate(estimatedCost);
2194
2195        /*
2196        ** Skip this access path if it takes too much memory.
2197        **
2198        ** NOTE: The default assumption here is that the number of rows in
2199        ** a single scan is the total number of rows divided by the number
2200        ** of outer rows.  The optimizable may over-ride this assumption.
2201        */
2202
2203        // RESOLVE: The following call to memoryUsageOK does not behave
2204        // correctly if outerCost.rowCount() is POSITIVE_INFINITY; see
2205        // DERBY-1259.
2206        if( ! optimizable.memoryUsageOK( estimatedCost.rowCount() / outerCost.rowCount(),
2207                                         maxMemoryPerTable))
2208        {
2209            if (optimizerTrace)
2210            {
2211                trace(SKIPPING_DUE_TO_EXCESS_MEMORY, 0, 0, 0.0, null);
2212            }
2213            return;
2214        }
2215
2216        /* Pick the cheapest cost for this particular optimizable. 
2217         * NOTE: Originally, the code only chose the new access path if 
2218         * it was cheaper than the old access path.  However, I (Jerry)
2219         * found that the new and old costs were the same for a derived
2220         * table and the old access path did not have a join strategy
2221         * associated with it in that case.  So, we now choose the new
2222         * access path if it is the same cost or cheaper than the current
2223         * access path.
2224         */
2225        AccessPath ap = optimizable.getBestAccessPath();
2226        CostEstimate bestCostEstimate = ap.getCostEstimate();
2227
2228        if ((bestCostEstimate == null) ||
2229            bestCostEstimate.isUninitialized() ||
2230            (estimatedCost.compare(bestCostEstimate) <= 0))
2231        {
2232            ap.setCostEstimate(estimatedCost);
2233            optimizable.rememberJoinStrategyAsBest(ap);
2234        }
2235
2236        /*
2237        ** Keep track of the best sort-avoidance path if there is a
2238        ** required row ordering.
2239        */
2240        if (requiredRowOrdering != null)
2241        {
2242            /*
2243            ** The current optimizable can avoid a sort only if the
2244            ** outer one does, also (if there is an outer one).
2245            */
2246            if (joinPosition == 0 ||
2247                optimizableList.getOptimizable(
2248                                        proposedJoinOrder[joinPosition - 1]).
2249                                                considerSortAvoidancePath())
2250            {
2251                /*
2252                ** There is a required row ordering - does the proposed access
2253                ** path avoid a sort?
2254                */
2255                if (requiredRowOrdering.sortRequired(currentRowOrdering,
2256                                                        assignedTableMap)
2257                                        == RequiredRowOrdering.NOTHING_REQUIRED)
2258                {
2259                    ap = optimizable.getBestSortAvoidancePath();
2260                    bestCostEstimate = ap.getCostEstimate();
2261
2262                    /* Is this the cheapest sort-avoidance path? */
2263                    if ((bestCostEstimate == null) ||
2264                        bestCostEstimate.isUninitialized() ||
2265                        (estimatedCost.compare(bestCostEstimate) < 0))
2266                    {
2267                        ap.setCostEstimate(estimatedCost);
2268                        optimizable.rememberJoinStrategyAsBest(ap);
2269                        optimizable.rememberSortAvoidancePath();
2270
2271                        /*
2272                        ** Remember the current row ordering as best
2273                        */
2274                        currentRowOrdering.copy(bestRowOrdering);
2275                    }
2276                }
2277            }
2278        }
2279    }
2280
2281    /**
2282     * @see org.apache.derby.iapi.sql.compile.Optimizer#getDataDictionary
2283     */
2284
2285    public DataDictionary getDataDictionary()
2286    {
2287        return dDictionary;
2288    }
2289
2290    /**
2291     * @see Optimizer#modifyAccessPaths
2292     *
2293     * @exception StandardException     Thrown on error
2294     */
2295    public void modifyAccessPaths() throws StandardException
2296    {
2297        if (optimizerTrace)
2298        {
2299            trace(MODIFYING_ACCESS_PATHS, 0, 0, 0.0, null);
2300        }
2301
2302        if ( ! foundABestPlan)
2303        {
2304            if (optimizerTrace)
2305            {
2306                trace(NO_BEST_PLAN, 0, 0, 0.0, null);
2307            }
2308
2309            throw StandardException.newException(SQLState.LANG_NO_BEST_PLAN_FOUND);
2310        }
2311
2312        /* Change the join order of the list of optimizables */
2313        optimizableList.reOrder(bestJoinOrder);
2314
2315        /* Form a bit map of the tables as they are put into the join order */
2316        JBitSet outerTables = new JBitSet(numOptimizables);
2317
2318        /* Modify the access path of each table, as necessary */
2319        for (int ictr = 0; ictr < numOptimizables; ictr++)
2320        {
2321            Optimizable optimizable = optimizableList.getOptimizable(ictr);
2322
2323            /* Current table is treated as an outer table */
2324            outerTables.or(optimizable.getReferencedTableMap());
2325
2326            /*
2327            ** Push any appropriate predicates from this optimizer's list
2328            ** to the optimizable, as appropriate.
2329            */
2330            pushPredicates(optimizable, outerTables);
2331
2332            optimizableList.setOptimizable(
2333                ictr,
2334                optimizable.modifyAccessPath(outerTables));
2335        }
2336    }
2337
2338    /** @see Optimizer#newCostEstimate */
2339    public CostEstimate newCostEstimate()
2340    {
2341        return new CostEstimateImpl();
2342    }
2343
2344    /** @see Optimizer#getOptimizedCost */
2345    public CostEstimate getOptimizedCost()
2346    {
2347        return bestCost;
2348    }
2349
2350    /**
2351     * @see Optimizer#getFinalCost
2352     *
2353     * Sum up the cost of all of the trulyTheBestAccessPaths
2354     * for the Optimizables in our list.  Assumption is that
2355     * we only get here after optimization has completed--i.e.
2356     * while modifying access paths.
2357     */
2358    public CostEstimate getFinalCost()
2359    {
2360        // If we already did this once, just return the result.
2361        if (finalCostEstimate != null)
2362            return finalCostEstimate;
2363
2364        // The total cost is the sum of all the costs, but the total
2365        // number of rows is the number of rows returned by the innermost
2366        // optimizable.
2367        finalCostEstimate = getNewCostEstimate(0.0d, 0.0d, 0.0d);
2368        CostEstimate ce = null;
2369        for (int i = 0; i < bestJoinOrder.length; i++)
2370        {
2371            ce = optimizableList.getOptimizable(bestJoinOrder[i])
2372                    .getTrulyTheBestAccessPath().getCostEstimate();
2373
2374            finalCostEstimate.setCost(
2375                finalCostEstimate.getEstimatedCost() + ce.getEstimatedCost(),
2376                ce.rowCount(),
2377                ce.singleScanRowCount());
2378        }
2379
2380        return finalCostEstimate;
2381    }
2382
2383    /** @see Optimizer#setOuterRows */
2384    public void setOuterRows(double outerRows)
2385    {
2386        outermostCostEstimate.setCost(
2387                outermostCostEstimate.getEstimatedCost(),
2388                outerRows,
2389                outermostCostEstimate.singleScanRowCount());
2390    }
2391
2392    /** @see Optimizer#tableLockThreshold */
2393    public int tableLockThreshold()
2394    {
2395        return tableLockThreshold;
2396    }
2397
2398    /**
2399     * Get the number of join strategies supported by this optimizer.
2400     */
2401    public int getNumberOfJoinStrategies()
2402    {
2403        return joinStrategies.length;
2404    }
2405
2406    /** @see Optimizer#getJoinStrategy */
2407    public JoinStrategy getJoinStrategy(int whichStrategy) {
2408        if (SanityManager.DEBUG) {
2409            if (whichStrategy < 0 || whichStrategy >= joinStrategies.length) {
2410                SanityManager.THROWASSERT("whichStrategy value " +
2411                                    whichStrategy +
2412                                    " out of range - should be between 0 and " +
2413                                    (joinStrategies.length - 1));
2414            }
2415
2416            if (joinStrategies[whichStrategy] == null) {
2417                SanityManager.THROWASSERT("Strategy " + whichStrategy +
2418                                            " not filled in.");
2419            }
2420        }
2421
2422        return joinStrategies[whichStrategy];
2423    }
2424
2425    /** @see Optimizer#getJoinStrategy */
2426    public JoinStrategy getJoinStrategy(String   whichStrategy) {
2427        JoinStrategy retval = null;
2428        String   upperValue = StringUtil.SQLToUpperCase(whichStrategy);
2429
2430        for (int i = 0; i < joinStrategies.length; i++) {
2431            if (upperValue.equals(joinStrategies[i].getName())) {
2432                retval = joinStrategies[i];
2433            }
2434        }
2435
2436        return retval;
2437    }
2438
2439    /**
2440        @see Optimizer#uniqueJoinWithOuterTable
2441
2442        @exception StandardException    Thrown on error
2443     */
2444    public double uniqueJoinWithOuterTable(OptimizablePredicateList predList)
2445                                            throws StandardException
2446    {
2447        double retval = -1.0;
2448        double numUniqueKeys = 1.0;
2449        double currentRows = currentCost.rowCount();
2450
2451        if (predList != null)
2452        {
2453
2454            for (int i = joinPosition - 1; i >= 0; i--)
2455            {
2456                Optimizable opt = optimizableList.getOptimizable(
2457                                                        proposedJoinOrder[i]);
2458                double uniqueKeysThisOptimizable = opt.uniqueJoin(predList);
2459                if (uniqueKeysThisOptimizable > 0.0)
2460                    numUniqueKeys *= opt.uniqueJoin(predList);
2461            }
2462        }
2463
2464        if (numUniqueKeys != 1.0)
2465        {
2466            retval = numUniqueKeys / currentRows;
2467        }
2468
2469        return retval;
2470    }
2471
2472    private boolean isPushable(OptimizablePredicate pred)
2473    {
2474        /* Predicates which contain subqueries that are not materializable are
2475         * not currently pushable.
2476         */
2477        if (pred.hasSubquery())
2478        {
2479            return false;
2480        }
2481        else
2482        {
2483            return true;
2484        }
2485    }
2486
2487    /**
2488     * Estimate the total cost of doing a join with the given optimizable.
2489     *
2490     * @exception StandardException     Thrown on error
2491     */
2492    private CostEstimate estimateTotalCost(OptimizablePredicateList predList,
2493                                            ConglomerateDescriptor cd,
2494                                            CostEstimate outerCost,
2495                                            Optimizable optimizable)
2496        throws StandardException
2497    {
2498        /* Get the cost of a single scan */
2499        CostEstimate resultCost =
2500            optimizable.estimateCost(predList,
2501                                    cd,
2502                                    outerCost,
2503                                    this,
2504                                    currentRowOrdering);
2505
2506        return resultCost;
2507    }
2508
2509    /** @see Optimizer#getLevel */
2510    public int getLevel()
2511    {
2512        return 1;
2513    }
2514
2515    public CostEstimateImpl getNewCostEstimate(double theCost,
2516                            double theRowCount,
2517                            double theSingleScanRowCount)
2518    {
2519        return new CostEstimateImpl(theCost, theRowCount, theSingleScanRowCount);
2520    }
2521
2522    // Optimzer trace
2523    public void trace(int traceFlag, int intParam1, int intParam2,
2524                      double doubleParam, Object   objectParam1)
2525    {
2526    }
2527    
2528    /** @see Optimizer#useStatistics */
2529    public boolean useStatistics() { return useStatistics && optimizableList.useStatistics(); }
2530
2531    /**
2532     * Process (i.e. add, load, or remove) current best join order as the
2533     * best one for some outer query or ancestor node, represented by another
2534     * OptimizerImpl or an instance of FromTable, respectively. Then
2535     * iterate through our optimizableList and tell each Optimizable
2536     * to do the same.  See Optimizable.updateBestPlan() for more on why
2537     * this is necessary.
2538     *
2539     * @param action Indicates whether to add, load, or remove the plan
2540     * @param planKey Object to use as the map key when adding/looking up
2541     *  a plan.  If this is an instance of OptimizerImpl then it corresponds
2542     *  to an outer query; otherwise it's some Optimizable above this
2543     *  OptimizerImpl that could potentially reject plans chosen by this
2544     *  OptimizerImpl.
2545     */
2546    protected void updateBestPlanMaps(short action,
2547        Object   planKey) throws StandardException
2548    {
2549        // First we process this OptimizerImpl's best join order.  If there's
2550        // only one optimizable in the list, then there's only one possible
2551        // join order, so don't bother.
2552        if (numOptimizables > 1)
2553        {
2554            int [] joinOrder = null;
2555            if (action == FromTable.REMOVE_PLAN)
2556            {
2557                if (savedJoinOrders != null)
2558                {
2559                    savedJoinOrders.remove(planKey);
2560                    if (savedJoinOrders.size() == 0)
2561                        savedJoinOrders = null;
2562                }
2563            }
2564            else if (action == FromTable.ADD_PLAN)
2565            {
2566                // If the savedJoinOrder map already exists, search for the
2567                // join order for the target optimizer and reuse that.
2568                if (savedJoinOrders == null)
2569                    savedJoinOrders = new HashMap  ();
2570                else
2571                    joinOrder = (int[])savedJoinOrders.get(planKey);
2572
2573                // If we don't already have a join order array for the optimizer,
2574                // create a new one.
2575                if (joinOrder == null)
2576                    joinOrder = new int[numOptimizables];
2577
2578                // Now copy current bestJoinOrder and save it.
2579                for (int i = 0; i < bestJoinOrder.length; i++)
2580                    joinOrder[i] = bestJoinOrder[i];
2581
2582                savedJoinOrders.put(planKey, joinOrder);
2583            }
2584            else
2585            {
2586                // If we get here, we want to load the best join order from our
2587                // map into this OptimizerImpl's bestJoinOrder array.
2588
2589                // If we don't have any join orders saved, then there's nothing to
2590                // load.  This can happen if the optimizer tried some join order
2591                // for which there was no valid plan.
2592                if (savedJoinOrders != null)
2593                {
2594                    joinOrder = (int[])savedJoinOrders.get(planKey);
2595                    if (joinOrder != null)
2596                    {
2597                        // Load the join order we found into our
2598                        // bestJoinOrder array.
2599                        for (int i = 0; i < joinOrder.length; i++)
2600                            bestJoinOrder[i] = joinOrder[i];
2601                    }
2602                }
2603            }
2604        }
2605
2606        // Now iterate through all Optimizables in this OptimizerImpl's
2607        // list and add/load/remove the best plan "mapping" for each one,
2608        // as described in in Optimizable.updateBestPlanMap().
2609        for (int i = optimizableList.size() - 1; i >= 0; i--)
2610        {
2611            optimizableList.getOptimizable(i).
2612                updateBestPlanMap(action, planKey);
2613        }
2614    }
2615
2616    /**
2617     * Add scoped predicates to this optimizer's predicateList. This method
2618     * is intended for use during the modifyAccessPath() phase of
2619     * compilation, as it allows nodes (esp. SelectNodes) to add to the
2620     * list of predicates available for the final "push" before code
2621     * generation.  Just as the constructor for this class allows a
2622     * caller to specify a predicate list to use during the optimization
2623     * phase, this method allows a caller to specify a predicate list to
2624     * use during the modify-access-paths phase.
2625     *
2626     * Before adding the received predicates, this method also
2627     * clears out any scoped predicates that might be sitting in
2628     * OptimizerImpl's list from the last round of optimizing.
2629     *
2630     * @param pList List of predicates to add to this OptimizerImpl's
2631     *  own list for pushing.
2632     */
2633    protected void addScopedPredicatesToList(PredicateList pList)
2634        throws StandardException
2635    {
2636        if ((pList == null) || (pList == predicateList))
2637        // nothing to do.
2638            return;
2639
2640        if (predicateList == null)
2641        // in this case, there is no 'original' predicateList, so we
2642        // can just create one.
2643            predicateList = new PredicateList();
2644
2645        // First, we need to go through and remove any predicates in this
2646        // optimizer's list that may have been pushed here from outer queries
2647        // during the previous round(s) of optimization.  We know if the
2648        // predicate was pushed from an outer query because it will have
2649        // been scoped to the node for which this OptimizerImpl was
2650        // created.
2651        Predicate pred = null;
2652        for (int i = predicateList.size() - 1; i >= 0; i--) {
2653            pred = (Predicate)predicateList.getOptPredicate(i);
2654            if (pred.isScopedForPush())
2655                predicateList.removeOptPredicate(i);
2656        }
2657
2658        // Now transfer scoped predicates in the received list to
2659        // this OptimizerImpl's list, where appropriate.
2660        for (int i = pList.size() - 1; i >= 0; i--)
2661        {
2662            pred = (Predicate)pList.getOptPredicate(i);
2663            if (pred.isScopedToSourceResultSet())
2664            {
2665                // Clear the scoped predicate's scan flags; they'll be set
2666                // as appropriate when they make it to the restrictionList
2667                // of the scoped pred's source result set.
2668                pred.clearScanFlags();
2669                predicateList.addOptPredicate(pred);
2670                pList.removeOptPredicate(i);
2671            }
2672        }
2673
2674        return;
2675    }
2676
2677}
2678
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags