1 /*-------------------------------------------------------------------------
4 * Routines to find possible search paths for processing a query
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/path/allpaths.c,v 1.189 2009/11/15 02:45:35 tgl Exp $
13 *-------------------------------------------------------------------------
20 #include "nodes/nodeFuncs.h"
21 #ifdef OPTIMIZER_DEBUG
22 #include "nodes/print.h"
24 #include "optimizer/clauses.h"
25 #include "optimizer/cost.h"
26 #include "optimizer/geqo.h"
27 #include "optimizer/pathnode.h"
28 #include "optimizer/paths.h"
29 #include "optimizer/plancat.h"
30 #include "optimizer/planner.h"
31 #include "optimizer/prep.h"
32 #include "optimizer/restrictinfo.h"
33 #include "optimizer/var.h"
34 #include "parser/parse_clause.h"
35 #include "parser/parsetree.h"
36 #include "rewrite/rewriteManip.h"
39 /* These parameters are set by GUC */
40 bool enable_geqo = false; /* just in case GUC doesn't set it */
43 /* Hook for plugins to replace standard_join_search() */
44 join_search_hook_type join_search_hook = NULL;
47 static void set_base_rel_pathlists(PlannerInfo *root);
48 static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
49 Index rti, RangeTblEntry *rte);
50 static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
52 static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
53 Index rti, RangeTblEntry *rte);
54 static void set_dummy_rel_pathlist(RelOptInfo *rel);
55 static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
56 Index rti, RangeTblEntry *rte);
57 static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel,
59 static void set_values_pathlist(PlannerInfo *root, RelOptInfo *rel,
61 static void set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel,
63 static void set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel,
65 static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist);
66 static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery,
67 bool *differentTypes);
68 static bool recurse_pushdown_safe(Node *setOp, Query *topquery,
69 bool *differentTypes);
70 static void compare_tlist_datatypes(List *tlist, List *colTypes,
71 bool *differentTypes);
72 static bool qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
73 bool *differentTypes);
74 static void subquery_push_qual(Query *subquery,
75 RangeTblEntry *rte, Index rti, Node *qual);
76 static void recurse_push_qual(Node *setOp, Query *topquery,
77 RangeTblEntry *rte, Index rti, Node *qual);
82 * Finds all possible access paths for executing a query, returning a
83 * single rel that represents the join of all base rels in the query.
86 make_one_rel(PlannerInfo *root, List *joinlist)
91 * Generate access paths for the base rels.
93 set_base_rel_pathlists(root);
96 * Generate access paths for the entire join tree.
98 rel = make_rel_from_joinlist(root, joinlist);
101 * The result should join all and only the query's base rels.
103 #ifdef USE_ASSERT_CHECKING
105 int num_base_rels = 0;
108 for (rti = 1; rti < root->simple_rel_array_size; rti++)
110 RelOptInfo *brel = root->simple_rel_array[rti];
115 Assert(brel->relid == rti); /* sanity check on array */
117 /* ignore RTEs that are "other rels" */
118 if (brel->reloptkind != RELOPT_BASEREL)
121 Assert(bms_is_member(rti, rel->relids));
125 Assert(bms_num_members(rel->relids) == num_base_rels);
133 * set_base_rel_pathlists
134 * Finds all paths available for scanning each base-relation entry.
135 * Sequential scan and any available indices are considered.
136 * Each useful path is attached to its relation's 'pathlist' field.
139 set_base_rel_pathlists(PlannerInfo *root)
143 for (rti = 1; rti < root->simple_rel_array_size; rti++)
145 RelOptInfo *rel = root->simple_rel_array[rti];
147 /* there may be empty slots corresponding to non-baserel RTEs */
151 Assert(rel->relid == rti); /* sanity check on array */
153 /* ignore RTEs that are "other rels" */
154 if (rel->reloptkind != RELOPT_BASEREL)
157 set_rel_pathlist(root, rel, rti, root->simple_rte_array[rti]);
163 * Build access paths for a base relation
166 set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
167 Index rti, RangeTblEntry *rte)
171 /* It's an "append relation", process accordingly */
172 set_append_rel_pathlist(root, rel, rti, rte);
174 else if (rel->rtekind == RTE_SUBQUERY)
176 /* Subquery --- generate a separate plan for it */
177 set_subquery_pathlist(root, rel, rti, rte);
179 else if (rel->rtekind == RTE_FUNCTION)
181 /* RangeFunction --- generate a suitable path for it */
182 set_function_pathlist(root, rel, rte);
184 else if (rel->rtekind == RTE_VALUES)
186 /* Values list --- generate a suitable path for it */
187 set_values_pathlist(root, rel, rte);
189 else if (rel->rtekind == RTE_CTE)
191 /* CTE reference --- generate a suitable path for it */
192 if (rte->self_reference)
193 set_worktable_pathlist(root, rel, rte);
195 set_cte_pathlist(root, rel, rte);
200 Assert(rel->rtekind == RTE_RELATION);
201 set_plain_rel_pathlist(root, rel, rte);
204 #ifdef OPTIMIZER_DEBUG
205 debug_print_rel(root, rel);
210 * set_plain_rel_pathlist
211 * Build access paths for a plain relation (no subquery, no inheritance)
214 set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
217 * If we can prove we don't need to scan the rel via constraint exclusion,
218 * set up a single dummy path for it. We only need to check for regular
219 * baserels; if it's an otherrel, CE was already checked in
220 * set_append_rel_pathlist().
222 if (rel->reloptkind == RELOPT_BASEREL &&
223 relation_excluded_by_constraints(root, rel, rte))
225 set_dummy_rel_pathlist(rel);
230 * Test any partial indexes of rel for applicability. We must do this
231 * first since partial unique indexes can affect size estimates.
233 check_partial_indexes(root, rel);
235 /* Mark rel with estimated output rows, width, etc */
236 set_baserel_size_estimates(root, rel);
239 * Check to see if we can extract any restriction conditions from join
240 * quals that are OR-of-AND structures. If so, add them to the rel's
241 * restriction list, and redo the above steps.
243 if (create_or_index_quals(root, rel))
245 check_partial_indexes(root, rel);
246 set_baserel_size_estimates(root, rel);
250 * Generate paths and add them to the rel's pathlist.
252 * Note: add_path() will discard any paths that are dominated by another
253 * available path, keeping only those paths that are superior along at
254 * least one dimension of cost or sortedness.
257 /* Consider sequential scan */
258 add_path(rel, create_seqscan_path(root, rel));
260 /* Consider index scans */
261 create_index_paths(root, rel);
263 /* Consider TID scans */
264 create_tidscan_paths(root, rel);
266 /* Now find the cheapest of the paths for this rel */
271 * set_append_rel_pathlist
272 * Build access paths for an "append relation"
274 * The passed-in rel and RTE represent the entire append relation. The
275 * relation's contents are computed by appending together the output of
276 * the individual member relations. Note that in the inheritance case,
277 * the first member relation is actually the same table as is mentioned in
278 * the parent RTE ... but it has a different RTE and RelOptInfo. This is
279 * a good thing because their outputs are not the same size.
282 set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
283 Index rti, RangeTblEntry *rte)
285 int parentRTindex = rti;
286 List *subpaths = NIL;
289 double *parent_attrsizes;
294 * Initialize to compute size estimates for whole append relation.
296 * We handle width estimates by weighting the widths of different child
297 * rels proportionally to their number of rows. This is sensible because
298 * the use of width estimates is mainly to compute the total relation
299 * "footprint" if we have to sort or hash it. To do this, we sum the
300 * total equivalent size (in "double" arithmetic) and then divide by the
301 * total rowcount estimate. This is done separately for the total rel
302 * width and each attribute.
304 * Note: if you consider changing this logic, beware that child rels could
305 * have zero rows and/or width, if they were excluded by constraints.
309 nattrs = rel->max_attr - rel->min_attr + 1;
310 parent_attrsizes = (double *) palloc0(nattrs * sizeof(double));
313 * Generate access paths for each member relation, and pick the cheapest
316 foreach(l, root->append_rel_list)
318 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
320 RangeTblEntry *childRTE;
321 RelOptInfo *childrel;
325 ListCell *parentvars;
328 /* append_rel_list contains all append rels; ignore others */
329 if (appinfo->parent_relid != parentRTindex)
332 childRTindex = appinfo->child_relid;
333 childRTE = root->simple_rte_array[childRTindex];
336 * The child rel's RelOptInfo was already created during
337 * add_base_rels_to_query.
339 childrel = find_base_rel(root, childRTindex);
340 Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
343 * We have to copy the parent's targetlist and quals to the child,
344 * with appropriate substitution of variables. However, only the
345 * baserestrictinfo quals are needed before we can check for
346 * constraint exclusion; so do that first and then check to see if we
347 * can disregard this child.
349 * As of 8.4, the child rel's targetlist might contain non-Var
350 * expressions, which means that substitution into the quals
351 * could produce opportunities for const-simplification, and perhaps
352 * even pseudoconstant quals. To deal with this, we strip the
353 * RestrictInfo nodes, do the substitution, do const-simplification,
354 * and then reconstitute the RestrictInfo layer.
356 childquals = get_all_actual_clauses(rel->baserestrictinfo);
357 childquals = (List *) adjust_appendrel_attrs((Node *) childquals,
359 childqual = eval_const_expressions(root, (Node *)
360 make_ands_explicit(childquals));
361 if (childqual && IsA(childqual, Const) &&
362 (((Const *) childqual)->constisnull ||
363 !DatumGetBool(((Const *) childqual)->constvalue)))
366 * Restriction reduces to constant FALSE or constant NULL after
367 * substitution, so this child need not be scanned.
369 set_dummy_rel_pathlist(childrel);
372 childquals = make_ands_implicit((Expr *) childqual);
373 childquals = make_restrictinfos_from_actual_clauses(root,
375 childrel->baserestrictinfo = childquals;
377 if (relation_excluded_by_constraints(root, childrel, childRTE))
380 * This child need not be scanned, so we can omit it from the
381 * appendrel. Mark it with a dummy cheapest-path though, in case
382 * best_appendrel_indexscan() looks at it later.
384 set_dummy_rel_pathlist(childrel);
388 /* CE failed, so finish copying targetlist and join quals */
389 childrel->joininfo = (List *)
390 adjust_appendrel_attrs((Node *) rel->joininfo,
392 childrel->reltargetlist = (List *)
393 adjust_appendrel_attrs((Node *) rel->reltargetlist,
397 * We have to make child entries in the EquivalenceClass data
398 * structures as well.
400 if (rel->has_eclass_joins)
402 add_child_rel_equivalences(root, appinfo, rel, childrel);
403 childrel->has_eclass_joins = true;
407 * Note: we could compute appropriate attr_needed data for the child's
408 * variables, by transforming the parent's attr_needed through the
409 * translated_vars mapping. However, currently there's no need
410 * because attr_needed is only examined for base relations not
411 * otherrels. So we just leave the child's attr_needed empty.
415 * Compute the child's access paths, and add the cheapest one to the
416 * Append path we are constructing for the parent.
418 * It's possible that the child is itself an appendrel, in which case
419 * we can "cut out the middleman" and just add its child paths to our
420 * own list. (We don't try to do this earlier because we need to
421 * apply both levels of transformation to the quals.)
423 set_rel_pathlist(root, childrel, childRTindex, childRTE);
425 childpath = childrel->cheapest_total_path;
426 if (IsA(childpath, AppendPath))
427 subpaths = list_concat(subpaths,
428 ((AppendPath *) childpath)->subpaths);
430 subpaths = lappend(subpaths, childpath);
433 * Accumulate size information from each child.
435 if (childrel->rows > 0)
437 parent_rows += childrel->rows;
438 parent_size += childrel->width * childrel->rows;
440 forboth(parentvars, rel->reltargetlist,
441 childvars, childrel->reltargetlist)
443 Var *parentvar = (Var *) lfirst(parentvars);
444 Var *childvar = (Var *) lfirst(childvars);
447 * Accumulate per-column estimates too. Whole-row Vars and
448 * PlaceHolderVars can be ignored here.
450 if (IsA(parentvar, Var) &&
453 int pndx = parentvar->varattno - rel->min_attr;
454 int cndx = childvar->varattno - childrel->min_attr;
456 parent_attrsizes[pndx] += childrel->attr_widths[cndx] * childrel->rows;
463 * Save the finished size estimates.
465 rel->rows = parent_rows;
470 rel->width = rint(parent_size / parent_rows);
471 for (i = 0; i < nattrs; i++)
472 rel->attr_widths[i] = rint(parent_attrsizes[i] / parent_rows);
475 rel->width = 0; /* attr_widths should be zero already */
478 * Set "raw tuples" count equal to "rows" for the appendrel; needed
479 * because some places assume rel->tuples is valid for any baserel.
481 rel->tuples = parent_rows;
483 pfree(parent_attrsizes);
486 * Finally, build Append path and install it as the only access path for
487 * the parent rel. (Note: this is correct even if we have zero or one
488 * live subpath due to constraint exclusion.)
490 add_path(rel, (Path *) create_append_path(rel, subpaths));
492 /* Select cheapest path (pretty easy in this case...) */
497 * set_dummy_rel_pathlist
498 * Build a dummy path for a relation that's been excluded by constraints
500 * Rather than inventing a special "dummy" path type, we represent this as an
501 * AppendPath with no members (see also IS_DUMMY_PATH macro).
504 set_dummy_rel_pathlist(RelOptInfo *rel)
506 /* Set dummy size estimates --- we leave attr_widths[] as zeroes */
510 add_path(rel, (Path *) create_append_path(rel, NIL));
512 /* Select cheapest path (pretty easy in this case...) */
516 /* quick-and-dirty test to see if any joining is needed */
518 has_multiple_baserels(PlannerInfo *root)
520 int num_base_rels = 0;
523 for (rti = 1; rti < root->simple_rel_array_size; rti++)
525 RelOptInfo *brel = root->simple_rel_array[rti];
530 /* ignore RTEs that are "other rels" */
531 if (brel->reloptkind == RELOPT_BASEREL)
532 if (++num_base_rels > 1)
539 * set_subquery_pathlist
540 * Build the (single) access path for a subquery RTE
543 set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
544 Index rti, RangeTblEntry *rte)
546 Query *parse = root->parse;
547 Query *subquery = rte->subquery;
548 bool *differentTypes;
549 double tuple_fraction;
550 PlannerInfo *subroot;
554 * Must copy the Query so that planning doesn't mess up the RTE contents
555 * (really really need to fix the planner to not scribble on its input,
558 subquery = copyObject(subquery);
560 /* We need a workspace for keeping track of set-op type coercions */
561 differentTypes = (bool *)
562 palloc0((list_length(subquery->targetList) + 1) * sizeof(bool));
565 * If there are any restriction clauses that have been attached to the
566 * subquery relation, consider pushing them down to become WHERE or HAVING
567 * quals of the subquery itself. This transformation is useful because it
568 * may allow us to generate a better plan for the subquery than evaluating
569 * all the subquery output rows and then filtering them.
571 * There are several cases where we cannot push down clauses. Restrictions
572 * involving the subquery are checked by subquery_is_pushdown_safe().
573 * Restrictions on individual clauses are checked by
574 * qual_is_pushdown_safe(). Also, we don't want to push down
575 * pseudoconstant clauses; better to have the gating node above the
578 * Non-pushed-down clauses will get evaluated as qpquals of the
581 * XXX Are there any cases where we want to make a policy decision not to
582 * push down a pushable qual, because it'd result in a worse plan?
584 if (rel->baserestrictinfo != NIL &&
585 subquery_is_pushdown_safe(subquery, subquery, differentTypes))
587 /* OK to consider pushing down individual quals */
588 List *upperrestrictlist = NIL;
591 foreach(l, rel->baserestrictinfo)
593 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
594 Node *clause = (Node *) rinfo->clause;
596 if (!rinfo->pseudoconstant &&
597 qual_is_pushdown_safe(subquery, rti, clause, differentTypes))
600 subquery_push_qual(subquery, rte, rti, clause);
604 /* Keep it in the upper query */
605 upperrestrictlist = lappend(upperrestrictlist, rinfo);
608 rel->baserestrictinfo = upperrestrictlist;
611 pfree(differentTypes);
614 * We can safely pass the outer tuple_fraction down to the subquery if the
615 * outer level has no joining, aggregation, or sorting to do. Otherwise
616 * we'd better tell the subquery to plan for full retrieval. (XXX This
617 * could probably be made more intelligent ...)
619 if (parse->hasAggs ||
620 parse->groupClause ||
622 parse->distinctClause ||
624 has_multiple_baserels(root))
625 tuple_fraction = 0.0; /* default case */
627 tuple_fraction = root->tuple_fraction;
629 /* Generate the plan for the subquery */
630 rel->subplan = subquery_planner(root->glob, subquery,
632 false, tuple_fraction,
634 rel->subrtable = subroot->parse->rtable;
635 rel->subrowmark = subroot->rowMarks;
637 /* Copy number of output rows from subplan */
638 rel->tuples = rel->subplan->plan_rows;
640 /* Mark rel with estimated output rows, width, etc */
641 set_baserel_size_estimates(root, rel);
643 /* Convert subquery pathkeys to outer representation */
644 pathkeys = convert_subquery_pathkeys(root, rel, subroot->query_pathkeys);
646 /* Generate appropriate path */
647 add_path(rel, create_subqueryscan_path(rel, pathkeys));
649 /* Select cheapest path (pretty easy in this case...) */
654 * set_function_pathlist
655 * Build the (single) access path for a function RTE
658 set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
660 /* Mark rel with estimated output rows, width, etc */
661 set_function_size_estimates(root, rel);
663 /* Generate appropriate path */
664 add_path(rel, create_functionscan_path(root, rel));
666 /* Select cheapest path (pretty easy in this case...) */
671 * set_values_pathlist
672 * Build the (single) access path for a VALUES RTE
675 set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
677 /* Mark rel with estimated output rows, width, etc */
678 set_values_size_estimates(root, rel);
680 /* Generate appropriate path */
681 add_path(rel, create_valuesscan_path(root, rel));
683 /* Select cheapest path (pretty easy in this case...) */
689 * Build the (single) access path for a non-self-reference CTE RTE
692 set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
695 PlannerInfo *cteroot;
702 * Find the referenced CTE, and locate the plan previously made for it.
704 levelsup = rte->ctelevelsup;
706 while (levelsup-- > 0)
708 cteroot = cteroot->parent_root;
709 if (!cteroot) /* shouldn't happen */
710 elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
714 * Note: cte_plan_ids can be shorter than cteList, if we are still working
715 * on planning the CTEs (ie, this is a side-reference from another CTE).
716 * So we mustn't use forboth here.
719 foreach(lc, cteroot->parse->cteList)
721 CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
723 if (strcmp(cte->ctename, rte->ctename) == 0)
727 if (lc == NULL) /* shouldn't happen */
728 elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
729 if (ndx >= list_length(cteroot->cte_plan_ids))
730 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
731 plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
733 cteplan = (Plan *) list_nth(root->glob->subplans, plan_id - 1);
735 /* Mark rel with estimated output rows, width, etc */
736 set_cte_size_estimates(root, rel, cteplan);
738 /* Generate appropriate path */
739 add_path(rel, create_ctescan_path(root, rel));
741 /* Select cheapest path (pretty easy in this case...) */
746 * set_worktable_pathlist
747 * Build the (single) access path for a self-reference CTE RTE
750 set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
753 PlannerInfo *cteroot;
757 * We need to find the non-recursive term's plan, which is in the plan
758 * level that's processing the recursive UNION, which is one level *below*
759 * where the CTE comes from.
761 levelsup = rte->ctelevelsup;
762 if (levelsup == 0) /* shouldn't happen */
763 elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
766 while (levelsup-- > 0)
768 cteroot = cteroot->parent_root;
769 if (!cteroot) /* shouldn't happen */
770 elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
772 cteplan = cteroot->non_recursive_plan;
773 if (!cteplan) /* shouldn't happen */
774 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
776 /* Mark rel with estimated output rows, width, etc */
777 set_cte_size_estimates(root, rel, cteplan);
779 /* Generate appropriate path */
780 add_path(rel, create_worktablescan_path(root, rel));
782 /* Select cheapest path (pretty easy in this case...) */
787 * make_rel_from_joinlist
788 * Build access paths using a "joinlist" to guide the join path search.
790 * See comments for deconstruct_jointree() for definition of the joinlist
794 make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
801 * Count the number of child joinlist nodes. This is the depth of the
802 * dynamic-programming algorithm we must employ to consider all ways of
803 * joining the child nodes.
805 levels_needed = list_length(joinlist);
807 if (levels_needed <= 0)
808 return NULL; /* nothing to do? */
811 * Construct a list of rels corresponding to the child joinlist nodes.
812 * This may contain both base rels and rels constructed according to
816 foreach(jl, joinlist)
818 Node *jlnode = (Node *) lfirst(jl);
821 if (IsA(jlnode, RangeTblRef))
823 int varno = ((RangeTblRef *) jlnode)->rtindex;
825 thisrel = find_base_rel(root, varno);
827 else if (IsA(jlnode, List))
829 /* Recurse to handle subproblem */
830 thisrel = make_rel_from_joinlist(root, (List *) jlnode);
834 elog(ERROR, "unrecognized joinlist node type: %d",
835 (int) nodeTag(jlnode));
836 thisrel = NULL; /* keep compiler quiet */
839 initial_rels = lappend(initial_rels, thisrel);
842 if (levels_needed == 1)
845 * Single joinlist node, so we're done.
847 return (RelOptInfo *) linitial(initial_rels);
852 * Consider the different orders in which we could join the rels,
853 * using a plugin, GEQO, or the regular join search code.
855 * We put the initial_rels list into a PlannerInfo field because
856 * has_legal_joinclause() needs to look at it (ugly :-().
858 root->initial_rels = initial_rels;
860 if (join_search_hook)
861 return (*join_search_hook) (root, levels_needed, initial_rels);
862 else if (enable_geqo && levels_needed >= geqo_threshold)
863 return geqo(root, levels_needed, initial_rels);
865 return standard_join_search(root, levels_needed, initial_rels);
870 * standard_join_search
871 * Find possible joinpaths for a query by successively finding ways
872 * to join component relations into join relations.
874 * 'levels_needed' is the number of iterations needed, ie, the number of
875 * independent jointree items in the query. This is > 1.
877 * 'initial_rels' is a list of RelOptInfo nodes for each independent
878 * jointree item. These are the components to be joined together.
879 * Note that levels_needed == list_length(initial_rels).
881 * Returns the final level of join relations, i.e., the relation that is
882 * the result of joining all the original relations together.
883 * At least one implementation path must be provided for this relation and
884 * all required sub-relations.
886 * To support loadable plugins that modify planner behavior by changing the
887 * join searching algorithm, we provide a hook variable that lets a plugin
888 * replace or supplement this function. Any such hook must return the same
889 * final join relation as the standard code would, but it might have a
890 * different set of implementation paths attached, and only the sub-joinrels
891 * needed for these paths need have been instantiated.
893 * Note to plugin authors: the functions invoked during standard_join_search()
894 * modify root->join_rel_list and root->join_rel_hash. If you want to do more
895 * than one join-order search, you'll probably need to save and restore the
896 * original states of those data structures. See geqo_eval() for an example.
899 standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels)
906 * We employ a simple "dynamic programming" algorithm: we first find all
907 * ways to build joins of two jointree items, then all ways to build joins
908 * of three items (from two-item joins and single items), then four-item
909 * joins, and so on until we have considered all ways to join all the
910 * items into one rel.
912 * joinitems[j] is a list of all the j-item rels. Initially we set
913 * joinitems[1] to represent all the single-jointree-item relations.
915 joinitems = (List **) palloc0((levels_needed + 1) * sizeof(List *));
917 joinitems[1] = initial_rels;
919 for (lev = 2; lev <= levels_needed; lev++)
924 * Determine all possible pairs of relations to be joined at this
925 * level, and build paths for making each one from every available
926 * pair of lower-level relations.
928 joinitems[lev] = join_search_one_level(root, lev, joinitems);
931 * Do cleanup work on each just-processed rel.
933 foreach(x, joinitems[lev])
935 rel = (RelOptInfo *) lfirst(x);
937 /* Find and save the cheapest paths for this rel */
940 #ifdef OPTIMIZER_DEBUG
941 debug_print_rel(root, rel);
947 * We should have a single rel at the final level.
949 if (joinitems[levels_needed] == NIL)
950 elog(ERROR, "failed to build any %d-way joins", levels_needed);
951 Assert(list_length(joinitems[levels_needed]) == 1);
953 rel = (RelOptInfo *) linitial(joinitems[levels_needed]);
958 /*****************************************************************************
959 * PUSHING QUALS DOWN INTO SUBQUERIES
960 *****************************************************************************/
963 * subquery_is_pushdown_safe - is a subquery safe for pushing down quals?
965 * subquery is the particular component query being checked. topquery
966 * is the top component of a set-operations tree (the same Query if no
967 * set-op is involved).
969 * Conditions checked here:
971 * 1. If the subquery has a LIMIT clause, we must not push down any quals,
972 * since that could change the set of rows returned.
974 * 2. If the subquery contains any window functions, we can't push quals
975 * into it, because that could change the results.
977 * 3. If the subquery contains EXCEPT or EXCEPT ALL set ops we cannot push
978 * quals into it, because that could change the results.
980 * 4. For subqueries using UNION/UNION ALL/INTERSECT/INTERSECT ALL, we can
981 * push quals into each component query, but the quals can only reference
982 * subquery columns that suffer no type coercions in the set operation.
983 * Otherwise there are possible semantic gotchas. So, we check the
984 * component queries to see if any of them have different output types;
985 * differentTypes[k] is set true if column k has different type in any
989 subquery_is_pushdown_safe(Query *subquery, Query *topquery,
990 bool *differentTypes)
992 SetOperationStmt *topop;
995 if (subquery->limitOffset != NULL || subquery->limitCount != NULL)
999 if (subquery->hasWindowFuncs)
1002 /* Are we at top level, or looking at a setop component? */
1003 if (subquery == topquery)
1005 /* Top level, so check any component queries */
1006 if (subquery->setOperations != NULL)
1007 if (!recurse_pushdown_safe(subquery->setOperations, topquery,
1013 /* Setop component must not have more components (too weird) */
1014 if (subquery->setOperations != NULL)
1016 /* Check whether setop component output types match top level */
1017 topop = (SetOperationStmt *) topquery->setOperations;
1018 Assert(topop && IsA(topop, SetOperationStmt));
1019 compare_tlist_datatypes(subquery->targetList,
1027 * Helper routine to recurse through setOperations tree
1030 recurse_pushdown_safe(Node *setOp, Query *topquery,
1031 bool *differentTypes)
1033 if (IsA(setOp, RangeTblRef))
1035 RangeTblRef *rtr = (RangeTblRef *) setOp;
1036 RangeTblEntry *rte = rt_fetch(rtr->rtindex, topquery->rtable);
1037 Query *subquery = rte->subquery;
1039 Assert(subquery != NULL);
1040 return subquery_is_pushdown_safe(subquery, topquery, differentTypes);
1042 else if (IsA(setOp, SetOperationStmt))
1044 SetOperationStmt *op = (SetOperationStmt *) setOp;
1046 /* EXCEPT is no good */
1047 if (op->op == SETOP_EXCEPT)
1050 if (!recurse_pushdown_safe(op->larg, topquery, differentTypes))
1052 if (!recurse_pushdown_safe(op->rarg, topquery, differentTypes))
1057 elog(ERROR, "unrecognized node type: %d",
1058 (int) nodeTag(setOp));
1064 * Compare tlist's datatypes against the list of set-operation result types.
1065 * For any items that are different, mark the appropriate element of
1066 * differentTypes[] to show that this column will have type conversions.
1068 * We don't have to care about typmods here: the only allowed difference
1069 * between set-op input and output typmods is input is a specific typmod
1070 * and output is -1, and that does not require a coercion.
1073 compare_tlist_datatypes(List *tlist, List *colTypes,
1074 bool *differentTypes)
1077 ListCell *colType = list_head(colTypes);
1081 TargetEntry *tle = (TargetEntry *) lfirst(l);
1084 continue; /* ignore resjunk columns */
1085 if (colType == NULL)
1086 elog(ERROR, "wrong number of tlist entries");
1087 if (exprType((Node *) tle->expr) != lfirst_oid(colType))
1088 differentTypes[tle->resno] = true;
1089 colType = lnext(colType);
1091 if (colType != NULL)
1092 elog(ERROR, "wrong number of tlist entries");
1096 * qual_is_pushdown_safe - is a particular qual safe to push down?
1098 * qual is a restriction clause applying to the given subquery (whose RTE
1099 * has index rti in the parent query).
1101 * Conditions checked here:
1103 * 1. The qual must not contain any subselects (mainly because I'm not sure
1104 * it will work correctly: sublinks will already have been transformed into
1105 * subplans in the qual, but not in the subquery).
1107 * 2. The qual must not refer to the whole-row output of the subquery
1108 * (since there is no easy way to name that within the subquery itself).
1110 * 3. The qual must not refer to any subquery output columns that were
1111 * found to have inconsistent types across a set operation tree by
1112 * subquery_is_pushdown_safe().
1114 * 4. If the subquery uses DISTINCT ON, we must not push down any quals that
1115 * refer to non-DISTINCT output columns, because that could change the set
1116 * of rows returned. (This condition is vacuous for DISTINCT, because then
1117 * there are no non-DISTINCT output columns, so we needn't check. But note
1118 * we are assuming that the qual can't distinguish values that the DISTINCT
1119 * operator sees as equal. This is a bit shaky but we have no way to test
1120 * for the case, and it's unlikely enough that we shouldn't refuse the
1121 * optimization just because it could theoretically happen.)
1123 * 5. We must not push down any quals that refer to subselect outputs that
1124 * return sets, else we'd introduce functions-returning-sets into the
1125 * subquery's WHERE/HAVING quals.
1127 * 6. We must not push down any quals that refer to subselect outputs that
1128 * contain volatile functions, for fear of introducing strange results due
1129 * to multiple evaluation of a volatile function.
1132 qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
1133 bool *differentTypes)
1138 Bitmapset *tested = NULL;
1140 /* Refuse subselects (point 1) */
1141 if (contain_subplans(qual))
1145 * It would be unsafe to push down window function calls, but at least for
1146 * the moment we could never see any in a qual anyhow.
1148 Assert(!contain_window_function(qual));
1151 * Examine all Vars used in clause; since it's a restriction clause, all
1152 * such Vars must refer to subselect output columns.
1154 vars = pull_var_clause(qual, PVC_INCLUDE_PLACEHOLDERS);
1157 Var *var = (Var *) lfirst(vl);
1161 * XXX Punt if we find any PlaceHolderVars in the restriction clause.
1162 * It's not clear whether a PHV could safely be pushed down, and even
1163 * less clear whether such a situation could arise in any cases of
1164 * practical interest anyway. So for the moment, just refuse to push
1173 Assert(var->varno == rti);
1176 if (var->varattno == 0)
1183 * We use a bitmapset to avoid testing the same attno more than once.
1184 * (NB: this only works because subquery outputs can't have negative
1187 if (bms_is_member(var->varattno, tested))
1189 tested = bms_add_member(tested, var->varattno);
1192 if (differentTypes[var->varattno])
1198 /* Must find the tlist element referenced by the Var */
1199 tle = get_tle_by_resno(subquery->targetList, var->varattno);
1200 Assert(tle != NULL);
1201 Assert(!tle->resjunk);
1203 /* If subquery uses DISTINCT ON, check point 4 */
1204 if (subquery->hasDistinctOn &&
1205 !targetIsInSortList(tle, InvalidOid, subquery->distinctClause))
1207 /* non-DISTINCT column, so fail */
1212 /* Refuse functions returning sets (point 5) */
1213 if (expression_returns_set((Node *) tle->expr))
1219 /* Refuse volatile functions (point 6) */
1220 if (contain_volatile_functions((Node *) tle->expr))
1234 * subquery_push_qual - push down a qual that we have determined is safe
1237 subquery_push_qual(Query *subquery, RangeTblEntry *rte, Index rti, Node *qual)
1239 if (subquery->setOperations != NULL)
1241 /* Recurse to push it separately to each component query */
1242 recurse_push_qual(subquery->setOperations, subquery,
1248 * We need to replace Vars in the qual (which must refer to outputs of
1249 * the subquery) with copies of the subquery's targetlist expressions.
1250 * Note that at this point, any uplevel Vars in the qual should have
1251 * been replaced with Params, so they need no work.
1253 * This step also ensures that when we are pushing into a setop tree,
1254 * each component query gets its own copy of the qual.
1256 qual = ResolveNew(qual, rti, 0, rte,
1257 subquery->targetList,
1259 &subquery->hasSubLinks);
1262 * Now attach the qual to the proper place: normally WHERE, but if the
1263 * subquery uses grouping or aggregation, put it in HAVING (since the
1264 * qual really refers to the group-result rows).
1266 if (subquery->hasAggs || subquery->groupClause || subquery->havingQual)
1267 subquery->havingQual = make_and_qual(subquery->havingQual, qual);
1269 subquery->jointree->quals =
1270 make_and_qual(subquery->jointree->quals, qual);
1273 * We need not change the subquery's hasAggs or hasSublinks flags,
1274 * since we can't be pushing down any aggregates that weren't there
1275 * before, and we don't push down subselects at all.
1281 * Helper routine to recurse through setOperations tree
1284 recurse_push_qual(Node *setOp, Query *topquery,
1285 RangeTblEntry *rte, Index rti, Node *qual)
1287 if (IsA(setOp, RangeTblRef))
1289 RangeTblRef *rtr = (RangeTblRef *) setOp;
1290 RangeTblEntry *subrte = rt_fetch(rtr->rtindex, topquery->rtable);
1291 Query *subquery = subrte->subquery;
1293 Assert(subquery != NULL);
1294 subquery_push_qual(subquery, rte, rti, qual);
1296 else if (IsA(setOp, SetOperationStmt))
1298 SetOperationStmt *op = (SetOperationStmt *) setOp;
1300 recurse_push_qual(op->larg, topquery, rte, rti, qual);
1301 recurse_push_qual(op->rarg, topquery, rte, rti, qual);
1305 elog(ERROR, "unrecognized node type: %d",
1306 (int) nodeTag(setOp));
1310 /*****************************************************************************
1312 *****************************************************************************/
1314 #ifdef OPTIMIZER_DEBUG
1317 print_relids(Relids relids)
1323 tmprelids = bms_copy(relids);
1324 while ((x = bms_first_member(tmprelids)) >= 0)
1331 bms_free(tmprelids);
1335 print_restrictclauses(PlannerInfo *root, List *clauses)
1341 RestrictInfo *c = lfirst(l);
1343 print_expr((Node *) c->clause, root->parse->rtable);
1350 print_path(PlannerInfo *root, Path *path, int indent)
1354 Path *subpath = NULL;
1357 switch (nodeTag(path))
1365 case T_BitmapHeapPath:
1366 ptype = "BitmapHeapScan";
1368 case T_BitmapAndPath:
1369 ptype = "BitmapAndPath";
1371 case T_BitmapOrPath:
1372 ptype = "BitmapOrPath";
1383 case T_MaterialPath:
1385 subpath = ((MaterialPath *) path)->subpath;
1389 subpath = ((UniquePath *) path)->subpath;
1393 subpath = ((NoOpPath *) path)->subpath;
1400 ptype = "MergeJoin";
1412 for (i = 0; i < indent; i++)
1414 printf("%s", ptype);
1419 print_relids(path->parent->relids);
1420 printf(") rows=%.0f", path->parent->rows);
1422 printf(" cost=%.2f..%.2f\n", path->startup_cost, path->total_cost);
1426 for (i = 0; i < indent; i++)
1428 printf(" pathkeys: ");
1429 print_pathkeys(path->pathkeys, root->parse->rtable);
1434 JoinPath *jp = (JoinPath *) path;
1436 for (i = 0; i < indent; i++)
1438 printf(" clauses: ");
1439 print_restrictclauses(root, jp->joinrestrictinfo);
1442 if (IsA(path, MergePath))
1444 MergePath *mp = (MergePath *) path;
1446 for (i = 0; i < indent; i++)
1448 printf(" sortouter=%d sortinner=%d materializeinner=%d\n",
1449 ((mp->outersortkeys) ? 1 : 0),
1450 ((mp->innersortkeys) ? 1 : 0),
1451 ((mp->materialize_inner) ? 1 : 0));
1455 print_path(root, jp->outerjoinpath, indent + 1);
1456 print_path(root, jp->innerjoinpath, indent + 1);
1460 print_path(root, subpath, indent + 1);
1464 debug_print_rel(PlannerInfo *root, RelOptInfo *rel)
1468 printf("RELOPTINFO (");
1469 print_relids(rel->relids);
1470 printf("): rows=%.0f width=%d\n", rel->rows, rel->width);
1472 if (rel->baserestrictinfo)
1474 printf("\tbaserestrictinfo: ");
1475 print_restrictclauses(root, rel->baserestrictinfo);
1481 printf("\tjoininfo: ");
1482 print_restrictclauses(root, rel->joininfo);
1486 printf("\tpath list:\n");
1487 foreach(l, rel->pathlist)
1488 print_path(root, lfirst(l), 1);
1489 printf("\n\tcheapest startup path:\n");
1490 print_path(root, rel->cheapest_startup_path, 1);
1491 printf("\n\tcheapest total path:\n");
1492 print_path(root, rel->cheapest_total_path, 1);
1497 #endif /* OPTIMIZER_DEBUG */