You are viewing a plain text version of this content. The canonical link for it is here.
Posted to derby-commits@db.apache.org by dj...@apache.org on 2006/09/01 00:57:33 UTC
svn commit: r439083 - in /db/derby/code/trunk/java/engine/org/apache/derby:
iapi/sql/compile/ impl/sql/compile/
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);
}
}