Source code: org/apache/derby/impl/sql/compile/OptimizerImpl.java
1 /*
2
3 Derby - Class org.apache.derby.impl.sql.compile.OptimizerImpl
4
5 Copyright 1997, 2004 The Apache Software Foundation or its licensors, as applicable.
6
7 Licensed under the Apache License, Version 2.0 (the "License");
8 you may not use this file except in compliance with the License.
9 You may obtain a copy of the License at
10
11 http://www.apache.org/licenses/LICENSE-2.0
12
13 Unless required by applicable law or agreed to in writing, software
14 distributed under the License is distributed on an "AS IS" BASIS,
15 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 See the License for the specific language governing permissions and
17 limitations under the License.
18
19 */
20
21 package org.apache.derby.impl.sql.compile;
22
23 import org.apache.derby.iapi.services.sanity.SanityManager;
24
25 import org.apache.derby.iapi.error.StandardException;
26
27 import org.apache.derby.iapi.sql.compile.JoinStrategy;
28 import org.apache.derby.iapi.sql.compile.Optimizable;
29 import org.apache.derby.iapi.sql.compile.OptimizableList;
30 import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
31 import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
32 import org.apache.derby.iapi.sql.compile.Optimizer;
33 import org.apache.derby.iapi.sql.compile.CostEstimate;
34 import org.apache.derby.iapi.sql.compile.RequiredRowOrdering;
35 import org.apache.derby.iapi.sql.compile.RowOrdering;
36 import org.apache.derby.iapi.sql.compile.AccessPath;
37
38 import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
39
40 import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
41 import org.apache.derby.iapi.sql.dictionary.DataDictionary;
42 import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
43
44 import org.apache.derby.catalog.IndexDescriptor;
45 import org.apache.derby.iapi.reference.SQLState;
46
47 import org.apache.derby.iapi.util.JBitSet;
48 import org.apache.derby.iapi.util.StringUtil;
49
50 import java.util.Properties;
51
52 /**
53 * This will be the Level 1 Optimizer.
54 * RESOLVE - it's a level 0 optimizer right now.
55 * Current State:
56 * o No costing services
57 * o We can only cost a derived table with a join once.
58 *
59 * Optimizer uses OptimizableList to keep track of the best join order as it
60 * builds it. For each available slot in the join order, we cost all of the
61 * Optimizables from that slot til the end of the OptimizableList. Later,
62 * we will choose the best Optimizable for that slot and reorder the list
63 * accordingly.
64 * In order to do this, we probably need to move the temporary pushing and
65 * pulling of join clauses into Optimizer, since the logic will be different
66 * for other implementations. (Of course, we're not pushing and pulling join
67 * clauses between permutations yet.)
68 */
69
70 public class OptimizerImpl implements Optimizer
71 {
72
73 DataDictionary dDictionary;
74 /* The number of tables in the query as a whole. (Size of bit maps.) */
75 int numTablesInQuery;
76 /* The number of optimizables in the list to optimize */
77 int numOptimizables;
78
79 /* Bit map of tables that have already been assigned to slots.
80 * Useful for pushing join clauses as slots are assigned.
81 */
82 protected JBitSet assignedTableMap;
83 protected OptimizableList optimizableList;
84 OptimizablePredicateList predicateList;
85 JBitSet nonCorrelatedTableMap;
86
87 protected int[] proposedJoinOrder;
88 protected int[] bestJoinOrder;
89 protected int joinPosition;
90 boolean desiredJoinOrderFound;
91
92 /* This implements a state machine to jump start to a appearingly good join
93 * order, when the number of tables is high, and the optimization could take
94 * a long time. A good start can prune better, and timeout sooner. Otherwise,
95 * it may take forever to exhaust or timeout (see beetle 5870). Basically after
96 * we jump, we walk the high part, then fall when we reach the peak, finally we
97 * walk the low part til where we jumped to.
98 */
99 private static final int NO_JUMP = 0;
100 private static final int READY_TO_JUMP = 1;
101 private static final int JUMPING = 2;
102 private static final int WALK_HIGH = 3;
103 private static final int WALK_LOW = 4;
104 private int permuteState;
105 private int[] firstLookOrder;
106
107 private boolean ruleBasedOptimization;
108
109 private CostEstimateImpl outermostCostEstimate;
110 protected CostEstimateImpl currentCost;
111 protected CostEstimateImpl currentSortAvoidanceCost;
112 protected CostEstimateImpl bestCost;
113
114 protected long timeOptimizationStarted;
115 protected long currentTime;
116 protected boolean timeExceeded;
117 private boolean noTimeout;
118 private boolean useStatistics;
119 private int tableLockThreshold;
120
121 private JoinStrategy[] joinStrategies;
122
123 protected RequiredRowOrdering requiredRowOrdering;
124
125 private boolean foundABestPlan;
126
127 protected CostEstimate sortCost;
128
129 private RowOrdering currentRowOrdering = new RowOrderingImpl();
130 private RowOrdering bestRowOrdering = new RowOrderingImpl();
131
132 private boolean conglomerate_OneRowResultSet;
133
134 // optimizer trace
135 protected boolean optimizerTrace;
136 protected boolean optimizerTraceHtml;
137
138 // max memory use per table
139 protected int maxMemoryPerTable;
140
141 protected OptimizerImpl(OptimizableList optimizableList,
142 OptimizablePredicateList predicateList,
143 DataDictionary dDictionary,
144 boolean ruleBasedOptimization,
145 boolean noTimeout,
146 boolean useStatistics,
147 int maxMemoryPerTable,
148 JoinStrategy[] joinStrategies,
149 int tableLockThreshold,
150 RequiredRowOrdering requiredRowOrdering,
151 int numTablesInQuery)
152 throws StandardException
153 {
154 if (SanityManager.DEBUG) {
155 SanityManager.ASSERT(optimizableList != null,
156 "optimizableList is not expected to be null");
157 }
158
159 outermostCostEstimate = getNewCostEstimate(0.0d, 1.0d, 1.0d);
160
161 currentCost = getNewCostEstimate(0.0d, 0.0d, 0.0d);
162
163 currentSortAvoidanceCost = getNewCostEstimate(0.0d, 0.0d, 0.0d);
164
165 bestCost = getNewCostEstimate(Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);
166
167 // Verify that any Properties lists for user overrides are valid
168 optimizableList.verifyProperties(dDictionary);
169
170 this.numTablesInQuery = numTablesInQuery;
171 numOptimizables = optimizableList.size();
172 proposedJoinOrder = new int[numOptimizables];
173 if (numTablesInQuery > 6)
174 {
175 permuteState = READY_TO_JUMP;
176 firstLookOrder = new int[numOptimizables];
177 }
178 else
179 permuteState = NO_JUMP;
180
181 /* Mark all join positions as unused */
182 for (int i = 0; i < numOptimizables; i++)
183 proposedJoinOrder[i] = -1;
184
185 bestJoinOrder = new int[numOptimizables];
186 joinPosition = -1;
187 this.optimizableList = optimizableList;
188 this.predicateList = predicateList;
189 this.dDictionary = dDictionary;
190 this.ruleBasedOptimization = ruleBasedOptimization;
191 this.noTimeout = noTimeout;
192 this.maxMemoryPerTable = maxMemoryPerTable;
193 this.joinStrategies = joinStrategies;
194 this.tableLockThreshold = tableLockThreshold;
195 this.requiredRowOrdering = requiredRowOrdering;
196 this.useStatistics = useStatistics;
197
198 /* initialize variables for tracking permutations */
199 assignedTableMap = new JBitSet(numTablesInQuery);
200
201 /*
202 ** Make a map of the non-correlated tables, which are the tables
203 ** in the list of Optimizables we're optimizing. An reference
204 ** to a table that is not defined in the list of Optimizables
205 ** is presumed to be correlated.
206 */
207 nonCorrelatedTableMap = new JBitSet(numTablesInQuery);
208 for (int tabCtr = 0; tabCtr < numOptimizables; tabCtr++)
209 {
210 Optimizable curTable = optimizableList.getOptimizable(tabCtr);
211 nonCorrelatedTableMap.or(curTable.getReferencedTableMap());
212 }
213
214 /* Get the time that optimization starts */
215 timeOptimizationStarted = System.currentTimeMillis();
216 }
217
218 public int getMaxMemoryPerTable()
219 {
220 return maxMemoryPerTable;
221 }
222
223 /**
224 * @see Optimizer#getNextPermutation
225 *
226 * @exception StandardException Thrown on error
227 */
228 public boolean getNextPermutation()
229 throws StandardException
230 {
231 /* Don't get any permutations if there is nothing to optimize */
232 if (numOptimizables < 1)
233 {
234 if (optimizerTrace)
235 {
236 trace(NO_TABLES, 0, 0, 0.0, null);
237 }
238
239 return false;
240 }
241
242 /* Make sure that all Optimizables init their access paths.
243 * (They wait until optimization since the access path
244 * references the optimizer.)
245 */
246 optimizableList.initAccessPaths(this);
247
248 /*
249 ** Experiments show that optimization time only starts to
250 ** become a problem with seven tables, so only check for
251 ** too much time if there are more than seven tables.
252 ** Also, don't check for too much time if user has specified
253 ** no timeout.
254 */
255 if ( ( ! timeExceeded ) &&
256 (numTablesInQuery > 6) &&
257 ( ! noTimeout) )
258 {
259 /*
260 ** Stop optimizing if the time spent optimizing is greater than
261 ** the current best cost.
262 */
263 currentTime = System.currentTimeMillis();
264 timeExceeded = (currentTime - timeOptimizationStarted) >
265 bestCost.getEstimatedCost();
266
267 if (optimizerTrace && timeExceeded)
268 {
269 trace(TIME_EXCEEDED, 0, 0, 0.0, null);
270 }
271 }
272
273 /*
274 ** Pick the next table in the join order, if there is an unused position
275 ** in the join order, and the current plan is less expensive than
276 ** the best plan so far, and the amount of time spent optimizing is
277 ** still less than the cost of the best plan so far, and a best
278 ** cost has been found in the current join position. Otherwise,
279 ** just pick the next table in the current position.
280 */
281 boolean joinPosAdvanced = false;
282 if ((joinPosition < (numOptimizables - 1)) &&
283 ((currentCost.compare(bestCost) < 0) ||
284 (currentSortAvoidanceCost.compare(bestCost) < 0)) &&
285 ( ! timeExceeded )
286 )
287 {
288 /*
289 ** Are we either starting at the first join position (in which
290 ** case joinPosition will be -1), or has a best cost been found
291 ** in the current join position? The latter case might not be
292 ** true if there is no feasible join order.
293 */
294 if ((joinPosition < 0) ||
295 optimizableList.getOptimizable(
296 proposedJoinOrder[joinPosition]).
297 getBestAccessPath().getCostEstimate() != null)
298 {
299 joinPosition++;
300 joinPosAdvanced = true;
301
302 /*
303 ** When adding a table to the join order, the best row
304 ** row ordering for the outer tables becomes the starting
305 ** point for the row ordering of the current table.
306 */
307 bestRowOrdering.copy(currentRowOrdering);
308 }
309 }
310 else if (optimizerTrace)
311 {
312 /*
313 ** Not considered short-circuiting if all slots in join
314 ** order are taken.
315 */
316 if (joinPosition < (numOptimizables - 1))
317 {
318 trace(SHORT_CIRCUITING, 0, 0, 0.0, null);
319 }
320 }
321 if (permuteState == JUMPING && !joinPosAdvanced && joinPosition >= 0)
322 {
323 //not feeling well in the middle of jump
324 rewindJoinOrder(); //fall
325 permuteState = NO_JUMP; //give up
326 }
327
328 /*
329 ** The join position becomes < 0 when all the permutations have been
330 ** looked at.
331 */
332 while (joinPosition >= 0)
333 {
334 int nextOptimizable = 0;
335
336 if (desiredJoinOrderFound || timeExceeded)
337 {
338 /*
339 ** If the desired join order has been found (which will happen
340 ** if the user specifies a join order), pretend that there are
341 ** no more optimizables at this join position. This will cause
342 ** us to back out of the current join order.
343 **
344 ** Also, don't look at any more join orders if we have taken
345 ** too much time with this optimization.
346 */
347 nextOptimizable = numOptimizables;
348 }
349 else if (permuteState == JUMPING) //still jumping
350 {
351 nextOptimizable = firstLookOrder[joinPosition];
352 Optimizable nextOpt = optimizableList.getOptimizable(nextOptimizable);
353 if (! (nextOpt.legalJoinOrder(assignedTableMap)))
354 {
355 if (joinPosition < numOptimizables - 1)
356 {
357 firstLookOrder[joinPosition] = firstLookOrder[numOptimizables - 1];
358 firstLookOrder[numOptimizables - 1] = nextOptimizable;
359 }
360 else
361 permuteState = NO_JUMP; //not good
362 if (joinPosition > 0)
363 {
364 joinPosition--;
365 rewindJoinOrder(); //jump again?
366 }
367 continue;
368 }
369
370 if (joinPosition == numOptimizables - 1) //ready to walk
371 permuteState = WALK_HIGH; //walk high hill
372 }
373 else
374 {
375 /* Find the next unused table at this join position */
376 nextOptimizable = proposedJoinOrder[joinPosition] + 1;
377
378 for ( ; nextOptimizable < numOptimizables; nextOptimizable++)
379 {
380 boolean found = false;
381 for (int posn = 0; posn < joinPosition; posn++)
382 {
383 /*
384 ** Is this optimizable already somewhere
385 ** in the join order?
386 */
387 if (proposedJoinOrder[posn] == nextOptimizable)
388 {
389 found = true;
390 break;
391 }
392 }
393
394 /* Check to make sure that all of the next optimizable's
395 * dependencies have been satisfied.
396 */
397 if (nextOptimizable < numOptimizables)
398 {
399 Optimizable nextOpt =
400 optimizableList.getOptimizable(nextOptimizable);
401 if (! (nextOpt.legalJoinOrder(assignedTableMap)))
402 {
403 if (optimizerTrace)
404 {
405 trace(SKIPPING_JOIN_ORDER, nextOptimizable, 0, 0.0, null);
406 }
407
408 /*
409 ** If this is a user specified join order then it is illegal.
410 */
411 if ( ! optimizableList.optimizeJoinOrder())
412 {
413 if (optimizerTrace)
414 {
415 trace(ILLEGAL_USER_JOIN_ORDER, 0, 0, 0.0, null);
416 }
417
418 throw StandardException.newException(SQLState.LANG_ILLEGAL_FORCED_JOIN_ORDER);
419 }
420 continue;
421 }
422 }
423
424 if (! found)
425 {
426 break;
427 }
428 }
429
430 }
431
432 /*
433 ** We are going to try an optimizable at the current join order
434 ** position. Is there one already at that position?
435 */
436 if (proposedJoinOrder[joinPosition] >= 0)
437 {
438 /*
439 ** We are either going to try another table at the current
440 ** join order position, or we have exhausted all the tables
441 ** at the current join order position. In either case, we
442 ** need to pull the table at the current join order position
443 ** and remove it from the join order.
444 */
445 Optimizable pullMe =
446 optimizableList.getOptimizable(
447 proposedJoinOrder[joinPosition]);
448
449 /*
450 ** Subtract the cost estimate of the optimizable being
451 ** removed from the total cost estimate.
452 **
453 ** The total cost is the sum of all the costs, but the total
454 ** number of rows is the number of rows returned by the
455 ** innermost optimizable.
456 */
457 double prevRowCount;
458 double prevSingleScanRowCount;
459 int prevPosition = 0;
460 if (joinPosition == 0)
461 {
462 prevRowCount = outermostCostEstimate.rowCount();
463 prevSingleScanRowCount = outermostCostEstimate.singleScanRowCount();
464 }
465 else
466 {
467 prevPosition = proposedJoinOrder[joinPosition - 1];
468 CostEstimate localCE =
469 optimizableList.
470 getOptimizable(prevPosition).
471 getBestAccessPath().
472 getCostEstimate();
473 prevRowCount = localCE.rowCount();
474 prevSingleScanRowCount = localCE.singleScanRowCount();
475 }
476
477 /*
478 ** If there is no feasible join order, the cost estimate
479 ** in the best access path may never have been set.
480 ** In this case, do not subtract anything from the
481 ** current cost, since nothing was added to the current
482 ** cost.
483 */
484 double newCost = currentCost.getEstimatedCost();
485 double pullCost = 0.0;
486 CostEstimate pullCostEstimate =
487 pullMe.getBestAccessPath().getCostEstimate();
488 if (pullCostEstimate != null)
489 {
490 pullCost = pullCostEstimate.getEstimatedCost();
491
492 newCost -= pullCost;
493
494 /*
495 ** It's possible for newCost to go negative here due to
496 ** loss of precision.
497 */
498 if (newCost < 0.0)
499 newCost = 0.0;
500 }
501
502 /* If we are choosing a new outer table, then
503 * we rest the starting cost to the outermostCost.
504 * (Thus avoiding any problems with floating point
505 * accuracy and going negative.)
506 */
507 if (joinPosition == 0)
508 {
509 if (outermostCostEstimate != null)
510 {
511 newCost = outermostCostEstimate.getEstimatedCost();
512 }
513 else
514 {
515 newCost = 0.0;
516 }
517 }
518
519 currentCost.setCost(
520 newCost,
521 prevRowCount,
522 prevSingleScanRowCount);
523
524 /*
525 ** Subtract from the sort avoidance cost if there is a
526 ** required row ordering.
527 **
528 ** NOTE: It is not necessary here to check whether the
529 ** best cost was ever set for the sort avoidance path,
530 ** because it considerSortAvoidancePath() would not be
531 ** set if there cost were not set.
532 */
533 if (requiredRowOrdering != null)
534 {
535 if (pullMe.considerSortAvoidancePath())
536 {
537 AccessPath ap = pullMe.getBestSortAvoidancePath();
538 double prevEstimatedCost = 0.0d;
539
540 /*
541 ** Subtract the sort avoidance cost estimate of the
542 ** optimizable being removed from the total sort
543 ** avoidance cost estimate.
544 **
545 ** The total cost is the sum of all the costs, but the
546 ** total number of rows is the number of rows returned
547 ** by the innermost optimizable.
548 */
549 if (joinPosition == 0)
550 {
551 prevRowCount = outermostCostEstimate.rowCount();
552 prevSingleScanRowCount = outermostCostEstimate.singleScanRowCount();
553 /* If we are choosing a new outer table, then
554 * we rest the starting cost to the outermostCost.
555 * (Thus avoiding any problems with floating point
556 * accuracy and going negative.)
557 */
558 prevEstimatedCost = outermostCostEstimate.getEstimatedCost();
559 }
560 else
561 {
562 CostEstimate localCE =
563 optimizableList.
564 getOptimizable(prevPosition).
565 getBestSortAvoidancePath().
566 getCostEstimate();
567 prevRowCount = localCE.rowCount();
568 prevSingleScanRowCount = localCE.singleScanRowCount();
569 prevEstimatedCost = currentSortAvoidanceCost.getEstimatedCost() -
570 ap.getCostEstimate().getEstimatedCost();
571 }
572
573 currentSortAvoidanceCost.setCost(
574 prevEstimatedCost,
575 prevRowCount,
576 prevSingleScanRowCount);
577
578 /*
579 ** Remove the table from the best row ordering.
580 ** It should not be necessary to remove it from
581 ** the current row ordering, because it is
582 ** maintained as we step through the access paths
583 ** for the current Optimizable.
584 */
585 bestRowOrdering.removeOptimizable(
586 pullMe.getTableNumber());
587
588 /*
589 ** When removing a table from the join order,
590 ** the best row ordering for the remaining outer tables
591 ** becomes the starting point for the row ordering of
592 ** the current table.
593 */
594 bestRowOrdering.copy(currentRowOrdering);
595 }
596 }
597
598 /*
599 ** Pull the predicates at from the optimizable and put
600 ** them back in the predicate list.
601 **
602 ** NOTE: This is a little inefficient because it pulls the
603 ** single-table predicates, which are guaranteed to always
604 ** be pushed to the same optimizable. We could make this
605 ** leave the single-table predicates where they are.
606 */
607 pullMe.pullOptPredicates(predicateList);
608
609 /* Mark current join position as unused */
610 proposedJoinOrder[joinPosition] = -1;
611 }
612
613 /* Have we exhausted all the optimizables at this join position? */
614 if (nextOptimizable >= numOptimizables)
615 {
616 /*
617 ** If we're not optimizing the join order, remember the first
618 ** join order.
619 */
620 if ( ! optimizableList.optimizeJoinOrder())
621 {
622 // Verify that the user specified a legal join order
623 if ( ! optimizableList.legalJoinOrder(numTablesInQuery))
624 {
625 if (optimizerTrace)
626 {
627 trace(ILLEGAL_USER_JOIN_ORDER, 0, 0, 0.0, null);
628 }
629
630 throw StandardException.newException(SQLState.LANG_ILLEGAL_FORCED_JOIN_ORDER);
631 }
632
633 if (optimizerTrace)
634 {
635 trace(USER_JOIN_ORDER_OPTIMIZED, 0, 0, 0.0, null);
636 }
637
638 desiredJoinOrderFound = true;
639 }
640
641 if (permuteState == READY_TO_JUMP && joinPosition > 0 && joinPosition == numOptimizables-1)
642 {
643 permuteState = JUMPING;
644
645 /* A simple heuristics is that the row count we got indicates a potentially
646 * good join order. We'd like row count to get big as late as possible, so
647 * that less load is carried over.
648 */
649 double rc[] = new double[numOptimizables];
650 for (int i = 0; i < numOptimizables; i++)
651 {
652 firstLookOrder[i] = i;
653 CostEstimate ce = optimizableList.getOptimizable(i).
654 getBestAccessPath().getCostEstimate();
655 if (ce == null)
656 {
657 permuteState = READY_TO_JUMP; //come again?
658 break;
659 }
660 rc[i] = ce.singleScanRowCount();
661 }
662 if (permuteState == JUMPING)
663 {
664 boolean doIt = false;
665 int temp;
666 for (int i = 0; i < numOptimizables; i++) //simple selection sort
667 {
668 int k = i;
669 for (int j = i+1; j < numOptimizables; j++)
670 if (rc[j] < rc[k]) k = j;
671 if (k != i)
672 {
673 rc[k] = rc[i]; //destroy the bridge
674 temp = firstLookOrder[i];
675 firstLookOrder[i] = firstLookOrder[k];
676 firstLookOrder[k] = temp;
677 doIt = true;
678 }
679 }
680
681 if (doIt)
682 {
683 joinPosition--;
684 rewindJoinOrder(); //jump from ground
685 continue;
686 }
687 else permuteState = NO_JUMP; //never
688 }
689 }
690
691 /*
692 ** We have exhausted all the optimizables at this level.
693 ** Go back up one level.
694 */
695
696 /* Go back up one join position */
697 joinPosition--;
698
699 /* Clear the assigned table map for the previous position
700 * NOTE: We need to do this here to for the dependency tracking
701 */
702 if (joinPosition >= 0)
703 {
704 Optimizable pullMe =
705 optimizableList.getOptimizable(
706 proposedJoinOrder[joinPosition]);
707
708 /*
709 ** Clear the bits from the table at this join position.
710 ** This depends on them having been set previously.
711 ** NOTE: We need to do this here to for the dependency tracking
712 */
713 assignedTableMap.xor(pullMe.getReferencedTableMap());
714 }
715
716 if (joinPosition < 0 && permuteState == WALK_HIGH) //reached peak
717 {
718 joinPosition = 0; //reset, fall down the hill
719 permuteState = WALK_LOW;
720 }
721 continue;
722 }
723
724 /*
725 ** We have found another optimizable to try at this join position.
726 */
727 proposedJoinOrder[joinPosition] = nextOptimizable;
728
729 if (permuteState == WALK_LOW)
730 {
731 boolean finishedCycle = true;
732 for (int i = 0; i < numOptimizables; i++)
733 {
734 if (proposedJoinOrder[i] < firstLookOrder[i])
735 {
736 finishedCycle = false;
737 break;
738 }
739 else if (proposedJoinOrder[i] > firstLookOrder[i]) //done
740 break;
741 }
742 if (finishedCycle)
743 {
744 joinPosition--;
745 if (joinPosition >= 0)
746 {
747 rewindJoinOrder();
748 joinPosition = -1;
749 }
750 permuteState = READY_TO_JUMP;
751 return false;
752 }
753 }
754
755 /* Re-init (clear out) the cost for the best access path
756 * when placing a table.
757 */
758 optimizableList.getOptimizable(nextOptimizable).
759 getBestAccessPath().setCostEstimate((CostEstimate) null);
760
761 /* Set the assigned table map to be exactly the tables
762 * in the current join order.
763 */
764 assignedTableMap.clearAll();
765 for (int index = 0; index <= joinPosition; index++)
766 {
767 assignedTableMap.or(optimizableList.getOptimizable(proposedJoinOrder[index]).getReferencedTableMap());
768 }
769
770 if (optimizerTrace)
771 {
772 trace(CONSIDERING_JOIN_ORDER, 0, 0, 0.0, null);
773 }
774
775 Optimizable nextOpt =
776 optimizableList.getOptimizable(nextOptimizable);
777
778 nextOpt.startOptimizing(this, currentRowOrdering);
779
780 pushPredicates(
781 optimizableList.getOptimizable(nextOptimizable),
782 assignedTableMap);
783
784 return true;
785 }
786
787 return false;
788 }
789
790 private void rewindJoinOrder()
791 throws StandardException
792 {
793 for (; ; joinPosition--)
794 {
795 Optimizable pullMe =
796 optimizableList.getOptimizable(
797 proposedJoinOrder[joinPosition]);
798 pullMe.pullOptPredicates(predicateList);
799 proposedJoinOrder[joinPosition] = -1;
800 if (joinPosition == 0) break;
801 }
802 currentCost.setCost(0.0d, 0.0d, 0.0d);
803 currentSortAvoidanceCost.setCost(0.0d, 0.0d, 0.0d);
804 assignedTableMap.clearAll();
805 }
806
807 /*
808 ** Push predicates from this optimizer's list to the given optimizable,
809 ** as appropriate given the outer tables.
810 **
811 ** @param curTable The Optimizable to push predicates down to
812 ** @param outerTables A bit map of outer tables
813 **
814 ** @exception StandardException Thrown on error
815 */
816 void pushPredicates(Optimizable curTable, JBitSet outerTables)
817 throws StandardException
818 {
819 /*
820 ** Push optimizable clauses to current position in join order.
821 **
822 ** RESOLVE - We do not push predicates with subqueries not materializable.
823 */
824
825 int numPreds = predicateList.size();
826 JBitSet predMap = new JBitSet(numTablesInQuery);
827 OptimizablePredicate pred;
828
829 /* Walk the OptimizablePredicateList. For each OptimizablePredicate,
830 * see if it can be assigned to the Optimizable at the current join
831 * position.
832 *
833 * NOTE - We walk the OPL backwards since we will hopefully be deleted
834 * entries as we walk it.
835 */
836 for (int predCtr = numPreds - 1; predCtr >= 0; predCtr--)
837 {
838 pred = predicateList.getOptPredicate(predCtr);
839
840 /* Skip over non-pushable predicates */
841 if (! isPushable(pred))
842 {
843 continue;
844 }
845
846 /* Make copy of referenced map so that we can do destructive
847 * manipulation on the copy.
848 */
849 predMap.setTo(pred.getReferencedMap());
850
851 /* Clear bits representing those tables that have already been
852 * assigned, except for the current table. The outer table map
853 * includes the current table, so if the predicate is ready to
854 * be pushed, predMap will end up with no bits set.
855 */
856 for (int index = 0; index < predMap.size(); index++)
857 {
858 if (outerTables.get(index))
859 {
860 predMap.clear(index);
861 }
862 }
863
864 /*
865 ** Only consider non-correlated variables when deciding where
866 ** to push predicates down to.
867 */
868 predMap.and(nonCorrelatedTableMap);
869
870 /*
871 ** Finally, push the predicate down to the Optimizable at the
872 ** end of the current proposed join order, if it can be evaluated
873 ** there.
874 */
875 if (predMap.getFirstSetBit() == -1)
876 {
877 /* Push the predicate and remove it from the list */
878 if (curTable.pushOptPredicate(pred))
879 {
880 predicateList.removeOptPredicate(predCtr);
881 }
882 }
883 }
884 }
885
886 /**
887 * @see Optimizer#getNextDecoratedPermutation
888 *
889 * @exception StandardException Thrown on error
890 */
891 public boolean getNextDecoratedPermutation()
892 throws StandardException
893 {
894 boolean retval;
895 Optimizable curOpt =
896 optimizableList.getOptimizable(proposedJoinOrder[joinPosition]);
897 double originalRowCount = 0.0;
898
899 // RESOLVE: Should we step through the different join strategies here?
900
901 /* Returns true until all access paths are exhausted */
902 retval = curOpt.nextAccessPath(this,
903 (OptimizablePredicateList) null,
904 currentRowOrdering);
905
906 /*
907 ** When all the access paths have been looked at, we know what the
908 ** cheapest one is, so remember it. Only do this if a cost estimate
909 ** has been set for the best access path - one will not have been
910 ** set if no feasible plan has been found.
911 */
912 CostEstimate ce = curOpt.getBestAccessPath().getCostEstimate();
913 if ( ( ! retval ) && (ce != null))
914 {
915 /*
916 ** Add the cost of the current optimizable to the total cost.
917 ** The total cost is the sum of all the costs, but the total
918 ** number of rows is the number of rows returned by the innermost
919 ** optimizable.
920 */
921 currentCost.setCost(
922 currentCost.getEstimatedCost() + ce.getEstimatedCost(),
923 ce.rowCount(),
924 ce.singleScanRowCount());
925
926 if (curOpt.considerSortAvoidancePath() &&
927 requiredRowOrdering != null)
928 {
929 /* Add the cost for the sort avoidance path, if there is one */
930 ce = curOpt.getBestSortAvoidancePath().getCostEstimate();
931
932 currentSortAvoidanceCost.setCost(
933 currentSortAvoidanceCost.getEstimatedCost() +
934 ce.getEstimatedCost(),
935 ce.rowCount(),
936 ce.singleScanRowCount());
937 }
938
939 if (optimizerTrace)
940 {
941 trace(TOTAL_COST_NON_SA_PLAN, 0, 0, 0.0, null);
942 if (curOpt.considerSortAvoidancePath())
943 {
944 trace(TOTAL_COST_SA_PLAN, 0, 0, 0.0, null);
945 }
946 }
947
948 /* Do we have a complete join order? */
949 if ( joinPosition == (numOptimizables - 1) )
950 {
951 if (optimizerTrace)
952 {
953 trace(COMPLETE_JOIN_ORDER, 0, 0, 0.0, null);
954 }
955
956 /* Add cost of sorting to non-sort-avoidance cost */
957 if (requiredRowOrdering != null)
958 {
959 boolean gotSortCost = false;
960
961 /* Only get the sort cost once */
962 if (sortCost == null)
963 {
964 sortCost = newCostEstimate();
965 }
966 /* requiredRowOrdering records if the bestCost so far is
967 * sort-needed or not, as done in rememberBestCost. If
968 * the bestCost so far is sort-needed, and assume
969 * currentCost is also sort-needed, we want this comparison
970 * to be as accurate as possible. Different plans may
971 * produce different estimated row count (eg., heap scan
972 * vs. index scan during a join), sometimes the difference
973 * could be very big. However the actual row count should
974 * be only one value. So when comparing these two plans,
975 * we want them to have the same sort cost. We want to
976 * take the smaller row count, because a better estimation
977 * (eg. through index) would yield a smaller number. We
978 * adjust the bestCost here if it had a bigger rowCount
979 * estimate. The performance improvement of doing this
980 * sometimes is quite dramatic, eg. from 17 sec to 0.5 sec,
981 * see beetle 4353.
982 */
983 else if (requiredRowOrdering.getSortNeeded())
984 {
985 if (bestCost.rowCount() > currentCost.rowCount())
986 {
987 // adjust bestCost
988 requiredRowOrdering.estimateCost(
989 bestCost.rowCount(),
990 bestRowOrdering,
991 sortCost
992 );
993 double oldSortCost = sortCost.getEstimatedCost();
994 requiredRowOrdering.estimateCost(
995 currentCost.rowCount(),
996 bestRowOrdering,
997 sortCost
998 );
999 gotSortCost = true;
1000 bestCost.setCost(bestCost.getEstimatedCost() -
1001 oldSortCost +
1002 sortCost.getEstimatedCost(),
1003 sortCost.rowCount(),
1004 currentCost.singleScanRowCount());
1005 }
1006 else if (bestCost.rowCount() < currentCost.rowCount())
1007 {
1008 // adjust currentCost's rowCount
1009 currentCost.setCost(currentCost.getEstimatedCost(),
1010 bestCost.rowCount(),
1011 currentCost.singleScanRowCount());
1012 }
1013 }
1014
1015 /* This does not figure out if sorting is necessary, just
1016 * an asumption that sort is needed; if the assumption is
1017 * wrong, we'll look at sort-avoidance cost as well, later
1018 */
1019 if (! gotSortCost)
1020 {
1021 requiredRowOrdering.estimateCost(
1022 currentCost.rowCount(),
1023 bestRowOrdering,
1024 sortCost
1025 );
1026 }
1027
1028 originalRowCount = currentCost.rowCount();
1029
1030 currentCost.setCost(currentCost.getEstimatedCost() +
1031 sortCost.getEstimatedCost(),
1032 sortCost.rowCount(),
1033 currentCost.singleScanRowCount()
1034 );
1035
1036 if (optimizerTrace)
1037 {
1038 trace(COST_OF_SORTING, 0, 0, 0.0, null);
1039 trace(TOTAL_COST_WITH_SORTING, 0, 0, 0.0, null);
1040 }
1041 }
1042
1043 /*
1044 ** Is the cost of this join order lower than the best one we've
1045 ** found so far?
1046 **
1047 ** NOTE: If the user has specified a join order, it will be the
1048 ** only join order the optimizer considers, so it is OK to use
1049 ** costing to decide that it is the "best" join order.
1050 */
1051 if ((! foundABestPlan) || currentCost.compare(bestCost) < 0)
1052 {
1053 rememberBestCost(currentCost, Optimizer.NORMAL_PLAN);
1054 }
1055
1056 /* Subtract cost of sorting from non-sort-avoidance cost */
1057 if (requiredRowOrdering != null)
1058 {
1059 /*
1060 ** The cost could go negative due to loss of precision.
1061 */
1062 double newCost = currentCost.getEstimatedCost() -
1063 sortCost.getEstimatedCost();
1064 if (newCost < 0.0)
1065 newCost = 0.0;
1066
1067 currentCost.setCost(newCost,
1068 originalRowCount,
1069 currentCost.singleScanRowCount()
1070 );
1071 }
1072
1073 /*
1074 ** This may be the best sort-avoidance plan if there is a
1075 ** required row ordering, and we are to consider a sort
1076 ** avoidance path on the last Optimizable in the join order.
1077 */
1078 if (requiredRowOrdering != null &&
1079 curOpt.considerSortAvoidancePath())
1080 {
1081 if (requiredRowOrdering.sortRequired(bestRowOrdering) ==
1082 RequiredRowOrdering.NOTHING_REQUIRED)
1083 {
1084 if (optimizerTrace)
1085 {
1086 trace(CURRENT_PLAN_IS_SA_PLAN, 0, 0, 0.0, null);
1087 }
1088
1089 if (currentSortAvoidanceCost.compare(bestCost) <= 0)
1090 {
1091 rememberBestCost(currentSortAvoidanceCost,
1092 Optimizer.SORT_AVOIDANCE_PLAN);
1093 }
1094 }
1095 }
1096 }
1097 }
1098
1099 return retval;
1100 }
1101
1102 /**
1103 * Is the cost of this join order lower than the best one we've
1104 * found so far? If so, remember it.
1105 *
1106 * NOTE: If the user has specified a join order, it will be the
1107 * only join order the optimizer considers, so it is OK to use
1108 * costing to decide that it is the "best" join order.
1109 * @exception StandardException Thrown on error
1110 */
1111 private void rememberBestCost(CostEstimate currentCost, int planType)
1112 throws StandardException
1113 {
1114 foundABestPlan = true;
1115
1116 if (optimizerTrace)
1117 {
1118 trace(CHEAPEST_PLAN_SO_FAR, 0, 0, 0.0, null);
1119 trace(PLAN_TYPE, planType, 0, 0.0, null);
1120 trace(COST_OF_CHEAPEST_PLAN_SO_FAR, 0, 0, 0.0, null);
1121 }
1122
1123 /* Remember the current cost as best */
1124 bestCost.setCost(currentCost);
1125
1126 /*
1127 ** Remember the current join order and access path
1128 ** selections as best.
1129 ** NOTE: We want the optimizer trace to print out in
1130 ** join order instead of in table number order, so
1131 ** we use 2 loops.
1132 */
1133 for (int i = 0; i < numOptimizables; i++)
1134 {
1135 bestJoinOrder[i] = proposedJoinOrder[i];
1136 }
1137 for (int i = 0; i < numOptimizables; i++)
1138 {
1139 optimizableList.getOptimizable(bestJoinOrder[i]).rememberAsBest(planType);
1140 }
1141
1142 /* Remember if a sort is not needed for this plan */
1143 if (requiredRowOrdering != null)
1144 {
1145 if (planType == Optimizer.SORT_AVOIDANCE_PLAN)
1146 requiredRowOrdering.sortNotNeeded();
1147 else
1148 requiredRowOrdering.sortNeeded();
1149 }
1150
1151 if (optimizerTrace)
1152 {
1153 if (requiredRowOrdering != null)
1154 {
1155 trace(SORT_NEEDED_FOR_ORDERING, planType, 0, 0.0, null);
1156 }
1157 trace(REMEMBERING_BEST_JOIN_ORDER, 0, 0, 0.0, null);
1158 }
1159 }
1160
1161 /**
1162 * @see org.apache.derby.iapi.sql.compile.Optimizer#costPermutation
1163 *
1164 * @exception StandardException Thrown on error
1165 */
1166 public void costPermutation() throws StandardException
1167 {
1168 /*
1169 ** Get the cost of the outer plan so far. This gives us the current
1170 ** estimated rows, ordering, etc.
1171 */
1172 CostEstimate outerCost;
1173 if (joinPosition == 0)
1174 {
1175 outerCost = outermostCostEstimate;
1176 }
1177 else
1178 {
1179 /*
1180 ** NOTE: This is somewhat problematic. We assume here that the
1181 ** outer cost from the best access path for the outer table
1182 ** is OK to use even when costing the sort avoidance path for
1183 ** the inner table. This is probably OK, since all we use
1184 ** from the outer cost is the row count.
1185 */
1186 outerCost =
1187 optimizableList.getOptimizable(
1188 proposedJoinOrder[joinPosition - 1]).
1189 getBestAccessPath().getCostEstimate();
1190 }
1191
1192 Optimizable optimizable = optimizableList.getOptimizable(proposedJoinOrder[joinPosition]);
1193
1194 /*
1195 ** Don't consider non-feasible join strategies.
1196 */
1197 if ( ! optimizable.feasibleJoinStrategy(predicateList, this))
1198 {
1199 return;
1200 }
1201
1202 /* Cost the optimizable at the current join position */
1203 optimizable.optimizeIt(this,
1204 predicateList,
1205 outerCost,
1206 currentRowOrdering);
1207 }
1208
1209 /**
1210 * @see org.apache.derby.iapi.sql.compile.Optimizer#costOptimizable
1211 *
1212 * @exception StandardException Thrown on error
1213 */
1214 public void costOptimizable(Optimizable optimizable,
1215 TableDescriptor td,
1216 ConglomerateDescriptor cd,
1217 OptimizablePredicateList predList,
1218 CostEstimate outerCost)
1219 throws StandardException
1220 {
1221 /*
1222 ** Don't consider non-feasible join strategies.
1223 */
1224 if ( ! optimizable.feasibleJoinStrategy(predList, this))
1225 {
1226 return;
1227 }
1228
1229 /*
1230 ** Classify the predicates according to the given conglomerate.
1231 ** The predicates are classified as start keys, stop keys,
1232 ** qualifiers, and none-of-the-above. They are also ordered
1233 ** to match the ordering of columns in keyed conglomerates (no
1234 ** ordering is done for heaps).
1235 */
1236 // if (predList != null)
1237 // predList.classify(optimizable, cd);
1238
1239 if (ruleBasedOptimization)
1240 {
1241 ruleBasedCostOptimizable(optimizable,
1242 td,
1243 cd,
1244 predList,
1245 outerCost);
1246 }
1247 else
1248 {
1249 costBasedCostOptimizable(optimizable,
1250 td,
1251 cd,
1252 predList,
1253 outerCost);
1254 }
1255 }
1256
1257 /**
1258 * This method decides whether the given conglomerate descriptor is
1259 * cheapest based on rules, rather than based on cost estimates.
1260 * The rules are:
1261 *
1262 * Covering matching indexes are preferred above all
1263 * Non-covering matching indexes are next in order of preference
1264 * Covering non-matching indexes are next in order of preference
1265 * Heap scans are next in order of preference
1266 * Non-covering, non-matching indexes are last in order of
1267 * preference.
1268 *
1269 * In the current language architecture, there will always be a
1270 * heap, so a non-covering, non-matching index scan will never be
1271 * chosen. However, the optimizer may see a non-covering, non-matching
1272 * index first, in which case it will choose it temporarily as the
1273 * best conglomerate seen so far.
1274 *
1275 * NOTE: This method sets the cost in the optimizable, even though it
1276 * doesn't use the cost to determine which access path to choose. There
1277 * are two reasons for this: the cost might be needed to determine join
1278 * order, and the cost information is copied to the query plan.
1279 */
1280 private void ruleBasedCostOptimizable(Optimizable optimizable,
1281 TableDescriptor td,
1282 ConglomerateDescriptor cd,
1283 OptimizablePredicateList predList,
1284 CostEstimate outerCost)
1285 throws StandardException
1286 {
1287 /* CHOOSE BEST CONGLOMERATE HERE */
1288 ConglomerateDescriptor conglomerateDescriptor = null;
1289 ConglomerateDescriptor bestConglomerateDescriptor = null;
1290 AccessPath bestAp = optimizable.getBestAccessPath();
1291 int lockMode = optimizable.getCurrentAccessPath().getLockMode();
1292
1293
1294 /*
1295 ** If the current conglomerate better than the best so far?
1296 ** The pecking order is:
1297 ** o covering index useful for predicates
1298 ** (if there are predicates)
1299 ** o index useful for predicates (if there are predicates)
1300 ** o covering index
1301 ** o table scan
1302 */
1303
1304 /*
1305 ** If there is more than one conglomerate descriptor
1306 ** choose any index that is potentially useful.
1307 */
1308 if (predList != null &&
1309 predList.useful(optimizable, cd))
1310 {
1311 /*
1312 ** Do not let a non-covering matching index scan supplant a
1313 ** covering matching index scan.
1314 */
1315 boolean newCoveringIndex = optimizable.isCoveringIndex(cd);
1316 if ( ( ! bestAp.getCoveringIndexScan()) ||
1317 bestAp.getNonMatchingIndexScan() ||
1318 newCoveringIndex )
1319 {
1320 bestAp.setCostEstimate(
1321 estimateTotalCost(
1322 predList,
1323 cd,
1324 outerCost,
1325 optimizable
1326 )
1327 );
1328 bestAp.setConglomerateDescriptor(cd);
1329 bestAp.setNonMatchingIndexScan(false);
1330 bestAp.setCoveringIndexScan(newCoveringIndex);
1331
1332 bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode());
1333
1334 optimizable.rememberJoinStrategyAsBest(bestAp);
1335 }
1336
1337 return;
1338 }
1339
1340 /* Remember the "last" covering index.
1341 * NOTE - Since we don't have costing, we just go for the
1342 * last one since that's as good as any
1343 */
1344 if (optimizable.isCoveringIndex(cd))
1345 {
1346 bestAp.setCostEstimate(
1347 estimateTotalCost(predList,
1348 cd,
1349 outerCost,
1350 optimizable)
1351 );
1352 bestAp.setConglomerateDescriptor(cd);
1353 bestAp.setNonMatchingIndexScan(true);
1354 bestAp.setCoveringIndexScan(true);
1355
1356 bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode());
1357
1358 optimizable.rememberJoinStrategyAsBest(bestAp);
1359 return;
1360 }
1361
1362 /*
1363 ** If this is the heap, and the best conglomerate so far is a
1364 ** non-covering, non-matching index scan, pick the heap.
1365 */
1366 if ( ( ! bestAp.getCoveringIndexScan()) &&
1367 bestAp.getNonMatchingIndexScan() &&
1368 ( ! cd.isIndex() )
1369 )
1370 {
1371 bestAp.setCostEstimate(
1372 estimateTotalCost(predList,
1373 cd,
1374 outerCost,
1375 optimizable)
1376 );
1377
1378 bestAp.setConglomerateDescriptor(cd);
1379
1380 bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode());
1381
1382 optimizable.rememberJoinStrategyAsBest(bestAp);
1383
1384 /*
1385 ** No need to set non-matching index scan and covering
1386 ** index scan, as these are already correct.
1387 */
1388 return;
1389 }
1390
1391
1392 /*
1393 ** If all else fails, and no conglomerate has been picked yet,
1394 ** pick this one.
1395 */
1396 bestConglomerateDescriptor = bestAp.getConglomerateDescriptor();
1397 if (bestConglomerateDescriptor == null)
1398 {
1399 bestAp.setCostEstimate(
1400 estimateTotalCost(predList,
1401 cd,
1402 outerCost,
1403 optimizable)
1404 );
1405
1406 bestAp.setConglomerateDescriptor(cd);
1407
1408 /*
1409 ** We have determined above that this index is neither covering
1410 ** nor matching.
1411 */
1412 bestAp.setCoveringIndexScan(false);
1413 bestAp.setNonMatchingIndexScan(cd.isIndex());
1414
1415 bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode());
1416
1417 optimizable.rememberJoinStrategyAsBest(bestAp);
1418 }
1419
1420 return;
1421 }
1422
1423 /**
1424 * This method decides whether the given conglomerate descriptor is
1425 * cheapest based on cost, rather than based on rules. It compares
1426 * the cost of using the given ConglomerateDescriptor with the cost
1427 * of using the best ConglomerateDescriptor so far.
1428 */
1429 private void costBasedCostOptimizable(Optimizable optimizable,
1430 TableDescriptor td,
1431 ConglomerateDescriptor cd,
1432 OptimizablePredicateList predList,
1433 CostEstimate outerCost)
1434 throws StandardException
1435 {
1436 CostEstimate estimatedCost = estimateTotalCost(predList,
1437 cd,
1438 outerCost,
1439 optimizable);
1440
1441 /*
1442 ** Skip this access path if it takes too much memory.
1443 **
1444 ** NOTE: The default assumption here is that the number of rows in
1445 ** a single scan is the total number of rows divided by the number
1446 ** of outer rows. The optimizable may over-ride this assumption.
1447 */
1448 if( ! optimizable.memoryUsageOK( estimatedCost.rowCount() / outerCost.rowCount(), maxMemoryPerTable))
1449 {
1450 if (optimizerTrace)
1451 {
1452 trace(SKIPPING_DUE_TO_EXCESS_MEMORY, 0, 0, 0.0, null);
1453 }
1454 return;
1455 }
1456
1457 /* Pick the cheapest cost for this particular optimizable. */
1458 AccessPath ap = optimizable.getBestAccessPath();
1459 CostEstimate bestCostEstimate = ap.getCostEstimate();
1460
1461 if ((bestCostEstimate == null) ||
1462 (estimatedCost.compare(bestCostEstimate) < 0))
1463 {
1464 ap.setConglomerateDescriptor(cd);
1465 ap.setCostEstimate(estimatedCost);
1466 ap.setCoveringIndexScan(optimizable.isCoveringIndex(cd));
1467
1468 /*
1469 ** It's a non-matching index scan either if there is no
1470 ** predicate list, or nothing in the predicate list is useful
1471 ** for limiting the scan.
1472 */
1473 ap.setNonMatchingIndexScan(
1474 (predList == null) ||
1475 ( ! ( predList.useful(optimizable, cd) ) )
1476 );
1477 ap.setLockMode(optimizable.getCurrentAccessPath().getLockMode());
1478 optimizable.rememberJoinStrategyAsBest(ap);
1479 }
1480
1481 /*
1482 ** Keep track of the best sort-avoidance path if there is a
1483 ** required row ordering.
1484 */
1485 if (requiredRowOrdering != null)
1486 {
1487 /*
1488 ** The current optimizable can avoid a sort only if the
1489 ** outer one does, also (if there is an outer one).
1490 */
1491 if (joinPosition == 0 ||
1492 optimizableList.getOptimizable(
1493 proposedJoinOrder[joinPosition - 1]).
1494 considerSortAvoidancePath())
1495 {
1496 /*
1497 ** There is a required row ordering - does the proposed access
1498 ** path avoid a sort?
1499 */
1500 if (requiredRowOrdering.sortRequired(currentRowOrdering,
1501 assignedTableMap)
1502 == RequiredRowOrdering.NOTHING_REQUIRED)
1503 {
1504 ap = optimizable.getBestSortAvoidancePath();
1505 bestCostEstimate = ap.getCostEstimate();
1506
1507 /* Is this the cheapest sort-avoidance path? */
1508 if ((bestCostEstimate == null) ||
1509 (estimatedCost.compare(bestCostEstimate) < 0))
1510 {
1511 ap.setConglomerateDescriptor(cd);
1512 ap.setCostEstimate(estimatedCost);
1513 ap.setCoveringIndexScan(
1514 optimizable.isCoveringIndex(cd));
1515
1516 /*
1517 ** It's a non-matching index scan either if there is no
1518 ** predicate list, or nothing in the predicate list is
1519 ** useful for limiting the scan.
1520 */
1521 ap.setNonMatchingIndexScan(
1522 (predList == null) ||
1523 ( ! (predList.useful(optimizable, cd)) )
1524 );
1525 ap.setLockMode(
1526 optimizable.getCurrentAccessPath().getLockMode());
1527 optimizable.rememberJoinStrategyAsBest(ap);
1528 optimizable.rememberSortAvoidancePath();
1529
1530 /*
1531 ** Remember the current row ordering as best
1532 */
1533 currentRowOrdering.copy(bestRowOrdering);
1534 }
1535 }
1536 }
1537 }
1538 }
1539
1540 /**
1541 * This is the version of costOptimizable for non-base-tables.
1542 *
1543 * @see Optimizer#considerCost
1544 *
1545 * @exception StandardException Thrown on error
1546 */
1547 public void considerCost(Optimizable optimizable,
1548 OptimizablePredicateList predList,
1549 CostEstimate estimatedCost,
1550 CostEstimate outerCost)
1551 throws StandardException
1552 {
1553 /*
1554 ** Don't consider non-feasible join strategies.
1555 */
1556 if ( ! optimizable.feasibleJoinStrategy(predList, this))
1557 {
1558 return;
1559 }
1560
1561 /*
1562 ** Skip this access path if it takes too much memory.
1563 **
1564 ** NOTE: The default assumption here is that the number of rows in
1565 ** a single scan is the total number of rows divided by the number
1566 ** of outer rows. The optimizable may over-ride this assumption.
1567 **
1568 ** NOTE: This is probably not necessary here, because we should
1569 ** get here only for nested loop joins, which don't use memory.
1570 */
1571 if( ! optimizable.memoryUsageOK( estimatedCost.rowCount() / outerCost.rowCount(),
1572 maxMemoryPerTable))
1573 {
1574 if (optimizerTrace)
1575 {
1576 trace(SKIPPING_DUE_TO_EXCESS_MEMORY, 0, 0, 0.0, null);
1577 }
1578 return;
1579 }
1580
1581 /* Pick the cheapest cost for this particular optimizable.
1582 * NOTE: Originally, the code only chose the new access path if
1583 * it was cheaper than the old access path. However, I (Jerry)
1584 * found that the new and old costs were the same for a derived
1585 * table and the old access path did not have a join strategy
1586 * associated with it in that case. So, we now choose the new
1587 * access path if it is the same cost or cheaper than the current
1588 * access path.
1589 */
1590 AccessPath ap = optimizable.getBestAccessPath();
1591 CostEstimate bestCostEstimate = ap.getCostEstimate();
1592
1593 if ((bestCostEstimate == null) ||
1594 (estimatedCost.compare(bestCostEstimate) <= 0))
1595 {
1596 ap.setCostEstimate(estimatedCost);
1597 optimizable.rememberJoinStrategyAsBest(ap);
1598 }
1599
1600 /*
1601 ** Keep track of the best sort-avoidance path if there is a
1602 ** required row ordering.
1603 */
1604 if (requiredRowOrdering != null)
1605 {
1606 /*
1607 ** The current optimizable can avoid a sort only if the
1608 ** outer one does, also (if there is an outer one).
1609 */
1610 if (joinPosition == 0 ||
1611 optimizableList.getOptimizable(
1612 proposedJoinOrder[joinPosition - 1]).
1613 considerSortAvoidancePath())
1614 {
1615 /*
1616 ** There is a required row ordering - does the proposed access
1617 ** path avoid a sort?
1618 */
1619 if (requiredRowOrdering.sortRequired(currentRowOrdering,
1620 assignedTableMap)
1621 ==