joinrels.c

postgresql8.3.4源码,开源数据库

		 * If we already joined IN's RHS to any other rels in either input
		 * path, then this join is not constrained (the necessary work was
		 * done at the lower level where that join occurred).
		 */
		if (bms_is_subset(ininfo->righthand, rel1->relids) &&
			!bms_equal(ininfo->righthand, rel1->relids))
			continue;
		if (bms_is_subset(ininfo->righthand, rel2->relids) &&
			!bms_equal(ininfo->righthand, rel2->relids))
			continue;

		/*
		 * JOIN_IN technique will work if outerrel includes LHS and innerrel
		 * is exactly RHS; conversely JOIN_REVERSE_IN handles RHS/LHS.
		 *
		 * JOIN_UNIQUE_OUTER will work if outerrel is exactly RHS; conversely
		 * JOIN_UNIQUE_INNER will work if innerrel is exactly RHS.
		 *
		 * But none of these will work if we already found an OJ or another IN
		 * that needs to trigger here.
		 */
		if (jointype != JOIN_INNER)
			return false;
		if (bms_is_subset(ininfo->lefthand, rel1->relids) &&
			bms_equal(ininfo->righthand, rel2->relids))
			jointype = JOIN_IN;
		else if (bms_is_subset(ininfo->lefthand, rel2->relids) &&
				 bms_equal(ininfo->righthand, rel1->relids))
			jointype = JOIN_REVERSE_IN;
		else if (bms_equal(ininfo->righthand, rel1->relids))
			jointype = JOIN_UNIQUE_OUTER;
		else if (bms_equal(ininfo->righthand, rel2->relids))
			jointype = JOIN_UNIQUE_INNER;
		else
			return false;		/* invalid join path */
	}

	/* Join is valid */
	*jointype_p = jointype;
	return true;
}


/*
 * make_join_rel
 *	   Find or create a join RelOptInfo that represents the join of
 *	   the two given rels, and add to it path information for paths
 *	   created with the two rels as outer and inner rel.
 *	   (The join rel may already contain paths generated from other
 *	   pairs of rels that add up to the same set of base rels.)
 *
 * NB: will return NULL if attempted join is not valid.  This can happen
 * when working with outer joins, or with IN clauses that have been turned
 * into joins.
 */
RelOptInfo *
make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
{
	Relids		joinrelids;
	JoinType	jointype;
	RelOptInfo *joinrel;
	List	   *restrictlist;

	/* We should never try to join two overlapping sets of rels. */
	Assert(!bms_overlap(rel1->relids, rel2->relids));

	/* Construct Relids set that identifies the joinrel. */
	joinrelids = bms_union(rel1->relids, rel2->relids);

	/* Check validity and determine join type. */
	if (!join_is_legal(root, rel1, rel2, joinrelids, &jointype))
	{
		/* invalid join path */
		bms_free(joinrelids);
		return NULL;
	}

	/*
	 * Find or build the join RelOptInfo, and compute the restrictlist that
	 * goes with this particular joining.
	 */
	joinrel = build_join_rel(root, joinrelids, rel1, rel2, jointype,
							 &restrictlist);

	/*
	 * If we've already proven this join is empty, we needn't consider
	 * any more paths for it.
	 */
	if (is_dummy_rel(joinrel))
	{
		bms_free(joinrelids);
		return joinrel;
	}

	/*
	 * Consider paths using each rel as both outer and inner.  Depending
	 * on the join type, a provably empty outer or inner rel might mean
	 * the join is provably empty too; in which case throw away any
	 * previously computed paths and mark the join as dummy.  (We do it
	 * this way since it's conceivable that dummy-ness of a multi-element
	 * join might only be noticeable for certain construction paths.)
	 */
	switch (jointype)
	{
		case JOIN_INNER:
			if (is_dummy_rel(rel1) || is_dummy_rel(rel2))
			{
				mark_dummy_join(joinrel);
				break;
			}
			add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_INNER,
								 restrictlist);
			add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_INNER,
								 restrictlist);
			break;
		case JOIN_LEFT:
			if (is_dummy_rel(rel1))
			{
				mark_dummy_join(joinrel);
				break;
			}
			add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_LEFT,
								 restrictlist);
			add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_RIGHT,
								 restrictlist);
			break;
		case JOIN_FULL:
			if (is_dummy_rel(rel1) && is_dummy_rel(rel2))
			{
				mark_dummy_join(joinrel);
				break;
			}
			add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_FULL,
								 restrictlist);
			add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_FULL,
								 restrictlist);
			break;
		case JOIN_RIGHT:
			if (is_dummy_rel(rel2))
			{
				mark_dummy_join(joinrel);
				break;
			}
			add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_RIGHT,
								 restrictlist);
			add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_LEFT,
								 restrictlist);
			break;
		case JOIN_IN:
			if (is_dummy_rel(rel1) || is_dummy_rel(rel2))
			{
				mark_dummy_join(joinrel);
				break;
			}
			add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_IN,
								 restrictlist);
			/* REVERSE_IN isn't supported by joinpath.c */
			add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_UNIQUE_INNER,
								 restrictlist);
			add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_UNIQUE_OUTER,
								 restrictlist);
			break;
		case JOIN_REVERSE_IN:
			if (is_dummy_rel(rel1) || is_dummy_rel(rel2))
			{
				mark_dummy_join(joinrel);
				break;
			}
			/* REVERSE_IN isn't supported by joinpath.c */
			add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_IN,
								 restrictlist);
			add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_UNIQUE_OUTER,
								 restrictlist);
			add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_UNIQUE_INNER,
								 restrictlist);
			break;
		case JOIN_UNIQUE_OUTER:
			if (is_dummy_rel(rel1) || is_dummy_rel(rel2))
			{
				mark_dummy_join(joinrel);
				break;
			}
			add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_UNIQUE_OUTER,
								 restrictlist);
			add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_UNIQUE_INNER,
								 restrictlist);
			break;
		case JOIN_UNIQUE_INNER:
			if (is_dummy_rel(rel1) || is_dummy_rel(rel2))
			{
				mark_dummy_join(joinrel);
				break;
			}
			add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_UNIQUE_INNER,
								 restrictlist);
			add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_UNIQUE_OUTER,
								 restrictlist);
			break;
		default:
			elog(ERROR, "unrecognized join type: %d",
				 (int) jointype);
			break;
	}

	bms_free(joinrelids);

	return joinrel;
}


/*
 * have_join_order_restriction
 *		Detect whether the two relations should be joined to satisfy
 *		a join-order restriction arising from outer joins or IN clauses.
 *
 * In practice this is always used with have_relevant_joinclause(), and so
 * could be merged with that function, but it seems clearer to separate the
 * two concerns.  We need these tests because there are degenerate cases where
 * a clauseless join must be performed to satisfy join-order restrictions.
 *
 * Note: this is only a problem if one side of a degenerate outer join
 * contains multiple rels, or a clauseless join is required within an IN's
 * RHS; else we will find a join path via the "last ditch" case in
 * join_search_one_level().  We could dispense with this test if we were
 * willing to try bushy plans in the "last ditch" case, but that seems much
 * less efficient.
 */
bool
have_join_order_restriction(PlannerInfo *root,
							RelOptInfo *rel1, RelOptInfo *rel2)
{
	bool		result = false;
	ListCell   *l;

	/*
	 * It's possible that the rels correspond to the left and right sides of a
	 * degenerate outer join, that is, one with no joinclause mentioning the
	 * non-nullable side; in which case we should force the join to occur.
	 *
	 * Also, the two rels could represent a clauseless join that has to be
	 * completed to build up the LHS or RHS of an outer join.
	 */
	foreach(l, root->oj_info_list)
	{
		OuterJoinInfo *ojinfo = (OuterJoinInfo *) lfirst(l);

		/* ignore full joins --- other mechanisms handle them */
		if (ojinfo->is_full_join)
			continue;

		/* Can we perform the OJ with these rels? */
		if (bms_is_subset(ojinfo->min_lefthand, rel1->relids) &&
			bms_is_subset(ojinfo->min_righthand, rel2->relids))
		{
			result = true;
			break;
		}
		if (bms_is_subset(ojinfo->min_lefthand, rel2->relids) &&
			bms_is_subset(ojinfo->min_righthand, rel1->relids))
		{
			result = true;
			break;
		}

		/*
		 * Might we need to join these rels to complete the RHS?  We have to
		 * use "overlap" tests since either rel might include a lower OJ that
		 * has been proven to commute with this one.
		 */
		if (bms_overlap(ojinfo->min_righthand, rel1->relids) &&
			bms_overlap(ojinfo->min_righthand, rel2->relids))
		{
			result = true;
			break;
		}

		/* Likewise for the LHS. */
		if (bms_overlap(ojinfo->min_lefthand, rel1->relids) &&
			bms_overlap(ojinfo->min_lefthand, rel2->relids))
		{
			result = true;
			break;
		}
	}

	/*
	 * Similarly, we need to allow a join that completes a degenerate
	 * IN-clause, or one that builds up its LHS or RHS.
	 */
	foreach(l, root->in_info_list)
	{
		InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);

		/* Can we perform the IN with these rels? */
		if (bms_is_subset(ininfo->lefthand, rel1->relids) &&
			bms_is_subset(ininfo->righthand, rel2->relids))
		{
			result = true;
			break;
		}
		if (bms_is_subset(ininfo->lefthand, rel2->relids) &&
			bms_is_subset(ininfo->righthand, rel1->relids))
		{
			result = true;
			break;
		}

		/*
		 * Might we need to join these rels to complete the RHS?  It's
		 * probably overkill to test "overlap", since we never join part of an
		 * IN's RHS to anything else, but may as well keep the coding similar
		 * to the OJ case.
		 */
		if (bms_overlap(ininfo->righthand, rel1->relids) &&
			bms_overlap(ininfo->righthand, rel2->relids))
		{
			result = true;
			break;
		}

		/* Likewise for the LHS. */
		if (bms_overlap(ininfo->lefthand, rel1->relids) &&
			bms_overlap(ininfo->lefthand, rel2->relids))
		{
			result = true;
			break;
		}
	}

	/*
	 * We do not force the join to occur if either input rel can legally be
	 * joined to anything else using joinclauses.  This essentially means that
	 * clauseless bushy joins are put off as long as possible. The reason is
	 * that when there is a join order restriction high up in the join tree
	 * (that is, with many rels inside the LHS or RHS), we would otherwise
	 * expend lots of effort considering very stupid join combinations within
	 * its LHS or RHS.
	 */
	if (result)
	{
		if (has_legal_joinclause(root, rel1) ||
			has_legal_joinclause(root, rel2))
			result = false;
	}

	return result;
}


/*
 * has_join_restriction
 *		Detect whether the specified relation has join-order restrictions
 *		due to being inside an outer join or an IN (sub-SELECT).
 *
 * Essentially, this tests whether have_join_order_restriction() could
 * succeed with this rel and some other one.  It's OK if we sometimes
 * say "true" incorrectly.	(Therefore, we don't bother with the relatively
 * expensive has_legal_joinclause test.)
 */
static bool
has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
{
	ListCell   *l;

	foreach(l, root->oj_info_list)
	{
		OuterJoinInfo *ojinfo = (OuterJoinInfo *) lfirst(l);

		/* ignore full joins --- other mechanisms preserve their ordering */
		if (ojinfo->is_full_join)
			continue;

		/* ignore if OJ is already contained in rel */
		if (bms_is_subset(ojinfo->min_lefthand, rel->relids) &&
			bms_is_subset(ojinfo->min_righthand, rel->relids))
			continue;

		/* restricted if it overlaps LHS or RHS, but doesn't contain OJ */
		if (bms_overlap(ojinfo->min_lefthand, rel->relids) ||
			bms_overlap(ojinfo->min_righthand, rel->relids))
			return true;
	}

	foreach(l, root->in_info_list)
	{
		InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);

		/* ignore if IN is already contained in rel */
		if (bms_is_subset(ininfo->lefthand, rel->relids) &&
			bms_is_subset(ininfo->righthand, rel->relids))
			continue;

		/* restricted if it overlaps LHS or RHS, but doesn't contain IN */
		if (bms_overlap(ininfo->lefthand, rel->relids) ||
			bms_overlap(ininfo->righthand, rel->relids))
			return true;
	}

	return false;
}


/*
 * has_legal_joinclause
 *		Detect whether the specified relation can legally be joined
 *		to any other rels using join clauses.
 *
 * We consider only joins to single other relations in the current
 * initial_rels list.  This is sufficient to get a "true" result in most real
 * queries, and an occasional erroneous "false" will only cost a bit more
 * planning time.  The reason for this limitation is that considering joins to
 * other joins would require proving that the other join rel can legally be
 * formed, which seems like too much trouble for something that's only a
 * heuristic to save planning time.  (Note: we must look at initial_rels
 * and not all of the query, since when we are planning a sub-joinlist we
 * may be forced to make clauseless joins within initial_rels even though
 * there are join clauses linking to other parts of the query.)
 */
static bool
has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
{
	ListCell   *lc;

	foreach(lc, root->initial_rels)
	{
		RelOptInfo *rel2 = (RelOptInfo *) lfirst(lc);

		/* ignore rels that are already in "rel" */
		if (bms_overlap(rel->relids, rel2->relids))
			continue;

		if (have_relevant_joinclause(root, rel, rel2))
		{
			Relids		joinrelids;
			JoinType	jointype;

			/* join_is_legal needs relids of the union */
			joinrelids = bms_union(rel->relids, rel2->relids);

			if (join_is_legal(root, rel, rel2, joinrelids, &jointype))
			{
				/* Yes, this will work */
				bms_free(joinrelids);
				return true;
			}

			bms_free(joinrelids);
		}
	}

	return false;
}


/*
 * is_dummy_rel --- has relation been proven empty?
 *
 * If so, it will have a single path that is dummy.
 */
static bool
is_dummy_rel(RelOptInfo *rel)
{
	return (rel->cheapest_total_path != NULL &&
			IS_DUMMY_PATH(rel->cheapest_total_path));
}

/*
 * Mark a joinrel as proven empty.
 */
static void
mark_dummy_join(RelOptInfo *rel)
{
	/* Set dummy size estimate */
	rel->rows = 0;

	/* Evict any previously chosen paths */
	rel->pathlist = NIL;

	/* Set up the dummy path */
	add_path(rel, (Path *) create_append_path(rel, NIL));

	/*
	 * Although set_cheapest will be done again later, we do it immediately
	 * in order to keep is_dummy_rel as cheap as possible (ie, not have
	 * to examine the pathlist).
	 */
	set_cheapest(rel);
}