optimizerimpl.java

derby database source code.good for you.

/*

   Derby - Class org.apache.derby.impl.sql.compile.OptimizerImpl

   Copyright 1997, 2004 The Apache Software Foundation or its licensors, as applicable.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.

 */

package org.apache.derby.impl.sql.compile;

import org.apache.derby.iapi.services.sanity.SanityManager;

import org.apache.derby.iapi.error.StandardException;

import org.apache.derby.iapi.sql.compile.JoinStrategy;
import org.apache.derby.iapi.sql.compile.Optimizable;
import org.apache.derby.iapi.sql.compile.OptimizableList;
import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
import org.apache.derby.iapi.sql.compile.Optimizer;
import org.apache.derby.iapi.sql.compile.CostEstimate;
import org.apache.derby.iapi.sql.compile.RequiredRowOrdering;
import org.apache.derby.iapi.sql.compile.RowOrdering;
import org.apache.derby.iapi.sql.compile.AccessPath;

import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;

import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
import org.apache.derby.iapi.sql.dictionary.DataDictionary;
import org.apache.derby.iapi.sql.dictionary.TableDescriptor;

import org.apache.derby.catalog.IndexDescriptor;
import org.apache.derby.iapi.reference.SQLState;

import org.apache.derby.iapi.util.JBitSet;
import org.apache.derby.iapi.util.StringUtil;

import java.util.Properties;
import java.util.HashMap;

/**
 * This will be the Level 1 Optimizer.
 * RESOLVE - it's a level 0 optimizer right now.
 * Current State:
 *	o  No costing services
 *	o  We can only cost a derived table with a join once.
 *  
 * Optimizer uses OptimizableList to keep track of the best join order as it
 * builds it.  For each available slot in the join order, we cost all of the
 * Optimizables from that slot til the end of the OptimizableList.  Later,
 * we will choose the best Optimizable for that slot and reorder the list
 * accordingly.
 * In order to do this, we probably need to move the temporary pushing and
 * pulling of join clauses into Optimizer, since the logic will be different
 * for other implementations.  (Of course, we're not pushing and pulling join
 * clauses between permutations yet.)
 */

public class OptimizerImpl implements Optimizer 
{

	DataDictionary			 dDictionary;
	/* The number of tables in the query as a whole.  (Size of bit maps.) */
	int						 numTablesInQuery;
	/* The number of optimizables in the list to optimize */
	int						 numOptimizables;

	/* Bit map of tables that have already been assigned to slots.
	 * Useful for pushing join clauses as slots are assigned.
	 */
	protected JBitSet		 assignedTableMap;
	protected OptimizableList optimizableList;
	OptimizablePredicateList predicateList;
	JBitSet					 nonCorrelatedTableMap;

	protected int[]			 proposedJoinOrder;
	protected int[]					 bestJoinOrder;
	protected int			 joinPosition;
	boolean					 desiredJoinOrderFound;

	/* This implements a state machine to jump start to a appearingly good join
	 * order, when the number of tables is high, and the optimization could take
	 * a long time.  A good start can prune better, and timeout sooner.  Otherwise,
	 * it may take forever to exhaust or timeout (see beetle 5870).  Basically after
	 * we jump, we walk the high part, then fall when we reach the peak, finally we
	 * walk the low part til where we jumped to.
	 */
	private static final int NO_JUMP = 0;
	private static final int READY_TO_JUMP = 1;
	private static final int JUMPING = 2;
	private static final int WALK_HIGH = 3;
	private static final int WALK_LOW = 4;
	private int				 permuteState;
	private int[]			 firstLookOrder;

	private boolean			 ruleBasedOptimization;

	private CostEstimateImpl outermostCostEstimate;
	protected CostEstimateImpl currentCost;
	protected CostEstimateImpl currentSortAvoidanceCost;
	protected CostEstimateImpl bestCost;

	protected long			 timeOptimizationStarted;
	protected long			 currentTime;
	protected boolean		 timeExceeded;
	private boolean			 noTimeout;
	private boolean 		 useStatistics;
	private int				 tableLockThreshold;

	private JoinStrategy[]	joinStrategies;

	protected RequiredRowOrdering	requiredRowOrdering;

	private boolean			 foundABestPlan;

	protected CostEstimate sortCost;

	private RowOrdering currentRowOrdering = new RowOrderingImpl();
	private RowOrdering bestRowOrdering = new RowOrderingImpl();

	private boolean	conglomerate_OneRowResultSet;

	// optimizer trace
	protected boolean optimizerTrace;
	protected boolean optimizerTraceHtml;

	// max memory use per table
	protected int maxMemoryPerTable;

	// Whether or not we need to reload the best plan for an Optimizable
	// when we "pull" it.  If the latest complete join order was the
	// best one so far, then the Optimizable will already have the correct
	// best plan loaded so we don't need to do the extra work.  But if
	// the most recent join order was _not_ the best, then this flag tells
	// us that we need to reload the best plan when pulling.
	private boolean reloadBestPlan;

	// Set of optimizer->bestJoinOrder mappings used to keep track of which
	// of this OptimizerImpl's "bestJoinOrder"s was the best with respect to a
	// a specific outer query; the outer query is represented by an instance
	// of Optimizer.  Each outer query could potentially have a different
	// idea of what this OptimizerImpl's "best join order" is, so we have
	// to keep track of them all.
	private HashMap savedJoinOrders;

	// Value used to figure out when/if we've timed out for this
	// Optimizable.
	protected double timeLimit;

	// Cost estimate for the final "best join order" that we chose--i.e.
	// the one that's actually going to be generated.
	CostEstimate finalCostEstimate;

	// Have we already delayed timeout for the current round of
	// optimization?  We need this flag to make sure we don't
	// infinitely delay the timeout for the current round.
	private boolean alreadyDelayedTimeout;
	
	protected  OptimizerImpl(OptimizableList optimizableList, 
				  OptimizablePredicateList predicateList,
				  DataDictionary dDictionary,
				  boolean ruleBasedOptimization,
				  boolean noTimeout,
				  boolean useStatistics,
				  int maxMemoryPerTable,
				  JoinStrategy[] joinStrategies,
				  int tableLockThreshold,
				  RequiredRowOrdering requiredRowOrdering,
				  int numTablesInQuery)
		throws StandardException
	{
		if (SanityManager.DEBUG) {
			SanityManager.ASSERT(optimizableList != null,
							 "optimizableList is not expected to be null");
		}

		outermostCostEstimate =  getNewCostEstimate(0.0d, 1.0d, 1.0d);

		currentCost = getNewCostEstimate(0.0d, 0.0d, 0.0d);

		currentSortAvoidanceCost = getNewCostEstimate(0.0d, 0.0d, 0.0d);

		bestCost = getNewCostEstimate(Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);

		// Verify that any Properties lists for user overrides are valid
		optimizableList.verifyProperties(dDictionary);

		this.numTablesInQuery = numTablesInQuery;
		numOptimizables = optimizableList.size();
		proposedJoinOrder = new int[numOptimizables];
		if (numTablesInQuery > 6)
		{
			permuteState = READY_TO_JUMP;
			firstLookOrder = new int[numOptimizables];
		}
		else
			permuteState = NO_JUMP;

		/* Mark all join positions as unused */
		for (int i = 0; i < numOptimizables; i++)
			proposedJoinOrder[i] = -1;

		bestJoinOrder = new int[numOptimizables];
		joinPosition = -1;
		this.optimizableList = optimizableList;
		this.predicateList = predicateList;
		this.dDictionary = dDictionary;
		this.ruleBasedOptimization = ruleBasedOptimization;
		this.noTimeout = noTimeout;
		this.maxMemoryPerTable = maxMemoryPerTable;
		this.joinStrategies = joinStrategies;
		this.tableLockThreshold = tableLockThreshold;
		this.requiredRowOrdering = requiredRowOrdering;
		this.useStatistics = useStatistics;

		/* initialize variables for tracking permutations */
		assignedTableMap = new JBitSet(numTablesInQuery);

		/*
		** Make a map of the non-correlated tables, which are the tables
		** in the list of Optimizables we're optimizing.  An reference
		** to a table that is not defined in the list of Optimizables
		** is presumed to be correlated.
		*/
		nonCorrelatedTableMap = new JBitSet(numTablesInQuery);
		for (int tabCtr = 0; tabCtr < numOptimizables; tabCtr++)
		{
			Optimizable	curTable = optimizableList.getOptimizable(tabCtr);
			nonCorrelatedTableMap.or(curTable.getReferencedTableMap());
		}

		/* Get the time that optimization starts */
		timeOptimizationStarted = System.currentTimeMillis();
		reloadBestPlan = false;
		savedJoinOrders = null;
		timeLimit = Double.MAX_VALUE;
		alreadyDelayedTimeout = false;
	}

	/**
	 * This method is called before every "round" of optimization, where
	 * we define a "round" to be the period between the last time a call to
	 * getOptimizer() (on either a ResultSetNode or an OptimizerFactory)
	 * returned _this_ OptimizerImpl and the time a call to this OptimizerImpl's
	 * getNextPermutation() method returns FALSE.  Any re-initialization
	 * of state that is required before each round should be done in this
	 * method.
	 */
	public void prepForNextRound()
	{
		// We initialize reloadBestPlan to false so that if we end up
		// pulling an Optimizable before we find a best join order
		// (which can happen if there is no valid join order for this
		// round) we won't inadvertently reload the best plans based
		// on some previous round.
		reloadBestPlan = false;

		/* Since we're preparing for a new round, we have to clear
		 * out the "bestCost" from the previous round to ensure that,
		 * when this round of optimizing is done, bestCost will hold
		 * the best cost estimate found _this_ round, if there was
		 * one.  If there was no best cost found (which can happen if
		 * there is no feasible join order) then bestCost will remain
		 * at Double.MAX_VALUE.  Then when outer queries check the
		 * cost and see that it is so high, they will reject whatever
		 * outer join order they're trying in favor of something that's
		 * actually valid (and therefore cheaper).
		 *
		 * Note that we do _not_ reset the "foundABestPlan" variable nor
		 * the "bestJoinOrder" array.  This is because it's possible that
		 * a "best join order" may not exist for the current round, in
		 * which case this OptimizerImpl must know whether or not it found
		 * a best join order in a previous round (foundABestPlan) and if
		 * so what the corresponding join order was (bestJoinOrder).  This
		 * information is required so that the correct query plan can be
		 * generated after optimization is complete, even if that best
		 * plan was not found in the most recent round.
		 */
		bestCost = getNewCostEstimate(
			Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);

		/* If we have predicates that were pushed down to this OptimizerImpl
		 * from an outer query, then we reset the timeout state to prepare for
		 * the next round of optimization.  Otherwise if we timed out during
		 * a previous round and then we get here for another round, we'll
		 * immediately "timeout" again before optimizing any of the Optimizables
		 * in our list.  This is okay if we don't have any predicates from
		 * outer queries because in that case the plan we find this round
		 * will be the same one we found in the previous round, in which
		 * case there's no point in resetting the timeout state and doing
		 * the work a second time.  But if we have predicates from an outer
		 * query, those predicates could help us find a much better plan
		 * this round than we did in previous rounds--so we reset the timeout
		 * state to ensure that we have a chance to consider plans that
		 * can take advantage of the pushed predicates.
		 */
		boolean resetTimer = false;
		if ((predicateList != null) && (predicateList.size() > 0))
		{
			for (int i = predicateList.size() - 1; i >= 0; i--)
			{
				// If the predicate is "scoped", then we know it was pushed
				// here from an outer query.
				if (((Predicate)predicateList.
					getOptPredicate(i)).isScopedForPush())
				{
					resetTimer = true;
					break;
				}
			}
		}

		if (resetTimer)
		{
			timeOptimizationStarted = System.currentTimeMillis();
			timeExceeded = false;
		}

		alreadyDelayedTimeout = false;
	}

    public int getMaxMemoryPerTable()
    {
        return maxMemoryPerTable;
    }
    
	/**
	 * @see Optimizer#getNextPermutation
	 *
	 * @exception StandardException		Thrown on error
	 */
	public boolean getNextPermutation()
			throws StandardException
	{
		/* Don't get any permutations if there is nothing to optimize */
		if (numOptimizables < 1)
		{
			if (optimizerTrace)
			{
				trace(NO_TABLES, 0, 0, 0.0, null);
			}

			return false;
		}

		/* Make sure that all Optimizables init their access paths.
		 * (They wait until optimization since the access path
		 * references the optimizer.)
		 */
		optimizableList.initAccessPaths(this);

		/*
		** Experiments show that optimization time only starts to
		** become a problem with seven tables, so only check for
		** too much time if there are more than seven tables.
		** Also, don't check for too much time if user has specified
		** no timeout.
		*/
		if ( ( ! timeExceeded ) &&
			 (numTablesInQuery > 6)  &&
			 ( ! noTimeout) )
		{
			/*
			** Stop optimizing if the time spent optimizing is greater than
			** the current best cost.
			*/
			currentTime = System.currentTimeMillis();
			timeExceeded = (currentTime - timeOptimizationStarted) > timeLimit;

			if (optimizerTrace && timeExceeded)
			{
				trace(TIME_EXCEEDED, 0, 0, 0.0, null);
			}
		}

		/*
		 * It's possible that we can end up with an uninitialized cost after
		 * this round of optimization if there's no feasible join order.  In
		 * that case the following call to "isUninitialized()" will repeatedly
		 * return true, which could cause us to delay the timeout indefinitely.
		 * For this reason we have the "alreadyDelayedTimeout" flag, which we
		 * set the first time through and then, if we get here again for a
		 * complete join order in the same round, we skip the "delay" and just
		 * allow the timeout to occur.  The check for "if we get here again"
		 * is done via the alreadyDelayedTimeout flag, which is reset before