optimizerimpl.java

derby database source code.good for you.

			/* Clear bits representing those tables that have already been
			 * assigned, except for the current table.  The outer table map
			 * includes the current table, so if the predicate is ready to
			 * be pushed, predMap will end up with no bits set.
			 */
			for (int index = 0; index < predMap.size(); index++)
			{
				if (outerTables.get(index))
				{
					predMap.clear(index);
				}
			}

			/*
			** Only consider non-correlated variables when deciding where
			** to push predicates down to.
			*/
			predMap.and(nonCorrelatedTableMap);

			/*
			** Finally, push the predicate down to the Optimizable at the
			** end of the current proposed join order, if it can be evaluated
			** there.
			*/
			if (predMap.getFirstSetBit() == -1)
			{
				/* Push the predicate and remove it from the list */
				if (curTable.pushOptPredicate(pred))
				{
					predicateList.removeOptPredicate(predCtr);
				}
			}
		}
	}

	/**
	 * @see Optimizer#getNextDecoratedPermutation
	 *
	 * @exception StandardException		Thrown on error
	 */
	public boolean getNextDecoratedPermutation()
				throws StandardException
	{
		boolean		retval;
		Optimizable curOpt =
			optimizableList.getOptimizable(proposedJoinOrder[joinPosition]);
		double		originalRowCount = 0.0;
		
		// RESOLVE: Should we step through the different join strategies here?

		/* Returns true until all access paths are exhausted */
		retval =  curOpt.nextAccessPath(this,
										(OptimizablePredicateList) null,
										currentRowOrdering);

		// If the previous path that we considered for curOpt was _not_ the best
		// path for this round, then we need to revert back to whatever the
		// best plan for curOpt was this round.  Note that the cost estimate
		// for bestAccessPath could be null here if the last path that we
		// checked was the only one possible for this round.
		if ((curOpt.getBestAccessPath().getCostEstimate() != null) &&
			(curOpt.getCurrentAccessPath().getCostEstimate() != null))
		{
			// Note: we can't just check to see if bestCost is cheaper
			// than currentCost because it's possible that currentCost
			// is actually cheaper--but it may have been 'rejected' because
			// it would have required too much memory.  So we just check
			// to see if bestCost and currentCost are different.  If so
			// then we know that the most recent access path (represented
			// by "current" access path) was not the best.
			if (curOpt.getBestAccessPath().getCostEstimate().compare(
				curOpt.getCurrentAccessPath().getCostEstimate()) != 0)
			{
				curOpt.addOrLoadBestPlanMapping(false, curOpt);
			}
			else if (curOpt.getBestAccessPath().getCostEstimate().rowCount() <
				curOpt.getCurrentAccessPath().getCostEstimate().rowCount())
			{
				// If currentCost and bestCost have the same cost estimate
				// but currentCost has been rejected because of memory, we
				// still need to revert the plans.  In this case the row
				// count for currentCost will be greater than the row count
				// for bestCost, so that's what we just checked.
				curOpt.addOrLoadBestPlanMapping(false, curOpt);
			}
		}

		/*
		** When all the access paths have been looked at, we know what the
		** cheapest one is, so remember it.  Only do this if a cost estimate
		** has been set for the best access path - one will not have been
		** set if no feasible plan has been found.
		*/
		CostEstimate ce = curOpt.getBestAccessPath().getCostEstimate();
		if ( ( ! retval ) && (ce != null))
		{
			/*
			** Add the cost of the current optimizable to the total cost.
			** 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.
			*/
			currentCost.setCost(
				currentCost.getEstimatedCost() + ce.getEstimatedCost(),
				ce.rowCount(),
				ce.singleScanRowCount());

			if (curOpt.considerSortAvoidancePath() &&
				requiredRowOrdering != null)
			{
				/* Add the cost for the sort avoidance path, if there is one */
				ce = curOpt.getBestSortAvoidancePath().getCostEstimate();

				currentSortAvoidanceCost.setCost(
					currentSortAvoidanceCost.getEstimatedCost() +
						ce.getEstimatedCost(),
					ce.rowCount(),
					ce.singleScanRowCount());
			}

			if (optimizerTrace)
			{
				trace(TOTAL_COST_NON_SA_PLAN, 0, 0, 0.0, null);
				if (curOpt.considerSortAvoidancePath())
				{
					trace(TOTAL_COST_SA_PLAN, 0, 0, 0.0, null);
				}
			}
				
			/* Do we have a complete join order? */
			if ( joinPosition == (numOptimizables - 1) )
			{
				if (optimizerTrace)
				{
					trace(COMPLETE_JOIN_ORDER, 0, 0, 0.0, null);
				}

				/* Add cost of sorting to non-sort-avoidance cost */
				if (requiredRowOrdering != null)
				{
					boolean gotSortCost = false;

					/* Only get the sort cost once */
					if (sortCost == null)
					{
						sortCost = newCostEstimate();
					}
					/* requiredRowOrdering records if the bestCost so far is
					 * sort-needed or not, as done in rememberBestCost.  If
					 * the bestCost so far is sort-needed, and assume
					 * currentCost is also sort-needed, we want this comparison
					 * to be as accurate as possible.  Different plans may
					 * produce different estimated row count (eg., heap scan
					 * vs. index scan during a join), sometimes the difference
					 * could be very big.  However the actual row count should
					 * be only one value.  So when comparing these two plans,
					 * we want them to have the same sort cost.  We want to
					 * take the smaller row count, because a better estimation
					 * (eg. through index) would yield a smaller number.  We
					 * adjust the bestCost here if it had a bigger rowCount
					 * estimate.  The performance improvement of doing this
					 * sometimes is quite dramatic, eg. from 17 sec to 0.5 sec,
					 * see beetle 4353.
					 */
					else if (requiredRowOrdering.getSortNeeded())
					{
						if (bestCost.rowCount() > currentCost.rowCount())
						{
							// adjust bestCost
							requiredRowOrdering.estimateCost(
													bestCost.rowCount(),
													bestRowOrdering,
													sortCost
													);
							double oldSortCost = sortCost.getEstimatedCost();
							requiredRowOrdering.estimateCost(
													currentCost.rowCount(),
													bestRowOrdering,
													sortCost
													);
							gotSortCost = true;
							bestCost.setCost(bestCost.getEstimatedCost() -
											oldSortCost + 
											sortCost.getEstimatedCost(),
											sortCost.rowCount(),
											currentCost.singleScanRowCount());
						}
						else if (bestCost.rowCount() < currentCost.rowCount())
						{
							// adjust currentCost's rowCount
							currentCost.setCost(currentCost.getEstimatedCost(),
												bestCost.rowCount(),
												currentCost.singleScanRowCount());
						}
					}

					/* This does not figure out if sorting is necessary, just
					 * an asumption that sort is needed; if the assumption is
					 * wrong, we'll look at sort-avoidance cost as well, later
					 */
					if (! gotSortCost)
					{
						requiredRowOrdering.estimateCost(
													currentCost.rowCount(),
													bestRowOrdering,
													sortCost
													);
					}

					originalRowCount = currentCost.rowCount();

					currentCost.setCost(currentCost.getEstimatedCost() +
										sortCost.getEstimatedCost(),
										sortCost.rowCount(),
										currentCost.singleScanRowCount()
										);
					
					if (optimizerTrace)
					{
						trace(COST_OF_SORTING, 0, 0, 0.0, null);
						trace(TOTAL_COST_WITH_SORTING, 0, 0, 0.0, null);
					}
				}

				/*
				** Is the cost of this join order lower than the best one we've
				** found so far?
				**
				** NOTE: If the user has specified a join order, it will be the
				** only join order the optimizer considers, so it is OK to use
				** costing to decide that it is the "best" join order.
				**
				** For very deeply nested queries, it's possible that the optimizer
				** will return an estimated cost of Double.INFINITY, which is
				** greater than our uninitialized cost of Double.MAX_VALUE and
				** thus the "compare" check below will return false.   So we have
				** to check to see if bestCost is uninitialized and, if so, we
				** save currentCost regardless of what value it is--because we
				** haven't found anything better yet.
				**
				** That said, it's also possible for bestCost to be infinity
				** AND for current cost to be infinity, as well.  In that case
				** we can't really tell much by comparing the two, so for lack
				** of better alternative we look at the row counts.  See
				** CostEstimateImpl.compare() for more.
				*/
				if ((! foundABestPlan) ||
					(currentCost.compare(bestCost) < 0) ||
					bestCost.isUninitialized())
				{
					rememberBestCost(currentCost, Optimizer.NORMAL_PLAN);

					// Since we just remembered all of the best plans,
					// no need to reload them when pulling Optimizables
					// from this join order.
					reloadBestPlan = false;
				}
				else
					reloadBestPlan = true;

				/* Subtract cost of sorting from non-sort-avoidance cost */
				if (requiredRowOrdering != null)
				{
					/*
					** The cost could go negative due to loss of precision.
					*/
					double newCost = currentCost.getEstimatedCost() -
										sortCost.getEstimatedCost();
					if (newCost < 0.0)
						newCost = 0.0;
					
					currentCost.setCost(newCost,
										originalRowCount,
										currentCost.singleScanRowCount()
										);
				}

				/*
				** This may be the best sort-avoidance plan if there is a
				** required row ordering, and we are to consider a sort
				** avoidance path on the last Optimizable in the join order.
				*/
				if (requiredRowOrdering != null &&
					curOpt.considerSortAvoidancePath())
				{
					if (requiredRowOrdering.sortRequired(bestRowOrdering) ==
									RequiredRowOrdering.NOTHING_REQUIRED)
					{
						if (optimizerTrace)
						{
							trace(CURRENT_PLAN_IS_SA_PLAN, 0, 0, 0.0, null);
						}

						if ((currentSortAvoidanceCost.compare(bestCost) <= 0)
							|| bestCost.isUninitialized())
						{
							rememberBestCost(currentSortAvoidanceCost,
											Optimizer.SORT_AVOIDANCE_PLAN);
						}
					}
				}
			}
		}

		return retval;
	}

	/**
	 * Is the cost of this join order lower than the best one we've
	 * found so far?  If so, remember it.
	 *
	 * NOTE: If the user has specified a join order, it will be the
	 * only join order the optimizer considers, so it is OK to use
	 * costing to decide that it is the "best" join order.
	 *	@exception StandardException	Thrown on error
	 */
	private void rememberBestCost(CostEstimate currentCost, int planType)
		throws StandardException
	{
		foundABestPlan = true;

		if (optimizerTrace)
		{
			trace(CHEAPEST_PLAN_SO_FAR, 0, 0, 0.0, null);
			trace(PLAN_TYPE, planType, 0, 0.0, null);
			trace(COST_OF_CHEAPEST_PLAN_SO_FAR, 0, 0, 0.0, null);
		}

		/* Remember the current cost as best */
		bestCost.setCost(currentCost);

		// Our time limit for optimizing this round is the time we think
		// it will take us to execute the best join order that we've 
		// found so far (across all rounds of optimizing).  In other words,
		// don't spend more time optimizing this OptimizerImpl than we think
		// it's going to take to execute the best plan.  So if we've just
		// found a new "best" join order, use that to update our time limit.
		if (bestCost.getEstimatedCost() < timeLimit)
			timeLimit = bestCost.getEstimatedCost();

		/*
		** Remember the current join order and access path
		** selections as best.
		** NOTE: We want the optimizer trace to print out in
		** join order instead of in table number order, so
		** we use 2 loops.
		*/
		for (int i = 0; i < numOptimizables; i++)
		{
			bestJoinOrder[i] = proposedJoinOrder[i];
		}
		for (int i = 0; i < numOptimizables; i++)
		{
			optimizableList.getOptimizable(bestJoinOrder[i]).
				rememberAsBest(planType, this);
		}

		/* Remember if a sort is not needed for this plan */
		if (requiredRowOrdering != null)
		{
			if (planType == Optimizer.SORT_AVOIDANCE_PLAN)
				requiredRowOrdering.sortNotNeeded();
			else
				requiredRowOrdering.sortNeeded();
		}

		if (optimizerTrace)
		{
			if (requiredRowOrdering != null)
			{
				trace(SORT_NEEDED_FOR_ORDERING, planType, 0, 0.0, null);
			}
			trace(REMEMBERING_BEST_JOIN_ORDER, 0, 0, 0.0, null);
		}
	}

	/**
	 * @see org.apache.derby.iapi.sql.compile.Optimizer#costPermutation
	 *
	 * @exception StandardException		Thrown on error
	 */
	public void costPermutation() throws StandardException
	{
		/*
		** Get the cost of the outer plan so far.  This gives us the current
		** estimated rows, ordering, etc.
		*/
		CostEstimate outerCost;
		if (joinPosition == 0)
		{
			outerCost = outermostCostEstimate;
		}
		else
		{
			/*
			** NOTE: This is somewhat problematic.  We assume here that the
			** outer cost from the best access path for the outer table