frombasetable.java

derby database source code.good for you.

	public void startOptimizing(Optimizer optimizer, RowOrdering rowOrdering)
	{
		AccessPath ap = getCurrentAccessPath();
		AccessPath bestAp = getBestAccessPath();
		AccessPath bestSortAp = getBestSortAvoidancePath();

		ap.setConglomerateDescriptor((ConglomerateDescriptor) null);
		bestAp.setConglomerateDescriptor((ConglomerateDescriptor) null);
		bestSortAp.setConglomerateDescriptor((ConglomerateDescriptor) null);
		ap.setCoveringIndexScan(false);
		bestAp.setCoveringIndexScan(false);
		bestSortAp.setCoveringIndexScan(false);
		ap.setLockMode(0);
		bestAp.setLockMode(0);
		bestSortAp.setLockMode(0);

		/*
		** Only need to do this for current access path, because the
		** costEstimate will be copied to the best access paths as
		** necessary.
		*/
		CostEstimate costEstimate = getCostEstimate(optimizer);
		ap.setCostEstimate(costEstimate);

		/*
		** This is the initial cost of this optimizable.  Initialize it
		** to the maximum cost so that the optimizer will think that
		** any access path is better than none.
		*/
		costEstimate.setCost(Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);

		super.startOptimizing(optimizer, rowOrdering);
	}

	/** @see Optimizable#convertAbsoluteToRelativeColumnPosition */
	public int convertAbsoluteToRelativeColumnPosition(int absolutePosition)
	{
		return mapAbsoluteToRelativeColumnPosition(absolutePosition);
	}

	/**
	 * @see Optimizable#estimateCost
	 *
	 * @exception StandardException		Thrown on error
	 */
	public CostEstimate estimateCost(OptimizablePredicateList predList,
									ConglomerateDescriptor cd,
									CostEstimate outerCost,
									Optimizer optimizer,
									RowOrdering rowOrdering)
			throws StandardException
	{
		double cost;
		boolean statisticsForTable = false;
		boolean statisticsForConglomerate = false;
		/* unknownPredicateList contains all predicates whose effect on
		 * cost/selectivity can't be calculated by the store.
		 */
		PredicateList unknownPredicateList = null;

		if (optimizer.useStatistics() && predList != null)
		{
			/* if user has specified that we don't use statistics,
			   pretend that statistics don't exist.
			*/
			statisticsForConglomerate = tableDescriptor.statisticsExist(cd);
			statisticsForTable = tableDescriptor.statisticsExist(null);
			unknownPredicateList = new PredicateList();
			predList.copyPredicatesToOtherList(unknownPredicateList);

		}

		AccessPath currentAccessPath = getCurrentAccessPath();
		JoinStrategy currentJoinStrategy = 
			currentAccessPath.getJoinStrategy();

		optimizer.trace(Optimizer.ESTIMATING_COST_OF_CONGLOMERATE,
						tableNumber, 0, 0.0, cd);

		/* Get the uniqueness factory for later use (see below) */
		double tableUniquenessFactor =
				optimizer.uniqueJoinWithOuterTable(predList);

		boolean oneRowResultSetForSomeConglom = isOneRowResultSet(predList);

		/* Get the predicates that can be used for scanning the base table */
		baseTableRestrictionList.removeAllElements();

		currentJoinStrategy.getBasePredicates(predList,	
									   baseTableRestrictionList,
									   this);
									
		/* RESOLVE: Need to figure out how to cache the StoreCostController */
		StoreCostController scc = getStoreCostController(cd);

		CostEstimate costEstimate = getScratchCostEstimate(optimizer);

		/* First, get the cost for one scan */

		/* Does the conglomerate match at most one row? */
		if (isOneRowResultSet(cd, baseTableRestrictionList))
		{
			/*
			** Tell the RowOrdering that this optimizable is always ordered.
			** It will figure out whether it is really always ordered in the
			** context of the outer tables and their orderings.
			*/
			rowOrdering.optimizableAlwaysOrdered(this);

			singleScanRowCount = 1.0;

			/* Yes, the cost is to fetch exactly one row */
			// RESOLVE: NEED TO FIGURE OUT HOW TO GET REFERENCED COLUMN LIST,
			// FIELD STATES, AND ACCESS TYPE
			cost = scc.getFetchFromFullKeyCost(
										(FormatableBitSet) null,
										0);

			optimizer.trace(Optimizer.MATCH_SINGLE_ROW_COST,
							tableNumber, 0, cost, null);

			costEstimate.setCost(cost, 1.0d, 1.0d);

			/*
			** Let the join strategy decide whether the cost of the base
			** scan is a single scan, or a scan per outer row.
			** NOTE: The multiplication should only be done against the
			** total row count, not the singleScanRowCount.
			*/
			double newCost = costEstimate.getEstimatedCost();

			if (currentJoinStrategy.multiplyBaseCostByOuterRows())
			{
				newCost *= outerCost.rowCount();
			}

			costEstimate.setCost(
				newCost,
				costEstimate.rowCount() * outerCost.rowCount(),
				costEstimate.singleScanRowCount());

			/*
			** Choose the lock mode.  If the start/stop conditions are
			** constant, choose row locking, because we will always match
			** the same row.  If they are not constant (i.e. they include
			** a join), we decide whether to do row locking based on
			** the total number of rows for the life of the query.
			*/
			boolean constantStartStop = true;
			for (int i = 0; i < predList.size(); i++)
			{
				OptimizablePredicate pred = predList.getOptPredicate(i);

				/*
				** The predicates are in index order, so the start and
				** stop keys should be first.
				*/
				if ( ! (pred.isStartKey() || pred.isStopKey()))
				{
					break;
				}

				/* Stop when we've found a join */
				if ( ! pred.getReferencedMap().hasSingleBitSet())
				{
					constantStartStop = false;
					break;
				}
			}

			if (constantStartStop)
			{
				currentAccessPath.setLockMode(
											TransactionController.MODE_RECORD);

				optimizer.trace(Optimizer.ROW_LOCK_ALL_CONSTANT_START_STOP,
								0, 0, 0.0, null);
			}
			else
			{
				setLockingBasedOnThreshold(optimizer, costEstimate.rowCount());
			}

			optimizer.trace(Optimizer.COST_OF_N_SCANS, 
							tableNumber, 0, outerCost.rowCount(), costEstimate);

			/* Add in cost of fetching base row for non-covering index */
			if (cd.isIndex() && ( ! isCoveringIndex(cd) ) )
			{
				double singleFetchCost =
						getBaseCostController().getFetchFromRowLocationCost(
																(FormatableBitSet) null,
																0);
				cost = singleFetchCost * costEstimate.rowCount();

				costEstimate.setEstimatedCost(
								costEstimate.getEstimatedCost() + cost);

				optimizer.trace(Optimizer.NON_COVERING_INDEX_COST,
								tableNumber, 0, cost, null);
			}
		}
		else
		{
			/* Conglomerate might match more than one row */

			/*
			** Some predicates are good for start/stop, but we don't know
			** the values they are being compared to at this time, so we
			** estimate their selectivity in language rather than ask the
			** store about them .  The predicates on the first column of
			** the conglomerate reduce the number of pages and rows scanned.
			** The predicates on columns after the first reduce the number
			** of rows scanned, but have a much smaller effect on the number
			** of pages scanned, so we keep track of these selectivities in
			** two separate variables: extraFirstColumnSelectivity and
			** extraStartStopSelectivity. (Theoretically, we could try to
			** figure out the effect of predicates after the first column
			** on the number of pages scanned, but it's too hard, so we
			** use these predicates only to reduce the estimated number of
			** rows.  For comparisons with known values, though, the store
			** can figure out exactly how many rows and pages are scanned.)
			**
			** Other predicates are not good for start/stop.  We keep track
			** of their selectvities separately, because these limit the
			** number of rows, but not the number of pages, and so need to
			** be factored into the row count but not into the cost.
			** These selectivities are factored into extraQualifierSelectivity.
			**
			** statStartStopSelectivity (using statistics) represents the 
			** selectivity of start/stop predicates that can be used to scan 
			** the index. If no statistics exist for the conglomerate then 
			** the value of this variable remains at 1.0
			** 
			** statCompositeSelectivity (using statistics) represents the 
			** selectivity of all the predicates (including NonBaseTable 
			** predicates). This represents the most educated guess [among 
			** all the wild surmises in this routine] as to the number
			** of rows that will be returned from this joinNode.
			** If no statistics exist on the table or no statistics at all
			** can be found to satisfy the predicates at this join opertor,
			** then statCompositeSelectivity is left initialized at 1.0
			*/
			double extraFirstColumnSelectivity = 1.0d;
			double extraStartStopSelectivity = 1.0d;
			double extraQualifierSelectivity = 1.0d;
			double extraNonQualifierSelectivity = 1.0d;
			double statStartStopSelectivity = 1.0d;
			double statCompositeSelectivity = 1.0d;

			int	   numExtraFirstColumnPreds = 0;
			int	   numExtraStartStopPreds = 0;
			int	   numExtraQualifiers = 0;
			int	   numExtraNonQualifiers = 0;

			/*
			** It is possible for something to be a start or stop predicate
			** without it being possible to use it as a key for cost estimation.
			** For example, with an index on (c1, c2), and the predicate
			** c1 = othertable.c3 and c2 = 1, the comparison on c1 is with
			** an unknown value, so we can't pass it to the store.  This means
			** we can't pass the comparison on c2 to the store, either.
			**
			** The following booleans keep track of whether we have seen
			** gaps in the keys we can pass to the store.
			*/
			boolean startGap = false;
			boolean stopGap = false;
			boolean seenFirstColumn = false;

			/*
			** We need to figure out the number of rows touched to decide
			** whether to use row locking or table locking.  If the start/stop
			** conditions are constant (i.e. no joins), the number of rows
			** touched is the number of rows per scan.  But if the start/stop
			** conditions contain a join, the number of rows touched must
			** take the number of outer rows into account.
			*/
			boolean constantStartStop = true;
			boolean startStopFound = false;

			/* Count the number of start and stop keys */
			int startKeyNum = 0;
			int stopKeyNum = 0;
			OptimizablePredicate pred;
			int predListSize;

			if (predList != null)
				predListSize = baseTableRestrictionList.size();
			else
				predListSize = 0;

			int startStopPredCount = 0;
			ColumnReference firstColumn = null;
			for (int i = 0; i < predListSize; i++)
			{
				pred = baseTableRestrictionList.getOptPredicate(i);
				boolean startKey = pred.isStartKey();
				boolean stopKey = pred.isStopKey();
				if (startKey || stopKey)
				{
					startStopFound = true;

					if ( ! pred.getReferencedMap().hasSingleBitSet())
					{
						constantStartStop = false;
					}

					boolean knownConstant =
						pred.compareWithKnownConstant(this, true);
					if (startKey)
					{
						if (knownConstant && ( ! startGap ) )
						{
							startKeyNum++;
  							if (unknownPredicateList != null)
  								unknownPredicateList.removeOptPredicate(pred);
						}
						else
						{
							startGap = true;
						}
					}

					if (stopKey)
					{
						if (knownConstant && ( ! stopGap ) )
						{
							stopKeyNum++;
  							if (unknownPredicateList != null)
  								unknownPredicateList.removeOptPredicate(pred);
						}
						else
						{
							stopGap = true;
						}
					}

					/* If either we are seeing startGap or stopGap because start/stop key is
					 * comparison with non-constant, we should multiply the selectivity to
					 * extraFirstColumnSelectivity.  Beetle 4787.
					 */
					if (startGap || stopGap)
					{
						// Don't include redundant join predicates in selectivity calculations
						if (baseTableRestrictionList.isRedundantPredicate(i))
							continue;

						if (startKey && stopKey)
							startStopPredCount++;

						if (pred.getIndexPosition() == 0)
						{
							extraFirstColumnSelectivity *=
														pred.selectivity(this);
							if (! seenFirstColumn)
							{
								ValueNode relNode = ((Predicate) pred).getAndNode().getLeftOperand();
								if (relNode instanceof BinaryRelationalOperatorNode)
									firstColumn = ((BinaryRelationalOperatorNode) relNode).getColumnOperand(this);
								seenFirstColumn = true;
							}
						}
						else
						{
							extraStartStopSelectivity *= pred.selectivity(this);
							numExtraStartStopPreds++;
						}
					}
				}
				else
				{
					// Don't include redundant join predicates in selectivity calculations
					if (baseTableRestrictionList.isRedundantPredicate(i))
					{
						continue;
					}

					/* If we have "like" predicate on the first index column, it is more likely
					 * to have a smaller range than "between", so we apply extra selectivity 0.2
					 * here.  beetle 4387, 4787.
					 */
					if (pred instanceof Predicate)
					{
						ValueNode leftOpnd = ((Predicate) pred).getAndNode().getLeftOperand();
						if (firstColumn != null && leftOpnd instanceof LikeEscapeOperatorNode)
						{
							LikeEscapeOperatorNode likeNode = (LikeEscapeOperatorNode) leftOpnd;
							if (likeNode.getLeftOperand().isParameterNode())
							{
								ValueNode receiver = ((TernaryOperatorNode) likeNode).getReceiver();
								if (receiver instanceof ColumnReference)
								{
									ColumnReference cr = (ColumnReference) receiver;
									if (cr.getTableNumber() == firstColumn.getTableNumber() &&
										cr.getColumnNumber() == firstColumn.getColumnNumber())
										extraFirstColumnSelectivity *= 0.2;
								}
							}
						}
					}

					if (pred.isQualifier())
					{
						extraQualifierSelectivity *= pred.selectivity(this);
						numExtraQualifiers++;
					}
					else
					{
						extraNonQualifierSelectivity *= pred.selectivity(this);
						numExtraNonQualifiers++;
					}

					/*
					** Strictly speaking, it shouldn't be necessary to
					** indicate a gap here, since there should be no more
					** start/stop predicates, but let's do it, anyway.
					*/
					startGap = true;
					stopGap = true;
				}
			}

			if (unknownPredicateList != null)
			{
				statCompositeSelectivity = unknownPredicateList.selectivity(this);
				if (statCompositeSelectivity == -1.0d)
					statCompositeSelectivity = 1.0d;