1 /*-------------------------------------------------------------------------
4 * Routines to find possible search paths for processing a query
6 * Portions Copyright (c) 1996-2008, 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.171 2008/06/27 03:56:55 tgl Exp $
13 *-------------------------------------------------------------------------
20 #ifdef OPTIMIZER_DEBUG
21 #include "nodes/print.h"
23 #include "optimizer/clauses.h"
24 #include "optimizer/cost.h"
25 #include "optimizer/geqo.h"
26 #include "optimizer/pathnode.h"
27 #include "optimizer/paths.h"
28 #include "optimizer/plancat.h"
29 #include "optimizer/planner.h"
30 #include "optimizer/prep.h"
31 #include "optimizer/var.h"
32 #include "parser/parse_clause.h"
33 #include "parser/parse_expr.h"
34 #include "parser/parsetree.h"
35 #include "rewrite/rewriteManip.h"
38 /* These parameters are set by GUC */
39 bool enable_geqo = false; /* just in case GUC doesn't set it */
42 /* Hook for plugins to replace standard_join_search() */
43 join_search_hook_type join_search_hook = NULL;
46 static void set_base_rel_pathlists(PlannerInfo *root);
47 static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
48 Index rti, RangeTblEntry *rte);
49 static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
51 static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
52 Index rti, RangeTblEntry *rte);
53 static void set_dummy_rel_pathlist(RelOptInfo *rel);
54 static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
55 Index rti, RangeTblEntry *rte);
56 static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel,
58 static void set_values_pathlist(PlannerInfo *root, RelOptInfo *rel,
60 static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist);
61 static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery,
62 bool *differentTypes);
63 static bool recurse_pushdown_safe(Node *setOp, Query *topquery,
64 bool *differentTypes);
65 static void compare_tlist_datatypes(List *tlist, List *colTypes,
66 bool *differentTypes);
67 static bool qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
68 bool *differentTypes);
69 static void subquery_push_qual(Query *subquery,
70 RangeTblEntry *rte, Index rti, Node *qual);
71 static void recurse_push_qual(Node *setOp, Query *topquery,
72 RangeTblEntry *rte, Index rti, Node *qual);
77 * Finds all possible access paths for executing a query, returning a
78 * single rel that represents the join of all base rels in the query.
81 make_one_rel(PlannerInfo *root, List *joinlist)
86 * Generate access paths for the base rels.
88 set_base_rel_pathlists(root);
91 * Generate access paths for the entire join tree.
93 rel = make_rel_from_joinlist(root, joinlist);
96 * The result should join all and only the query's base rels.
98 #ifdef USE_ASSERT_CHECKING
100 int num_base_rels = 0;
103 for (rti = 1; rti < root->simple_rel_array_size; rti++)
105 RelOptInfo *brel = root->simple_rel_array[rti];
110 Assert(brel->relid == rti); /* sanity check on array */
112 /* ignore RTEs that are "other rels" */
113 if (brel->reloptkind != RELOPT_BASEREL)
116 Assert(bms_is_member(rti, rel->relids));
120 Assert(bms_num_members(rel->relids) == num_base_rels);
128 * set_base_rel_pathlists
129 * Finds all paths available for scanning each base-relation entry.
130 * Sequential scan and any available indices are considered.
131 * Each useful path is attached to its relation's 'pathlist' field.
134 set_base_rel_pathlists(PlannerInfo *root)
138 for (rti = 1; rti < root->simple_rel_array_size; rti++)
140 RelOptInfo *rel = root->simple_rel_array[rti];
142 /* there may be empty slots corresponding to non-baserel RTEs */
146 Assert(rel->relid == rti); /* sanity check on array */
148 /* ignore RTEs that are "other rels" */
149 if (rel->reloptkind != RELOPT_BASEREL)
152 set_rel_pathlist(root, rel, rti, root->simple_rte_array[rti]);
158 * Build access paths for a base relation
161 set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
162 Index rti, RangeTblEntry *rte)
166 /* It's an "append relation", process accordingly */
167 set_append_rel_pathlist(root, rel, rti, rte);
169 else if (rel->rtekind == RTE_SUBQUERY)
171 /* Subquery --- generate a separate plan for it */
172 set_subquery_pathlist(root, rel, rti, rte);
174 else if (rel->rtekind == RTE_FUNCTION)
176 /* RangeFunction --- generate a separate plan for it */
177 set_function_pathlist(root, rel, rte);
179 else if (rel->rtekind == RTE_VALUES)
181 /* Values list --- generate a separate plan for it */
182 set_values_pathlist(root, rel, rte);
187 Assert(rel->rtekind == RTE_RELATION);
188 set_plain_rel_pathlist(root, rel, rte);
191 #ifdef OPTIMIZER_DEBUG
192 debug_print_rel(root, rel);
197 * set_plain_rel_pathlist
198 * Build access paths for a plain relation (no subquery, no inheritance)
201 set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
204 * If we can prove we don't need to scan the rel via constraint exclusion,
205 * set up a single dummy path for it. We only need to check for regular
206 * baserels; if it's an otherrel, CE was already checked in
207 * set_append_rel_pathlist().
209 if (rel->reloptkind == RELOPT_BASEREL &&
210 relation_excluded_by_constraints(root, rel, rte))
212 set_dummy_rel_pathlist(rel);
216 /* Mark rel with estimated output rows, width, etc */
217 set_baserel_size_estimates(root, rel);
219 /* Test any partial indexes of rel for applicability */
220 check_partial_indexes(root, rel);
223 * Check to see if we can extract any restriction conditions from join
224 * quals that are OR-of-AND structures. If so, add them to the rel's
225 * restriction list, and recompute the size estimates.
227 if (create_or_index_quals(root, rel))
228 set_baserel_size_estimates(root, rel);
231 * Generate paths and add them to the rel's pathlist.
233 * Note: add_path() will discard any paths that are dominated by another
234 * available path, keeping only those paths that are superior along at
235 * least one dimension of cost or sortedness.
238 /* Consider sequential scan */
239 add_path(rel, create_seqscan_path(root, rel));
241 /* Consider index scans */
242 create_index_paths(root, rel);
244 /* Consider TID scans */
245 create_tidscan_paths(root, rel);
247 /* Now find the cheapest of the paths for this rel */
252 * set_append_rel_pathlist
253 * Build access paths for an "append relation"
255 * The passed-in rel and RTE represent the entire append relation. The
256 * relation's contents are computed by appending together the output of
257 * the individual member relations. Note that in the inheritance case,
258 * the first member relation is actually the same table as is mentioned in
259 * the parent RTE ... but it has a different RTE and RelOptInfo. This is
260 * a good thing because their outputs are not the same size.
263 set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
264 Index rti, RangeTblEntry *rte)
266 int parentRTindex = rti;
267 List *subpaths = NIL;
270 double *parent_attrsizes;
275 * XXX for now, can't handle inherited expansion of FOR UPDATE/SHARE; can
276 * we do better? (This will take some redesign because the executor
277 * currently supposes that every rowMark relation is involved in every row
278 * returned by the query.)
280 if (get_rowmark(root->parse, parentRTindex))
282 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
283 errmsg("SELECT FOR UPDATE/SHARE is not supported for inheritance queries")));
286 * Initialize to compute size estimates for whole append relation.
288 * We handle width estimates by weighting the widths of different
289 * child rels proportionally to their number of rows. This is sensible
290 * because the use of width estimates is mainly to compute the total
291 * relation "footprint" if we have to sort or hash it. To do this,
292 * we sum the total equivalent size (in "double" arithmetic) and then
293 * divide by the total rowcount estimate. This is done separately for
294 * the total rel width and each attribute.
296 * Note: if you consider changing this logic, beware that child rels could
297 * have zero rows and/or width, if they were excluded by constraints.
301 nattrs = rel->max_attr - rel->min_attr + 1;
302 parent_attrsizes = (double *) palloc0(nattrs * sizeof(double));
305 * Generate access paths for each member relation, and pick the cheapest
308 foreach(l, root->append_rel_list)
310 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
312 RangeTblEntry *childRTE;
313 RelOptInfo *childrel;
315 ListCell *parentvars;
318 /* append_rel_list contains all append rels; ignore others */
319 if (appinfo->parent_relid != parentRTindex)
322 childRTindex = appinfo->child_relid;
323 childRTE = root->simple_rte_array[childRTindex];
326 * The child rel's RelOptInfo was already created during
327 * add_base_rels_to_query.
329 childrel = find_base_rel(root, childRTindex);
330 Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
333 * We have to copy the parent's targetlist and quals to the child,
334 * with appropriate substitution of variables. However, only the
335 * baserestrictinfo quals are needed before we can check for
336 * constraint exclusion; so do that first and then check to see if we
337 * can disregard this child.
339 childrel->baserestrictinfo = (List *)
340 adjust_appendrel_attrs((Node *) rel->baserestrictinfo,
343 if (relation_excluded_by_constraints(root, childrel, childRTE))
346 * This child need not be scanned, so we can omit it from the
347 * appendrel. Mark it with a dummy cheapest-path though, in case
348 * best_appendrel_indexscan() looks at it later.
350 set_dummy_rel_pathlist(childrel);
354 /* CE failed, so finish copying targetlist and join quals */
355 childrel->joininfo = (List *)
356 adjust_appendrel_attrs((Node *) rel->joininfo,
358 childrel->reltargetlist = (List *)
359 adjust_appendrel_attrs((Node *) rel->reltargetlist,
363 * We have to make child entries in the EquivalenceClass data
364 * structures as well.
366 if (rel->has_eclass_joins)
368 add_child_rel_equivalences(root, appinfo, rel, childrel);
369 childrel->has_eclass_joins = true;
373 * Copy the parent's attr_needed data as well, with appropriate
374 * adjustment of relids and attribute numbers.
376 pfree(childrel->attr_needed);
377 childrel->attr_needed =
378 adjust_appendrel_attr_needed(rel, appinfo,
383 * Compute the child's access paths, and add the cheapest one to the
384 * Append path we are constructing for the parent.
386 * It's possible that the child is itself an appendrel, in which case
387 * we can "cut out the middleman" and just add its child paths to our
388 * own list. (We don't try to do this earlier because we need to
389 * apply both levels of transformation to the quals.)
391 set_rel_pathlist(root, childrel, childRTindex, childRTE);
393 childpath = childrel->cheapest_total_path;
394 if (IsA(childpath, AppendPath))
395 subpaths = list_concat(subpaths,
396 ((AppendPath *) childpath)->subpaths);
398 subpaths = lappend(subpaths, childpath);
401 * Accumulate size information from each child.
403 if (childrel->rows > 0)
405 parent_rows += childrel->rows;
406 parent_size += childrel->width * childrel->rows;
408 forboth(parentvars, rel->reltargetlist,
409 childvars, childrel->reltargetlist)
411 Var *parentvar = (Var *) lfirst(parentvars);
412 Var *childvar = (Var *) lfirst(childvars);
414 if (IsA(parentvar, Var) &&
417 int pndx = parentvar->varattno - rel->min_attr;
418 int cndx = childvar->varattno - childrel->min_attr;
420 parent_attrsizes[pndx] += childrel->attr_widths[cndx] * childrel->rows;
427 * Save the finished size estimates.
429 rel->rows = parent_rows;
434 rel->width = rint(parent_size / parent_rows);
435 for (i = 0; i < nattrs; i++)
436 rel->attr_widths[i] = rint(parent_attrsizes[i] / parent_rows);
439 rel->width = 0; /* attr_widths should be zero already */
442 * Set "raw tuples" count equal to "rows" for the appendrel; needed
443 * because some places assume rel->tuples is valid for any baserel.
445 rel->tuples = parent_rows;
447 pfree(parent_attrsizes);
450 * Finally, build Append path and install it as the only access path for
451 * the parent rel. (Note: this is correct even if we have zero or one
452 * live subpath due to constraint exclusion.)
454 add_path(rel, (Path *) create_append_path(rel, subpaths));
456 /* Select cheapest path (pretty easy in this case...) */
461 * set_dummy_rel_pathlist
462 * Build a dummy path for a relation that's been excluded by constraints
464 * Rather than inventing a special "dummy" path type, we represent this as an
465 * AppendPath with no members (see also IS_DUMMY_PATH macro).
468 set_dummy_rel_pathlist(RelOptInfo *rel)
470 /* Set dummy size estimates --- we leave attr_widths[] as zeroes */
474 add_path(rel, (Path *) create_append_path(rel, NIL));
476 /* Select cheapest path (pretty easy in this case...) */
480 /* quick-and-dirty test to see if any joining is needed */
482 has_multiple_baserels(PlannerInfo *root)
484 int num_base_rels = 0;
487 for (rti = 1; rti < root->simple_rel_array_size; rti++)
489 RelOptInfo *brel = root->simple_rel_array[rti];
494 /* ignore RTEs that are "other rels" */
495 if (brel->reloptkind == RELOPT_BASEREL)
496 if (++num_base_rels > 1)
503 * set_subquery_pathlist
504 * Build the (single) access path for a subquery RTE
507 set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
508 Index rti, RangeTblEntry *rte)
510 Query *parse = root->parse;
511 Query *subquery = rte->subquery;
512 bool *differentTypes;
513 double tuple_fraction;
514 PlannerInfo *subroot;
517 /* We need a workspace for keeping track of set-op type coercions */
518 differentTypes = (bool *)
519 palloc0((list_length(subquery->targetList) + 1) * sizeof(bool));
522 * If there are any restriction clauses that have been attached to the
523 * subquery relation, consider pushing them down to become WHERE or HAVING
524 * quals of the subquery itself. This transformation is useful because it
525 * may allow us to generate a better plan for the subquery than evaluating
526 * all the subquery output rows and then filtering them.
528 * There are several cases where we cannot push down clauses. Restrictions
529 * involving the subquery are checked by subquery_is_pushdown_safe().
530 * Restrictions on individual clauses are checked by
531 * qual_is_pushdown_safe(). Also, we don't want to push down
532 * pseudoconstant clauses; better to have the gating node above the
535 * Non-pushed-down clauses will get evaluated as qpquals of the
538 * XXX Are there any cases where we want to make a policy decision not to
539 * push down a pushable qual, because it'd result in a worse plan?
541 if (rel->baserestrictinfo != NIL &&
542 subquery_is_pushdown_safe(subquery, subquery, differentTypes))
544 /* OK to consider pushing down individual quals */
545 List *upperrestrictlist = NIL;
548 foreach(l, rel->baserestrictinfo)
550 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
551 Node *clause = (Node *) rinfo->clause;
553 if (!rinfo->pseudoconstant &&
554 qual_is_pushdown_safe(subquery, rti, clause, differentTypes))
557 subquery_push_qual(subquery, rte, rti, clause);
561 /* Keep it in the upper query */
562 upperrestrictlist = lappend(upperrestrictlist, rinfo);
565 rel->baserestrictinfo = upperrestrictlist;
568 pfree(differentTypes);
571 * We can safely pass the outer tuple_fraction down to the subquery if the
572 * outer level has no joining, aggregation, or sorting to do. Otherwise
573 * we'd better tell the subquery to plan for full retrieval. (XXX This
574 * could probably be made more intelligent ...)
576 if (parse->hasAggs ||
577 parse->groupClause ||
579 parse->distinctClause ||
581 has_multiple_baserels(root))
582 tuple_fraction = 0.0; /* default case */
584 tuple_fraction = root->tuple_fraction;
586 /* Generate the plan for the subquery */
587 rel->subplan = subquery_planner(root->glob, subquery,
588 root->query_level + 1,
591 rel->subrtable = subroot->parse->rtable;
593 /* Copy number of output rows from subplan */
594 rel->tuples = rel->subplan->plan_rows;
596 /* Mark rel with estimated output rows, width, etc */
597 set_baserel_size_estimates(root, rel);
599 /* Convert subquery pathkeys to outer representation */
600 pathkeys = convert_subquery_pathkeys(root, rel, subroot->query_pathkeys);
602 /* Generate appropriate path */
603 add_path(rel, create_subqueryscan_path(rel, pathkeys));
605 /* Select cheapest path (pretty easy in this case...) */
610 * set_function_pathlist
611 * Build the (single) access path for a function RTE
614 set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
616 /* Mark rel with estimated output rows, width, etc */
617 set_function_size_estimates(root, rel);
619 /* Generate appropriate path */
620 add_path(rel, create_functionscan_path(root, rel));
622 /* Select cheapest path (pretty easy in this case...) */
627 * set_values_pathlist
628 * Build the (single) access path for a VALUES RTE
631 set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
633 /* Mark rel with estimated output rows, width, etc */
634 set_values_size_estimates(root, rel);
636 /* Generate appropriate path */
637 add_path(rel, create_valuesscan_path(root, rel));
639 /* Select cheapest path (pretty easy in this case...) */
644 * make_rel_from_joinlist
645 * Build access paths using a "joinlist" to guide the join path search.
647 * See comments for deconstruct_jointree() for definition of the joinlist
651 make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
658 * Count the number of child joinlist nodes. This is the depth of the
659 * dynamic-programming algorithm we must employ to consider all ways of
660 * joining the child nodes.
662 levels_needed = list_length(joinlist);
664 if (levels_needed <= 0)
665 return NULL; /* nothing to do? */
668 * Construct a list of rels corresponding to the child joinlist nodes.
669 * This may contain both base rels and rels constructed according to
673 foreach(jl, joinlist)
675 Node *jlnode = (Node *) lfirst(jl);
678 if (IsA(jlnode, RangeTblRef))
680 int varno = ((RangeTblRef *) jlnode)->rtindex;
682 thisrel = find_base_rel(root, varno);
684 else if (IsA(jlnode, List))
686 /* Recurse to handle subproblem */
687 thisrel = make_rel_from_joinlist(root, (List *) jlnode);
691 elog(ERROR, "unrecognized joinlist node type: %d",
692 (int) nodeTag(jlnode));
693 thisrel = NULL; /* keep compiler quiet */
696 initial_rels = lappend(initial_rels, thisrel);
699 if (levels_needed == 1)
702 * Single joinlist node, so we're done.
704 return (RelOptInfo *) linitial(initial_rels);
709 * Consider the different orders in which we could join the rels,
710 * using a plugin, GEQO, or the regular join search code.
712 * We put the initial_rels list into a PlannerInfo field because
713 * has_legal_joinclause() needs to look at it (ugly :-().
715 root->initial_rels = initial_rels;
717 if (join_search_hook)
718 return (*join_search_hook) (root, levels_needed, initial_rels);
719 else if (enable_geqo && levels_needed >= geqo_threshold)
720 return geqo(root, levels_needed, initial_rels);
722 return standard_join_search(root, levels_needed, initial_rels);
727 * standard_join_search
728 * Find possible joinpaths for a query by successively finding ways
729 * to join component relations into join relations.
731 * 'levels_needed' is the number of iterations needed, ie, the number of
732 * independent jointree items in the query. This is > 1.
734 * 'initial_rels' is a list of RelOptInfo nodes for each independent
735 * jointree item. These are the components to be joined together.
736 * Note that levels_needed == list_length(initial_rels).
738 * Returns the final level of join relations, i.e., the relation that is
739 * the result of joining all the original relations together.
740 * At least one implementation path must be provided for this relation and
741 * all required sub-relations.
743 * To support loadable plugins that modify planner behavior by changing the
744 * join searching algorithm, we provide a hook variable that lets a plugin
745 * replace or supplement this function. Any such hook must return the same
746 * final join relation as the standard code would, but it might have a
747 * different set of implementation paths attached, and only the sub-joinrels
748 * needed for these paths need have been instantiated.
750 * Note to plugin authors: the functions invoked during standard_join_search()
751 * modify root->join_rel_list and root->join_rel_hash. If you want to do more
752 * than one join-order search, you'll probably need to save and restore the
753 * original states of those data structures. See geqo_eval() for an example.
756 standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels)
763 * We employ a simple "dynamic programming" algorithm: we first find all
764 * ways to build joins of two jointree items, then all ways to build joins
765 * of three items (from two-item joins and single items), then four-item
766 * joins, and so on until we have considered all ways to join all the
767 * items into one rel.
769 * joinitems[j] is a list of all the j-item rels. Initially we set
770 * joinitems[1] to represent all the single-jointree-item relations.
772 joinitems = (List **) palloc0((levels_needed + 1) * sizeof(List *));
774 joinitems[1] = initial_rels;
776 for (lev = 2; lev <= levels_needed; lev++)
781 * Determine all possible pairs of relations to be joined at this
782 * level, and build paths for making each one from every available
783 * pair of lower-level relations.
785 joinitems[lev] = join_search_one_level(root, lev, joinitems);
788 * Do cleanup work on each just-processed rel.
790 foreach(x, joinitems[lev])
792 rel = (RelOptInfo *) lfirst(x);
794 /* Find and save the cheapest paths for this rel */
797 #ifdef OPTIMIZER_DEBUG
798 debug_print_rel(root, rel);
804 * We should have a single rel at the final level.
806 if (joinitems[levels_needed] == NIL)
807 elog(ERROR, "failed to build any %d-way joins", levels_needed);
808 Assert(list_length(joinitems[levels_needed]) == 1);
810 rel = (RelOptInfo *) linitial(joinitems[levels_needed]);
815 /*****************************************************************************
816 * PUSHING QUALS DOWN INTO SUBQUERIES
817 *****************************************************************************/
820 * subquery_is_pushdown_safe - is a subquery safe for pushing down quals?
822 * subquery is the particular component query being checked. topquery
823 * is the top component of a set-operations tree (the same Query if no
824 * set-op is involved).
826 * Conditions checked here:
828 * 1. If the subquery has a LIMIT clause, we must not push down any quals,
829 * since that could change the set of rows returned.
831 * 2. If the subquery contains EXCEPT or EXCEPT ALL set ops we cannot push
832 * quals into it, because that would change the results.
834 * 3. For subqueries using UNION/UNION ALL/INTERSECT/INTERSECT ALL, we can
835 * push quals into each component query, but the quals can only reference
836 * subquery columns that suffer no type coercions in the set operation.
837 * Otherwise there are possible semantic gotchas. So, we check the
838 * component queries to see if any of them have different output types;
839 * differentTypes[k] is set true if column k has different type in any
843 subquery_is_pushdown_safe(Query *subquery, Query *topquery,
844 bool *differentTypes)
846 SetOperationStmt *topop;
849 if (subquery->limitOffset != NULL || subquery->limitCount != NULL)
852 /* Are we at top level, or looking at a setop component? */
853 if (subquery == topquery)
855 /* Top level, so check any component queries */
856 if (subquery->setOperations != NULL)
857 if (!recurse_pushdown_safe(subquery->setOperations, topquery,
863 /* Setop component must not have more components (too weird) */
864 if (subquery->setOperations != NULL)
866 /* Check whether setop component output types match top level */
867 topop = (SetOperationStmt *) topquery->setOperations;
868 Assert(topop && IsA(topop, SetOperationStmt));
869 compare_tlist_datatypes(subquery->targetList,
877 * Helper routine to recurse through setOperations tree
880 recurse_pushdown_safe(Node *setOp, Query *topquery,
881 bool *differentTypes)
883 if (IsA(setOp, RangeTblRef))
885 RangeTblRef *rtr = (RangeTblRef *) setOp;
886 RangeTblEntry *rte = rt_fetch(rtr->rtindex, topquery->rtable);
887 Query *subquery = rte->subquery;
889 Assert(subquery != NULL);
890 return subquery_is_pushdown_safe(subquery, topquery, differentTypes);
892 else if (IsA(setOp, SetOperationStmt))
894 SetOperationStmt *op = (SetOperationStmt *) setOp;
896 /* EXCEPT is no good */
897 if (op->op == SETOP_EXCEPT)
900 if (!recurse_pushdown_safe(op->larg, topquery, differentTypes))
902 if (!recurse_pushdown_safe(op->rarg, topquery, differentTypes))
907 elog(ERROR, "unrecognized node type: %d",
908 (int) nodeTag(setOp));
914 * Compare tlist's datatypes against the list of set-operation result types.
915 * For any items that are different, mark the appropriate element of
916 * differentTypes[] to show that this column will have type conversions.
918 * We don't have to care about typmods here: the only allowed difference
919 * between set-op input and output typmods is input is a specific typmod
920 * and output is -1, and that does not require a coercion.
923 compare_tlist_datatypes(List *tlist, List *colTypes,
924 bool *differentTypes)
927 ListCell *colType = list_head(colTypes);
931 TargetEntry *tle = (TargetEntry *) lfirst(l);
934 continue; /* ignore resjunk columns */
936 elog(ERROR, "wrong number of tlist entries");
937 if (exprType((Node *) tle->expr) != lfirst_oid(colType))
938 differentTypes[tle->resno] = true;
939 colType = lnext(colType);
942 elog(ERROR, "wrong number of tlist entries");
946 * qual_is_pushdown_safe - is a particular qual safe to push down?
948 * qual is a restriction clause applying to the given subquery (whose RTE
949 * has index rti in the parent query).
951 * Conditions checked here:
953 * 1. The qual must not contain any subselects (mainly because I'm not sure
954 * it will work correctly: sublinks will already have been transformed into
955 * subplans in the qual, but not in the subquery).
957 * 2. The qual must not refer to the whole-row output of the subquery
958 * (since there is no easy way to name that within the subquery itself).
960 * 3. The qual must not refer to any subquery output columns that were
961 * found to have inconsistent types across a set operation tree by
962 * subquery_is_pushdown_safe().
964 * 4. If the subquery uses DISTINCT ON, we must not push down any quals that
965 * refer to non-DISTINCT output columns, because that could change the set
966 * of rows returned. This condition is vacuous for DISTINCT, because then
967 * there are no non-DISTINCT output columns, but unfortunately it's fairly
968 * expensive to tell the difference between DISTINCT and DISTINCT ON in the
969 * parsetree representation. It's cheaper to just make sure all the Vars
970 * in the qual refer to DISTINCT columns.
972 * 5. We must not push down any quals that refer to subselect outputs that
973 * return sets, else we'd introduce functions-returning-sets into the
974 * subquery's WHERE/HAVING quals.
976 * 6. We must not push down any quals that refer to subselect outputs that
977 * contain volatile functions, for fear of introducing strange results due
978 * to multiple evaluation of a volatile function.
981 qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
982 bool *differentTypes)
987 Bitmapset *tested = NULL;
989 /* Refuse subselects (point 1) */
990 if (contain_subplans(qual))
994 * Examine all Vars used in clause; since it's a restriction clause, all
995 * such Vars must refer to subselect output columns.
997 vars = pull_var_clause(qual, false);
1000 Var *var = (Var *) lfirst(vl);
1003 Assert(var->varno == rti);
1006 if (var->varattno == 0)
1013 * We use a bitmapset to avoid testing the same attno more than once.
1014 * (NB: this only works because subquery outputs can't have negative
1017 if (bms_is_member(var->varattno, tested))
1019 tested = bms_add_member(tested, var->varattno);
1022 if (differentTypes[var->varattno])
1028 /* Must find the tlist element referenced by the Var */
1029 tle = get_tle_by_resno(subquery->targetList, var->varattno);
1030 Assert(tle != NULL);
1031 Assert(!tle->resjunk);
1033 /* If subquery uses DISTINCT or DISTINCT ON, check point 4 */
1034 if (subquery->distinctClause != NIL &&
1035 !targetIsInSortList(tle, InvalidOid, subquery->distinctClause))
1037 /* non-DISTINCT column, so fail */
1042 /* Refuse functions returning sets (point 5) */
1043 if (expression_returns_set((Node *) tle->expr))
1049 /* Refuse volatile functions (point 6) */
1050 if (contain_volatile_functions((Node *) tle->expr))
1064 * subquery_push_qual - push down a qual that we have determined is safe
1067 subquery_push_qual(Query *subquery, RangeTblEntry *rte, Index rti, Node *qual)
1069 if (subquery->setOperations != NULL)
1071 /* Recurse to push it separately to each component query */
1072 recurse_push_qual(subquery->setOperations, subquery,
1078 * We need to replace Vars in the qual (which must refer to outputs of
1079 * the subquery) with copies of the subquery's targetlist expressions.
1080 * Note that at this point, any uplevel Vars in the qual should have
1081 * been replaced with Params, so they need no work.
1083 * This step also ensures that when we are pushing into a setop tree,
1084 * each component query gets its own copy of the qual.
1086 qual = ResolveNew(qual, rti, 0, rte,
1087 subquery->targetList,
1091 * Now attach the qual to the proper place: normally WHERE, but if the
1092 * subquery uses grouping or aggregation, put it in HAVING (since the
1093 * qual really refers to the group-result rows).
1095 if (subquery->hasAggs || subquery->groupClause || subquery->havingQual)
1096 subquery->havingQual = make_and_qual(subquery->havingQual, qual);
1098 subquery->jointree->quals =
1099 make_and_qual(subquery->jointree->quals, qual);
1102 * We need not change the subquery's hasAggs or hasSublinks flags,
1103 * since we can't be pushing down any aggregates that weren't there
1104 * before, and we don't push down subselects at all.
1110 * Helper routine to recurse through setOperations tree
1113 recurse_push_qual(Node *setOp, Query *topquery,
1114 RangeTblEntry *rte, Index rti, Node *qual)
1116 if (IsA(setOp, RangeTblRef))
1118 RangeTblRef *rtr = (RangeTblRef *) setOp;
1119 RangeTblEntry *subrte = rt_fetch(rtr->rtindex, topquery->rtable);
1120 Query *subquery = subrte->subquery;
1122 Assert(subquery != NULL);
1123 subquery_push_qual(subquery, rte, rti, qual);
1125 else if (IsA(setOp, SetOperationStmt))
1127 SetOperationStmt *op = (SetOperationStmt *) setOp;
1129 recurse_push_qual(op->larg, topquery, rte, rti, qual);
1130 recurse_push_qual(op->rarg, topquery, rte, rti, qual);
1134 elog(ERROR, "unrecognized node type: %d",
1135 (int) nodeTag(setOp));
1139 /*****************************************************************************
1141 *****************************************************************************/
1143 #ifdef OPTIMIZER_DEBUG
1146 print_relids(Relids relids)
1152 tmprelids = bms_copy(relids);
1153 while ((x = bms_first_member(tmprelids)) >= 0)
1160 bms_free(tmprelids);
1164 print_restrictclauses(PlannerInfo *root, List *clauses)
1170 RestrictInfo *c = lfirst(l);
1172 print_expr((Node *) c->clause, root->parse->rtable);
1179 print_path(PlannerInfo *root, Path *path, int indent)
1183 Path *subpath = NULL;
1186 switch (nodeTag(path))
1194 case T_BitmapHeapPath:
1195 ptype = "BitmapHeapScan";
1197 case T_BitmapAndPath:
1198 ptype = "BitmapAndPath";
1200 case T_BitmapOrPath:
1201 ptype = "BitmapOrPath";
1212 case T_MaterialPath:
1214 subpath = ((MaterialPath *) path)->subpath;
1218 subpath = ((UniquePath *) path)->subpath;
1225 ptype = "MergeJoin";
1237 for (i = 0; i < indent; i++)
1239 printf("%s", ptype);
1244 print_relids(path->parent->relids);
1245 printf(") rows=%.0f", path->parent->rows);
1247 printf(" cost=%.2f..%.2f\n", path->startup_cost, path->total_cost);
1251 for (i = 0; i < indent; i++)
1253 printf(" pathkeys: ");
1254 print_pathkeys(path->pathkeys, root->parse->rtable);
1259 JoinPath *jp = (JoinPath *) path;
1261 for (i = 0; i < indent; i++)
1263 printf(" clauses: ");
1264 print_restrictclauses(root, jp->joinrestrictinfo);
1267 if (IsA(path, MergePath))
1269 MergePath *mp = (MergePath *) path;
1271 if (mp->outersortkeys || mp->innersortkeys)
1273 for (i = 0; i < indent; i++)
1275 printf(" sortouter=%d sortinner=%d\n",
1276 ((mp->outersortkeys) ? 1 : 0),
1277 ((mp->innersortkeys) ? 1 : 0));
1281 print_path(root, jp->outerjoinpath, indent + 1);
1282 print_path(root, jp->innerjoinpath, indent + 1);
1286 print_path(root, subpath, indent + 1);
1290 debug_print_rel(PlannerInfo *root, RelOptInfo *rel)
1294 printf("RELOPTINFO (");
1295 print_relids(rel->relids);
1296 printf("): rows=%.0f width=%d\n", rel->rows, rel->width);
1298 if (rel->baserestrictinfo)
1300 printf("\tbaserestrictinfo: ");
1301 print_restrictclauses(root, rel->baserestrictinfo);
1307 printf("\tjoininfo: ");
1308 print_restrictclauses(root, rel->joininfo);
1312 printf("\tpath list:\n");
1313 foreach(l, rel->pathlist)
1314 print_path(root, lfirst(l), 1);
1315 printf("\n\tcheapest startup path:\n");
1316 print_path(root, rel->cheapest_startup_path, 1);
1317 printf("\n\tcheapest total path:\n");
1318 print_path(root, rel->cheapest_total_path, 1);
1323 #endif /* OPTIMIZER_DEBUG */