1 /*-------------------------------------------------------------------------
4 * Relation-node lookup/construction routines
6 * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.95 2009/10/12 18:10:48 tgl Exp $
13 *-------------------------------------------------------------------------
17 #include "optimizer/cost.h"
18 #include "optimizer/pathnode.h"
19 #include "optimizer/paths.h"
20 #include "optimizer/placeholder.h"
21 #include "optimizer/plancat.h"
22 #include "optimizer/restrictinfo.h"
23 #include "parser/parsetree.h"
24 #include "utils/hsearch.h"
27 typedef struct JoinHashEntry
29 Relids join_relids; /* hash key --- MUST BE FIRST */
33 static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
34 RelOptInfo *input_rel);
35 static List *build_joinrel_restrictlist(PlannerInfo *root,
37 RelOptInfo *outer_rel,
38 RelOptInfo *inner_rel);
39 static void build_joinrel_joinlist(RelOptInfo *joinrel,
40 RelOptInfo *outer_rel,
41 RelOptInfo *inner_rel);
42 static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
44 List *new_restrictlist);
45 static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel,
52 * Construct a new RelOptInfo for a base relation or 'other' relation.
55 build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind)
60 /* Rel should not exist already */
61 Assert(relid > 0 && relid < root->simple_rel_array_size);
62 if (root->simple_rel_array[relid] != NULL)
63 elog(ERROR, "rel %d already exists", relid);
65 /* Fetch RTE for relation */
66 rte = root->simple_rte_array[relid];
69 rel = makeNode(RelOptInfo);
70 rel->reloptkind = reloptkind;
71 rel->relids = bms_make_singleton(relid);
74 rel->reltargetlist = NIL;
76 rel->cheapest_startup_path = NULL;
77 rel->cheapest_total_path = NULL;
78 rel->cheapest_unique_path = NULL;
80 rel->rtekind = rte->rtekind;
81 /* min_attr, max_attr, attr_needed, attr_widths are set below */
87 rel->subrowmark = NIL;
88 rel->baserestrictinfo = NIL;
89 rel->baserestrictcost.startup = 0;
90 rel->baserestrictcost.per_tuple = 0;
92 rel->has_eclass_joins = false;
93 rel->index_outer_relids = NULL;
94 rel->index_inner_paths = NIL;
96 /* Check type of rtable entry */
100 /* Table --- retrieve statistics from the system catalogs */
101 get_relation_info(root, rte->relid, rte->inh, rel);
109 * Subquery, function, or values list --- set up attr range and
112 * Note: 0 is included in range to support whole-row Vars
115 rel->max_attr = list_length(rte->eref->colnames);
116 rel->attr_needed = (Relids *)
117 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
118 rel->attr_widths = (int32 *)
119 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
122 elog(ERROR, "unrecognized RTE kind: %d",
127 /* Save the finished struct in the query's simple_rel_array */
128 root->simple_rel_array[relid] = rel;
131 * If this rel is an appendrel parent, recurse to build "other rel"
132 * RelOptInfos for its children. They are "other rels" because they are
133 * not in the main join tree, but we will need RelOptInfos to plan access
140 foreach(l, root->append_rel_list)
142 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
144 /* append_rel_list contains all append rels; ignore others */
145 if (appinfo->parent_relid != relid)
148 (void) build_simple_rel(root, appinfo->child_relid,
149 RELOPT_OTHER_MEMBER_REL);
158 * Find a base or other relation entry, which must already exist.
161 find_base_rel(PlannerInfo *root, int relid)
167 if (relid < root->simple_rel_array_size)
169 rel = root->simple_rel_array[relid];
174 elog(ERROR, "no relation entry for relid %d", relid);
176 return NULL; /* keep compiler quiet */
180 * build_join_rel_hash
181 * Construct the auxiliary hash table for join relations.
184 build_join_rel_hash(PlannerInfo *root)
190 /* Create the hash table */
191 MemSet(&hash_ctl, 0, sizeof(hash_ctl));
192 hash_ctl.keysize = sizeof(Relids);
193 hash_ctl.entrysize = sizeof(JoinHashEntry);
194 hash_ctl.hash = bitmap_hash;
195 hash_ctl.match = bitmap_match;
196 hash_ctl.hcxt = CurrentMemoryContext;
197 hashtab = hash_create("JoinRelHashTable",
200 HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
202 /* Insert all the already-existing joinrels */
203 foreach(l, root->join_rel_list)
205 RelOptInfo *rel = (RelOptInfo *) lfirst(l);
206 JoinHashEntry *hentry;
209 hentry = (JoinHashEntry *) hash_search(hashtab,
214 hentry->join_rel = rel;
217 root->join_rel_hash = hashtab;
222 * Returns relation entry corresponding to 'relids' (a set of RT indexes),
223 * or NULL if none exists. This is for join relations.
226 find_join_rel(PlannerInfo *root, Relids relids)
229 * Switch to using hash lookup when list grows "too long". The threshold
230 * is arbitrary and is known only here.
232 if (!root->join_rel_hash && list_length(root->join_rel_list) > 32)
233 build_join_rel_hash(root);
236 * Use either hashtable lookup or linear search, as appropriate.
238 * Note: the seemingly redundant hashkey variable is used to avoid taking
239 * the address of relids; unless the compiler is exceedingly smart, doing
240 * so would force relids out of a register and thus probably slow down the
243 if (root->join_rel_hash)
245 Relids hashkey = relids;
246 JoinHashEntry *hentry;
248 hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
253 return hentry->join_rel;
259 foreach(l, root->join_rel_list)
261 RelOptInfo *rel = (RelOptInfo *) lfirst(l);
263 if (bms_equal(rel->relids, relids))
273 * Returns relation entry corresponding to the union of two given rels,
274 * creating a new relation entry if none already exists.
276 * 'joinrelids' is the Relids set that uniquely identifies the join
277 * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
279 * 'sjinfo': join context info
280 * 'restrictlist_ptr': result variable. If not NULL, *restrictlist_ptr
281 * receives the list of RestrictInfo nodes that apply to this
282 * particular pair of joinable relations.
284 * restrictlist_ptr makes the routine's API a little grotty, but it saves
285 * duplicated calculation of the restrictlist...
288 build_join_rel(PlannerInfo *root,
290 RelOptInfo *outer_rel,
291 RelOptInfo *inner_rel,
292 SpecialJoinInfo *sjinfo,
293 List **restrictlist_ptr)
299 * See if we already have a joinrel for this set of base rels.
301 joinrel = find_join_rel(root, joinrelids);
306 * Yes, so we only need to figure the restrictlist for this particular
307 * pair of component relations.
309 if (restrictlist_ptr)
310 *restrictlist_ptr = build_joinrel_restrictlist(root,
320 joinrel = makeNode(RelOptInfo);
321 joinrel->reloptkind = RELOPT_JOINREL;
322 joinrel->relids = bms_copy(joinrelids);
325 joinrel->reltargetlist = NIL;
326 joinrel->pathlist = NIL;
327 joinrel->cheapest_startup_path = NULL;
328 joinrel->cheapest_total_path = NULL;
329 joinrel->cheapest_unique_path = NULL;
330 joinrel->relid = 0; /* indicates not a baserel */
331 joinrel->rtekind = RTE_JOIN;
332 joinrel->min_attr = 0;
333 joinrel->max_attr = 0;
334 joinrel->attr_needed = NULL;
335 joinrel->attr_widths = NULL;
336 joinrel->indexlist = NIL;
339 joinrel->subplan = NULL;
340 joinrel->subrtable = NIL;
341 joinrel->subrowmark = NIL;
342 joinrel->baserestrictinfo = NIL;
343 joinrel->baserestrictcost.startup = 0;
344 joinrel->baserestrictcost.per_tuple = 0;
345 joinrel->joininfo = NIL;
346 joinrel->has_eclass_joins = false;
347 joinrel->index_outer_relids = NULL;
348 joinrel->index_inner_paths = NIL;
351 * Create a new tlist containing just the vars that need to be output from
352 * this join (ie, are needed for higher joinclauses or final output).
354 * NOTE: the tlist order for a join rel will depend on which pair of outer
355 * and inner rels we first try to build it from. But the contents should
356 * be the same regardless.
358 build_joinrel_tlist(root, joinrel, outer_rel);
359 build_joinrel_tlist(root, joinrel, inner_rel);
360 add_placeholders_to_joinrel(root, joinrel);
363 * Construct restrict and join clause lists for the new joinrel. (The
364 * caller might or might not need the restrictlist, but I need it anyway
365 * for set_joinrel_size_estimates().)
367 restrictlist = build_joinrel_restrictlist(root, joinrel,
368 outer_rel, inner_rel);
369 if (restrictlist_ptr)
370 *restrictlist_ptr = restrictlist;
371 build_joinrel_joinlist(joinrel, outer_rel, inner_rel);
374 * This is also the right place to check whether the joinrel has any
375 * pending EquivalenceClass joins.
377 joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel);
380 * Set estimates of the joinrel's size.
382 set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
383 sjinfo, restrictlist);
386 * Add the joinrel to the query's joinrel list, and store it into the
387 * auxiliary hashtable if there is one. NB: GEQO requires us to append
388 * the new joinrel to the end of the list!
390 root->join_rel_list = lappend(root->join_rel_list, joinrel);
392 if (root->join_rel_hash)
394 JoinHashEntry *hentry;
397 hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
402 hentry->join_rel = joinrel;
409 * build_joinrel_tlist
410 * Builds a join relation's target list from an input relation.
411 * (This is invoked twice to handle the two input relations.)
413 * The join's targetlist includes all Vars of its member relations that
414 * will still be needed above the join. This subroutine adds all such
415 * Vars from the specified input rel's tlist to the join rel's tlist.
417 * We also compute the expected width of the join's output, making use
418 * of data that was cached at the baserel level by set_rel_width().
421 build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
422 RelOptInfo *input_rel)
424 Relids relids = joinrel->relids;
427 foreach(vars, input_rel->reltargetlist)
429 Node *origvar = (Node *) lfirst(vars);
435 * Ignore PlaceHolderVars in the input tlists; we'll make our own
436 * decisions about whether to copy them.
438 if (IsA(origvar, PlaceHolderVar))
442 * We can't run into any child RowExprs here, but we could find a
443 * whole-row Var with a ConvertRowtypeExpr atop it.
445 var = (Var *) origvar;
446 while (!IsA(var, Var))
448 if (IsA(var, ConvertRowtypeExpr))
449 var = (Var *) ((ConvertRowtypeExpr *) var)->arg;
451 elog(ERROR, "unexpected node type in reltargetlist: %d",
455 /* Get the Var's original base rel */
456 baserel = find_base_rel(root, var->varno);
458 /* Is it still needed above this joinrel? */
459 ndx = var->varattno - baserel->min_attr;
460 if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
462 /* Yup, add it to the output */
463 joinrel->reltargetlist = lappend(joinrel->reltargetlist, origvar);
464 joinrel->width += baserel->attr_widths[ndx];
470 * build_joinrel_restrictlist
471 * build_joinrel_joinlist
472 * These routines build lists of restriction and join clauses for a
473 * join relation from the joininfo lists of the relations it joins.
475 * These routines are separate because the restriction list must be
476 * built afresh for each pair of input sub-relations we consider, whereas
477 * the join list need only be computed once for any join RelOptInfo.
478 * The join list is fully determined by the set of rels making up the
479 * joinrel, so we should get the same results (up to ordering) from any
480 * candidate pair of sub-relations. But the restriction list is whatever
481 * is not handled in the sub-relations, so it depends on which
482 * sub-relations are considered.
484 * If a join clause from an input relation refers to base rels still not
485 * present in the joinrel, then it is still a join clause for the joinrel;
486 * we put it into the joininfo list for the joinrel. Otherwise,
487 * the clause is now a restrict clause for the joined relation, and we
488 * return it to the caller of build_joinrel_restrictlist() to be stored in
489 * join paths made from this pair of sub-relations. (It will not need to
490 * be considered further up the join tree.)
492 * In many case we will find the same RestrictInfos in both input
493 * relations' joinlists, so be careful to eliminate duplicates.
494 * Pointer equality should be a sufficient test for dups, since all
495 * the various joinlist entries ultimately refer to RestrictInfos
496 * pushed into them by distribute_restrictinfo_to_rels().
498 * 'joinrel' is a join relation node
499 * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
502 * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
503 * whereas build_joinrel_joinlist() stores its results in the joinrel's
504 * joininfo list. One or the other must accept each given clause!
506 * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
507 * up to the join relation. I believe this is no longer necessary, because
508 * RestrictInfo nodes are no longer context-dependent. Instead, just include
509 * the original nodes in the lists made for the join relation.
512 build_joinrel_restrictlist(PlannerInfo *root,
514 RelOptInfo *outer_rel,
515 RelOptInfo *inner_rel)
520 * Collect all the clauses that syntactically belong at this level,
521 * eliminating any duplicates (important since we will see many of the
522 * same clauses arriving from both input relations).
524 result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL);
525 result = subbuild_joinrel_restrictlist(joinrel, inner_rel->joininfo, result);
528 * Add on any clauses derived from EquivalenceClasses. These cannot be
529 * redundant with the clauses in the joininfo lists, so don't bother
532 result = list_concat(result,
533 generate_join_implied_equalities(root,
542 build_joinrel_joinlist(RelOptInfo *joinrel,
543 RelOptInfo *outer_rel,
544 RelOptInfo *inner_rel)
549 * Collect all the clauses that syntactically belong above this level,
550 * eliminating any duplicates (important since we will see many of the
551 * same clauses arriving from both input relations).
553 result = subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo, NIL);
554 result = subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo, result);
556 joinrel->joininfo = result;
560 subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
562 List *new_restrictlist)
566 foreach(l, joininfo_list)
568 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
570 if (bms_is_subset(rinfo->required_relids, joinrel->relids))
573 * This clause becomes a restriction clause for the joinrel, since
574 * it refers to no outside rels. Add it to the list, being
575 * careful to eliminate duplicates. (Since RestrictInfo nodes in
576 * different joinlists will have been multiply-linked rather than
577 * copied, pointer equality should be a sufficient test.)
579 new_restrictlist = list_append_unique_ptr(new_restrictlist, rinfo);
584 * This clause is still a join clause at this level, so we ignore
585 * it in this routine.
590 return new_restrictlist;
594 subbuild_joinrel_joinlist(RelOptInfo *joinrel,
600 foreach(l, joininfo_list)
602 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
604 if (bms_is_subset(rinfo->required_relids, joinrel->relids))
607 * This clause becomes a restriction clause for the joinrel, since
608 * it refers to no outside rels. So we can ignore it in this
615 * This clause is still a join clause at this level, so add it to
616 * the new joininfo list, being careful to eliminate duplicates.
617 * (Since RestrictInfo nodes in different joinlists will have been
618 * multiply-linked rather than copied, pointer equality should be
619 * a sufficient test.)
621 new_joininfo = list_append_unique_ptr(new_joininfo, rinfo);