optimizerimpl.java

derby database source code.good for you.

					/*
					** It's possible for newCost to go negative here due to
					** loss of precision.
					*/
					if (newCost < 0.0)
						newCost = 0.0;
				}

				/* If we are choosing a new outer table, then
				 * we rest the starting cost to the outermostCost.
				 * (Thus avoiding any problems with floating point
				 * accuracy and going negative.)
				 */
				if (joinPosition == 0)
				{
					if (outermostCostEstimate != null)
					{
						newCost = outermostCostEstimate.getEstimatedCost();
					}
					else
					{
						newCost = 0.0;
					}
				}

				currentCost.setCost(
					newCost,
					prevRowCount,
					prevSingleScanRowCount);
				
				/*
				** Subtract from the sort avoidance cost if there is a
				** required row ordering.
				**
				** NOTE: It is not necessary here to check whether the
				** best cost was ever set for the sort avoidance path,
				** because it considerSortAvoidancePath() would not be
				** set if there cost were not set.
				*/
				if (requiredRowOrdering != null)
				{
					if (pullMe.considerSortAvoidancePath())
					{
						AccessPath ap = pullMe.getBestSortAvoidancePath();
						double	   prevEstimatedCost = 0.0d;

						/*
						** Subtract the sort avoidance cost estimate of the
						** optimizable being removed from the total sort
						** avoidance cost estimate.
						**
						** The total cost is the sum of all the costs, but the
						** total number of rows is the number of rows returned
						** by the innermost optimizable.
						*/
						if (joinPosition == 0)
						{
							prevRowCount = outermostCostEstimate.rowCount();
							prevSingleScanRowCount = outermostCostEstimate.singleScanRowCount();
							/* If we are choosing a new outer table, then
							 * we rest the starting cost to the outermostCost.
							 * (Thus avoiding any problems with floating point
							 * accuracy and going negative.)
							 */
							prevEstimatedCost = outermostCostEstimate.getEstimatedCost();
						}
						else
						{
							CostEstimate localCE = 
								optimizableList.
									getOptimizable(prevPosition).
										getBestSortAvoidancePath().
											getCostEstimate();
							prevRowCount = localCE.rowCount();
							prevSingleScanRowCount = localCE.singleScanRowCount();
							prevEstimatedCost = currentSortAvoidanceCost.getEstimatedCost() -
													ap.getCostEstimate().getEstimatedCost();
						}

						currentSortAvoidanceCost.setCost(
							prevEstimatedCost,
							prevRowCount,
							prevSingleScanRowCount);

						/*
						** Remove the table from the best row ordering.
						** It should not be necessary to remove it from
						** the current row ordering, because it is
						** maintained as we step through the access paths
						** for the current Optimizable.
						*/
						bestRowOrdering.removeOptimizable(
													pullMe.getTableNumber());

						/*
						** When removing a table from the join order,
						** the best row ordering for the remaining outer tables
						** becomes the starting point for the row ordering of
						** the current table.
						*/
						bestRowOrdering.copy(currentRowOrdering);
					}
				}

				/*
				** Pull the predicates at from the optimizable and put
				** them back in the predicate list.
				**
				** NOTE: This is a little inefficient because it pulls the
				** single-table predicates, which are guaranteed to always
				** be pushed to the same optimizable.  We could make this
				** leave the single-table predicates where they are.
				*/
				pullMe.pullOptPredicates(predicateList);

				/*
				** When we pull an Optimizable we need to go through and
				** load whatever best path we found for that Optimizable
				** with respect to _this_ OptimizerImpl.  An Optimizable
				** can have different "best paths" for different Optimizer
				** Impls if there are subqueries beneath it; we need to make
				** sure that when we pull it, it's holding the best path as
				** as we determined it to be for _us_.
				**
				** NOTE: We we only reload the best plan if it's necessary
				** to do so--i.e. if the best plans aren't already loaded.
				** The plans will already be loaded if the last complete
				** join order we had was the best one so far, because that
				** means we called "rememberAsBest" on every Optimizable
				** in the list and, as part of that call, we will run through
				** and set trulyTheBestAccessPath for the entire subtree.
				** So if we haven't tried any other plans since then,
				** we know that every Optimizable (and its subtree) already
				** has the correct best plan loaded in its trulyTheBest
				** path field.  It's good to skip the load in this case
				** because 'reloading best plans' involves walking the
				** entire subtree of _every_ Optimizable in the list, which
				** can be expensive if there are deeply nested subqueries.
				*/
				if (reloadBestPlan)
					pullMe.addOrLoadBestPlanMapping(false, this);

				/* Mark current join position as unused */
				proposedJoinOrder[joinPosition] = -1;
			}

			/* Have we exhausted all the optimizables at this join position? */
			if (nextOptimizable >= numOptimizables)
			{
				/*
				** If we're not optimizing the join order, remember the first
				** join order.
				*/
				if ( ! optimizableList.optimizeJoinOrder())
				{
					// Verify that the user specified a legal join order
					if ( ! optimizableList.legalJoinOrder(numTablesInQuery))
					{
						if (optimizerTrace)
						{
							trace(ILLEGAL_USER_JOIN_ORDER, 0, 0, 0.0, null);
						}

						throw StandardException.newException(SQLState.LANG_ILLEGAL_FORCED_JOIN_ORDER);
					}

					if (optimizerTrace)
					{
						trace(USER_JOIN_ORDER_OPTIMIZED, 0, 0, 0.0, null);
					}

					desiredJoinOrderFound = true;
				}

				if (permuteState == READY_TO_JUMP && joinPosition > 0 && joinPosition == numOptimizables-1)
				{
					permuteState = JUMPING;

					/* A simple heuristics is that the row count we got indicates a potentially
					 * good join order.  We'd like row count to get big as late as possible, so
					 * that less load is carried over.
					 */
					double rc[] = new double[numOptimizables];
					for (int i = 0; i < numOptimizables; i++)
					{
						firstLookOrder[i] = i;
						CostEstimate ce = optimizableList.getOptimizable(i).
												getBestAccessPath().getCostEstimate();
						if (ce == null)
						{
							permuteState = READY_TO_JUMP;  //come again?
							break;
						}
						rc[i] = ce.singleScanRowCount();
					}
					if (permuteState == JUMPING)
					{
						boolean doIt = false;
						int temp;
						for (int i = 0; i < numOptimizables; i++)	//simple selection sort
						{
							int k = i;
							for (int j = i+1; j < numOptimizables; j++)
								if (rc[j] < rc[k])  k = j;
							if (k != i)
							{
								rc[k] = rc[i];	//destroy the bridge
								temp = firstLookOrder[i];
								firstLookOrder[i] = firstLookOrder[k];
								firstLookOrder[k] = temp;
								doIt = true;
							}
						}

						if (doIt)
						{
							joinPosition--;
							rewindJoinOrder();  //jump from ground
							continue;
						}
						else permuteState = NO_JUMP;	//never
					}
				}

				/*
				** We have exhausted all the optimizables at this level.
				** Go back up one level.
				*/

				/* Go back up one join position */
				joinPosition--;

				/* Clear the assigned table map for the previous position 
				 * NOTE: We need to do this here to for the dependency tracking
				 */
				if (joinPosition >= 0)
				{
					Optimizable pullMe =
						optimizableList.getOptimizable(
											proposedJoinOrder[joinPosition]);

					/*
					** Clear the bits from the table at this join position.
					** This depends on them having been set previously.
					** NOTE: We need to do this here to for the dependency tracking
					*/
					assignedTableMap.xor(pullMe.getReferencedTableMap());
				}

				if (joinPosition < 0 && permuteState == WALK_HIGH) //reached peak
				{
					joinPosition = 0;	//reset, fall down the hill
					permuteState = WALK_LOW;
				}
				continue;
			}

			/*
			** We have found another optimizable to try at this join position.
			*/
			proposedJoinOrder[joinPosition] = nextOptimizable;

			if (permuteState == WALK_LOW)
			{
				boolean finishedCycle = true;
				for (int i = 0; i < numOptimizables; i++)
				{
					if (proposedJoinOrder[i] < firstLookOrder[i])
					{
						finishedCycle = false;
						break;
					}
					else if (proposedJoinOrder[i] > firstLookOrder[i])  //done
						break;
				}
				if (finishedCycle)
				{
					// We just set proposedJoinOrder[joinPosition] above, so
					// if we're done we need to put it back to -1 to indicate
					// that it's an empty slot.  Then we rewind and pull any
					// other Optimizables at positions < joinPosition.
					// Note: we have to make sure we reload the best plans
					// as we rewind since they may have been clobbered
					// (as part of the current join order) before we got
					// here.
					proposedJoinOrder[joinPosition] = -1;
					joinPosition--;
					if (joinPosition >= 0)
					{
						reloadBestPlan = true;
						rewindJoinOrder();
						joinPosition = -1;
					}
					permuteState = READY_TO_JUMP;
					return false;
				}
			}

			/* Re-init (clear out) the cost for the best access path
			 * when placing a table.
			 */
			optimizableList.getOptimizable(nextOptimizable).
				getBestAccessPath().setCostEstimate((CostEstimate) null);

			/* Set the assigned table map to be exactly the tables
			 * in the current join order. 
			 */
			assignedTableMap.clearAll();
			for (int index = 0; index <= joinPosition; index++)
			{
				assignedTableMap.or(optimizableList.getOptimizable(proposedJoinOrder[index]).getReferencedTableMap());
			}

			if (optimizerTrace)
			{
				trace(CONSIDERING_JOIN_ORDER, 0, 0, 0.0, null);
			}

			Optimizable nextOpt =
							optimizableList.getOptimizable(nextOptimizable);

			nextOpt.startOptimizing(this, currentRowOrdering);

			pushPredicates(
				optimizableList.getOptimizable(nextOptimizable),
				assignedTableMap);

			return true;
		}

		return false;
	}

	private void rewindJoinOrder()
		throws StandardException
	{
		for (; ; joinPosition--)
		{
			Optimizable pullMe =
				optimizableList.getOptimizable(
									proposedJoinOrder[joinPosition]);
			pullMe.pullOptPredicates(predicateList);
			if (reloadBestPlan)
				pullMe.addOrLoadBestPlanMapping(false, this);
			proposedJoinOrder[joinPosition] = -1;
			if (joinPosition == 0) break;
		}
		currentCost.setCost(0.0d, 0.0d, 0.0d);
		currentSortAvoidanceCost.setCost(0.0d, 0.0d, 0.0d);
		assignedTableMap.clearAll();
	}

	/*
	** Push predicates from this optimizer's list to the given optimizable,
	** as appropriate given the outer tables.
	**
	** @param curTable	The Optimizable to push predicates down to
	** @param outerTables	A bit map of outer tables
	**
	** @exception StandardException		Thrown on error
	*/
	void pushPredicates(Optimizable curTable, JBitSet outerTables)
			throws StandardException
	{
		/*
		** Push optimizable clauses to current position in join order.
		**
		** RESOLVE - We do not push predicates with subqueries not materializable.
		*/

		int		numPreds = predicateList.size();
		JBitSet	predMap = new JBitSet(numTablesInQuery);
		OptimizablePredicate pred;

		/* Walk the OptimizablePredicateList.  For each OptimizablePredicate,
		 * see if it can be assigned to the Optimizable at the current join
		 * position.
		 *
		 * NOTE - We walk the OPL backwards since we will hopefully be deleted
		 * entries as we walk it.
		 */
		for (int predCtr = numPreds - 1; predCtr >= 0; predCtr--)
		{
			pred = predicateList.getOptPredicate(predCtr);

			/* Skip over non-pushable predicates */
			if (! isPushable(pred))
			{
				continue;
			}
				
			/* Make copy of referenced map so that we can do destructive
			 * manipulation on the copy.
			 */
			predMap.setTo(pred.getReferencedMap());