selectnode.java

derby database source code.good for you.

	 * Determine whether or not the specified name is an exposed name in
	 * the current query block.
	 *
	 * @param name	The specified name to search for as an exposed name.
	 * @param schemaName	Schema name, if non-null.
	 * @param exactMatch	Whether or not we need an exact match on specified schema and table
	 *						names or match on table id.
	 *
	 * @return The FromTable, if any, with the exposed name.
	 *
	 * @exception StandardException		Thrown on error
	 */
	protected FromTable getFromTableByName(String name, String schemaName, boolean exactMatch)
		throws StandardException
	{
		return fromList.getFromTableByName(name, schemaName, exactMatch);
	}

	/**
	 * Check for (and reject) ? parameters directly under the ResultColumns.
	 * This is done for SELECT statements.
	 *
	 * @return	Nothing
	 *
	 * @exception StandardException		Thrown if a ? parameter found
	 *									directly under a ResultColumn
	 */

	public void rejectParameters() throws StandardException
	{
		super.rejectParameters();
		fromList.rejectParameters();
	}

	/**
	 * Push the order by list down from the cursor node
	 * into its child result set so that the optimizer
	 * has all of the information that it needs to 
	 * consider sort avoidance.
	 *
	 * @param orderByList	The order by list
	 *
	 * @return Nothing.
	 */
	void pushOrderByList(OrderByList orderByList)
	{
		this.orderByList = orderByList;
		// remember that there was an order by list
		orderByQuery = true;
	}

	/** 
	 * Put a ProjectRestrictNode on top of each FromTable in the FromList.
	 * ColumnReferences must continue to point to the same ResultColumn, so
	 * that ResultColumn must percolate up to the new PRN.  However,
	 * that ResultColumn will point to a new expression, a VirtualColumnNode, 
	 * which points to the FromTable and the ResultColumn that is the source for
	 * the ColumnReference.  
	 * (The new PRN will have the original of the ResultColumnList and
	 * the ResultColumns from that list.  The FromTable will get shallow copies
	 * of the ResultColumnList and its ResultColumns.  ResultColumn.expression
	 * will remain at the FromTable, with the PRN getting a new 
	 * VirtualColumnNode for each ResultColumn.expression.)
	 * We then project out the non-referenced columns.  If there are no referenced
	 * columns, then the PRN's ResultColumnList will consist of a single ResultColumn
	 * whose expression is 1.
	 *
	 * @param numTables			The number of tables in the DML Statement
	 * @param gbl				The outer group by list, if any
	 * @param fl			The from list, if any
	 *
	 * @return The generated ProjectRestrictNode atop the original FromTable.
	 *
	 * @exception StandardException		Thrown on error
	 */

	public ResultSetNode preprocess(int numTables,
									GroupByList gbl,
									FromList fl)
								throws StandardException
	{
		ResultSetNode newTop = this;

		/* Put the expression trees in conjunctive normal form.
		 * NOTE - This needs to occur before we preprocess the subqueries
		 * because the subquery transformations assume that any subquery operator 
		 * negation has already occurred.
		 */
		normExpressions();

		/**
		 * This method determines if (1) the query is a LOJ, and (2) if the LOJ is a candidate for
		 * reordering (i.e., linearization).  The condition for LOJ linearization is:
		 * 1. either LOJ or ROJ in the fromList, i.e., no INNER, NO FULL JOINs
		 * 2. ON clause must be equality join between left and right operands and in CNF (i.e., AND is allowed)
		 */
		boolean anyChange = fromList.LOJ_reorderable(numTables);
		if (anyChange)
		{
			FromList afromList = (FromList) getNodeFactory().getNode(C_NodeTypes.FROM_LIST,
																	 getNodeFactory().doJoinOrderOptimization(),
																	 getContextManager());
			bindExpressions(afromList);
		}

		/* Preprocess the fromList.  For each FromTable, if it is a FromSubquery
		 * then we will preprocess it, replacing the FromSubquery with a
		 * ProjectRestrictNode. If it is a FromBaseTable, then we will generate
		 * the ProjectRestrictNode above it.
		 */
		fromList.preprocess(numTables, groupByList, whereClause);

		/* selectSubquerys is always allocated at bind() time */
		if (SanityManager.DEBUG)
		{
			SanityManager.ASSERT(selectSubquerys != null,
				"selectSubquerys is expected to be non-null");
		}

		/* Preprocess the RCL after the from list so that
		 * we can flatten/optimize any subqueries in the
		 * select list.
		 */
		resultColumns.preprocess(numTables, 
								 fromList, whereSubquerys,
								 wherePredicates);

		/* Preprocess the expressions.  (This is necessary for subqueries.
		 * This is also where we do tranformations such as for LIKE.)
		 *
		 * NOTE: We do this after preprocessing the fromList so that, for
		 * quantified subqueries, the join expression with the outer
		 * expression will be pushable (to be pushable, the ColumnReference
		 * has to point to a VirtualColumnNode, and not to a BaseColumnNode).
		 */
		if (whereClause != null)
		{
			whereClause.preprocess(numTables,
								   fromList, whereSubquerys,
								   wherePredicates);
		}

		/* Pull apart the expression trees */
		if (whereClause != null)
		{
			wherePredicates.pullExpressions(numTables, whereClause);
			whereClause = null;
		}

		/* RESOLVE - Where should we worry about expression pull up for
		 * expensive predicates?
		 */

		// Flatten any flattenable FromSubquerys or JoinNodes
		fromList.flattenFromTables(resultColumns, 
								   wherePredicates, 
								   whereSubquerys,
								   groupByList);

		if (wherePredicates != null && wherePredicates.size() > 0 && fromList.size() > 0)
		{
			// Perform various forms of transitive closure on wherePredicates
			if (fromList.size() > 1)
			{
				performTransitiveClosure(numTables);
			}

			if (orderByList != null)
			{
				// Remove constant columns from order by list.  Constant
				// columns are ones that have equality comparisons with
				// constant expressions (e.g. x = 3)
				orderByList.removeConstantColumns(wherePredicates);

				/*
				** It's possible for the order by list to shrink to nothing
				** as a result of removing constant columns.  If this happens,
				** get rid of the list entirely.
				*/
				if (orderByList.size() == 0)
				{
					orderByList = null;
				}
			}
		}

		/* A valid group by without any aggregates is equivalent to 
		 * a distinct without the group by.  We do the transformation
		 * in order to simplify the group by code.
		 */
		if (groupByList != null &&
			selectAggregates.size() == 0 &&
			whereAggregates.size() == 0)
		{
			isDistinct = true;
			groupByList = null;
		}

		/* Consider distinct elimination based on a uniqueness condition.
		 * In order to do this:
		 *	o  All top level ColumnReferences in the select list are
		 *	   from the same base table.  (select t1.c1, t2.c2 + t3.c3 is 
		 *	   okay - t1 is the table of interest.)
		 *  o  If the from list is a single table then the columns in the
		 *	   select list plus the columns in the where clause that are
		 *	   in = comparisons with constants or parameters must be a
		 *	   superset of any unique index.
		 *  o  If the from list has multiple tables then at least 1 table
		 *	   meet the following - the set of columns in = comparisons
		 *	   with constants or parameters is a superset of any unique
		 *	   index on the table.  All of the other tables must meet
		 *	   the following - the set of columns in = comparisons with
		 *	   constants, parameters or join columns is a superset of
		 *	   any unique index on the table.  If the table from which
		 *	   the columns in the select list are coming from is in this
		 *     later group then the rule for it is to also include
		 *     the columns in the select list in the set of columns that
		 *     needs to be a superset of the unique index.  Whew!
		 */
		if (isDistinct && groupByList == null)
		{
			int distinctTable =	resultColumns.allTopCRsFromSameTable();
			
			if (distinctTable != -1)
			{
				if (fromList.returnsAtMostSingleRow(resultColumns, 
											   whereClause, wherePredicates,
											   getDataDictionary()))
				{
					isDistinct = false;
				}
			}

			/* If we were unable to eliminate the distinct and we have
			 * an order by then we can consider eliminating the sort for the
			 * order by.  All of the columns in the order by list must
			 * be ascending in order to do this.  There are 2 cases:
			 *	o	The order by list is an in order prefix of the columns
			 *		in the select list.  In this case the output of the
			 *		sort from the distinct will be in the right order
			 *		so we simply eliminate the order by list.
			 *	o	The order by list is a subset of the columns in the
			 *		the select list.  In this case we need to reorder the
			 *		columns in the select list so that the ordering columns
			 *		are an in order prefix of the select list and put a PRN
			 *		above the select so that the shape of the result set
			 *		is as expected.
			 */
			if (isDistinct && orderByList != null && orderByList.allAscending())
			{
				/* Order by list currently restricted to columns in select
				 * list, so we will always eliminate the order by here.
				 */
				if (orderByList.isInOrderPrefix(resultColumns))
				{
					orderByList = null;
				}
				else 
				{
					/* Order by list is not an in order prefix of the select list
					 * so we must reorder the columns in the the select list to
					 * match the order by list and generate the PRN above us to
					 * preserve the expected order.
					 */
					newTop = genProjectRestrictForReordering();
					orderByList.resetToSourceRCs();
					resultColumns = orderByList.reorderRCL(resultColumns);
					orderByList = null;
				}
				orderByAndDistinctMerged = true;
			}
		}

		/*
		 * Push predicates that are pushable.
		 *
		 * NOTE: We pass the wherePredicates down to the new PRNs here,
		 * so they can pull any clauses and possibily push them down further.
		 * NOTE: We wait until all of the FromTables have been preprocessed
		 * until we attempt to push down predicates, because we cannot push down
		 * a predicate if the immediate source of any of its column references
		 * is not a ColumnReference or a VirtualColumnNode.
		 */
		fromList.pushPredicates(wherePredicates);

		/* Set up the referenced table map */
		referencedTableMap = new JBitSet(numTables);
		int flSize = fromList.size();
		for (int index = 0; index < flSize; index++)
		{
			referencedTableMap.or(((FromTable) fromList.elementAt(index)).
													getReferencedTableMap());
		}

		/* Copy the referenced table map to the new tree top, if necessary */
		if (newTop != this)
		{
			newTop.setReferencedTableMap((JBitSet) referencedTableMap.clone());
		}
		return newTop;
	}

	/**
	 * Peform the various types of transitive closure on the where clause.
	 * The 2 types are transitive closure on join clauses and on search clauses.
	 * Join clauses will be processed first to maximize benefit for search clauses.
	 *
	 * @param numTables		The number of tables in the query
	 *
	 * @return None.
	 *
	 * @exception StandardException		Thrown on error
	 */
	private void performTransitiveClosure(int numTables)
		throws StandardException
	{
		// Join clauses
		wherePredicates.joinClauseTransitiveClosure(numTables, fromList, getCompilerContext());

		// Search clauses
		wherePredicates.searchClauseTransitiveClosure(numTables, fromList.hashJoinSpecified());
	}

	/** Put the expression trees in conjunctive normal form 
	 *
	 * @return None.
	 *
	 * @exception StandardException		Thrown on error
	 */
	private void normExpressions()
				throws StandardException
	{
		/* For each expression tree:
		 *	o Eliminate NOTs (eliminateNots())
		 *	o Ensure that there is an AndNode on top of every
		 *	  top level expression. (putAndsOnTop())
		 *	o Finish the job (changeToCNF())
		 */
		if (whereClause != null)
		{
			whereClause = whereClause.eliminateNots(false);
			if (SanityManager.DEBUG)
			{
				if (!(whereClause.verifyEliminateNots()) )
				{
					whereClause.treePrint();
					SanityManager.THROWASSERT(
						"whereClause in invalid form: " + whereClause); 
				}
			}
			whereClause = whereClause.putAndsOnTop();
			if (SanityManager.DEBUG)
			{
				if (! ((whereClause instanceof AndNode) &&
					   (whereClause.verifyPutAndsOnTop())) )
				{
					whereClause.treePrint();
					SanityManager.THROWASSERT(
						"whereClause in invalid form: " + whereClause); 
				}
			}
			whereClause = whereClause.changeToCNF(true);
			if (SanityManager.DEBUG)
			{
				if (! ((whereClause instanceof AndNode) &&
					   (whereClause.verifyChangeToCNF())) )
				{
					whereClause.treePrint();
					SanityManager.THROWASSERT(
						"whereClause in invalid form: " + whereClause); 
				}
			}
		}
	}

	/**
	 * Add a new predicate to the list.  This is useful when doing subquery
	 * transformations, when we build a new predicate with the left side of
	 * the subquery operator and the subquery's result column.
	 *
	 * @param predicate		The predicate to add
	 *
	 * @return ResultSetNode	The new top of the tree.
	 *
	 * @exception StandardException		Thrown on error
	 */
	public ResultSetNode addNewPredicate(Predicate predicate)
			throws StandardException
	{
		wherePredicates.addPredicate(predicate);
		return this;
	}

	/**
	 * Evaluate whether or not the subquery in a FromSubquery is flattenable.  
	 * Currently, a FSqry is flattenable if all of the following are true:
	 *		o  Subquery is a SelectNode. (ie, not a RowResultSetNode or a UnionNode)
	 *		o  It contains a single table in its FROM list.
	 *		o  It contains no subqueries in the SELECT list.
	 *		o  It does not contain a group by or having clause
	 *		o  It does not contain aggregates.
	 *		o  It is not a DISTINCT.
	 *
	 * @param fromList	The outer from list
	 *
	 * @return boolean	Whether or not the FromSubquery is flattenable.
	 */
	public boolean flattenableInFromSubquery(FromList fromList)
	{
		if (isDistinct) 
		{
			return false;
		}
		if (this.fromList.size() > 1)
		{
			return false;
		}

		/* Don't flatten (at least for now) if selectNode's SELECT list contains a subquery */
		if ((selectSubquerys != null) && 
			 (selectSubquerys.size() > 0))
		{