createplan.c

关系型数据库 Postgresql 6.5.2

/*-------------------------------------------------------------------------
 *
 * createplan.c
 *	  Routines to create the desired plan for processing a query
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /usr/local/cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.57.2.1 1999/07/29 03:34:11 tgl Exp $
 *
 *-------------------------------------------------------------------------
 */
#include <string.h>
#include <sys/types.h>

#include "postgres.h"

#include <utils/syscache.h>
#include <catalog/pg_index.h>

#include "nodes/execnodes.h"
#include "nodes/plannodes.h"
#include "nodes/relation.h"
#include "nodes/primnodes.h"
#include "nodes/nodeFuncs.h"

#include "nodes/makefuncs.h"

#include "utils/lsyscache.h"
#include "utils/palloc.h"
#include "utils/builtins.h"

#include "optimizer/restrictinfo.h"
#include "optimizer/cost.h"
#include "optimizer/clauses.h"
#include "optimizer/planmain.h"
#include "optimizer/tlist.h"
#include "optimizer/planner.h"
#include "optimizer/xfunc.h"
#include "optimizer/internal.h"


#define NONAME_SORT		1
#define NONAME_MATERIAL 2

static List *switch_outer(List *clauses);
static Oid *generate_merge_input_sortorder(List *pathkeys,
							   MergeOrder *mergeorder);
static Scan *create_scan_node(Path *best_path, List *tlist);
static Join *create_join_node(JoinPath *best_path, List *tlist);
static SeqScan *create_seqscan_node(Path *best_path, List *tlist,
					List *scan_clauses);
static IndexScan *create_indexscan_node(IndexPath *best_path, List *tlist,
					  List *scan_clauses);
static NestLoop *create_nestloop_node(NestPath *best_path, List *tlist,
					 List *clauses, Plan *outer_node, List *outer_tlist,
					 Plan *inner_node, List *inner_tlist);
static MergeJoin *create_mergejoin_node(MergePath *best_path, List *tlist,
					  List *clauses, Plan *outer_node, List *outer_tlist,
					  Plan *inner_node, List *inner_tlist);
static HashJoin *create_hashjoin_node(HashPath *best_path, List *tlist,
					 List *clauses, Plan *outer_node, List *outer_tlist,
					 Plan *inner_node, List *inner_tlist);
static Node *fix_indxqual_references(Node *clause, Path *index_path);
static Noname *make_noname(List *tlist, List *pathkeys, Oid *operators,
			Plan *plan_node, int nonametype);
static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
			   List *indxid, List *indxqual, List *indxqualorig);
static NestLoop *make_nestloop(List *qptlist, List *qpqual, Plan *lefttree,
			  Plan *righttree);
static HashJoin *make_hashjoin(List *tlist, List *qpqual,
			  List *hashclauses, Plan *lefttree, Plan *righttree);
static Hash *make_hash(List *tlist, Var *hashkey, Plan *lefttree);
static MergeJoin *make_mergejoin(List *tlist, List *qpqual,
			   List *mergeclauses, Plan *righttree, Plan *lefttree);
static Material *make_material(List *tlist, Oid nonameid, Plan *lefttree,
			  int keycount);
static void copy_costsize(Plan *dest, Plan *src);

/*
 * create_plan
 *	  Creates the access plan for a query by tracing backwards through the
 *	  desired chain of pathnodes, starting at the node 'best_path'.  For
 *	  every pathnode found:
 *	  (1) Create a corresponding plan node containing appropriate id,
 *		  target list, and qualification information.
 *	  (2) Modify ALL clauses so that attributes are referenced using
 *		  relative values.
 *	  (3) Target lists are not modified, but will be in another routine.
 *
 *	  best_path is the best access path
 *
 *	  Returns the optimal(?) access plan.
 */
Plan *
create_plan(Path *best_path)
{
	List	   *tlist;
	Plan	   *plan_node = (Plan *) NULL;
	RelOptInfo *parent_rel;
	int			size;
	int			width;
	int			pages;
	int			tuples;

	parent_rel = best_path->parent;
	tlist = get_actual_tlist(parent_rel->targetlist);
	size = parent_rel->size;
	width = parent_rel->width;
	pages = parent_rel->pages;
	tuples = parent_rel->tuples;

	switch (best_path->pathtype)
	{
		case T_IndexScan:
		case T_SeqScan:
			plan_node = (Plan *) create_scan_node(best_path, tlist);
			break;
		case T_HashJoin:
		case T_MergeJoin:
		case T_NestLoop:
			plan_node = (Plan *) create_join_node((JoinPath *) best_path, tlist);
			break;
		default:
			/* do nothing */
			break;
	}

	plan_node->plan_size = size;
	plan_node->plan_width = width;
	if (pages == 0)
		pages = 1;
	plan_node->plan_tupperpage = tuples / pages;

#ifdef NOT_USED					/* fix xfunc */
	/* sort clauses by cost/(1-selectivity) -- JMH 2/26/92 */
	if (XfuncMode != XFUNC_OFF)
	{
		set_qpqual((Plan) plan_node,
				   lisp_qsort(get_qpqual((Plan) plan_node),
							  xfunc_clause_compare));
		if (XfuncMode != XFUNC_NOR)
			/* sort the disjuncts within each clause by cost -- JMH 3/4/92 */
			xfunc_disjunct_sort(plan_node->qpqual);
	}
#endif

	return plan_node;
}

/*
 * create_scan_node
 *	 Create a scan path for the parent relation of 'best_path'.
 *
 *	 tlist is the targetlist for the base relation scanned by 'best_path'
 *
 *	 Returns the scan node.
 */
static Scan *
create_scan_node(Path *best_path, List *tlist)
{

	Scan	   *node = NULL;
	List	   *scan_clauses;

	/*
	 * Extract the relevant clauses from the parent relation and replace
	 * the operator OIDs with the corresponding regproc ids.
	 *
	 * now that local predicate clauses are copied into paths in
	 * find_rel_paths() and then (possibly) pulled up in
	 * xfunc_trypullup(), we get the relevant clauses from the path
	 * itself, not its parent relation.   --- JMH, 6/15/92
	 */
	scan_clauses = fix_opids(get_actual_clauses(best_path->loc_restrictinfo));

	switch (best_path->pathtype)
	{
		case T_SeqScan:
			node = (Scan *) create_seqscan_node(best_path, tlist, scan_clauses);
			break;

		case T_IndexScan:
			node = (Scan *) create_indexscan_node((IndexPath *) best_path,
												  tlist,
												  scan_clauses);
			break;

		default:
			elog(ERROR, "create_scan_node: unknown node type",
				 best_path->pathtype);
			break;
	}

	return node;
}

/*
 * create_join_node
 *	  Create a join path for 'best_path' and(recursively) paths for its
 *	  inner and outer paths.
 *
 *	  'tlist' is the targetlist for the join relation corresponding to
 *		'best_path'
 *
 *	  Returns the join node.
 */
static Join *
create_join_node(JoinPath *best_path, List *tlist)
{
	Plan	   *outer_node;
	List	   *outer_tlist;
	Plan	   *inner_node;
	List	   *inner_tlist;
	List	   *clauses;
	Join	   *retval = NULL;

	outer_node = create_plan((Path *) best_path->outerjoinpath);
	outer_tlist = outer_node->targetlist;

	inner_node = create_plan((Path *) best_path->innerjoinpath);
	inner_tlist = inner_node->targetlist;

	clauses = get_actual_clauses(best_path->pathinfo);

	switch (best_path->path.pathtype)
	{
		case T_MergeJoin:
			retval = (Join *) create_mergejoin_node((MergePath *) best_path,
													tlist,
													clauses,
													outer_node,
													outer_tlist,
													inner_node,
													inner_tlist);
			break;
		case T_HashJoin:
			retval = (Join *) create_hashjoin_node((HashPath *) best_path,
												   tlist,
												   clauses,
												   outer_node,
												   outer_tlist,
												   inner_node,
												   inner_tlist);
			break;
		case T_NestLoop:
			retval = (Join *) create_nestloop_node((NestPath *) best_path,
												   tlist,
												   clauses,
												   outer_node,
												   outer_tlist,
												   inner_node,
												   inner_tlist);
			break;
		default:
			/* do nothing */
			elog(ERROR, "create_join_node: unknown node type",
				 best_path->path.pathtype);
	}

#if 0

	/*
	 * * Expensive function pullups may have pulled local predicates *
	 * into this path node.  Put them in the qpqual of the plan node. *
	 * JMH, 6/15/92
	 */
	if (get_loc_restrictinfo(best_path) != NIL)
		set_qpqual((Plan) retval,
				   nconc(get_qpqual((Plan) retval),
						 fix_opids(get_actual_clauses
								   (get_loc_restrictinfo(best_path)))));
#endif

	return retval;
}

/*****************************************************************************
 *
 *	BASE-RELATION SCAN METHODS
 *
 *****************************************************************************/


/*
 * create_seqscan_node
 *	 Returns a seqscan node for the base relation scanned by 'best_path'
 *	 with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static SeqScan *
create_seqscan_node(Path *best_path, List *tlist, List *scan_clauses)
{
	SeqScan    *scan_node = (SeqScan *) NULL;
	Index		scan_relid = -1;
	List	   *temp;

	temp = best_path->parent->relids;
	if (temp == NULL)
		elog(ERROR, "scanrelid is empty");
	else
		scan_relid = (Index) lfirsti(temp);		/* ??? who takes care of
												 * lnext? - ay */
	scan_node = make_seqscan(tlist,
							 scan_clauses,
							 scan_relid,
							 (Plan *) NULL);

	scan_node->plan.cost = best_path->path_cost;

	return scan_node;
}

/*
 * create_indexscan_node
 *	  Returns a indexscan node for the base relation scanned by 'best_path'
 *	  with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static IndexScan *
create_indexscan_node(IndexPath *best_path,
					  List *tlist,
					  List *scan_clauses)
{

	/*
	 * Extract the(first if conjunct, only if disjunct) clause from the
	 * restrictinfo list.
	 */
	Expr	   *index_clause = (Expr *) NULL;
	List	   *indxqual = NIL;
	List	   *qpqual = NIL;
	List	   *fixed_indxqual = NIL;
	List	   *ixid;
	IndexScan  *scan_node = (IndexScan *) NULL;
	bool		lossy = FALSE;
	HeapTuple	indexTuple;
	Form_pg_index index;

	/*
	 * If an 'or' clause is to be used with this index, the indxqual field
	 * will contain a list of the 'or' clause arguments, e.g., the
	 * clause(OR a b c) will generate: ((a) (b) (c)).  Otherwise, the
	 * indxqual will simply contain one conjunctive qualification: ((a)).
	 */
	if (best_path->indexqual != NULL)
		/* added call to fix_opids, JMH 6/23/92 */
		index_clause = (Expr *)
			lfirst(fix_opids(get_actual_clauses(best_path->indexqual)));

	if (or_clause((Node *) index_clause))
	{
		List	   *temp = NIL;

		foreach(temp, index_clause->args)
			indxqual = lappend(indxqual, lcons(lfirst(temp), NIL));
	}
	else
	{
		indxqual = lcons(get_actual_clauses(best_path->indexqual),
						 NIL);
	}

	/* check and see if any indices are lossy */
	foreach(ixid, best_path->indexid)
	{
		indexTuple = SearchSysCacheTuple(INDEXRELID,
										 ObjectIdGetDatum(lfirsti(ixid)),
										 0, 0, 0);
		if (!HeapTupleIsValid(indexTuple))
			elog(ERROR, "create_plan: index %u not found", lfirsti(ixid));
		index = (Form_pg_index) GETSTRUCT(indexTuple);
		if (index->indislossy)
			lossy = TRUE;
	}


	/*
	 * The qpqual field contains all restrictions not automatically
	 * handled by the index.  Note that for non-lossy indices, the
	 * predicates in the indxqual are handled by the index, while for
	 * lossy indices the indxqual predicates need to be double-checked
	 * after the index fetches the best-guess tuples.
	 */
	if (or_clause((Node *) index_clause))
	{
		qpqual = set_difference(scan_clauses,
								lcons(index_clause, NIL));

		if (lossy)
			qpqual = lappend(qpqual, (List *) copyObject(index_clause));
	}
	else
	{
		qpqual = set_difference(scan_clauses, lfirst(indxqual));
		if (lossy)
			qpqual = nconc(qpqual,
						   (List *) copyObject(lfirst(indxqual)));
	}

	fixed_indxqual = (List *) fix_indxqual_references((Node *) indxqual, (Path *) best_path);

	scan_node = make_indexscan(tlist,
							   qpqual,
							   lfirsti(best_path->path.parent->relids),
							   best_path->indexid,
							   fixed_indxqual,
							   indxqual);

	scan_node->scan.plan.cost = best_path->path.path_cost;

	return scan_node;
}

/*****************************************************************************
 *
 *	JOIN METHODS
 *
 *****************************************************************************/

static NestLoop *
create_nestloop_node(NestPath *best_path,
					 List *tlist,
					 List *clauses,
					 Plan *outer_node,
					 List *outer_tlist,
					 Plan *inner_node,
					 List *inner_tlist)
{
	NestLoop   *join_node = (NestLoop *) NULL;

	if (IsA(inner_node, IndexScan))
	{

		/*
		 * An index is being used to reduce the number of tuples scanned