Author: shawkins
Date: 2011-04-04 18:35:34 -0400 (Mon, 04 Apr 2011)
New Revision: 3059
Modified:
trunk/build/kits/jboss-container/teiid-releasenotes.html
trunk/engine/src/main/java/org/teiid/common/buffer/STree.java
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/PlanToProcessConverter.java
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/CapabilitiesUtil.java
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/JoinRegion.java
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/NewCalculateCostUtil.java
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleChooseDependent.java
trunk/engine/src/main/java/org/teiid/query/processor/relational/AccessNode.java
trunk/engine/src/main/java/org/teiid/query/processor/relational/DependentCriteriaProcessor.java
trunk/engine/src/main/java/org/teiid/query/processor/relational/EnhancedSortMergeJoinStrategy.java
trunk/engine/src/main/java/org/teiid/query/sql/lang/DependentSetCriteria.java
trunk/engine/src/test/java/org/teiid/common/buffer/TestSTree.java
trunk/engine/src/test/java/org/teiid/query/processor/TestDependentJoins.java
trunk/engine/src/test/java/org/teiid/query/processor/TestProcessor.java
trunk/engine/src/test/java/org/teiid/query/processor/relational/TestAccessNode.java
Log:
TEIID-1533 adding cost based back off of dependent joins
Modified: trunk/build/kits/jboss-container/teiid-releasenotes.html
===================================================================
--- trunk/build/kits/jboss-container/teiid-releasenotes.html 2011-04-04 22:34:47 UTC (rev
3058)
+++ trunk/build/kits/jboss-container/teiid-releasenotes.html 2011-04-04 22:35:34 UTC (rev
3059)
@@ -41,13 +41,14 @@
<LI><B>InterSystems Cache</B> - InterSystems Cache database translator
is now available to use as supported source under Teiid.
<LI><B>userRequestSourceConcurrency</B> - was added to control the
number of concurrent source queries allowed for each user request.
<LI><B>Memory Management Improvements</B> - maxReserveBatchColumns and
maxProcessingBatchesColumns will be default be determined automatically and will more
reliably prevent memory issues. See the admin guide for more.
- <LI><B>Subquery optimization control</B> - added the MJ and NO_UNNEST
hints and the org.teiid.subqueryUnnestDefault system property to control the optimization
of subqueries to traditional joins or to a merge join implemenation of a semijoin or
antijoin.
+ <LI><B>Subquery optimization control</B> - added the MJ and NO_UNNEST
hints and the org.teiid.subqueryUnnestDefault system property to control the optimization
of subqueries to traditional joins or to a merge join implementation of a semijoin or
antijoin.
<LI><B>Local connection threads</B> - local connection calling threads
will be used to process work rather than using an engine thread. This helps decouple the
configuration of maxThreads.
<LI><B>Dependent Join Improvements</B> - several major improvements
were made to increase performance and develop better plans.
<UL>
<LI><B>Improved Planning</B> - the decision to create a dependent
join is now considered earlier in planning and is much more effective for dependent joins
involving multiple unrelated independent tables.
<LI><B>IN predicate splitting</B> - the planner can now split large
dependent IN predicates into multiple IN predicates, which is controlled by the translator
property MaxDepdendentInPredicates. This allows for much larger dependent joins to be
performed as a single query.
- <LI><B>Dependent query parallization</B> - when multiple dependent
queries are still required, then they will be run in parallel (up to
MaxUserSourceRequestConcurrency), rather than sequentially.
+ <LI><B>Dependent query parallization</B> - when multiple dependent
queries are still required, then they will be run in parallel (up to
MaxUserSourceRequestConcurrency), rather than sequentially.
+ <LI><B>Cost based back-off</B> - for cost based dependent joins if
the number of independent values is too large, then the join will be performed as normal.
</UL>
<LI><B>Enhanced Sort Join</B> - the partitioned merge join was
replaced with an enhanced sort join. The enhanced sort join will use the actual row
counts from each side of the relation to perform a index based join if one side is small
enough, a partial sort of the larger side and a repeated merge join if the tuples are
unbalanced but one side is not small enough to form an index, or a standard sort merge
join if the tuples are balanced.
</UL>
Modified: trunk/engine/src/main/java/org/teiid/common/buffer/STree.java
===================================================================
--- trunk/engine/src/main/java/org/teiid/common/buffer/STree.java 2011-04-04 22:34:47 UTC
(rev 3058)
+++ trunk/engine/src/main/java/org/teiid/common/buffer/STree.java 2011-04-04 22:35:34 UTC
(rev 3059)
@@ -195,8 +195,12 @@
}
List key = extractKey(tuple);
int level = 0;
- if (mode != InsertMode.ORDERED || sizeHint == -1) {
- level = randomLevel();
+ if (mode != InsertMode.ORDERED) {
+ if (sizeHint > -1) {
+ level = Math.min(sizeHint, randomLevel());
+ } else {
+ level = randomLevel();
+ }
} else if (!places.isEmpty() && places.getLast().values.getTuples().size() ==
pageSize) {
int row = rowCount.get();
while (row != 0 && row%pageSize == 0) {
@@ -228,6 +232,18 @@
return null;
}
+ public int getExpectedHeight(int sizeHint) {
+ if (sizeHint == 0) {
+ return 0;
+ }
+ int logSize = 1;
+ while (sizeHint > this.pageSize) {
+ logSize++;
+ sizeHint/=this.pageSize;
+ }
+ return logSize;
+ }
+
List extractKey(List tuple) {
if (tuple.size() > keyLength) {
return new ArrayList(tuple.subList(0, keyLength));
Modified:
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/PlanToProcessConverter.java
===================================================================
---
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/PlanToProcessConverter.java 2011-04-04
22:34:47 UTC (rev 3058)
+++
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/PlanToProcessConverter.java 2011-04-04
22:35:34 UTC (rev 3059)
@@ -307,7 +307,7 @@
if(modelID != null){
depAccessNode.setMaxSetSize(CapabilitiesUtil.getMaxInCriteriaSize(modelID, metadata,
capFinder));
-
depAccessNode.setMaxPredicates(CapabilitiesUtil.getMaxDependentPredicatesSize(modelID,
metadata, capFinder));
+
depAccessNode.setMaxPredicates(CapabilitiesUtil.getMaxDependentPredicates(modelID,
metadata, capFinder));
}
processNode = depAccessNode;
aNode = depAccessNode;
Modified:
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/CapabilitiesUtil.java
===================================================================
---
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/CapabilitiesUtil.java 2011-04-04
22:34:47 UTC (rev 3058)
+++
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/CapabilitiesUtil.java 2011-04-04
22:35:34 UTC (rev 3059)
@@ -321,7 +321,7 @@
return value;
}
- public static int getMaxDependentPredicatesSize(Object modelID,
QueryMetadataInterface metadata, CapabilitiesFinder capFinder)
+ public static int getMaxDependentPredicates(Object modelID, QueryMetadataInterface
metadata, CapabilitiesFinder capFinder)
throws QueryMetadataException, TeiidComponentException {
return getProperty(Capability.MAX_DEPENDENT_PREDICATES, modelID, metadata,
capFinder);
}
Modified:
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/JoinRegion.java
===================================================================
---
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/JoinRegion.java 2011-04-04
22:34:47 UTC (rev 3058)
+++
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/JoinRegion.java 2011-04-04
22:35:34 UTC (rev 3059)
@@ -365,7 +365,7 @@
if (leftExpressions.isEmpty()) {
return null;
}
- return NewCalculateCostUtil.computeCostForDepJoin(indNode, depNode, leftExpressions,
rightExpressions, metadata, capFinder, context);
+ return NewCalculateCostUtil.computeCostForDepJoin(indNode, depNode, leftExpressions,
rightExpressions, metadata, capFinder, context).expectedCardinality;
}
/**
Modified:
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/NewCalculateCostUtil.java
===================================================================
---
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/NewCalculateCostUtil.java 2011-04-04
22:34:47 UTC (rev 3058)
+++
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/NewCalculateCostUtil.java 2011-04-04
22:35:34 UTC (rev 3059)
@@ -97,6 +97,12 @@
NDV,
NNV
}
+
+ public static class DependentCostAnalysis {
+ Float[] maxNdv;
+ Float[] expectedNdv;
+ Float expectedCardinality;
+ }
@SuppressWarnings("serial")
private static class ColStats extends LinkedHashMap<Expression, float[]> {
@@ -1112,7 +1118,7 @@
* @throws QueryPlannerException
*
*/
- public static Float computeCostForDepJoin(PlanNode joinNode, boolean leftIndependent,
QueryMetadataInterface metadata, CapabilitiesFinder capFinder, CommandContext context)
+ public static DependentCostAnalysis computeCostForDepJoin(PlanNode joinNode, boolean
leftIndependent, QueryMetadataInterface metadata, CapabilitiesFinder capFinder,
CommandContext context)
throws TeiidComponentException, QueryMetadataException, QueryPlannerException {
PlanNode independentNode =
leftIndependent?joinNode.getFirstChild():joinNode.getLastChild();
@@ -1125,8 +1131,8 @@
independentExpressions, dependentExpressions, metadata,
capFinder, context);
}
-
- public static Float computeCostForDepJoin(PlanNode independentNode,
+
+ public static DependentCostAnalysis computeCostForDepJoin(PlanNode independentNode,
PlanNode dependentNode, List independentExpressions,
List dependentExpressions, QueryMetadataInterface metadata,
CapabilitiesFinder capFinder, CommandContext context)
@@ -1134,9 +1140,13 @@
float independentCardinality = computeCostForTree(independentNode, metadata);
float dependentCardinality = computeCostForTree(dependentNode, metadata);
-
+
+ DependentCostAnalysis dca = new DependentCostAnalysis();
+ dca.maxNdv = new Float[independentExpressions.size()];
+ dca.expectedNdv = new Float[independentExpressions.size()];
+
if (independentCardinality == UNKNOWN_VALUE || dependentCardinality ==
UNKNOWN_VALUE) {
- return null;
+ return dca; //no cost information to be determined
}
float processorBatchSize = BufferManager.DEFAULT_PROCESSOR_BATCH_SIZE;
@@ -1153,56 +1163,9 @@
float indSymbolNDV = getNDVEstimate(independentNode, metadata, independentCardinality,
indElements, true);
Expression depExpr = (Expression)dependentExpressions.get(i);
- LinkedList<PlanNode> critNodes = new LinkedList<PlanNode>();
- LinkedList<PlanNode> initialTargets = new LinkedList<PlanNode>();
-
LinkedList<Expression> depExpressions = new LinkedList<Expression>();
- LinkedList<PlanNode> targets = new LinkedList<PlanNode>();
- critNodes.add(RelationalPlanner.createSelectNode(new DependentSetCriteria(depExpr,
null), false));
- initialTargets.add(dependentNode);
- while (!critNodes.isEmpty()) {
- PlanNode critNode = critNodes.remove();
- PlanNode initial = initialTargets.remove();
- if (critNode.getGroups().isEmpty()) {
- //TODO: we need to project constants up through a plan to avoid this case
- continue;
- }
- PlanNode sourceNode = FrameUtil.findOriginatingNode(initial, critNode.getGroups());
- PlanNode target = sourceNode;
- if (initial != sourceNode) {
- target = rpsc.examinePath(initial, sourceNode, metadata, capFinder);
- }
- if (target != sourceNode || (sourceNode.getType() == NodeConstants.Types.SOURCE
&& sourceNode.getChildCount() == 0)) {
- targets.add(target);
- DependentSetCriteria dsc =
(DependentSetCriteria)critNode.getProperty(Info.SELECT_CRITERIA);
- depExpressions.add(dsc.getExpression());
- continue;
- }
- if (sourceNode.getType() == NodeConstants.Types.SOURCE) {
- PlanNode child = sourceNode.getFirstChild();
- child = FrameUtil.findOriginatingNode(child, child.getGroups());
- if (child != null && child.getType() == NodeConstants.Types.SET_OP)
{
- targets.add(target);
- DependentSetCriteria dsc =
(DependentSetCriteria)critNode.getProperty(Info.SELECT_CRITERIA);
- depExpressions.add(dsc.getExpression());
- //TODO: we need better handling for set op situations
- continue;
- }
- if (!rpsc.pushAcrossFrame(sourceNode, critNode, metadata)) {
- targets.add(target);
- DependentSetCriteria dsc =
(DependentSetCriteria)critNode.getProperty(Info.SELECT_CRITERIA);
- depExpressions.add(dsc.getExpression());
- }
- List<PlanNode> createdNodes = rpsc.getCreatedNodes();
- for (PlanNode planNode : createdNodes) {
- critNodes.add(planNode);
- initialTargets.add(planNode.getFirstChild());
- NodeEditor.removeChildNode(planNode.getParent(), planNode);
- }
- rpsc.getCreatedNodes().clear();
- }
- //the source must be a null or project node, which we don't care about
- }
+ LinkedList<PlanNode> targets = determineTargets(dependentNode,
+ metadata, capFinder, rpsc, depExpr, depExpressions);
Iterator<Expression> exprIter = depExpressions.iterator();
for (Iterator<PlanNode> targetIter = targets.iterator(); targetIter.hasNext();)
{
@@ -1216,6 +1179,11 @@
setCriteriaBatchSize =
CapabilitiesUtil.getMaxInCriteriaSize(RuleRaiseAccess.getModelIDFromAccess(accessNode,
metadata), metadata, capFinder);
if (setCriteriaBatchSize < 1) {
setCriteriaBatchSize = indSymbolNDV;
+ } else {
+ int numberOfSets =
CapabilitiesUtil.getMaxDependentPredicates(RuleRaiseAccess.getModelIDFromAccess(accessNode,
metadata), metadata, capFinder);
+ if (numberOfSets > 0) {
+ setCriteriaBatchSize *= Math.max(1, numberOfSets
/dependentExpressions.size()); //scale down to be conservative
+ }
}
} else if (indSymbolNDV > processorBatchSize) {
//don't bother making a virtual join dependent if they are likely to be
large
@@ -1259,27 +1227,112 @@
if (!usesKey && accessNode != null && target.getType() ==
NodeConstants.Types.SOURCE && target.getChildCount() == 0) {
usesIndex = usesKey(depElems, target.getGroups(), metadata, false);
}
- float dependentAccessCardinality = Math.min(depTargetCardinality,
depTargetCardinality * indSymbolNDV / depSymbolNDV);
- float scaledCardinality = Math.min(dependentCardinality, dependentCardinality *
indSymbolNDV / depSymbolNDV);
- float numberComparisons =
(usesIndex?safeLog(depTargetCardinality):depTargetCardinality) *
(usesIndex?indSymbolNDV:safeLog(indSymbolNDV));
- float newDependentQueries = accessNode == null?0:(float)Math.ceil(indSymbolNDV
/ setCriteriaBatchSize);
-
- float relativeCost = newDependentQueries*procNewRequestTime;
- float relativeComparisonCost = (numberComparisons - safeLog(scaledCardinality)
/*no longer needed by the join*/
- /*sort cost reduction, however it's always true if its on the source
and using an index
- TODO: there are other cost reductions, which we could get by checking the
other parent nodes */
- + (scaledCardinality*safeLog(scaledCardinality) -
dependentCardinality*safeLog(dependentCardinality)))
- * compareTime;
- float relativeReadCost = (dependentAccessCardinality -
depTargetCardinality)*readTime; //cardinality reductions
-
- if (relativeCost + relativeComparisonCost + relativeReadCost < 0) {
- return scaledCardinality;
+ float[] estimates = estimateCost(accessNode, setCriteriaBatchSize, usesIndex,
depTargetCardinality, indSymbolNDV, dependentCardinality, depSymbolNDV);
+ if (estimates[1] < 0) {
+ if (dca.expectedCardinality == null) {
+ dca.expectedCardinality = estimates[0];
+ } else {
+ dca.expectedCardinality = Math.min(dca.expectedCardinality, estimates[0]);
+ }
}
+ dca.expectedNdv[i] = indSymbolNDV;
+ //use a quick binary search to find the max ndv
+ float min = 0;
+ float max = Math.max(Integer.MAX_VALUE, indSymbolNDV);
+ for (int j = 0; j < 10; j++) {
+ if (estimates[1] > 1) {
+ max = indSymbolNDV;
+ indSymbolNDV = (indSymbolNDV + min)/2;
+ } else if (estimates[1] < 0) {
+ min = indSymbolNDV;
+ //we assume that values should be closer to the min side
+ indSymbolNDV = Math.min(indSymbolNDV * 8 + 1, (indSymbolNDV + max)/2);
+ } else {
+ break;
+ }
+ estimates = estimateCost(accessNode, setCriteriaBatchSize, usesIndex,
depTargetCardinality, indSymbolNDV, dependentCardinality, depSymbolNDV);
+ }
+ dca.maxNdv[i] = indSymbolNDV;
}
}
+ return dca;
+ }
+
+ private static float[] estimateCost(PlanNode accessNode, float setCriteriaBatchSize,
boolean usesIndex, float depTargetCardinality,
+ float indSymbolNDV, float dependentCardinality, float depSymbolNDV) {
+ float dependentAccessCardinality = Math.min(depTargetCardinality,
depTargetCardinality * indSymbolNDV / depSymbolNDV);
+ float scaledCardinality = Math.min(dependentCardinality, dependentCardinality *
indSymbolNDV / depSymbolNDV);
+ float numberComparisons =
(usesIndex?safeLog(depTargetCardinality):depTargetCardinality) *
(usesIndex?indSymbolNDV:safeLog(indSymbolNDV));
+ float newDependentQueries = accessNode == null?0:(float)Math.ceil(indSymbolNDV /
setCriteriaBatchSize);
- return null;
+ float relativeCost = newDependentQueries*procNewRequestTime;
+ float relativeComparisonCost = (numberComparisons - safeLog(scaledCardinality)
/*no longer needed by the join*/
+ /*sort cost reduction, however it's always true if its on the source and
using an index
+ TODO: there are other cost reductions, which we could get by checking the
other parent nodes */
+ + (scaledCardinality*safeLog(scaledCardinality) -
dependentCardinality*safeLog(dependentCardinality)))
+ * compareTime;
+ float relativeReadCost = (dependentAccessCardinality -
depTargetCardinality)*readTime; //cardinality reductions
+ return new float[] {scaledCardinality, relativeCost + relativeComparisonCost +
relativeReadCost};
}
+
+ /**
+ * For now we only consider a single target. In the future we may consider multiple.
+ */
+ private static LinkedList<PlanNode> determineTargets(
+ PlanNode dependentNode, QueryMetadataInterface metadata,
+ CapabilitiesFinder capFinder, RulePushSelectCriteria rpsc,
+ Expression depExpr, LinkedList<Expression> depExpressions)
+ throws QueryPlannerException, TeiidComponentException {
+ LinkedList<PlanNode> targets = new LinkedList<PlanNode>();
+ LinkedList<PlanNode> critNodes = new LinkedList<PlanNode>();
+ critNodes.add(RelationalPlanner.createSelectNode(new DependentSetCriteria(depExpr,
null), false));
+ LinkedList<PlanNode> initialTargets = new LinkedList<PlanNode>();
+ initialTargets.add(dependentNode);
+ while (!critNodes.isEmpty()) {
+ PlanNode critNode = critNodes.remove();
+ PlanNode initial = initialTargets.remove();
+ if (critNode.getGroups().isEmpty()) {
+ //TODO: we need to project constants up through a plan to avoid this case
+ continue;
+ }
+ PlanNode sourceNode = FrameUtil.findOriginatingNode(initial, critNode.getGroups());
+ PlanNode target = sourceNode;
+ if (initial != sourceNode) {
+ target = rpsc.examinePath(initial, sourceNode, metadata, capFinder);
+ }
+ if (target != sourceNode || (sourceNode.getType() == NodeConstants.Types.SOURCE
&& sourceNode.getChildCount() == 0)) {
+ targets.add(target);
+ DependentSetCriteria dsc =
(DependentSetCriteria)critNode.getProperty(Info.SELECT_CRITERIA);
+ depExpressions.add(dsc.getExpression());
+ continue;
+ }
+ if (sourceNode.getType() == NodeConstants.Types.SOURCE) {
+ PlanNode child = sourceNode.getFirstChild();
+ child = FrameUtil.findOriginatingNode(child, child.getGroups());
+ if (child != null && child.getType() == NodeConstants.Types.SET_OP) {
+ targets.add(target);
+ DependentSetCriteria dsc =
(DependentSetCriteria)critNode.getProperty(Info.SELECT_CRITERIA);
+ depExpressions.add(dsc.getExpression());
+ //TODO: we need better handling for set op situations
+ continue;
+ }
+ if (!rpsc.pushAcrossFrame(sourceNode, critNode, metadata)) {
+ targets.add(target);
+ DependentSetCriteria dsc =
(DependentSetCriteria)critNode.getProperty(Info.SELECT_CRITERIA);
+ depExpressions.add(dsc.getExpression());
+ }
+ List<PlanNode> createdNodes = rpsc.getCreatedNodes();
+ for (PlanNode planNode : createdNodes) {
+ critNodes.add(planNode);
+ initialTargets.add(planNode.getFirstChild());
+ NodeEditor.removeChildNode(planNode.getParent(), planNode);
+ }
+ rpsc.getCreatedNodes().clear();
+ }
+ //the source must be a null or project node, which we don't care about
+ }
+ return targets;
+ }
static float getNDVEstimate(PlanNode indNode,
QueryMetadataInterface metadata, float cardinality,
Modified:
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleChooseDependent.java
===================================================================
---
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleChooseDependent.java 2011-04-04
22:34:47 UTC (rev 3058)
+++
trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleChooseDependent.java 2011-04-04
22:35:34 UTC (rev 3059)
@@ -41,6 +41,7 @@
import org.teiid.query.optimizer.relational.plantree.NodeConstants;
import org.teiid.query.optimizer.relational.plantree.NodeEditor;
import org.teiid.query.optimizer.relational.plantree.PlanNode;
+import
org.teiid.query.optimizer.relational.rules.NewCalculateCostUtil.DependentCostAnalysis;
import org.teiid.query.sql.lang.DependentSetCriteria;
import org.teiid.query.sql.lang.JoinType;
import org.teiid.query.sql.symbol.ElementSymbol;
@@ -85,31 +86,31 @@
PlanNode chosenNode = chooseDepWithoutCosting(sourceNode,
bothCandidates?siblingNode:null, analysisRecord);
if(chosenNode != null) {
- pushCriteria |= markDependent(chosenNode, joinNode, metadata);
+ pushCriteria |= markDependent(chosenNode, joinNode, metadata, null);
continue;
}
- boolean useDepJoin = NewCalculateCostUtil.computeCostForDepJoin(joinNode,
!entry.leftCandidate, metadata, capFinder, context) != null;
+ DependentCostAnalysis dca =
NewCalculateCostUtil.computeCostForDepJoin(joinNode, !entry.leftCandidate, metadata,
capFinder, context);
PlanNode dependentNode = sourceNode;
- if (bothCandidates && !useDepJoin) {
- useDepJoin = NewCalculateCostUtil.computeCostForDepJoin(joinNode, true,
metadata, capFinder, context) != null;
- if (useDepJoin) {
+ if (bothCandidates && dca.expectedCardinality == null) {
+ dca = NewCalculateCostUtil.computeCostForDepJoin(joinNode, true,
metadata, capFinder, context);
+ if (dca.expectedCardinality != null) {
dependentNode = siblingNode;
}
}
- if (useDepJoin) {
- pushCriteria |= markDependent(dependentNode, joinNode, metadata);
+ if (dca.expectedCardinality != null) {
+ pushCriteria |= markDependent(dependentNode, joinNode, metadata, dca);
} else {
float sourceCost = NewCalculateCostUtil.computeCostForTree(sourceNode,
metadata);
float siblingCost = NewCalculateCostUtil.computeCostForTree(siblingNode,
metadata);
if (bothCandidates && sourceCost !=
NewCalculateCostUtil.UNKNOWN_VALUE && sourceCost <
RuleChooseDependent.DEFAULT_INDEPENDENT_CARDINALITY
&& (sourceCost < siblingCost || siblingCost ==
NewCalculateCostUtil.UNKNOWN_VALUE)) {
- pushCriteria |= markDependent(siblingNode, joinNode, metadata);
+ pushCriteria |= markDependent(siblingNode, joinNode, metadata,
null);
} else if (siblingCost != NewCalculateCostUtil.UNKNOWN_VALUE &&
siblingCost < RuleChooseDependent.DEFAULT_INDEPENDENT_CARDINALITY) {
- pushCriteria |= markDependent(sourceNode, joinNode, metadata);
+ pushCriteria |= markDependent(sourceNode, joinNode, metadata, null);
}
}
}
@@ -260,10 +261,11 @@
/**
* Mark the specified access node to be made dependent
* @param sourceNode Node to make dependent
+ * @param dca
* @throws TeiidComponentException
* @throws QueryMetadataException
*/
- boolean markDependent(PlanNode sourceNode, PlanNode joinNode, QueryMetadataInterface
metadata) throws QueryMetadataException, TeiidComponentException {
+ boolean markDependent(PlanNode sourceNode, PlanNode joinNode, QueryMetadataInterface
metadata, DependentCostAnalysis dca) throws QueryMetadataException,
TeiidComponentException {
boolean isLeft = joinNode.getFirstChild() == sourceNode;
@@ -279,7 +281,7 @@
// Create DependentValueSource and set on the independent side as this will feed
the values
joinNode.setProperty(NodeConstants.Info.DEPENDENT_VALUE_SOURCE, id);
- List<PlanNode> crits = getDependentCriteriaNodes(id,
independentExpressions, dependentExpressions,
isLeft?joinNode.getLastChild():joinNode.getFirstChild(), metadata);
+ List<PlanNode> crits = getDependentCriteriaNodes(id,
independentExpressions, dependentExpressions,
isLeft?joinNode.getLastChild():joinNode.getFirstChild(), metadata, dca);
PlanNode newRoot = sourceNode;
@@ -303,21 +305,30 @@
* @since 4.3
*/
private List<PlanNode> getDependentCriteriaNodes(String id, List
independentExpressions,
- List dependentExpressions, PlanNode indNode,
QueryMetadataInterface metadata) throws QueryMetadataException, TeiidComponentException {
+ List dependentExpressions, PlanNode indNode,
QueryMetadataInterface metadata, DependentCostAnalysis dca) throws QueryMetadataException,
TeiidComponentException {
List<PlanNode> result = new LinkedList<PlanNode>();
- Iterator depIter = dependentExpressions.iterator();
- Iterator indepIter = independentExpressions.iterator();
+ Float cardinality = null;
- float cardinality = NewCalculateCostUtil.computeCostForTree(indNode, metadata);
-
- while(depIter.hasNext()) {
- Expression depExpr = (Expression) depIter.next();
- Expression indepExpr = (Expression) indepIter.next();
+ for (int i = 0; i < dependentExpressions.size(); i++) {
+ Expression depExpr = (Expression) dependentExpressions.get(i);
+ Expression indepExpr = (Expression) independentExpressions.get(i);
DependentSetCriteria crit = new
DependentSetCriteria(SymbolMap.getExpression(depExpr), id);
- Collection<ElementSymbol> elems =
ElementCollectorVisitor.getElements(indepExpr, true);
- float ndv = NewCalculateCostUtil.getNDVEstimate(indNode, metadata,
cardinality, elems, true);
+ float ndv = NewCalculateCostUtil.UNKNOWN_VALUE;
+ if (dca != null && dca.expectedNdv[i] != null) {
+ if (dca.expectedNdv[i] > 4*dca.maxNdv[i]) {
+ continue; //not necessary to use
+ }
+ ndv = dca.expectedNdv[i];
+ crit.setMaxNdv(dca.maxNdv[i]);
+ } else {
+ Collection<ElementSymbol> elems =
ElementCollectorVisitor.getElements(indepExpr, true);
+ if (cardinality == null) {
+ cardinality = NewCalculateCostUtil.computeCostForTree(indNode, metadata);
+ }
+ ndv = NewCalculateCostUtil.getNDVEstimate(indNode, metadata, cardinality,
elems, true);
+ }
crit.setNdv(ndv);
crit.setValueExpression(indepExpr);
Modified: trunk/engine/src/main/java/org/teiid/query/processor/relational/AccessNode.java
===================================================================
---
trunk/engine/src/main/java/org/teiid/query/processor/relational/AccessNode.java 2011-04-04
22:34:47 UTC (rev 3058)
+++
trunk/engine/src/main/java/org/teiid/query/processor/relational/AccessNode.java 2011-04-04
22:35:34 UTC (rev 3059)
@@ -31,13 +31,16 @@
import org.teiid.api.exception.query.QueryValidatorException;
import org.teiid.client.plan.PlanNode;
import org.teiid.common.buffer.BlockedException;
+import org.teiid.common.buffer.BufferManager;
import org.teiid.common.buffer.TupleBatch;
import org.teiid.common.buffer.TupleSource;
+import org.teiid.common.buffer.BufferManager.BufferReserveMode;
import org.teiid.core.TeiidComponentException;
import org.teiid.core.TeiidProcessingException;
import org.teiid.query.QueryPlugin;
import org.teiid.query.eval.Evaluator;
import org.teiid.query.metadata.QueryMetadataInterface;
+import org.teiid.query.processor.ProcessorDataManager;
import org.teiid.query.rewriter.QueryRewriter;
import org.teiid.query.sql.lang.Command;
import org.teiid.query.util.CommandContext;
@@ -57,6 +60,8 @@
private boolean isUpdate = false;
private boolean returnedRows = false;
protected Command nextCommand;
+ private int reserved;
+ private int schemaSize;
protected AccessNode() {
super();
@@ -65,6 +70,13 @@
public AccessNode(int nodeID) {
super(nodeID);
}
+
+ @Override
+ public void initialize(CommandContext context, BufferManager bufferManager,
+ ProcessorDataManager dataMgr) {
+ super.initialize(context, bufferManager, dataMgr);
+ this.schemaSize = getBufferManager().getSchemaSize(getOutputElements());
+ }
public void reset() {
super.reset();
@@ -181,6 +193,10 @@
//end of source
tupleSource.closeSource();
tupleSources.remove(i--);
+ if (reserved > 0) {
+ reserved -= schemaSize;
+ getBufferManager().releaseBuffers(schemaSize);
+ }
if (!processCommandsIndividually()) {
registerNext();
}
@@ -238,6 +254,9 @@
}
}
tupleSources.add(getDataManager().registerRequest(getContext(), atomicCommand,
modelName, connectorBindingId, getID(), limit));
+ if (tupleSources.size() > 1) {
+ reserved += getBufferManager().reserveBuffers(schemaSize,
BufferReserveMode.FORCE);
+ }
}
protected boolean processCommandsIndividually() {
@@ -249,6 +268,8 @@
}
public void closeDirect() {
+ getBufferManager().releaseBuffers(reserved);
+ reserved = 0;
super.closeDirect();
closeSources();
}
Modified:
trunk/engine/src/main/java/org/teiid/query/processor/relational/DependentCriteriaProcessor.java
===================================================================
---
trunk/engine/src/main/java/org/teiid/query/processor/relational/DependentCriteriaProcessor.java 2011-04-04
22:34:47 UTC (rev 3058)
+++
trunk/engine/src/main/java/org/teiid/query/processor/relational/DependentCriteriaProcessor.java 2011-04-04
22:35:34 UTC (rev 3059)
@@ -38,6 +38,7 @@
import org.teiid.common.buffer.BlockedException;
import org.teiid.core.TeiidComponentException;
import org.teiid.core.TeiidProcessingException;
+import org.teiid.query.optimizer.relational.rules.NewCalculateCostUtil;
import org.teiid.query.processor.relational.SortUtility.Mode;
import org.teiid.query.rewriter.QueryRewriter;
import org.teiid.query.sql.lang.AbstractSetCriteria;
@@ -66,6 +67,10 @@
Object nextValue;
boolean isNull;
+
+ float maxNdv = NewCalculateCostUtil.UNKNOWN_VALUE;
+
+ boolean overMax;
}
class TupleState {
@@ -96,6 +101,21 @@
dvs = new DependentValueSource(sortUtility.sort());
for (SetState setState : dependentSetStates) {
setState.valueIterator =
dvs.getValueIterator(setState.valueExpression);
+ if (setState.maxNdv > 0 && setState.maxNdv <
dvs.getTupleBuffer().getRowCount()) {
+ ValueIterator vi = dvs.getValueIterator(setState.valueExpression);
+ Comparable last = null;
+ int distinctCount = 0;
+ while (vi.hasNext()) {
+ Comparable next = (Comparable) vi.next();
+ if (last == null || next.compareTo(last) != 0) {
+ distinctCount++;
+ }
+ last = next;
+ }
+ if (distinctCount > setState.maxNdv) {
+ setState.overMax = true;
+ }
+ }
}
}
}
@@ -177,6 +197,7 @@
sources.add(ts.getDepedentSetStates());
}
ts.getDepedentSetStates().add(state);
+ state.maxNdv = dsc.getMaxNdv();
}
}
}
@@ -276,21 +297,25 @@
if (i == currentIndex++) {
- boolean done = false;
+ int doneCount = 0;
- while (!done) {
+ while (doneCount < source.size()) {
boolean isNull = false;
boolean lessThanMax = true;
for (SetState state : source) {
+ if (state.overMax) {
+ doneCount++;
+ continue;
+ }
if (state.nextValue == null && !state.isNull) {
if (state.valueIterator.hasNext()) {
state.nextValue = state.valueIterator.next();
state.isNull = state.nextValue == null;
} else {
state.valueIterator.reset();
- done = true; // should be true for each iterator from this
source
+ doneCount++; // should be true for each iterator from this
source
continue;
}
}
@@ -299,7 +324,7 @@
lessThanMax &= state.replacement.size() < maxSize * (run +
1);
}
- if (done) {
+ if (doneCount == source.size()) {
if (!restartIndexes.isEmpty() &&
restartIndexes.getLast().intValue() == i) {
restartIndexes.removeLast();
}
@@ -316,7 +341,7 @@
}
} else {
restartIndexes.add(i);
- done = true;
+ break;
}
}
}
@@ -339,6 +364,9 @@
}
public Criteria replaceDependentCriteria(AbstractSetCriteria crit, SetState state) {
+ if (state.overMax) {
+ return QueryRewriter.TRUE_CRITERIA;
+ }
if (state.replacement.isEmpty()) {
// No values - return criteria that is always false
return QueryRewriter.FALSE_CRITERIA;
Modified:
trunk/engine/src/main/java/org/teiid/query/processor/relational/EnhancedSortMergeJoinStrategy.java
===================================================================
---
trunk/engine/src/main/java/org/teiid/query/processor/relational/EnhancedSortMergeJoinStrategy.java 2011-04-04
22:34:47 UTC (rev 3058)
+++
trunk/engine/src/main/java/org/teiid/query/processor/relational/EnhancedSortMergeJoinStrategy.java 2011-04-04
22:35:34 UTC (rev 3059)
@@ -136,6 +136,7 @@
int rowId = 0;
List<?> lastTuple = null;
boolean sortedDistinct = sorted && !state.isDistinct();
+ int sizeHint = index.getExpectedHeight(state.getTupleBuffer().getRowCount());
outer: while (its.hasNext()) {
//detect if sorted and distinct
List<?> originalTuple = its.nextTuple();
@@ -153,7 +154,7 @@
if (!state.isDistinct()) {
tuple.add(keyLength - 1, rowId++);
}
- index.insert(tuple, sorted?InsertMode.ORDERED:InsertMode.NEW,
state.getTupleBuffer().getRowCount());
+ index.insert(tuple, sorted?InsertMode.ORDERED:InsertMode.NEW, sizeHint);
}
if (!sorted) {
index.compact();
Modified: trunk/engine/src/main/java/org/teiid/query/sql/lang/DependentSetCriteria.java
===================================================================
---
trunk/engine/src/main/java/org/teiid/query/sql/lang/DependentSetCriteria.java 2011-04-04
22:34:47 UTC (rev 3058)
+++
trunk/engine/src/main/java/org/teiid/query/sql/lang/DependentSetCriteria.java 2011-04-04
22:35:34 UTC (rev 3059)
@@ -24,6 +24,7 @@
import org.teiid.core.util.EquivalenceUtil;
import org.teiid.core.util.HashCodeUtil;
+import org.teiid.query.optimizer.relational.rules.NewCalculateCostUtil;
import org.teiid.query.sql.LanguageVisitor;
import org.teiid.query.sql.symbol.ContextReference;
import org.teiid.query.sql.symbol.Expression;
@@ -46,7 +47,8 @@
/**
* The estimated number of distinct values for the value Expression
*/
- private float ndv;
+ private float ndv = NewCalculateCostUtil.UNKNOWN_VALUE;
+ private float maxNdv = NewCalculateCostUtil.UNKNOWN_VALUE;
/**
* Construct with the left expression
@@ -61,6 +63,14 @@
return id;
}
+ public float getMaxNdv() {
+ return maxNdv;
+ }
+
+ public void setMaxNdv(float maxNdv) {
+ this.maxNdv = maxNdv;
+ }
+
public float getNdv() {
return ndv;
}
@@ -144,6 +154,7 @@
}
criteriaCopy.id = this.id;
criteriaCopy.ndv = this.ndv;
+ criteriaCopy.maxNdv = this.maxNdv;
return criteriaCopy;
}
Modified: trunk/engine/src/test/java/org/teiid/common/buffer/TestSTree.java
===================================================================
--- trunk/engine/src/test/java/org/teiid/common/buffer/TestSTree.java 2011-04-04 22:34:47
UTC (rev 3058)
+++ trunk/engine/src/test/java/org/teiid/common/buffer/TestSTree.java 2011-04-04 22:35:34
UTC (rev 3059)
@@ -58,6 +58,25 @@
assertNull(map.insert(Arrays.asList(1, String.valueOf(1)), InsertMode.NEW, -1));
}
+ @Test public void testUnOrderedInsert() throws TeiidComponentException {
+ BufferManagerImpl bm = BufferManagerFactory.createBufferManager();
+ bm.setProcessorBatchSize(16);
+
+ ElementSymbol e1 = new ElementSymbol("x");
+ e1.setType(Integer.class);
+ List elements = Arrays.asList(e1);
+ STree map = bm.createSTree(elements, "1", 1);
+
+ int size = (1<<16)+(1<<4)+1;
+ int logSize = map.getExpectedHeight(size);
+
+ for (int i = 0; i < size; i++) {
+ assertNull(map.insert(Arrays.asList(i), InsertMode.NEW, logSize));
+ assertEquals(i + 1, map.getRowCount());
+ }
+ assertTrue(5 >= map.getHeight());
+ }
+
@Test public void testOrderedInsert() throws TeiidComponentException {
BufferManagerImpl bm = BufferManagerFactory.createBufferManager();
bm.setProcessorBatchSize(16);
Modified: trunk/engine/src/test/java/org/teiid/query/processor/TestDependentJoins.java
===================================================================
---
trunk/engine/src/test/java/org/teiid/query/processor/TestDependentJoins.java 2011-04-04
22:34:47 UTC (rev 3058)
+++
trunk/engine/src/test/java/org/teiid/query/processor/TestDependentJoins.java 2011-04-04
22:35:34 UTC (rev 3059)
@@ -25,12 +25,14 @@
import static org.junit.Assert.*;
import java.util.Arrays;
+import java.util.HashSet;
import java.util.List;
import org.junit.Test;
import org.teiid.core.TeiidComponentException;
import org.teiid.core.TeiidProcessingException;
import org.teiid.query.optimizer.TestOptimizer;
+import org.teiid.query.optimizer.TestOptimizer.ComparisonMode;
import org.teiid.query.optimizer.capabilities.BasicSourceCapabilities;
import org.teiid.query.optimizer.capabilities.FakeCapabilitiesFinder;
import org.teiid.query.optimizer.capabilities.SourceCapabilities.Capability;
@@ -810,4 +812,46 @@
TestProcessor.helpProcess(plan, dataManager, expected);
}
+ @Test public void testDependentJoinBackoff() throws Exception {
+ // Create query
+ String sql = "SELECT pm1.g1.e1 FROM pm1.g1, pm6.g1 WHERE
pm1.g1.e1=pm6.g1.e1"; //$NON-NLS-1$
+
+ // Construct data manager with data
+ FakeDataManager dataManager = new FakeDataManager();
+ sampleData4(dataManager);
+
+ FakeMetadataFacade fakeMetadata = FakeMetadataFactory.example1();
+
+ FakeMetadataFactory.setCardinality("pm1.g1", 1, fakeMetadata);
+ FakeMetadataFactory.setCardinality("pm6.g1", 1000, fakeMetadata);
+ // Plan query
+ FakeCapabilitiesFinder capFinder = new FakeCapabilitiesFinder();
+ BasicSourceCapabilities depcaps = new BasicSourceCapabilities();
+ depcaps.setCapabilitySupport(Capability.CRITERIA_IN, true);
+ depcaps.setSourceProperty(Capability.MAX_IN_CRITERIA_SIZE, new Integer(1));
+ depcaps.setCapabilitySupport(Capability.QUERY_ORDERBY, true);
+
+ BasicSourceCapabilities caps = new BasicSourceCapabilities();
+ caps.setCapabilitySupport(Capability.CRITERIA_IN, true);
+
+ capFinder.addCapabilities("pm1", caps); //$NON-NLS-1$
+ capFinder.addCapabilities("pm6", depcaps); //$NON-NLS-1$
+
+ List[] expected = new List[] {
+ Arrays.asList(new Object[] {
+ new String("b")})}; //$NON-NLS-1$
+
+ ProcessorPlan plan = TestOptimizer.helpPlan(sql, fakeMetadata, new String[] {
+ "SELECT pm6.g1.e1 FROM pm6.g1 WHERE pm6.g1.e1 IN (<dependent
values>) ORDER BY pm6.g1.e1",
+ "SELECT pm1.g1.e1 FROM pm1.g1"
+ }, capFinder, ComparisonMode.EXACT_COMMAND_STRING);
+
+ // Run query
+ TestProcessor.helpProcess(plan, dataManager, expected);
+
+ //note that the dependent join was not actually performed
+ assertEquals(new HashSet<String>(Arrays.asList("SELECT pm1.g1.e1 FROM
pm1.g1", "SELECT pm6.g1.e1 FROM pm6.g1 ORDER BY pm6.g1.e1")),
+ new HashSet<String>(dataManager.getQueries()));
+ }
+
}
Modified: trunk/engine/src/test/java/org/teiid/query/processor/TestProcessor.java
===================================================================
--- trunk/engine/src/test/java/org/teiid/query/processor/TestProcessor.java 2011-04-04
22:34:47 UTC (rev 3058)
+++ trunk/engine/src/test/java/org/teiid/query/processor/TestProcessor.java 2011-04-04
22:35:34 UTC (rev 3059)
@@ -7650,5 +7650,5 @@
helpProcess(plan, dataManager, expected);
}
- private static final boolean DEBUG = false;
+ private static final boolean DEBUG = true;
}
Modified:
trunk/engine/src/test/java/org/teiid/query/processor/relational/TestAccessNode.java
===================================================================
---
trunk/engine/src/test/java/org/teiid/query/processor/relational/TestAccessNode.java 2011-04-04
22:34:47 UTC (rev 3058)
+++
trunk/engine/src/test/java/org/teiid/query/processor/relational/TestAccessNode.java 2011-04-04
22:35:34 UTC (rev 3059)
@@ -61,7 +61,7 @@
BufferManager bm = BufferManagerFactory.getStandaloneBufferManager();
FakeDataManager dataManager = new FakeDataManager();
TestProcessor.sampleData1(dataManager);
-
+ node.setElements(command.getProjectedSymbols());
node.initialize(context, bm, dataManager);
node.setShouldEvaluateExpressions(true);
// Call open()
@@ -99,6 +99,7 @@
BufferManager bm = BufferManagerFactory.getStandaloneBufferManager();
FakeDataManager dataManager = new FakeDataManager();
TestProcessor.sampleData1(dataManager);
+ node.setElements(query.getProjectedSymbols());
node.initialize(context, bm, dataManager);
// Call open()
node.open();