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 mi...@apache.org on 2006/09/21 03:28:50 UTC
svn commit: r448426 - in
/db/derby/code/branches/10.1/java/engine/org/apache/derby:
iapi/sql/compile/ impl/sql/compile/
Author: mikem
Date: Wed Sep 20 18:28:50 2006
New Revision: 448426
URL: http://svn.apache.org/viewvc?view=rev&rev=448426
Log:
DERBY-1315
contributed by Army Brown
patch: d1315_10_1_merge.patch
Backporting fix from trunk to 10.1 line using contributed patch that resolves
merge conflicts.
DERBY-1315 This patch adds a small amount of logic to remove entries from an Opt
imizable'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/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromTable.java
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java
Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java?view=diff&rev=448426&r1=448425&r2=448426
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java Wed Sep 20 18:28:50 2006
@@ -255,15 +255,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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromTable.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromTable.java?view=diff&rev=448426&r1=448425&r2=448426
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromTable.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromTable.java Wed Sep 20 18:28:50 2006
@@ -100,13 +100,17 @@
private boolean considerSortAvoidancePath;
- // Set of optimizer->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.
- HashMap optimizerToBestPlanMap;
+ /**
+ 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 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 bestPlanMap;
//this flag tells you if all the columns from this table are projected using * from it.
//Used by replication enabled databases where the target-only view failure is detected
@@ -124,6 +128,11 @@
allColumnsProjected = flag;
}
+ /** 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.
*
@@ -135,7 +144,7 @@
this.correlationName = (String) correlationName;
this.tableProperties = (Properties) tableProperties;
tableNumber = -1;
- optimizerToBestPlanMap = null;
+ bestPlanMap = null;
}
/**
@@ -170,7 +179,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,
@@ -520,25 +529,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
@@ -553,7 +574,7 @@
}
ap.copy(bestPath);
- optimizerToBestPlanMap.put(planKey, ap);
+ bestPlanMap.put(planKey, ap);
return;
}
@@ -563,10 +584,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.
@@ -608,23 +629,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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java?view=diff&rev=448426&r1=448425&r2=448426
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java Wed Sep 20 18:28:50 2006
@@ -180,7 +180,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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java?view=diff&rev=448426&r1=448425&r2=448426
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java Wed Sep 20 18:28:50 2006
@@ -352,6 +352,7 @@
trace(NO_TABLES, 0, 0, 0.0, null);
}
+ endOfRoundCleanup();
return false;
}
@@ -936,7 +937,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;
@@ -1089,7 +1090,9 @@
rewindJoinOrder();
joinPosition = -1;
}
+
permuteState = READY_TO_JUMP;
+ endOfRoundCleanup();
return false;
}
}
@@ -1126,6 +1129,7 @@
return true;
}
+ endOfRoundCleanup();
return false;
}
@@ -1139,7 +1143,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;
}
@@ -1148,6 +1152,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.
@@ -1265,7 +1288,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())
@@ -1275,10 +1298,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
@@ -2333,30 +2363,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.
@@ -2398,13 +2437,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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java?view=diff&rev=448426&r1=448425&r2=448426
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java Wed Sep 20 18:28:50 2006
@@ -303,7 +303,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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java?view=diff&rev=448426&r1=448425&r2=448426
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java Wed Sep 20 18:28:50 2006
@@ -166,16 +166,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()
@@ -186,12 +187,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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java?view=diff&rev=448426&r1=448425&r2=448426
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java Wed Sep 20 18:28:50 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);
}
}
Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java?view=diff&rev=448426&r1=448425&r2=448426
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java Wed Sep 20 18:28:50 2006
@@ -246,7 +246,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);
leftResultSet = optimizeSource(
optimizer,