db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Army <qoz...@sbcglobal.net>
Subject [ optimizer ] Some questions on optimization cost estimates?
Date Sat, 01 Apr 2006 00:56:19 GMT
While trying to complete the Phase 4 work for DERBY-805 I've come across some 
behavior in the optimizer's treatment of cost estimates that I don't fully 
understand.  If anyone out there can offer answers/feedback for any of the 
following three questions, I'd appreciate it...

--------------------------------
1) Multiplication by outer rows.
--------------------------------

There are four classes--ProjectRestrictNode, UnionNode, JoinNode, and 
FromTable--that implement the "optimizeIt()" method and, in that method, call 
"getJoinStrategy().estimateCost(...)".  One of the arguments to optimizeIt() is 
an outerCost value which holds the estimated cost for FromTables left of the 
current one for this join order.  So if we have a FROM list that is [ FT1, FT2, 
FT3 ] and the current FromTable (the one we're optimizing) is FT2, then 
outerCost will hold the estimated cost for FT1.  For the sake of this question, 
assume FT1, FT2, and FT3 are instances of one of the above-mentioned classes. 
outerCost is then used in two ways by these FTs: a) it's passed down to the 
children nodes, where it's factored into the cost estimates of those children, 
and b) it's passed into a call to estimate the cost of the current FT itself. 
As an example, take UnionNode.  The a) code is like this:

	leftResultSet = optimizeSource(
				optimizer,
				leftResultSet,
				getLeftOptPredicateList(),
				outerCost);  // <==

	rightResultSet = optimizeSource(
				optimizer,
				rightResultSet,
				getRightOptPredicateList(),
				outerCost);  // <==

The b) code is then:

	/*
	** Get the cost of this result set in the context of the whole plan.
	*/
	getCurrentAccessPath().
		getJoinStrategy().
			estimateCost(
				this,
				predList,
				(ConglomerateDescriptor) null,
				outerCost,   // <==
				optimizer,
				costEstimate
				);

In both cases, the only part of outerCost that's actually used is the estimated 
row count.  In cases where we're costing a Nested Loop Join (either for the 
current FT or for any of it's children), we multiply the cost of the current FT 
(or its children) by the number of outer rows, since we will in effect be 
incurring the cost of the inner FT for each row of the outer FT.

All of that said, my question is this: why do we need to pass the outerCost down 
to the children, where it will be multiplied by their costs, AND at the same 
time pass it into the "getJoinStrategy().estimateCost()" method, where it will 
be multiplied (again) by the cost of the current FT?  It seems to me the like 
the correct thing to do here is to _not_ pass outerCost to the children and to 
instead just let the current FT do the multiplication if necessary.

As a trivialized example, assume our FT2 is a UnionNode over two subqueries, 
each of which just has a single table:

FT2 = (select * from T1) UNION (select * from T2)

And assume FT1 is an outer table with row count of 100.  Then in the part a) 
code above, we'll pass "100" down to the left child, where it will eventually 
make it down to T1 and we'll multiply the cost of T1 by 100.  Likewise we'll 
pass "100" down to the right child and multiply the cost of T2 by 100:

T1 estimated cost: 100 * T1_cost
T2 estimated cost: 100 * T2_cost

Then we'll set the cost of the UnionNode to be the sum of the estimated costs of 
its children:

FT2 estimated cost: (100 * T1_cost) + (100 * T2_cost)

That done, if the current join strategy for FT2 is NestedLoop, the call in part 
b) above will pass "100" to NestedLoopJoinStrategy.estimateCost(), where it will 
be multiplied by the cost of FT2:

FT2 estimatedCost: 100 * ((100 * T1_cost) + (100 * T2_cost))

In other words, we've ended up multiplying the cost of FT2 by the outer row 
count *TWICE*.

I guess this could be intentional in order to make sure we favor hash joins 
(which won't do the second multiplication--see below) over nested loop joins, 
but it'd be great if someone could confirm this one way or the other.  As it is, 
it seems a bit odd to me.

----------------------------------
2) HashJoinStrategy.estimateCost()
----------------------------------

As mentioned at the end of question 1, if the join strategy that we're currently 
costing is a HashJoin and we make a call to HashJoinStrategy.estimateCost() (see 
above for an example), we get here:

/** @see JoinStrategy#estimateCost */
public void estimateCost(Optimizable innerTable,
			 OptimizablePredicateList predList,
			 ConglomerateDescriptor cd,
			 CostEstimate outerCost,
			 Optimizer optimizer,
			 CostEstimate costEstimate) {
	/*
	** The cost of a hash join is the cost of building the hash table.
	** There is no extra cost per outer row.
	*/
}

I.e. we don't do anything.  But at the same time, if we're costing a 
FromBaseTable and considering a HashJoin, we _do_ actually use the outer row 
count.  See FromBaseTable.estimateCost():

	/*
	** Let the join strategy decide whether the cost of the base
	** scan is a single scan, or a scan per outer row.
	** NOTE: In this case we only want to multiply against the
	** total row count, not the singleScanRowCount.
	*/
	if (currentJoinStrategy.multiplyBaseCostByOuterRows())
	{
		newCost *= outerCost.rowCount();
	}
	rowCount *= outerCost.rowCount();

For a HashJoin the call to "multiplyBaseCostByOuterRows() will return false. 
Notice though that while we will not multiply the current cost (newCost) by the 
outer row count for a hash join, we _will_ multiply the current _rowCount_ by 
the outer row count.

So my question is this: why is it that, for a FromBaseTable, we multiply the 
current rowCount by the outer row count for a Hash join (as per 
FromBaseTable.estimateCost()), but for other (non-base-table) FromTables (such 
as UnionNode) we skip this multiplication (as per 
HashJoinStrategy.estimateCost())?  Is this an intentional difference, and if so, 
does anyone know why?

----------------------------------
3) Comparing plan costs.
----------------------------------

In OptimizerImpl.java there is the following code for comparing "current" cost 
with "best cost" for this round of optimization:

	/*
	** Is the cost of this join order lower than the best one we've
	** found so far?
	**
	** NOTE: If the user has specified a join order, it will be the
	** only join order the optimizer considers, so it is OK to use
	** costing to decide that it is the "best" join order.
	*/
	if ((! foundABestPlan) || currentCost.compare(bestCost) < 0)
	{
		rememberBestCost(currentCost, Optimizer.NORMAL_PLAN);

		// Since we just remembered all of the best plans,
		// no need to reload them when pulling Optimizables
		// from this join order.
		reloadBestPlan = false;
	}

The call to "currentCost.compare()" only compares the estimatedCost fields; it 
does not look at the other two fields of a CostEstimate--namely, rowCount and 
singleScanRowCount.

In running some tests against 10.1, though, I noticed that it is possible for 
currentCost and bestCost to have the same estimatedCost values but different row 
counts.  Since the above check does not look at row counts, we can end up in 
situations where the following two queries can result in different query plans:

select * from V1, V2 where V1.j = V2.b;
select * from V2, V1 where V1.j = V2.b;

I.e. the queries are identical with the exception of the order of V1 and V2.  In 
my particular example V1 and V2 are both unions of two tables, where V2 has 
100,000 rows and V1 has less than ten.  When I ran these queries against 10.1 
with NO optimizer timeout--meaning that the optimizer had time to examine all 
possible query plans--the result was surprising: the first query chose join 
order [ V2, V1 ] and took 4.5 to 5 seconds to complete; the second query chose 
join order [ V1, V2 ] and took 30-33 seconds to complete.  Wow.

I made a small change to the CostEstimateImpl.compare() method to consider 
rowCount as a secondary field of comparison (if the estimatedCosts are the same) 
  and singleScanRowCount as a third field of comparison (if the rowCounts are 
the same).  With that change the behavior was then what I expected: namely, the 
optimizer chose the same join order (the faster one) regardless of which query I 
ran.

So my question is this: if two cost estimates have the same estimatedCost but 
different rowCounts (or even singleScanRowCounts), it is reasonable to suppose 
that the estimate with the lower rowCount is actually better?  In the above case 
the query with the lower row count was the one that ran more quickly--is it 
reasonable to believe that this will generally be the case?

---

As always, thanks to anyone with the time and inclination to read this email and 
provide feedback...

Army


Mime
View raw message