db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From d..@apache.org
Subject svn commit: r439083 - in /db/derby/code/trunk/java/engine/org/apache/derby: iapi/sql/compile/ impl/sql/compile/
Date Thu, 31 Aug 2006 22:57:33 GMT
Author: djd
Date: Thu Aug 31 15:57:32 2006
New Revision: 439083

URL: http://svn.apache.org/viewvc?rev=439083&view=rev
Log:
DERBY-1315 This patch adds a small amount of logic to remove entries from an Optimizable's
"best plan" HashMap when they are no longer needed. For more on when this is possible, see
the discussion here:
http://article.gmane.org/gmane.comp.apache.db.derby.devel/26051
Patch contributed by "A B" qozinx@gmail.com

Modified:
    db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromTable.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java

Modified: db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java?rev=439083&r1=439082&r2=439083&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java Thu
Aug 31 15:57:32 2006
@@ -253,15 +253,15 @@
 	 * Optimizable saved which "best plan", and allows us to load the
 	 * appropriate plans after each round of optimization.
 	 * 
-	 * @param doAdd True if we're saving a best plan for the OptimizerImpl/
-	 *  Optimizable; false if we're loading/retrieving the best plan.
+	 * @param action Indicates whether we're adding, loading, or removing
+	 *  a best plan for the OptimizerImpl/Optimizable.
 	 * @param planKey Object to use as the map key when adding/looking up
 	 *  a plan.  If it is an instance of OptimizerImpl then it corresponds
 	 *  to an outer query; otherwise it's some Optimizable above this
 	 *  Optimizable that could potentially reject plans chosen by the
 	 *  OptimizerImpl to which this Optimizable belongs.
 	 */
-	public void addOrLoadBestPlanMapping(boolean doAdd,
+	public void updateBestPlanMap(short action,
 		Object planKey) throws StandardException;
 
 	/**

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromTable.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromTable.java?rev=439083&r1=439082&r2=439083&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromTable.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromTable.java Thu Aug
31 15:57:32 2006
@@ -102,14 +102,21 @@
 	private boolean considerSortAvoidancePath;
 
 	/**
-	 Set of optimizer->trulyTheBestAccessPath mappings used to keep track
+	 Set of object->trulyTheBestAccessPath mappings used to keep track
 	 of which of this Optimizable's "trulyTheBestAccessPath" was the best
-	 with respect to 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 Optimizable's "best access path" is, so
-	 we have to keep track of them all.
+	 with respect to a specific outer query or ancestor node.  In the case
+	 of an outer query, the object key will be an instance of OptimizerImpl.
+	 In the case of an ancestor node, the object key will be that node itself.
+	 Each ancestor node or outer query could potentially have a different
+	 idea of what this Optimizable's "best access path" is, so we have to
+	 keep track of them all.
 	*/
-	private HashMap optimizerToBestPlanMap;
+	private HashMap bestPlanMap;
+
+	/** Operations that can be performed on bestPlanMap. */
+	protected static final short REMOVE_PLAN = 0;
+	protected static final short ADD_PLAN = 1;
+	protected static final short LOAD_PLAN = 2;
 
 	/**
 	 * Initializer for a table in a FROM list.
@@ -122,7 +129,7 @@
 		this.correlationName = (String) correlationName;
 		this.tableProperties = (Properties) tableProperties;
 		tableNumber = -1;
-		optimizerToBestPlanMap = null;
+		bestPlanMap = null;
 	}
 
 	/**
@@ -157,7 +164,7 @@
 		// current plans using "this" node as the key.  If needed, we'll
 		// then make the call to revert the plans in OptimizerImpl's
 		// getNextDecoratedPermutation() method.
-		addOrLoadBestPlanMapping(true, this);
+		updateBestPlanMap(ADD_PLAN, this);
 
 		CostEstimate singleScanCost = estimateCost(predList,
 												(ConglomerateDescriptor) null,
@@ -507,25 +514,37 @@
 		return absolutePosition;
 	}
 
-	/** @see Optimizable#addOrLoadBestPlanMapping */
-	public void addOrLoadBestPlanMapping(boolean doAdd,
+	/** @see Optimizable#updateBestPlanMap */
+	public void updateBestPlanMap(short action,
 		Object planKey) throws StandardException
 	{
+		if (action == REMOVE_PLAN)
+		{
+			if (bestPlanMap != null)
+			{
+				bestPlanMap.remove(planKey);
+				if (bestPlanMap.size() == 0)
+					bestPlanMap = null;
+			}
+
+			return;
+		}
+
 		AccessPath bestPath = getTrulyTheBestAccessPath();
 		AccessPathImpl ap = null;
-		if (doAdd)
+		if (action == ADD_PLAN)
 		{
 			// If we get to this method before ever optimizing this node, then
 			// there will be no best path--so there's nothing to do.
 			if (bestPath == null)
 				return;
 
-			// If the optimizerToBestPlanMap already exists, search for an
+			// If the bestPlanMap already exists, search for an
 			// AccessPath for the received key and use that if we can.
-			if (optimizerToBestPlanMap == null)
-				optimizerToBestPlanMap = new HashMap();
+			if (bestPlanMap == null)
+				bestPlanMap = new HashMap();
 			else
-				ap = (AccessPathImpl)optimizerToBestPlanMap.get(planKey);
+				ap = (AccessPathImpl)bestPlanMap.get(planKey);
 
 			// If we don't already have an AccessPath for the key,
 			// create a new one.  If the key is an OptimizerImpl then
@@ -540,7 +559,7 @@
 			}
 
 			ap.copy(bestPath);
-			optimizerToBestPlanMap.put(planKey, ap);
+			bestPlanMap.put(planKey, ap);
 			return;
 		}
 
@@ -550,10 +569,10 @@
 		// If we don't have any plans saved, then there's nothing to load.
 		// This can happen if the key is an OptimizerImpl that tried some
 		// join order for which there was no valid plan.
-		if (optimizerToBestPlanMap == null)
+		if (bestPlanMap == null)
 			return;
 
-		ap = (AccessPathImpl)optimizerToBestPlanMap.get(planKey);
+		ap = (AccessPathImpl)bestPlanMap.get(planKey);
 
 		// It might be the case that there is no plan stored for
 		// the key, in which case there's nothing to load.
@@ -595,23 +614,23 @@
 		// Since we just set trulyTheBestAccessPath for the current
 		// join order of the received optimizer, take note of what
 		// that path is, in case we need to "revert" back to this
-		// path later.  See Optimizable.addOrLoadBestPlanMapping().
+		// path later.  See Optimizable.updateBestPlanMap().
 		// Note: Since this call descends all the way down to base
 		// tables, it can be relatively expensive when we have deeply
 		// nested subqueries.  So in an attempt to save some work, we
 		// skip the call if this node is a ProjectRestrictNode whose
 		// child is an Optimizable--in that case the ProjectRestrictNode
 		// will in turn call "rememberAsBest" on its child and so
-		// the required call to addOrLoadBestPlanMapping() will be
+		// the required call to updateBestPlanMap() will be
 		// made at that time.  If we did it here, too, then we would
 		// just end up duplicating the work.
 		if (!(this instanceof ProjectRestrictNode))
-			addOrLoadBestPlanMapping(true, optimizer);
+			updateBestPlanMap(ADD_PLAN, optimizer);
 		else
 		{
 			ProjectRestrictNode prn = (ProjectRestrictNode)this;
 			if (!(prn.getChildResult() instanceof Optimizable))
-				addOrLoadBestPlanMapping(true, optimizer);
+				updateBestPlanMap(ADD_PLAN, optimizer);
 		}
 		 
 		/* also store the name of the access path; i.e index name/constraint

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java?rev=439083&r1=439082&r2=439083&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java Thu Aug
31 15:57:32 2006
@@ -187,7 +187,7 @@
 		// current plans using "this" node as the key.  If needed, we'll
 		// then make the call to revert the plans in OptimizerImpl's
 		// getNextDecoratedPermutation() method.
-		addOrLoadBestPlanMapping(true, this);
+		updateBestPlanMap(ADD_PLAN, this);
 
 		/*
 		** RESOLVE: Most types of Optimizables only implement estimateCost(),

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java?rev=439083&r1=439082&r2=439083&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java Thu
Aug 31 15:57:32 2006
@@ -366,6 +366,7 @@
 				trace(NO_TABLES, 0, 0, 0.0, null);
 			}
 
+			endOfRoundCleanup();
 			return false;
 		}
 
@@ -980,7 +981,7 @@
 				** can be expensive if there are deeply nested subqueries.
 				*/
 				if (reloadBestPlan)
-					pullMe.addOrLoadBestPlanMapping(false, this);
+					pullMe.updateBestPlanMap(FromTable.LOAD_PLAN, this);
 
 				/* Mark current join position as unused */
 				proposedJoinOrder[joinPosition] = -1;
@@ -1133,7 +1134,9 @@
 						rewindJoinOrder();
 						joinPosition = -1;
 					}
+
 					permuteState = READY_TO_JUMP;
+					endOfRoundCleanup();
 					return false;
 				}
 			}
@@ -1170,6 +1173,7 @@
 			return true;
 		}
 
+		endOfRoundCleanup();
 		return false;
 	}
 
@@ -1183,7 +1187,7 @@
 									proposedJoinOrder[joinPosition]);
 			pullMe.pullOptPredicates(predicateList);
 			if (reloadBestPlan)
-				pullMe.addOrLoadBestPlanMapping(false, this);
+				pullMe.updateBestPlanMap(FromTable.LOAD_PLAN, this);
 			proposedJoinOrder[joinPosition] = -1;
 			if (joinPosition == 0) break;
 		}
@@ -1192,6 +1196,25 @@
 		assignedTableMap.clearAll();
 	}
 
+	/**
+	 * Do any work that needs to be done after the current round
+	 * of optimization has completed.  For now this just means walking
+	 * the subtrees for each optimizable and removing the "bestPlan"
+	 * that we saved (w.r.t to this OptimizerImpl) from all of the
+	 * nodes.  If we don't do this post-optimization cleanup we
+	 * can end up consuming a huge amount of memory for deeply-
+	 * nested queries, which can lead to OOM errors.  DERBY-1315.
+	 */
+	private void endOfRoundCleanup()
+		throws StandardException
+	{
+		for (int i = 0; i < numOptimizables; i++)
+		{
+			optimizableList.getOptimizable(i).
+				updateBestPlanMap(FromTable.REMOVE_PLAN, this);
+		}
+	}
+
 	/*
 	** Push predicates from this optimizer's list to the given optimizable,
 	** as appropriate given the outer tables.
@@ -1309,7 +1332,7 @@
 			if (curOpt.getBestAccessPath().getCostEstimate().compare(
 				curOpt.getCurrentAccessPath().getCostEstimate()) != 0)
 			{
-				curOpt.addOrLoadBestPlanMapping(false, curOpt);
+				curOpt.updateBestPlanMap(FromTable.LOAD_PLAN, curOpt);
 			}
 			else if (curOpt.getBestAccessPath().getCostEstimate().rowCount() <
 				curOpt.getCurrentAccessPath().getCostEstimate().rowCount())
@@ -1319,10 +1342,17 @@
 				// 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);
+				curOpt.updateBestPlanMap(FromTable.LOAD_PLAN, curOpt);
 			}
 		}
 
+		/* If we needed to revert plans for curOpt, we just did it above.
+		 * So we no longer need to keep the previous best plan--and in fact,
+		 * keeping it can lead to extreme memory usage for very large
+		 * queries.  So delete the stored plan for curOpt. DERBY-1315.
+		 */
+		curOpt.updateBestPlanMap(FromTable.REMOVE_PLAN, 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
@@ -2373,30 +2403,39 @@
 	public boolean useStatistics() { return useStatistics && optimizableList.useStatistics();
}
 
 	/**
-	 * Remember the current best join order as the best one for
-	 * some outer query, represented by another OptimizerImpl. Then
+	 * Process (i.e. add, load, or remove) current best join order as the
+	 * best one for some outer query or ancestor node, represented by another
+	 * OptimizerImpl or an instance of FromTable, respectively. Then
 	 * iterate through our optimizableList and tell each Optimizable
-	 * to remember its best plan with respect to the outer query.
-	 * See Optimizable.addOrLoadBestPlan() for more on why this is
-	 * necessary.
+	 * to do the same.  See Optimizable.updateBestPlan() for more on why
+	 * this is necessary.
 	 *
-	 * @param doAdd True if we're adding a mapping, false if we're loading.
+	 * @param action Indicates whether to add, load, or remove the plan
 	 * @param planKey Object to use as the map key when adding/looking up
 	 *  a plan.  If this is an instance of OptimizerImpl then it corresponds
 	 *  to an outer query; otherwise it's some Optimizable above this
 	 *  OptimizerImpl that could potentially reject plans chosen by this
 	 *  OptimizerImpl.
 	 */
-	protected void addOrLoadBestPlanMappings(boolean doAdd,
+	protected void updateBestPlanMaps(short action,
 		Object planKey) throws StandardException
 	{
-		// First we save this OptimizerImpl's best join order.  If there's
+		// First we process this OptimizerImpl's best join order.  If there's
 		// only one optimizable in the list, then there's only one possible
 		// join order, so don't bother.
 		if (numOptimizables > 1)
 		{
 			int [] joinOrder = null;
-			if (doAdd)
+			if (action == FromTable.REMOVE_PLAN)
+			{
+				if (savedJoinOrders != null)
+				{
+					savedJoinOrders.remove(planKey);
+					if (savedJoinOrders.size() == 0)
+						savedJoinOrders = null;
+				}
+			}
+			else if (action == FromTable.ADD_PLAN)
 			{
 				// If the savedJoinOrder map already exists, search for the
 				// join order for the target optimizer and reuse that.
@@ -2438,13 +2477,13 @@
 			}
 		}
 
-		// Now iterate through all Optimizables in this OptimizerImpl's list
-	 	// and add/load the best plan "mapping" for each one, as described in
-	 	// in Optimizable.addOrLoadBestPlanMapping().
+		// Now iterate through all Optimizables in this OptimizerImpl's
+	 	// list and add/load/remove the best plan "mapping" for each one,
+		// as described in in Optimizable.updateBestPlanMap().
 		for (int i = optimizableList.size() - 1; i >= 0; i--)
 		{
 			optimizableList.getOptimizable(i).
-				addOrLoadBestPlanMapping(doAdd, planKey);
+				updateBestPlanMap(action, planKey);
 		}
 	}
 

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java?rev=439083&r1=439082&r2=439083&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
Thu Aug 31 15:57:32 2006
@@ -304,7 +304,7 @@
 		// current plans using "this" node as the key.  If needed, we'll
 		// then make the call to revert the plans in OptimizerImpl's
 		// getNextDecoratedPermutation() method.
-		addOrLoadBestPlanMapping(true, this);
+		updateBestPlanMap(ADD_PLAN, this);
 
 		/* If the childResult is instanceof Optimizable, then we optimizeIt.
 		 * Otherwise, we are going into a new query block.  If the new query

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java?rev=439083&r1=439082&r2=439083&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
Thu Aug 31 15:57:32 2006
@@ -165,16 +165,17 @@
 	}
 
 	/**
-	 * @see Optimizable#addOrLoadBestPlanMapping
+	 * @see Optimizable#updateBestPlanMap
 	 *
-	 * Makes a call to add/load the plan mapping for this node,
+	 * Makes a call to add/load/remove a plan mapping for this node,
 	 * and then makes the necessary call to recurse on this node's
-	 * child, in order to ensure that we have a full plan mapped.
+	 * child, in order to ensure that we've handled the full plan
+	 * all the way down this node's subtree.
 	 */
-	public void addOrLoadBestPlanMapping(boolean doAdd,
+	public void updateBestPlanMap(short action,
 		Object planKey) throws StandardException
 	{
-		super.addOrLoadBestPlanMapping(doAdd, planKey);
+		super.updateBestPlanMap(action, planKey);
 
 		// Now walk the child.  Note that if the child is not an
 		// Optimizable and the call to child.getOptimizerImpl()
@@ -185,12 +186,12 @@
 		if (childResult instanceof Optimizable)
 		{
 			((Optimizable)childResult).
-				addOrLoadBestPlanMapping(doAdd, planKey);
+				updateBestPlanMap(action, planKey);
 		}
 		else if (childResult.getOptimizerImpl() != null)
 		{
 			childResult.getOptimizerImpl().
-				addOrLoadBestPlanMappings(doAdd, planKey);
+				updateBestPlanMaps(action, planKey);
 		}
 	}
 

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java?rev=439083&r1=439082&r2=439083&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
Thu Aug 31 15:57:32 2006
@@ -156,17 +156,17 @@
 	}
 
 	/**
-	 * @see Optimizable#addOrLoadBestPlanMapping
+	 * @see Optimizable#updateBestPlanMap
 	 *
-	 * Makes a call to add/load the plan mapping for this node,
+	 * Makes a call to add/load/remove the plan mapping for this node,
 	 * and then makes the necessary call to recurse on this node's
-	 * left and right child, in order to ensure that we have a
-	 * full plan mapped.
+	 * left and right child, in order to ensure that we've handled
+	 * the full plan all the way down this node's subtree. 
 	 */
-	public void addOrLoadBestPlanMapping(boolean doAdd,
+	public void updateBestPlanMap(short action,
 		Object planKey) throws StandardException
 	{
-		super.addOrLoadBestPlanMapping(doAdd, planKey);
+		super.updateBestPlanMap(action, planKey);
 
 		// Now walk the children.  Note that if either child is not
 		// an Optimizable and the call to child.getOptimizerImpl()
@@ -177,23 +177,23 @@
 		if (leftResultSet instanceof Optimizable)
 		{
 			((Optimizable)leftResultSet).
-				addOrLoadBestPlanMapping(doAdd, planKey);
+				updateBestPlanMap(action, planKey);
 		}
 		else if (leftResultSet.getOptimizerImpl() != null)
 		{
 			leftResultSet.getOptimizerImpl().
-				addOrLoadBestPlanMappings(doAdd, planKey);
+				updateBestPlanMaps(action, planKey);
 		}
 
 		if (rightResultSet instanceof Optimizable)
 		{
 			((Optimizable)rightResultSet).
-				addOrLoadBestPlanMapping(doAdd, planKey);
+				updateBestPlanMap(action, planKey);
 		}
 		else if (rightResultSet.getOptimizerImpl() != null)
 		{
 			rightResultSet.getOptimizerImpl().
-				addOrLoadBestPlanMappings(doAdd, planKey);
+				updateBestPlanMaps(action, planKey);
 		}
 	}
 



Mime
View raw message