hashjoinstrategy.java

derby database source code.good for you.

/*

   Derby - Class org.apache.derby.impl.sql.compile.HashJoinStrategy

   Copyright 1998, 2004 The Apache Software Foundation or its licensors, as applicable.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.

 */

package org.apache.derby.impl.sql.compile;

import org.apache.derby.iapi.sql.compile.CostEstimate;
import org.apache.derby.iapi.sql.compile.ExpressionClassBuilderInterface;
import org.apache.derby.iapi.sql.compile.JoinStrategy;
import org.apache.derby.iapi.sql.compile.Optimizable;
import org.apache.derby.iapi.sql.compile.Optimizer;
import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;

import org.apache.derby.iapi.sql.dictionary.DataDictionary;
import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;

import org.apache.derby.iapi.store.access.StoreCostController;
import org.apache.derby.iapi.store.access.TransactionController;

import org.apache.derby.iapi.services.compiler.MethodBuilder;

import org.apache.derby.impl.sql.compile.ExpressionClassBuilder;
import org.apache.derby.impl.sql.compile.ProjectRestrictNode;
import org.apache.derby.impl.sql.compile.Predicate;

import org.apache.derby.iapi.error.StandardException;

import org.apache.derby.iapi.reference.SQLState;

import org.apache.derby.iapi.services.cache.ClassSize;

import org.apache.derby.iapi.services.sanity.SanityManager;

import org.apache.derby.iapi.services.io.FormatableArrayHolder;
import org.apache.derby.iapi.services.io.FormatableIntHolder;

import java.util.Vector;

public class HashJoinStrategy extends BaseJoinStrategy {
	public HashJoinStrategy() {
	}

	/**
	 * @see JoinStrategy#feasible
	 *
	 * @exception StandardException		Thrown on error
	 */
	public boolean feasible(Optimizable innerTable,
							OptimizablePredicateList predList,
							Optimizer optimizer
							)
					throws StandardException 
	{
		int[] hashKeyColumns = null;

		ConglomerateDescriptor cd = null;

		/* If the innerTable is a VTI, then we
		 * must check to see if there are any
		 * join columns in the VTI's parameters.
		 * If so, then hash join is not feasible.
		 */
		if (! innerTable.isMaterializable())
		{

			optimizer.trace(Optimizer.HJ_SKIP_NOT_MATERIALIZABLE, 0, 0, 0.0,
							null);
			return false;
		}

		/* Don't consider hash join on the target table of an update/delete.
		 * RESOLVE - this is a temporary restriction.  Problem is that we
		 * do not put RIDs into the row in the hash table when scanning
		 * the heap and we need them for a target table.
		 */
		if (innerTable.isTargetTable())
		{
			return false;
		}

		if (innerTable.isBaseTable())
		{
			/* Must have an equijoin on a column in the conglomerate */
			cd = innerTable.getCurrentAccessPath().getConglomerateDescriptor();
		}
		
		/* Look for equijoins in the predicate list */
		hashKeyColumns = findHashKeyColumns(
											innerTable,
											cd,
											predList);

		if (SanityManager.DEBUG)
		{
			if (hashKeyColumns == null)
			{
				optimizer.trace(Optimizer.HJ_SKIP_NO_JOIN_COLUMNS, 0, 0, 0.0, null);
			}
			else
			{
				optimizer.trace(Optimizer.HJ_HASH_KEY_COLUMNS, 0, 0, 0.0, hashKeyColumns);
			}
		}

		if (hashKeyColumns == null)
		{
			return false;
		}

		return true;
	}

	/** @see JoinStrategy#ignoreBulkFetch */
	public boolean ignoreBulkFetch() {
		return true;
	}

	/** @see JoinStrategy#multiplyBaseCostByOuterRows */
	public boolean multiplyBaseCostByOuterRows() {
		return false;
	}

	/**
	 * @see JoinStrategy#getBasePredicates
	 *
	 * @exception StandardException		Thrown on error
	 */
	public OptimizablePredicateList getBasePredicates(
									OptimizablePredicateList predList,
									OptimizablePredicateList basePredicates,
									Optimizable innerTable)
							throws StandardException {
		if (SanityManager.DEBUG) {
			SanityManager.ASSERT(basePredicates.size() == 0,
				"The base predicate list should be empty.");
		}

		for (int i = predList.size() - 1; i >= 0; i--) {
			OptimizablePredicate pred = predList.getOptPredicate(i);

			if (innerTable.getReferencedTableMap().contains(pred.getReferencedMap()))
			{
				basePredicates.addOptPredicate(pred);
				predList.removeOptPredicate(i);
			}
		}

		basePredicates.classify(
				innerTable,
				innerTable.getCurrentAccessPath().getConglomerateDescriptor());

		return basePredicates;
	}

	/** @see JoinStrategy#nonBasePredicateSelectivity */
	public double nonBasePredicateSelectivity(
										Optimizable innerTable,
										OptimizablePredicateList predList) {
		double retval = 1.0;

		if (predList != null) {
			for (int i = 0; i < predList.size(); i++) {
				// Don't include redundant join predicates in selectivity calculations
				if (predList.isRedundantPredicate(i))
				{
					continue;
				}

				retval *= predList.getOptPredicate(i).selectivity(innerTable);
			}
		}

		return retval;
	}
	
	/**
	 * @see JoinStrategy#putBasePredicates
	 *
	 * @exception StandardException		Thrown on error
	 */
	public void putBasePredicates(OptimizablePredicateList predList,
									OptimizablePredicateList basePredicates)
						throws StandardException {
		for (int i = basePredicates.size() - 1; i >= 0; i--) {
			OptimizablePredicate pred = basePredicates.getOptPredicate(i);

			predList.addOptPredicate(pred);
			basePredicates.removeOptPredicate(i);
		}
	}

	/** @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, so don't do anything here.
		*/
	}

	/** @see JoinStrategy#maxCapacity */
	public int maxCapacity( int userSpecifiedCapacity,
                            int maxMemoryPerTable,
                            double perRowUsage) {
        if( userSpecifiedCapacity >= 0)
            return userSpecifiedCapacity;
        perRowUsage += ClassSize.estimateHashEntrySize();
        if( perRowUsage <= 1)
            return maxMemoryPerTable;
        return (int)(maxMemoryPerTable/perRowUsage);
	}

	/** @see JoinStrategy#getName */
	public String getName() {
		return "HASH";
	}

	/** @see JoinStrategy#scanCostType */
	public int scanCostType() {
		return StoreCostController.STORECOST_SCAN_SET;
	}

	/** @see JoinStrategy#resultSetMethodName */
	public String resultSetMethodName(boolean bulkFetch) {
		return "getHashScanResultSet";
	}

	/** @see JoinStrategy#joinResultSetMethodName */
	public String joinResultSetMethodName() {
		return "getHashJoinResultSet";
	}

	/** @see JoinStrategy#halfOuterJoinResultSetMethodName */
	public String halfOuterJoinResultSetMethodName() {
		return "getHashLeftOuterJoinResultSet";
	}

	/**
	 * @see JoinStrategy#getScanArgs
	 *
	 * @exception StandardException		Thrown on error
	 */
	public int getScanArgs(
							TransactionController tc,
							MethodBuilder mb,
							Optimizable innerTable,
							OptimizablePredicateList storeRestrictionList,
							OptimizablePredicateList nonStoreRestrictionList,
							ExpressionClassBuilderInterface acbi,
							int bulkFetch,
							MethodBuilder resultRowAllocator,
							int colRefItem,
							int indexColItem,
							int lockMode,
							boolean tableLocked,
							int isolationLevel,
                            int maxMemoryPerTable
							)
						throws StandardException {
		ExpressionClassBuilder acb = (ExpressionClassBuilder) acbi;

		fillInScanArgs1(tc,
										mb,
										innerTable,
										storeRestrictionList,
										acb,
										resultRowAllocator);

		nonStoreRestrictionList.generateQualifiers(acb,	mb, innerTable, true);
		mb.push(innerTable.initialCapacity());
		mb.push(innerTable.loadFactor());
		mb.push(innerTable.maxCapacity( (JoinStrategy) this, maxMemoryPerTable));