fromlist.java

derby database source code.good for you.

		PredicateList predicatesTemp;
		predicatesTemp = (PredicateList) getNodeFactory().getNode(
			C_NodeTypes.PREDICATE_LIST,	getContextManager());
		int wherePredicatesSize = wherePredicates.size();
		for (int index = 0; index < wherePredicatesSize; index++)
			predicatesTemp.addPredicate((Predicate)wherePredicates.elementAt(index));

		/* When considering subquery flattening, we are interested
		 * in the 1st (and only) entry in the RCL.  (The RCL will be
		 * null if result column is not of interest for subquery flattening.)
		 * We are interested in all entries in the RCL for distinct
		 * elimination.
		 */
		if (rcl != null)
		{
			ResultColumn rc = (ResultColumn) rcl.elementAt(0);
			if (rc.getExpression() instanceof ColumnReference)
			{
				additionalCR = (ColumnReference) rc.getExpression();
			}
		}

		/* First see if all entries are FromBaseTables.  No point
		 * in continuing if not.
		 */
		int size = size();
		for (int index = 0; index < size; index++)
		{
			FromTable fromTable = (FromTable) elementAt(index);
			if (! (fromTable instanceof ProjectRestrictNode))
			{
				return false;
			}

			ProjectRestrictNode prn = (ProjectRestrictNode) fromTable;

			if (! (prn.getChildResult() instanceof FromBaseTable))
			{
				return false;
			}
			FromBaseTable fbt = (FromBaseTable) prn.getChildResult();
			//Following for loop code is to take care of Derby-251 (DISTINCT returns
			//duplicate rows).
			//Derby-251 returned duplicate rows because we were looking at predicates
			//that belong to existsTable to determine DISTINCT elimination
			//
			//(Check method level comments to understand DISTINCT elimination rules.)
			//
			//For one specific example, consider the query below
			//select  distinct  q1."NO1" from IDEPT q1, IDEPT q2
			//where  ( q2."DISCRIM_DEPT" = 'HardwareDept')
			//and  ( q1."DISCRIM_DEPT" = 'SoftwareDept')  and  ( q1."NO1" <> ALL
			//(select  q3."NO1" from IDEPT q3 where  (q3."REPORTTO_NO" =  q2."NO1")))
			//(select  q3."NO1" from IDEPT q3 where  ( ABS(q3."REPORTTO_NO") =  q2."NO1")))
			//
			//Table IDEPT in the query above has a primary key defined on column "NO1"
			//This query gets converted to following during optimization
			//
			//select  distinct  q1."NO1" from IDEPT q1, IDEPT q2
			//where  ( q2."DISCRIM_DEPT" = 'HardwareDept')
			//and  ( q1."DISCRIM_DEPT" = 'SoftwareDept')  and  not exists (
			//(select  q3."NO1" from IDEPT q3 where
			//(  ( ABS(q3."REPORTTO_NO") =  q2."NO1")  and q3."NO1" = q1."NO1") ) )  ;
			//
			//For the optimized query above, Derby generates following predicates.
			//ABS(q3.reportto_no) = q2.no1
			//q2.discrim_dept = 'HardwareDept'
			//q1.descrim_dept = 'SoftwareDept'
			//q1.no1 = q3.no1
			//The predicate ABS(q3."NO1") = q1."NO1" should not be considered when trying
			//to determine if q1 in the outer query has equality comparisons. 
			//Similarly, the predicate q3.reportto_no = q2.no1 should not be
			//considered when trying to determine if q2 in the outer query has
			//equality comparisons. To achieve this, predicates based on exists base
			//table q3 (the first and the last predicate) should be removed while
			//evaluating outer query for uniqueness.
			//
			if (fbt.getExistsBaseTable())
			{
				int existsTableNumber = fbt.getTableNumber();
				int predicatesTempSize = predicatesTemp.size();
				for (int predicatesTempIndex = predicatesTempSize-1;
					predicatesTempIndex >= 0; predicatesTempIndex--)
				{
					AndNode topAndNode = (AndNode)
						((Predicate) predicatesTemp.elementAt(predicatesTempIndex)).getAndNode();

					for (ValueNode whereWalker = topAndNode; whereWalker instanceof AndNode;
						whereWalker = ((AndNode) whereWalker).getRightOperand())
					{
						// See if this is a candidate =
						AndNode and = (AndNode) whereWalker;

						//we only need to worry about equality predicates because only those
						//predicates are considered during DISTINCT elimination.
						if (!and.getLeftOperand().isRelationalOperator() ||
							!(((RelationalOperator)(and.getLeftOperand())).getOperator() ==
							RelationalOperator.EQUALS_RELOP))
						{
							continue;
						}

						JBitSet referencedTables = and.getLeftOperand().getTablesReferenced();
						if (referencedTables.get(existsTableNumber))
						{
							predicatesTemp.removeElementAt(predicatesTempIndex);
							break;
						}
					}
				}
			}
		}

		/* Build an array of tableNumbers from this query block.
		 * We will use that array to find out if we have at least
		 * one table with a uniqueness condition based only on
		 * constants, parameters and correlation columns.
		 */
		tableNumbers = getTableNumbers();
		JBitSet[][] tableColMap = new JBitSet[size][size];
		boolean[] oneRow = new boolean[size];
		boolean oneRowResult = false;

		/* See if each table has a uniqueness condition */
		for (int index = 0; index < size; index++)
		{
			ProjectRestrictNode prn = (ProjectRestrictNode) elementAt(index);
			FromBaseTable fbt = (FromBaseTable) prn.getChildResult();

			// Skip over EXISTS FBT since they cannot introduce duplicates
			if (fbt.getExistsBaseTable())
			{
				oneRow[index] = true;
				continue;
			}

			int numColumns = fbt.getTableDescriptor().getNumberOfColumns();
			boolean[] eqOuterCols = new boolean[numColumns + 1];
			int tableNumber = fbt.getTableNumber();
			boolean resultColTable = false;
			for (int i = 0; i < size; i++)
				tableColMap[index][i] = new JBitSet(numColumns + 1);

			if (additionalCR != null &&
				additionalCR.getTableNumber() == tableNumber)
			{
				rcl.recordColumnReferences(eqOuterCols, tableColMap[index], index);
				resultColTable = true;
			}

			/* Now see if there are any equality conditions
			 * of interest in the where clause.
			 */
			if (whereClause != null)
			{
				whereClause.checkTopPredicatesForEqualsConditions(
								tableNumber, eqOuterCols, tableNumbers,
								tableColMap[index], resultColTable);
			}

			/* Now see if there are any equality conditions
			 * of interest in the where predicates.
			 */
			predicatesTemp.checkTopPredicatesForEqualsConditions(
								tableNumber, eqOuterCols, tableNumbers,
								tableColMap[index], resultColTable);

			/* Now see if there are any equality conditions
			 * of interest that were already pushed down to the
			 * PRN above the FBT. (Single table predicates.)
			 */
			if (prn.getRestrictionList() != null)
			{
				prn.getRestrictionList().checkTopPredicatesForEqualsConditions(
								tableNumber, eqOuterCols, tableNumbers,
								tableColMap[index], resultColTable);
			}

			/* We can finally check to see if the marked columns
			 * are a superset of any unique index.
			 */
			if (! fbt.supersetOfUniqueIndex(tableColMap[index]))
			{
				return false;
			}
			
			/* Do we have at least 1 table whose equality condition
			 * is based solely on constants, parameters and correlation columns.
			 */
			oneRowResult = fbt.supersetOfUniqueIndex(eqOuterCols);
			if (oneRowResult)
			{
				oneRow[index] = true;
				satisfiesOuter = true;
			}
		}

		/* Have we met all of the criteria */
		if (satisfiesOuter)
		{
			/* check that all the tables are joined by unique indexes 
			 * or only produce 1 row
			 */
			boolean foundOneRow = true;
			while (foundOneRow)
			{
				foundOneRow = false;
				for (int index = 0; index < size; index++)
				{
					if (oneRow[index])
					{
						for (int i = 0; i < size; i++)
						{
							/* unique key join - exists tables already marked as 
							 * 1 row - so don't need to look at them
							 */
							if (!oneRow[i] && tableColMap[i][index].get(0))
							{
								oneRow[i] = true;
								foundOneRow = true;
							}
						}
					}
				}
			}
			/* does any table produce more than one row */
			for (int index = 0; index < size; index++)
			{
				if (!oneRow[index])
				{
					satisfiesOuter = false;
					break;
				}
			}
		}
		return satisfiesOuter;
	}

	int[] getTableNumbers()
	{
		int size = size();
		int[] tableNumbers = new int[size];
		for (int index = 0; index < size; index++)
		{
			ProjectRestrictNode prn = (ProjectRestrictNode) elementAt(index);
			if (! (prn.getChildResult() instanceof FromTable))
			{
				continue;
			}
			FromTable ft = (FromTable) prn.getChildResult();
			tableNumbers[index] = ft.getTableNumber();
		}

		return tableNumbers;
	}

	/**
	 * Mark all of the FromBaseTables in the list as EXISTS FBTs.
	 * Each EBT has the same dependency list - those tables that are referenced
	 * minus the tables in the from list.
	 *
	 * @param referencedTableMap	The referenced table map.
	 * @param outerFromList			FromList from outer query block
	 * @param isNotExists			Whether or not for NOT EXISTS
	 *
	 * @return Nothing.
	 *
	 * @exception StandardException		Thrown on error
	 */
	void genExistsBaseTables(JBitSet referencedTableMap, FromList outerFromList,
							 boolean isNotExists)
		throws StandardException
	{
		JBitSet			dependencyMap = (JBitSet) referencedTableMap.clone();

		// We currently only flatten single table from lists
		if (SanityManager.DEBUG)
		{
			if (size() != 1)
			{
				SanityManager.THROWASSERT(
					"size() expected to be 1, not " + size());
			}
		}

		/* Create the dependency map */
		int size = size();
		for (int index = 0; index < size; index++)
		{
			ResultSetNode ft = ((ProjectRestrictNode) elementAt(index)).getChildResult();
			if (ft instanceof FromTable)
			{
				dependencyMap.clear(((FromTable) ft).getTableNumber());
			}
		}

		/* Degenerate case - If flattening a non-correlated EXISTS subquery
		 * then we need to make the table that is getting flattened dependendent on
		 * all of the tables in the outer query block.  Gross but true.  Otherwise
		 * that table can get chosen as an outer table and introduce duplicates.
		 * The reason that duplicates can be introduced is that we do special processing
		 * in the join to make sure only one qualified row from the right side is
		 * returned.  If the exists table is on the left, we can return all the
		 * qualified rows. 
		 */
		if (dependencyMap.getFirstSetBit() == -1)
		{
			int outerSize = outerFromList.size();
			for (int outer = 0; outer < outerSize; outer++)
				dependencyMap.or(((FromTable) outerFromList.elementAt(outer)).getReferencedTableMap());
		}

		/* Do the marking */
		for (int index = 0; index < size; index++)
		{
			FromTable fromTable = (FromTable) elementAt(index);
			if (fromTable instanceof ProjectRestrictNode)
			{
				ProjectRestrictNode prn = (ProjectRestrictNode) fromTable;
				if (prn.getChildResult() instanceof FromBaseTable)
				{
					FromBaseTable fbt = (FromBaseTable) prn.getChildResult();
					fbt.setExistsBaseTable(true, (JBitSet) dependencyMap.clone(), isNotExists);
				}
			}
		}
	}

	/**
	 * Get the lock mode for the target of an update statement
	 * (a delete or update).  The update mode will always be row for
	 * CurrentOfNodes.  It will be table if there is no where clause.
	 *
	 * @return	The lock mode
	 */
	public int updateTargetLockMode()
	{
		if (SanityManager.DEBUG)
		{
			if (size() != 1)
			{
				SanityManager.THROWASSERT(
					"size() expected to be 1");
			}
		}
		return ((ResultSetNode) elementAt(0)).updateTargetLockMode();
	}

	/**
	 * Return whether or not the user specified a hash join for any of the 
	 * tables in this list.
	 *
	 * @return	Whether or not the user specified a hash join for any of the 
	 *			tables in this list.
	 */
	boolean hashJoinSpecified()
	{
		int size = size();
		for (int index = 0; index < size; index++)
		{
			FromTable ft = (FromTable) elementAt(index);
			String joinStrategy = ft.getUserSpecifiedJoinStrategy();

			if (joinStrategy != null && StringUtil.SQLToUpperCase(joinStrategy).equals("HASH"))
			{
				return true;
			}
		}

		return false;
	}

	/**
	 * Accept a visitor, and call v.visit()
	 * on child nodes as necessary.  
	 * 
	 * @param v the visitor
	 *
	 * @exception StandardException on error
	 */
	public Visitable accept(Visitor v) 
		throws StandardException
	{
		int size = size();
		for (int index = 0; index < size; index++)
		{
			FromTable fromTable = (FromTable) elementAt(index);
			setElementAt((QueryTreeNode) fromTable.accept(v), index);
		}

		return this;
	}
}