optimizerimpl.java

derby database source code.good for you.

			** is OK to use even when costing the sort avoidance path for
			** the inner table.  This is probably OK, since all we use
			** from the outer cost is the row count.
			*/
			outerCost =
				optimizableList.getOptimizable(
					proposedJoinOrder[joinPosition - 1]).
						getBestAccessPath().getCostEstimate();
		}

		Optimizable optimizable = optimizableList.getOptimizable(proposedJoinOrder[joinPosition]);

		/*
		** Don't consider non-feasible join strategies.
		*/
		if ( ! optimizable.feasibleJoinStrategy(predicateList, this))
		{
			return;
		}

		/* Cost the optimizable at the current join position */
		optimizable.optimizeIt(this,
							   predicateList,
							   outerCost,
							   currentRowOrdering);
	}

	/**
	 * @see org.apache.derby.iapi.sql.compile.Optimizer#costOptimizable
	 *
	 * @exception StandardException		Thrown on error
	 */
	public void	costOptimizable(Optimizable optimizable,
								TableDescriptor td, 
								ConglomerateDescriptor cd,
								OptimizablePredicateList predList,
								CostEstimate outerCost)
			throws StandardException
	{
		/*
		** Don't consider non-feasible join strategies.
		*/
		if ( ! optimizable.feasibleJoinStrategy(predList, this))
		{
			return;
		}

		/*
		** Classify the predicates according to the given conglomerate.
		** The predicates are classified as start keys, stop keys,
		** qualifiers, and none-of-the-above.  They are also ordered
		** to match the ordering of columns in keyed conglomerates (no
		** ordering is done for heaps).
		*/
		// if (predList != null)
		// 	predList.classify(optimizable, cd);

		if (ruleBasedOptimization)
		{
			ruleBasedCostOptimizable(optimizable,
										td,
										cd,
										predList,
										outerCost);
		}
		else
		{
			costBasedCostOptimizable(optimizable,
										td,
										cd,
										predList,
										outerCost);
		}
	}

	/**
	 * This method decides whether the given conglomerate descriptor is
	 * cheapest based on rules, rather than based on cost estimates.
	 * The rules are:
	 *
	 *		Covering matching indexes are preferred above all
	 *		Non-covering matching indexes are next in order of preference
	 *		Covering non-matching indexes are next in order of preference
	 *		Heap scans are next in order of preference
	 *		Non-covering, non-matching indexes are last in order of
	 *		preference.
	 *
	 * In the current language architecture, there will always be a
	 * heap, so a non-covering, non-matching index scan will never be
	 * chosen.  However, the optimizer may see a non-covering, non-matching
	 * index first, in which case it will choose it temporarily as the
	 * best conglomerate seen so far.
	 *
	 * NOTE: This method sets the cost in the optimizable, even though it
	 * doesn't use the cost to determine which access path to choose.  There
	 * are two reasons for this: the cost might be needed to determine join
	 * order, and the cost information is copied to the query plan.
	 */
	private void ruleBasedCostOptimizable(Optimizable optimizable,
											TableDescriptor td,
											ConglomerateDescriptor cd,
											OptimizablePredicateList predList,
											CostEstimate outerCost)
				throws StandardException
	{
		/* CHOOSE BEST CONGLOMERATE HERE */
		ConglomerateDescriptor	conglomerateDescriptor = null;
		ConglomerateDescriptor	bestConglomerateDescriptor = null;
		AccessPath bestAp = optimizable.getBestAccessPath();
		int lockMode = optimizable.getCurrentAccessPath().getLockMode();


		/*
		** If the current conglomerate better than the best so far?
		** The pecking order is:
		**		o  covering index useful for predicates
		**			(if there are predicates)
		**		o  index useful for predicates (if there are predicates)
		**		o  covering index
		**		o  table scan
		*/

		/*
		** If there is more than one conglomerate descriptor
		** choose any index that is potentially useful.
		*/
		if (predList != null &&
			predList.useful(optimizable, cd))
		{
			/*
			** Do not let a non-covering matching index scan supplant a
			** covering matching index scan.
			*/
			boolean newCoveringIndex = optimizable.isCoveringIndex(cd);
			if ( ( ! bestAp.getCoveringIndexScan()) ||
			    bestAp.getNonMatchingIndexScan() ||
				newCoveringIndex )
			{
				bestAp.setCostEstimate(
					estimateTotalCost(
									predList,
									cd,
									outerCost,
									optimizable
									)
								);
				bestAp.setConglomerateDescriptor(cd);
				bestAp.setNonMatchingIndexScan(false);
				bestAp.setCoveringIndexScan(newCoveringIndex);

				bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode());

				optimizable.rememberJoinStrategyAsBest(bestAp);
			}

			return;
		}

		/* Remember the "last" covering index.
		 * NOTE - Since we don't have costing, we just go for the
		 * last one since that's as good as any
		 */
		if (optimizable.isCoveringIndex(cd))
		{
			bestAp.setCostEstimate(
								estimateTotalCost(predList,
													cd,
													outerCost,
													optimizable)
								);
			bestAp.setConglomerateDescriptor(cd);
			bestAp.setNonMatchingIndexScan(true);
			bestAp.setCoveringIndexScan(true);

			bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode());

			optimizable.rememberJoinStrategyAsBest(bestAp);
			return;
		}

		/*
		** If this is the heap, and the best conglomerate so far is a
		** non-covering, non-matching index scan, pick the heap.
		*/
		if ( ( ! bestAp.getCoveringIndexScan()) &&
			 bestAp.getNonMatchingIndexScan() &&
			 ( ! cd.isIndex() )
		   )
		{
			bestAp.setCostEstimate(
									estimateTotalCost(predList,
														cd,
														outerCost,
														optimizable)
									);

			bestAp.setConglomerateDescriptor(cd);

			bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode());

			optimizable.rememberJoinStrategyAsBest(bestAp);

			/*
			** No need to set non-matching index scan and covering
			** index scan, as these are already correct.
			*/
			return;
		}


		/*
		** If all else fails, and no conglomerate has been picked yet,
		** pick this one.
		*/
		bestConglomerateDescriptor = bestAp.getConglomerateDescriptor();
		if (bestConglomerateDescriptor == null)
		{
			bestAp.setCostEstimate(
									estimateTotalCost(predList,
									 					cd,
														outerCost,
														optimizable)
									);

			bestAp.setConglomerateDescriptor(cd);

			/*
			** We have determined above that this index is neither covering
			** nor matching.
			*/
			bestAp.setCoveringIndexScan(false);
			bestAp.setNonMatchingIndexScan(cd.isIndex());

			bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode());

			optimizable.rememberJoinStrategyAsBest(bestAp);
		}

		return;
	}

	/**
	 * This method decides whether the given conglomerate descriptor is
	 * cheapest based on cost, rather than based on rules.  It compares
	 * the cost of using the given ConglomerateDescriptor with the cost
	 * of using the best ConglomerateDescriptor so far.
	 */
	private void costBasedCostOptimizable(Optimizable optimizable,
											TableDescriptor td,
											ConglomerateDescriptor cd,
											OptimizablePredicateList predList,
											CostEstimate outerCost)
				throws StandardException
	{
		CostEstimate estimatedCost = estimateTotalCost(predList,
														cd,
														outerCost,
														optimizable);

		// Before considering the cost, make sure we set the optimizable's
		// "current" cost to be the one that we found.  Doing this allows
		// us to compare "current" with "best" later on to find out if
		// the "current" plan is also the "best" one this round--if it's
		// not then we'll have to revert back to whatever the best plan is.
		// That check is performed in getNextDecoratedPermutation() of
		// this class.
		optimizable.getCurrentAccessPath().setCostEstimate(estimatedCost);

		/*
		** Skip this access path if it takes too much memory.
		**
		** NOTE: The default assumption here is that the number of rows in
		** a single scan is the total number of rows divided by the number
		** of outer rows.  The optimizable may over-ride this assumption.
		*/
		if( ! optimizable.memoryUsageOK( estimatedCost.rowCount() / outerCost.rowCount(), maxMemoryPerTable))
		{
			if (optimizerTrace)
			{
				trace(SKIPPING_DUE_TO_EXCESS_MEMORY, 0, 0, 0.0, null);
			}
			return;
		}

		/* Pick the cheapest cost for this particular optimizable. */
		AccessPath ap = optimizable.getBestAccessPath();
		CostEstimate bestCostEstimate = ap.getCostEstimate();

		if ((bestCostEstimate == null) ||
			bestCostEstimate.isUninitialized() ||
			(estimatedCost.compare(bestCostEstimate) < 0))
		{
			ap.setConglomerateDescriptor(cd);
			ap.setCostEstimate(estimatedCost);
			ap.setCoveringIndexScan(optimizable.isCoveringIndex(cd));

			/*
			** It's a non-matching index scan either if there is no
			** predicate list, or nothing in the predicate list is useful
			** for limiting the scan.
			*/
			ap.setNonMatchingIndexScan(
									(predList == null) ||
									( ! ( predList.useful(optimizable, cd) ) )
									);
			ap.setLockMode(optimizable.getCurrentAccessPath().getLockMode());
			optimizable.rememberJoinStrategyAsBest(ap);
		}

		/*
		** Keep track of the best sort-avoidance path if there is a
		** required row ordering.
		*/
		if (requiredRowOrdering != null)
		{
			/*
			** The current optimizable can avoid a sort only if the
			** outer one does, also (if there is an outer one).
			*/
			if (joinPosition == 0 ||
				optimizableList.getOptimizable(
										proposedJoinOrder[joinPosition - 1]).
												considerSortAvoidancePath())
			{
				/*
				** There is a required row ordering - does the proposed access
				** path avoid a sort?
				*/
				if (requiredRowOrdering.sortRequired(currentRowOrdering,
														assignedTableMap)
										== RequiredRowOrdering.NOTHING_REQUIRED)
				{
					ap = optimizable.getBestSortAvoidancePath();
					bestCostEstimate = ap.getCostEstimate();

					/* Is this the cheapest sort-avoidance path? */
					if ((bestCostEstimate == null) ||
						bestCostEstimate.isUninitialized() ||
						(estimatedCost.compare(bestCostEstimate) < 0))
					{
						ap.setConglomerateDescriptor(cd);
						ap.setCostEstimate(estimatedCost);
						ap.setCoveringIndexScan(
											optimizable.isCoveringIndex(cd));

						/*
						** It's a non-matching index scan either if there is no
						** predicate list, or nothing in the predicate list is
						** useful for limiting the scan.
						*/
						ap.setNonMatchingIndexScan(
										(predList == null) ||
										( ! (predList.useful(optimizable, cd)) )
										);
						ap.setLockMode(
							optimizable.getCurrentAccessPath().getLockMode());
						optimizable.rememberJoinStrategyAsBest(ap);
						optimizable.rememberSortAvoidancePath();

						/*
						** Remember the current row ordering as best
						*/
						currentRowOrdering.copy(bestRowOrdering);
					}
				}
			}
		}
	}

	/**
	 * This is the version of costOptimizable for non-base-tables.
	 *
	 * @see Optimizer#considerCost
	 *
	 * @exception StandardException		Thrown on error
	 */
	public void	considerCost(Optimizable optimizable,
								OptimizablePredicateList predList,
								CostEstimate estimatedCost,
								CostEstimate outerCost)
			throws StandardException
	{
		/*
		** Don't consider non-feasible join strategies.
		*/
		if ( ! optimizable.feasibleJoinStrategy(predList, this))
		{
			return;
		}

		// Before considering the cost, make sure we set the optimizable's
		// "current" cost to be the one that we received.  Doing this allows
		// us to compare "current" with "best" later on to find out if
		// the "current" plan is also the "best" one this round--if it's
		// not then we'll have to revert back to whatever the best plan is.
		// That che