frombasetable.java

derby database source code.good for you.

			}

			if (seenFirstColumn && statisticsForConglomerate &&
				(startStopPredCount > 0))
			{
				statStartStopSelectivity = 
					tableDescriptor.selectivityForConglomerate(cd, startStopPredCount);
			}

			/*
			** Factor the non-base-table predicates into the extra
			** non-qualifier selectivity, since these will restrict the
			** number of rows, but not the cost.
			*/
			extraNonQualifierSelectivity *=
				currentJoinStrategy.nonBasePredicateSelectivity(this, predList);

			/* Create the start and stop key arrays, and fill them in */
			DataValueDescriptor[] startKeys;
			DataValueDescriptor[] stopKeys;

			if (startKeyNum > 0)
				startKeys = new DataValueDescriptor[startKeyNum];
			else
				startKeys = null;

			if (stopKeyNum > 0)
				stopKeys = new DataValueDescriptor[stopKeyNum];
			else
				stopKeys = null;

			startKeyNum = 0;
			stopKeyNum = 0;
			startGap = false;
			stopGap = false;

			for (int i = 0; i < predListSize; i++)
			{
				pred = baseTableRestrictionList.getOptPredicate(i);
				boolean startKey = pred.isStartKey();
				boolean stopKey = pred.isStopKey();

				if (startKey || stopKey)
				{
					boolean knownConstant = pred.compareWithKnownConstant(this, true);

					if (startKey)
					{
						if (knownConstant && ( ! startGap ) )
						{
							startKeys[startKeyNum] = pred.getCompareValue(this);
							startKeyNum++;
						}
						else
						{
							startGap = true;
						}
					}

					if (stopKey)
					{
						if (knownConstant && ( ! stopGap ) )
						{
							stopKeys[stopKeyNum] = pred.getCompareValue(this);
							stopKeyNum++;
						}
						else
						{
							stopGap = true;
						}
					}
				}
				else
				{
					startGap = true;
					stopGap = true;
				}
			}

			int startOperator;
			int stopOperator;

			if (baseTableRestrictionList != null)
			{
				startOperator = baseTableRestrictionList.startOperator(this);
				stopOperator = baseTableRestrictionList.stopOperator(this);
			}
			else
			{
				/*
				** If we're doing a full scan, it doesn't matter what the
				** start and stop operators are.
				*/
				startOperator = ScanController.NA;
				stopOperator = ScanController.NA;
			}

			/*
			** Get a row template for this conglomerate.  For now, just tell
			** it we are using all the columns in the row.
			*/
			DataValueDescriptor[] rowTemplate = 
                getRowTemplate(cd, getBaseCostController());

			/* we prefer index than table scan for concurrency reason, by a small
			 * adjustment on estimated row count.  This affects optimizer's decision
			 * especially when few rows are in table. beetle 5006. This makes sense
			 * since the plan may stay long before we actually check and invalidate it.
			 * And new rows may be inserted before we check and invalidate the plan.
			 * Here we only prefer index that has start/stop key from predicates. Non-
			 * constant start/stop key case is taken care of by selectivity later.
			 */
			long baseRC = (startKeys != null || stopKeys != null) ? baseRowCount() : baseRowCount() + 5;

			scc.getScanCost(
					currentJoinStrategy.scanCostType(),
					baseRC,
                    1,
					forUpdate(),
					(FormatableBitSet) null,
					rowTemplate,
					startKeys,
					startOperator,
					stopKeys,
					stopOperator,
					false,
					0,
					costEstimate);

			/* initialPositionCost is the first part of the index scan cost we get above.
			 * It's the cost of initial positioning/fetch of key.  So it's unrelated to
			 * row count of how many rows we fetch from index.  We extract it here so that
			 * we only multiply selectivity to the other part of index scan cost, which is
			 * nearly linear, to make cost calculation more accurate and fair, especially
			 * compared to the plan of "one row result set" (unique index). beetle 4787.
			 */
			double initialPositionCost = 0.0;
			if (cd.isIndex())
			{
				initialPositionCost = scc.getFetchFromFullKeyCost((FormatableBitSet) null, 0);
				/* oneRowResultSetForSomeConglom means there's a unique index, but certainly
				 * not this one since we are here.  If store knows this non-unique index
				 * won't return any row or just returns one row (eg., the predicate is a
				 * comparison with constant or almost empty table), we do minor adjustment
				 * on cost (affecting decision for covering index) and rc (decision for
				 * non-covering). The purpose is favoring unique index. beetle 5006.
				 */
				if (oneRowResultSetForSomeConglom && costEstimate.rowCount() <= 1)
				{
					costEstimate.setCost(costEstimate.getEstimatedCost() * 2,
										 costEstimate.rowCount() + 2,
										 costEstimate.singleScanRowCount() + 2);
				}
			}

			optimizer.trace(Optimizer.COST_OF_CONGLOMERATE_SCAN1,
							tableNumber, 0, 0.0, cd);
			optimizer.trace(Optimizer.COST_OF_CONGLOMERATE_SCAN2,
							tableNumber, 0, 0.0, costEstimate);
			optimizer.trace(Optimizer.COST_OF_CONGLOMERATE_SCAN3,
							numExtraFirstColumnPreds, 0, 
							extraFirstColumnSelectivity, null);
			optimizer.trace(Optimizer.COST_OF_CONGLOMERATE_SCAN4,
							numExtraStartStopPreds, 0, 
							extraStartStopSelectivity, null);
			optimizer.trace(Optimizer.COST_OF_CONGLOMERATE_SCAN7,
							startStopPredCount, 0,
							statStartStopSelectivity, null);
			optimizer.trace(Optimizer.COST_OF_CONGLOMERATE_SCAN5,
							numExtraQualifiers, 0, 
							extraQualifierSelectivity, null);
			optimizer.trace(Optimizer.COST_OF_CONGLOMERATE_SCAN6,
							numExtraNonQualifiers, 0, 
							extraNonQualifierSelectivity, null);

			/* initial row count is the row count without applying
			   any predicates-- we use this at the end of the routine
			   when we use statistics to recompute the row count.
			*/
			double initialRowCount = costEstimate.rowCount();

			if (statStartStopSelectivity != 1.0d)
			{
				/*
				** If statistics exist use the selectivity computed 
				** from the statistics to calculate the cost. 
				** NOTE: we apply this selectivity to the cost as well
				** as both the row counts. In the absence of statistics
				** we only applied the FirstColumnSelectivity to the 
				** cost.
				*/
				costEstimate.setCost(
							 scanCostAfterSelectivity(costEstimate.getEstimatedCost(),
													  initialPositionCost,
													  statStartStopSelectivity,
													  oneRowResultSetForSomeConglom),
							 costEstimate.rowCount() * statStartStopSelectivity,
							 costEstimate.singleScanRowCount() *
							 statStartStopSelectivity);
				optimizer.trace(Optimizer.COST_INCLUDING_STATS_FOR_INDEX,
								tableNumber, 0, 0.0, costEstimate);

			}
			else
			{
				/*
				** Factor in the extra selectivity on the first column
				** of the conglomerate (see comment above).
				** NOTE: In this case we want to apply the selectivity to both
				** the total row count and singleScanRowCount.
				*/
				if (extraFirstColumnSelectivity != 1.0d)
				{
					costEstimate.setCost(
						 scanCostAfterSelectivity(costEstimate.getEstimatedCost(),
												  initialPositionCost,
												  extraFirstColumnSelectivity,
												  oneRowResultSetForSomeConglom),
						 costEstimate.rowCount() * extraFirstColumnSelectivity,
						 costEstimate.singleScanRowCount() * extraFirstColumnSelectivity);
					
					optimizer.trace(Optimizer.COST_INCLUDING_EXTRA_1ST_COL_SELECTIVITY,
									tableNumber, 0, 0.0, costEstimate);
				}

				/* Factor in the extra start/stop selectivity (see comment above).
				 * NOTE: In this case we want to apply the selectivity to both
				 * the row count and singleScanRowCount.
				 */
				if (extraStartStopSelectivity != 1.0d)
				{
					costEstimate.setCost(
						costEstimate.getEstimatedCost(),
						costEstimate.rowCount() * extraStartStopSelectivity,
						costEstimate.singleScanRowCount() * extraStartStopSelectivity);

					optimizer.trace(Optimizer.COST_INCLUDING_EXTRA_START_STOP,
									tableNumber, 0, 0.0, costEstimate);
				}
			}

			/*
			** Figure out whether to do row locking or table locking.
			**
			** If there are no start/stop predicates, we're doing full
			** conglomerate scans, so do table locking.
			*/
			if (! startStopFound)
			{
				currentAccessPath.setLockMode(
											TransactionController.MODE_TABLE);

				optimizer.trace(Optimizer.TABLE_LOCK_NO_START_STOP,
							    0, 0, 0.0, null);
			}
			else
			{
				/*
				** Figure out the number of rows touched.  If all the
				** start/stop predicates are constant, the number of
				** rows touched is the number of rows per scan.
				** This is also true for join strategies that scan the
				** inner table only once (like hash join) - we can
				** tell if we have one of those, because
				** multiplyBaseCostByOuterRows() will return false.
				*/
				double rowsTouched = costEstimate.rowCount();

				if ( (! constantStartStop) &&
					 currentJoinStrategy.multiplyBaseCostByOuterRows())
				{
					/*
					** This is a join where the inner table is scanned
					** more than once, so we have to take the number
					** of outer rows into account.  The formula for this
					** works out as follows:
					**
					**	total rows in table = r
					**  number of rows touched per scan = s
					**  number of outer rows = o
					**  proportion of rows touched per scan = s / r
					**  proportion of rows not touched per scan =
					**										1 - (s / r)
					**  proportion of rows not touched for all scans =
					**									(1 - (s / r)) ** o
					**  proportion of rows touched for all scans =
					**									1 - ((1 - (s / r)) ** o)
					**  total rows touched for all scans =
					**							r * (1 - ((1 - (s / r)) ** o))
					**
					** In doing these calculations, we must be careful not
					** to divide by zero.  This could happen if there are
					** no rows in the table.  In this case, let's do table
					** locking.
					*/
					double r = baseRowCount();
					if (r > 0.0)
					{
						double s = costEstimate.rowCount();
						double o = outerCost.rowCount();
						double pRowsNotTouchedPerScan = 1.0 - (s / r);
						double pRowsNotTouchedAllScans =
										Math.pow(pRowsNotTouchedPerScan, o);
						double pRowsTouchedAllScans =
										1.0 - pRowsNotTouchedAllScans;
						double rowsTouchedAllScans =
										r * pRowsTouchedAllScans;

						rowsTouched = rowsTouchedAllScans;
					}
					else
					{
						/* See comments in setLockingBasedOnThreshold */
						rowsTouched = optimizer.tableLockThreshold() + 1;
					}
				}

				setLockingBasedOnThreshold(optimizer, rowsTouched);
			}

			/*
			** If the index isn't covering, add the cost of getting the
			** base row.  Only apply extraFirstColumnSelectivity and extraStartStopSelectivity
			** before we do this, don't apply extraQualifierSelectivity etc.  The
			** reason is that the row count here should be the number of index rows
			** (and hence heap rows) we get, and we need to fetch all those rows, even
			** though later on some of them may be filtered out by other predicates.
			** beetle 4787.
			*/
			if (cd.isIndex() && ( ! isCoveringIndex(cd) ) )
			{
				double singleFetchCost =
						getBaseCostController().getFetchFromRowLocationCost(
																(FormatableBitSet) null,
																0);

				cost = singleFetchCost * costEstimate.rowCount();

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

				optimizer.trace(Optimizer.COST_OF_NONCOVERING_INDEX,
								tableNumber, 0, 0.0, costEstimate);
			}

			/* Factor in the extra qualifier selectivity (see comment above).
			 * NOTE: In this case we want to apply the selectivity to both
			 * the row count and singleScanRowCount.
			 */
			if (extraQualifierSelectivity != 1.0d)
			{
				costEstimate.setCost(
						costEstimate.getEstimatedCost(),
						costEstimate.rowCount() * extraQualifierSelectivity,
						costEstimate.singleScanRowCount() * extraQualifierSelectivity);

				optimizer.trace(Optimizer.COST_INCLUDING_EXTRA_QUALIFIER_SELECTIVITY,
								tableNumber, 0, 0.0, costEstimate);
			}

			singleScanRowCount = costEstimate.singleScanRowCount();

			/*
			** 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.
			** NOTE: Do not multiply row count if we determined that
			** conglomerate is a 1 row result set when costing nested
			** loop.  (eg, we will find at most 1 match when probing
			** the hash table.)
			*/
			double newCost = costEstimate.getEstimatedCost();
			double rowCount = costEstimate.rowCount();

			/*
			** RESOLVE - If there is a unique index on the joining
			** columns, the number of matching rows will equal the
			** number of outer rows, even if we're not considering the
			** unique index for this access path. To figure that out,
			** however, would require an analysis phase at the beginning
			** of optimization. So, we'll always multiply the number
			** of outer rows by the number of rows per scan. This will
			** give us a higher than actual row count when there is
			** such a unique index, which will bias the optimizer toward
			** using the unique index. This is probably OK most of the
			** time, since the optimizer would probably choose the
			** unique index, anyway. But it would be better if the
			** optimizer set the row count properly in this case.
			*/
			if (currentJoinStrategy.multiplyBaseCostByOuterRows())
			{
				newCost *= outerCost.rowCount();
			}

			rowCount *= outerCost.rowCount();
			initialRowCount *= outerCost.rowCount();


			/*
			** If this table can generate at most one row per scan,
			** the maximum row count is the number of outer rows.
			** NOTE: This does not completely take care of the RESOLVE
			** in the above comment, since it will only notice
			** one-row result sets for the current join order.
			*/
			if (oneRowResultSetForSomeConglom)
			{
				if (outerCost.rowCount() < rowCount)
				{
					rowCount = outerCost.rowCount();
				}
			}

			/*
			** The estimated cost may be too high for indexes, if the
			** estimated row count exceeds the maximum. Only do this
			** if we're not doing a full scan, and the start/stop position
			** is not constant (i.e. we're doing a join on the first column
			** of the index) - the reason being that this is when the
			** cost may be inaccurate.
			*/
			if (cd.isIndex() && startStopFound && ( ! constantStartStop ) )
			{
				/*
				** Does any table outer to this one have a unique key on
				** a subset of the joining columns? If so, the maximum number
				** of rows that this table can return is the number of rows