joinpath.c

关系型数据库 Postgresql 6.5.2

/*-------------------------------------------------------------------------
 *
 * joinpath.c
 *	  Routines to find all possible paths for processing a set of joins
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /usr/local/cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.38.2.1 1999/08/02 06:26:57 scrappy Exp $
 *
 *-------------------------------------------------------------------------
 */
#include <sys/types.h>
#include <math.h>

#include "postgres.h"

#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"

static Path *best_innerjoin(List *join_paths, List *outer_relid);
static List *sort_inner_and_outer(RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel,
					 List *mergeinfo_list);
static List *match_unsorted_outer(RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel,
		List *outerpath_list, Path *cheapest_inner, Path *best_innerjoin,
					 List *mergeinfo_list);
static List *match_unsorted_inner(RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel,
					 List *innerpath_list, List *mergeinfo_list);
static List *hash_inner_and_outer(RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel,
					 List *hashinfo_list);

/*
 * update_rels_pathlist_for_joins
 *	  Creates all possible ways to process joins for each of the join
 *	  relations in the list 'joinrels.'  Each unique path will be included
 *	  in the join relation's 'pathlist' field.
 *
 *	  In postgres, n-way joins are handled left-only(permuting clauseless
 *	  joins doesn't usually win much).
 *
 *	  if BushyPlanFlag is true, bushy tree plans will be generated
 *
 * 'joinrels' is the list of relation entries to be joined
 *
 * Modifies the pathlist field of the appropriate rel node to contain
 * the unique join paths.
 * If bushy trees are considered, may modify the relid field of the
 * join rel nodes to flatten the lists.
 *
 * It does a destructive modification.
 */
void
update_rels_pathlist_for_joins(Query *root, List *joinrels)
{
	List	   *mergeinfo_list = NIL;
	List	   *hashinfo_list = NIL;
	List	   *j;

	foreach(j, joinrels)
	{
		RelOptInfo *joinrel = (RelOptInfo *) lfirst(j);
		Relids		innerrelids;
		Relids		outerrelids;
		RelOptInfo *innerrel;
		RelOptInfo *outerrel;
		Path	   *bestinnerjoin;
		List	   *pathlist = NIL;

		/* flatten out relids later in this function */
		outerrelids = lfirst(joinrel->relids);
		innerrelids = lsecond(joinrel->relids);

		/*
		 * base relation id is an integer and join relation relid is a
		 * list of integers.
		 */
		innerrel = (length(innerrelids) == 1) ?
			get_base_rel(root, lfirsti(innerrelids)) :
			get_join_rel(root, innerrelids);
		outerrel = (length(outerrelids) == 1) ?
			get_base_rel(root, lfirsti(outerrelids)) :
			get_join_rel(root, outerrelids);

		bestinnerjoin = best_innerjoin(innerrel->innerjoin, outerrel->relids);

		if (_enable_mergejoin_)
			mergeinfo_list = group_clauses_by_order(joinrel->restrictinfo,
													innerrel->relids);

		if (_enable_hashjoin_)
			hashinfo_list = group_clauses_by_hashop(joinrel->restrictinfo,
													innerrel->relids);

		/* need to flatten the relids list */
		joinrel->relids = nconc(listCopy(outerrelids),
								listCopy(innerrelids));

		/*
		 * 1. Consider mergejoin paths where both relations must be
		 * explicitly sorted.
		 */
		pathlist = sort_inner_and_outer(joinrel, outerrel,
										innerrel, mergeinfo_list);

		/*
		 * 2. Consider paths where the outer relation need not be
		 * explicitly sorted. This may include either nestloops and
		 * mergejoins where the outer path is already ordered.
		 */
		pathlist = add_pathlist(joinrel, pathlist,
								match_unsorted_outer(joinrel,
													 outerrel,
													 innerrel,
													 outerrel->pathlist,
												  innerrel->cheapestpath,
													 bestinnerjoin,
													 mergeinfo_list));

		/*
		 * 3. Consider paths where the inner relation need not be
		 * explicitly sorted.  This may include nestloops and mergejoins
		 * the actual nestloop nodes were constructed in
		 * (match_unsorted_outer).
		 */
		pathlist = add_pathlist(joinrel, pathlist,
								match_unsorted_inner(joinrel, outerrel,
													 innerrel,
													 innerrel->pathlist,
													 mergeinfo_list));

		/*
		 * 4. Consider paths where both outer and inner relations must be
		 * hashed before being joined.
		 */
		pathlist = add_pathlist(joinrel, pathlist,
								hash_inner_and_outer(joinrel, outerrel,
											   innerrel, hashinfo_list));

		joinrel->pathlist = pathlist;
	}
}

/*
 * best_innerjoin
 *	  Find the cheapest index path that has already been identified by
 *	  (indexable_joinclauses) as being a possible inner path for the given
 *	  outer relation in a nestloop join.
 *
 * 'join_paths' is a list of join nodes
 * 'outer_relid' is the relid of the outer join relation
 *
 * Returns the pathnode of the selected path.
 */
static Path *
best_innerjoin(List *join_paths, Relids outer_relids)
{
	Path	   *cheapest = (Path *) NULL;
	List	   *join_path;

	foreach(join_path, join_paths)
	{
		Path	   *path = (Path *) lfirst(join_path);

		if (intMember(lfirsti(path->joinid), outer_relids) &&
			(cheapest == NULL ||
			 path_is_cheaper(path, cheapest)))
			cheapest = path;
	}
	return cheapest;
}

/*
 * sort_inner_and_outer
 *	  Create mergejoin join paths by explicitly sorting both the outer and
 *	  inner join relations on each available merge ordering.
 *
 * 'joinrel' is the join relation
 * 'outerrel' is the outer join relation
 * 'innerrel' is the inner join relation
 * 'mergeinfo_list' is a list of nodes containing info on(mergejoinable)
 *				clauses for joining the relations
 *
 * Returns a list of mergejoin paths.
 */
static List *
sort_inner_and_outer(RelOptInfo *joinrel,
					 RelOptInfo *outerrel,
					 RelOptInfo *innerrel,
					 List *mergeinfo_list)
{
	List	   *ms_list = NIL;
	MergeInfo  *xmergeinfo = (MergeInfo *) NULL;
	MergePath  *temp_node = (MergePath *) NULL;
	List	   *i;
	List	   *outerkeys = NIL;
	List	   *innerkeys = NIL;
	List	   *merge_pathkeys = NIL;

	foreach(i, mergeinfo_list)
	{
		xmergeinfo = (MergeInfo *) lfirst(i);

		outerkeys = make_pathkeys_from_joinkeys(xmergeinfo->jmethod.jmkeys,
												outerrel->targetlist,
												OUTER);

		innerkeys = make_pathkeys_from_joinkeys(xmergeinfo->jmethod.jmkeys,
												innerrel->targetlist,
												INNER);

		merge_pathkeys = new_join_pathkeys(outerkeys, joinrel->targetlist,
										   xmergeinfo->jmethod.clauses);

		temp_node = create_mergejoin_path(joinrel,
										  outerrel->size,
										  innerrel->size,
										  outerrel->width,
										  innerrel->width,
										  (Path *) outerrel->cheapestpath,
										  (Path *) innerrel->cheapestpath,
										  merge_pathkeys,
										  xmergeinfo->m_ordering,
										  xmergeinfo->jmethod.clauses,
										  outerkeys,
										  innerkeys);

		ms_list = lappend(ms_list, temp_node);
	}
	return ms_list;
}

/*
 * match_unsorted_outer
 *	  Creates possible join paths for processing a single join relation
 *	  'joinrel' by employing either iterative substitution or
 *	  mergejoining on each of its possible outer paths(assuming that the
 *	  outer relation need not be explicitly sorted).
 *
 *	  1. The inner path is the cheapest available inner path.
 *	  2. Mergejoin wherever possible.  Mergejoin are considered if there
 *		 are mergejoinable join clauses between the outer and inner join
 *		 relations such that the outer path is keyed on the variables
 *		 appearing in the clauses.	The corresponding inner merge path is
 *		 either a path whose keys match those of the outer path(if such a
 *		 path is available) or an explicit sort on the appropriate inner
 *		 join keys, whichever is cheaper.
 *
 * 'joinrel' is the join relation
 * 'outerrel' is the outer join relation
 * 'innerrel' is the inner join relation
 * 'outerpath_list' is the list of possible outer paths
 * 'cheapest_inner' is the cheapest inner path
 * 'best_innerjoin' is the best inner index path(if any)
 * 'mergeinfo_list' is a list of nodes containing info on mergejoinable
 *		clauses
 *
 * Returns a list of possible join path nodes.
 */
static List *
match_unsorted_outer(RelOptInfo *joinrel,
					 RelOptInfo *outerrel,
					 RelOptInfo *innerrel,
					 List *outerpath_list,
					 Path *cheapest_inner,
					 Path *best_innerjoin,
					 List *mergeinfo_list)
{
	Path	   *outerpath = (Path *) NULL;
	List	   *jp_list = NIL;
	List	   *temp_node = NIL;
	List	   *merge_pathkeys = NIL;
	Path	   *nestinnerpath = (Path *) NULL;
	List	   *paths = NIL;
	List	   *i = NIL;