optimizerimpl.java

derby database source code.good for you.

		 * each round of optimization; the check for "a complete join order"
		 * is done by looking to see if the current join position is the
		 * final one.
		 */
		if (timeExceeded && bestCost.isUninitialized() &&
			(!alreadyDelayedTimeout || (joinPosition < numOptimizables - 1)))
		{
			/* We can get here if this OptimizerImpl is for a subquery
			 * that timed out for a previous permutation of the outer
			 * query, but then the outer query itself did _not_ timeout.
			 * In that case we'll end up back here for another round of
			 * optimization, but our timeExceeded flag will be true.
			 * We don't want to reset all of the timeout state here
			 * because that could lead to redundant work (see comments
			 * in prepForNextRound()), but we also don't want to return
			 * without having a plan, because then we'd return an unfairly
			 * high "bestCost" value--i.e. Double.MAX_VALUE.  Note that
			 * we can't just revert back to whatever bestCost we had
			 * prior to this because that cost is for some previous
			 * permutation of the outer query--not the current permutation--
			 * and thus would be incorrect.  So instead we have to delay
			 * the timeout until we find a complete (and valid) join order,
			 * so that we can return a valid cost estimate.  Once we have
			 * a valid cost we'll then go through the timeout logic
			 * and stop optimizing.
			 * 
			 * All of that said, instead of just trying the first possible
			 * join order, we jump to the join order that gave us the best
			 * cost in previous rounds.  We know that such a join order exists
			 * because that's how our timeout value was set to begin with--so
			 * if there was no best join order, we never would have timed out
			 * and thus we wouldn't be here.
			 */
			if (permuteState != JUMPING)
			{
				// By setting firstLookOrder to our target join order
				// and then setting our permuteState to JUMPING, we'll
				// jump to the target join order and get the cost.  That
				// cost will then be saved as bestCost, allowing us to
				// proceed with normal timeout logic.
				for (int i = 0; i < numOptimizables; i++)
					firstLookOrder[i] = bestJoinOrder[i];
				permuteState = JUMPING;

				// If we were in the middle of a join order when this
				// happened, then reset the join order before jumping.
				// The call to rewindJoinOrder() here will put joinPosition
				// back to 0.  But that said, we'll then end up incrementing 
				// joinPosition before we start looking for the next join
				// order (see below), which means we need to set it to -1
				// here so that it gets incremented to "0" and then
				// processing can continue as normal from there.  Note:
				// we don't need to set reloadBestPlan to true here
				// because we only get here if we have *not* found a
				// best plan yet.
				if (joinPosition > 0)
				{
					rewindJoinOrder();
					joinPosition = -1;
				}
			}

			// Reset the timeExceeded flag so that we'll keep going
			// until we find a complete join order.  NOTE: we intentionally
			// do _not_ reset the timeOptimizationStarted value because we
			// we want to go through this timeout logic for every
			// permutation, to make sure we timeout as soon as we have
			// our first complete join order.
			timeExceeded = false;
			alreadyDelayedTimeout = true;
		}

		/*
		** Pick the next table in the join order, if there is an unused position
		** in the join order, and the current plan is less expensive than
		** the best plan so far, and the amount of time spent optimizing is
		** still less than the cost of the best plan so far, and a best
		** cost has been found in the current join position.  Otherwise,
		** just pick the next table in the current position.
		*/
		boolean joinPosAdvanced = false;
		if ((joinPosition < (numOptimizables - 1)) &&
			((currentCost.compare(bestCost) < 0) ||
			(currentSortAvoidanceCost.compare(bestCost) < 0)) &&
			( ! timeExceeded )
			)
		{
			/*
			** Are we either starting at the first join position (in which
			** case joinPosition will be -1), or has a best cost been found
			** in the current join position?  The latter case might not be
			** true if there is no feasible join order.
			*/
			if ((joinPosition < 0) ||
				optimizableList.getOptimizable(
											proposedJoinOrder[joinPosition]).
								getBestAccessPath().getCostEstimate() != null)
			{
				joinPosition++;
				joinPosAdvanced = true;

				/*
				** When adding a table to the join order, the best row
				** row ordering for the outer tables becomes the starting
				** point for the row ordering of the current table.
				*/
				bestRowOrdering.copy(currentRowOrdering);
			}
		}
		else if (optimizerTrace)
		{
			/*
			** Not considered short-circuiting if all slots in join
			** order are taken.
			*/
			if (joinPosition < (numOptimizables - 1))
			{
				trace(SHORT_CIRCUITING, 0, 0, 0.0, null);
			}
		}

		if (permuteState == JUMPING && !joinPosAdvanced && joinPosition >= 0)
		{
			//not feeling well in the middle of jump
			// 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 gave
			// up on jumping.
			reloadBestPlan = true;
			rewindJoinOrder();  //fall
			permuteState = NO_JUMP;  //give up
		}

		/*
		** The join position becomes < 0 when all the permutations have been
		** looked at.
		*/
		while (joinPosition >= 0)
		{
			int nextOptimizable = 0;

			if (desiredJoinOrderFound || timeExceeded)
			{
				/*
				** If the desired join order has been found (which will happen
				** if the user specifies a join order), pretend that there are
				** no more optimizables at this join position.  This will cause
				** us to back out of the current join order.
				**
				** Also, don't look at any more join orders if we have taken
				** too much time with this optimization.
				*/
				nextOptimizable = numOptimizables;
			}
			else if (permuteState == JUMPING)  //still jumping
			{
				/* We're "jumping" to a join order that puts the optimizables
				** with the lowest estimated costs first (insofar as it
				** is legal to do so).  The "firstLookOrder" array holds the
				** ideal join order for position <joinPosition> up thru
				** position <numOptimizables-1>.  So here, we look at the
				** ideal optimizable to place at <joinPosition> and see if
				** it's legal; if it is, then we're done.  Otherwise, we
				** swap it with <numOptimizables-1> and see if that gives us
				** a legal join order w.r.t <joinPosition>.  If not, then we
				** swap it with <numOptimizables-2> and check, and if that
				** fails, then we swap it with <numOptimizables-3>, and so
				** on.  For example, assume we have 6 optimizables whose
				** order from least expensive to most expensive is 2, 1, 4,
				** 5, 3, 0.  Assume also that we've already verified the
				** legality of the first two positions--i.e. that joinPosition
				** is now "2". That means that "firstLookOrder" currently
				** contains the following:
				**
				** [ pos ]    0  1  2  3  4  5
				** [ opt ]    2  1  4  5  3  0
				**
				** Then at this point, we do the following:
				**
				**  -- Check to see if the ideal optimizable "4" is valid
				**     at its current position (2)
				**  -- If opt "4" is valid, then we're done; else we
				**     swap it with the value at position _5_:
				**
				** [ pos ]    0  1  2  3  4  5
				** [ opt ]    2  1  0  5  3  4
				**
				**  -- Check to see if optimizable "0" is valid at its
				**     new position (2).
				**  -- If opt "0" is valid, then we're done; else we
				**     put "0" back in its original position and swap
				**     the ideal optimizer ("4") with the value at
				**     position _4_:
				**
				** [ pos ]    0  1  2  3  4  5
				** [ opt ]    2  1  3  5  4  0
				**
				**  -- Check to see if optimizable "3" is valid at its
				**     new position (2).
				**  -- If opt "3" is valid, then we're done; else we
				**     put "3" back in its original position and swap
				**     the ideal optimizer ("4") with the value at
				**     position _3_:
				**
				** [ pos ]    0  1  2  3  4  5
				** [ opt ]    2  1  5  4  3  0
				**
				**  -- Check to see if optimizable "5" is valid at its
				**     new position (2).
				**  -- If opt "5" is valid, then we're done; else we've
				**     tried all the available optimizables and none
				**     of them are legal at position 2.  In this case,
				**     we give up on "JUMPING" and fall back to normal
				**     join-order processing.
				*/

				int idealOptimizable = firstLookOrder[joinPosition];
				nextOptimizable = idealOptimizable;
				int lookPos = numOptimizables;
				int lastSwappedOpt = -1;

				Optimizable nextOpt;
				for (nextOpt = optimizableList.getOptimizable(nextOptimizable);
					!(nextOpt.legalJoinOrder(assignedTableMap));
					nextOpt = optimizableList.getOptimizable(nextOptimizable))
				{
					// Undo last swap, if we had one.
					if (lastSwappedOpt >= 0) {
						firstLookOrder[joinPosition] = idealOptimizable;
						firstLookOrder[lookPos] = lastSwappedOpt;
					}

					if (lookPos > joinPosition + 1) {
					// we still have other possibilities; get the next
					// one by "swapping" it into the current position.
						lastSwappedOpt = firstLookOrder[--lookPos];
						firstLookOrder[joinPosition] = lastSwappedOpt;
						firstLookOrder[lookPos] = idealOptimizable;
						nextOptimizable = lastSwappedOpt;
					}
					else {
					// we went through all of the available optimizables
					// and none of them were legal in the current position;
					// so we give up and fall back to normal processing.
					// 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.
						if (joinPosition > 0) {
							joinPosition--;
							reloadBestPlan = true;
							rewindJoinOrder();
						}
						permuteState = NO_JUMP;
						break;
					}
				}

				if (permuteState == NO_JUMP)
					continue;

				if (joinPosition == numOptimizables - 1) {
				// we just set the final position within our
				// "firstLookOrder" join order; now go ahead
				// and search for the best join order, starting from
				// the join order stored in "firstLookOrder".  This
				// is called walking "high" because we're searching
				// the join orders that are at or "above" (after) the
				// order found in firstLookOrder.  Ex. if we had three
				// optimizables and firstLookOrder was [1 2 0], then
				// the "high" would be [1 2 0], [2 0 1] and [2 1 0];
				// the "low" would be [0 1 2], [0 2 1], and [1 0 2].
				// We walk the "high" first, then fall back and
				// walk the "low".
					permuteState = WALK_HIGH;
				}
			}
			else
			{
				/* Find the next unused table at this join position */
				nextOptimizable = proposedJoinOrder[joinPosition] + 1;

				for ( ; nextOptimizable < numOptimizables; nextOptimizable++)
				{
					boolean found = false;
					for (int posn = 0; posn < joinPosition; posn++)
					{
						/*
						** Is this optimizable already somewhere
						** in the join order?
						*/
						if (proposedJoinOrder[posn] == nextOptimizable)
						{
							found = true;
							break;
						}
					}

					/* Check to make sure that all of the next optimizable's
					 * dependencies have been satisfied.
					 */
					if (nextOptimizable < numOptimizables)
					{
						Optimizable nextOpt =
								optimizableList.getOptimizable(nextOptimizable);
						if (! (nextOpt.legalJoinOrder(assignedTableMap)))
						{
							if (optimizerTrace)
							{
								trace(SKIPPING_JOIN_ORDER, nextOptimizable, 0, 0.0, null);
							}

							/*
							** If this is a user specified join order then it is illegal.
							*/
							if ( ! optimizableList.optimizeJoinOrder())
							{
								if (optimizerTrace)
								{
									trace(ILLEGAL_USER_JOIN_ORDER, 0, 0, 0.0, null);
								}

								throw StandardException.newException(SQLState.LANG_ILLEGAL_FORCED_JOIN_ORDER);
							}
							continue;
						}
					}

					if (! found)
					{
						break;
					}
				}

			}

			/*
			** We are going to try an optimizable at the current join order
			** position.  Is there one already at that position?
			*/
			if (proposedJoinOrder[joinPosition] >= 0)
			{
				/*
				** We are either going to try another table at the current
				** join order position, or we have exhausted all the tables
				** at the current join order position.  In either case, we
				** need to pull the table at the current join order position
				** and remove it from the join order.
				*/
				Optimizable pullMe =
					optimizableList.getOptimizable(
											proposedJoinOrder[joinPosition]);

				/*
				** Subtract the cost estimate of the optimizable being
				** removed from the total 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.
				*/
				double prevRowCount;
				double prevSingleScanRowCount;
				int prevPosition = 0;
				if (joinPosition == 0)
				{
					prevRowCount = outermostCostEstimate.rowCount();
					prevSingleScanRowCount = outermostCostEstimate.singleScanRowCount();
				}
				else
				{
					prevPosition = proposedJoinOrder[joinPosition - 1];
					CostEstimate localCE = 
						optimizableList.
							getOptimizable(prevPosition).
								getBestAccessPath().
									getCostEstimate();
					prevRowCount = localCE.rowCount();
					prevSingleScanRowCount = localCE.singleScanRowCount();
				}

				/*
				** If there is no feasible join order, the cost estimate
				** in the best access path may never have been set.
				** In this case, do not subtract anything from the
				** current cost, since nothing was added to the current
				** cost.
				*/
				double newCost = currentCost.getEstimatedCost();
				double pullCost = 0.0;
				CostEstimate pullCostEstimate =
								pullMe.getBestAccessPath().getCostEstimate();
				if (pullCostEstimate != null)
				{
					pullCost = pullCostEstimate.getEstimatedCost();

					newCost -= pullCost;