1 /*-------------------------------------------------------------------------
4 * Routines to find possible search paths for processing a query
6 * Portions Copyright (c) 1996-2007, 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.164 2007/05/26 18:23:01 tgl Exp $
13 *-------------------------------------------------------------------------
18 #ifdef OPTIMIZER_DEBUG
19 #include "nodes/print.h"
21 #include "optimizer/clauses.h"
22 #include "optimizer/cost.h"
23 #include "optimizer/geqo.h"
24 #include "optimizer/pathnode.h"
25 #include "optimizer/paths.h"
26 #include "optimizer/plancat.h"
27 #include "optimizer/planner.h"
28 #include "optimizer/prep.h"
29 #include "optimizer/var.h"
30 #include "parser/parse_clause.h"
31 #include "parser/parse_expr.h"
32 #include "parser/parsetree.h"
33 #include "rewrite/rewriteManip.h"
36 /* These parameters are set by GUC */
37 bool enable_geqo = false; /* just in case GUC doesn't set it */
41 static void set_base_rel_pathlists(PlannerInfo *root);
42 static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
43 Index rti, RangeTblEntry *rte);
44 static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
46 static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
47 Index rti, RangeTblEntry *rte);
48 static void set_dummy_rel_pathlist(RelOptInfo *rel);
49 static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
50 Index rti, RangeTblEntry *rte);
51 static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel,
53 static void set_values_pathlist(PlannerInfo *root, RelOptInfo *rel,
55 static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist);
56 static RelOptInfo *make_one_rel_by_joins(PlannerInfo *root, int levels_needed,
58 static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery,
59 bool *differentTypes);
60 static bool recurse_pushdown_safe(Node *setOp, Query *topquery,
61 bool *differentTypes);
62 static void compare_tlist_datatypes(List *tlist, List *colTypes,
63 bool *differentTypes);
64 static bool qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
65 bool *differentTypes);
66 static void subquery_push_qual(Query *subquery,
67 RangeTblEntry *rte, Index rti, Node *qual);
68 static void recurse_push_qual(Node *setOp, Query *topquery,
69 RangeTblEntry *rte, Index rti, Node *qual);
74 * Finds all possible access paths for executing a query, returning a
75 * single rel that represents the join of all base rels in the query.
78 make_one_rel(PlannerInfo *root, List *joinlist)
83 * Generate access paths for the base rels.
85 set_base_rel_pathlists(root);
88 * Generate access paths for the entire join tree.
90 rel = make_rel_from_joinlist(root, joinlist);
93 * The result should join all and only the query's base rels.
95 #ifdef USE_ASSERT_CHECKING
97 int num_base_rels = 0;
100 for (rti = 1; rti < root->simple_rel_array_size; rti++)
102 RelOptInfo *brel = root->simple_rel_array[rti];
107 Assert(brel->relid == rti); /* sanity check on array */
109 /* ignore RTEs that are "other rels" */
110 if (brel->reloptkind != RELOPT_BASEREL)
113 Assert(bms_is_member(rti, rel->relids));
117 Assert(bms_num_members(rel->relids) == num_base_rels);
125 * set_base_rel_pathlists
126 * Finds all paths available for scanning each base-relation entry.
127 * Sequential scan and any available indices are considered.
128 * Each useful path is attached to its relation's 'pathlist' field.
131 set_base_rel_pathlists(PlannerInfo *root)
135 for (rti = 1; rti < root->simple_rel_array_size; rti++)
137 RelOptInfo *rel = root->simple_rel_array[rti];
139 /* there may be empty slots corresponding to non-baserel RTEs */
143 Assert(rel->relid == rti); /* sanity check on array */
145 /* ignore RTEs that are "other rels" */
146 if (rel->reloptkind != RELOPT_BASEREL)
149 set_rel_pathlist(root, rel, rti, root->simple_rte_array[rti]);
155 * Build access paths for a base relation
158 set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
159 Index rti, RangeTblEntry *rte)
163 /* It's an "append relation", process accordingly */
164 set_append_rel_pathlist(root, rel, rti, rte);
166 else if (rel->rtekind == RTE_SUBQUERY)
168 /* Subquery --- generate a separate plan for it */
169 set_subquery_pathlist(root, rel, rti, rte);
171 else if (rel->rtekind == RTE_FUNCTION)
173 /* RangeFunction --- generate a separate plan for it */
174 set_function_pathlist(root, rel, rte);
176 else if (rel->rtekind == RTE_VALUES)
178 /* Values list --- generate a separate plan for it */
179 set_values_pathlist(root, rel, rte);
184 Assert(rel->rtekind == RTE_RELATION);
185 set_plain_rel_pathlist(root, rel, rte);
188 #ifdef OPTIMIZER_DEBUG
189 debug_print_rel(root, rel);
194 * set_plain_rel_pathlist
195 * Build access paths for a plain relation (no subquery, no inheritance)
198 set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
201 * If we can prove we don't need to scan the rel via constraint exclusion,
202 * set up a single dummy path for it. We only need to check for regular
203 * baserels; if it's an otherrel, CE was already checked in
204 * set_append_rel_pathlist().
206 if (rel->reloptkind == RELOPT_BASEREL &&
207 relation_excluded_by_constraints(rel, rte))
209 set_dummy_rel_pathlist(rel);
213 /* Mark rel with estimated output rows, width, etc */
214 set_baserel_size_estimates(root, rel);
216 /* Test any partial indexes of rel for applicability */
217 check_partial_indexes(root, rel);
220 * Check to see if we can extract any restriction conditions from join
221 * quals that are OR-of-AND structures. If so, add them to the rel's
222 * restriction list, and recompute the size estimates.
224 if (create_or_index_quals(root, rel))
225 set_baserel_size_estimates(root, rel);
228 * Generate paths and add them to the rel's pathlist.
230 * Note: add_path() will discard any paths that are dominated by another
231 * available path, keeping only those paths that are superior along at
232 * least one dimension of cost or sortedness.
235 /* Consider sequential scan */
236 add_path(rel, create_seqscan_path(root, rel));
238 /* Consider index scans */
239 create_index_paths(root, rel);
241 /* Consider TID scans */
242 create_tidscan_paths(root, rel);
244 /* Now find the cheapest of the paths for this rel */
249 * set_append_rel_pathlist
250 * Build access paths for an "append relation"
252 * The passed-in rel and RTE represent the entire append relation. The
253 * relation's contents are computed by appending together the output of
254 * the individual member relations. Note that in the inheritance case,
255 * the first member relation is actually the same table as is mentioned in
256 * the parent RTE ... but it has a different RTE and RelOptInfo. This is
257 * a good thing because their outputs are not the same size.
260 set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
261 Index rti, RangeTblEntry *rte)
263 int parentRTindex = rti;
264 List *subpaths = NIL;
268 * XXX for now, can't handle inherited expansion of FOR UPDATE/SHARE; can
269 * we do better? (This will take some redesign because the executor
270 * currently supposes that every rowMark relation is involved in every row
271 * returned by the query.)
273 if (get_rowmark(root->parse, parentRTindex))
275 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
276 errmsg("SELECT FOR UPDATE/SHARE is not supported for inheritance queries")));
279 * Initialize to compute size estimates for whole append relation
285 * Generate access paths for each member relation, and pick the cheapest
288 foreach(l, root->append_rel_list)
290 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
292 RangeTblEntry *childRTE;
293 RelOptInfo *childrel;
295 ListCell *parentvars;
298 /* append_rel_list contains all append rels; ignore others */
299 if (appinfo->parent_relid != parentRTindex)
302 childRTindex = appinfo->child_relid;
303 childRTE = root->simple_rte_array[childRTindex];
306 * The child rel's RelOptInfo was already created during
307 * add_base_rels_to_query.
309 childrel = find_base_rel(root, childRTindex);
310 Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
313 * We have to copy the parent's targetlist and quals to the child,
314 * with appropriate substitution of variables. However, only the
315 * baserestrictinfo quals are needed before we can check for
316 * constraint exclusion; so do that first and then check to see
317 * if we can disregard this child.
319 childrel->baserestrictinfo = (List *)
320 adjust_appendrel_attrs((Node *) rel->baserestrictinfo,
323 if (relation_excluded_by_constraints(childrel, childRTE))
326 * This child need not be scanned, so we can omit it from the
327 * appendrel. Mark it with a dummy cheapest-path though, in
328 * case best_appendrel_indexscan() looks at it later.
330 set_dummy_rel_pathlist(childrel);
334 /* CE failed, so finish copying targetlist and join quals */
335 childrel->joininfo = (List *)
336 adjust_appendrel_attrs((Node *) rel->joininfo,
338 childrel->reltargetlist = (List *)
339 adjust_appendrel_attrs((Node *) rel->reltargetlist,
343 * We have to make child entries in the EquivalenceClass data
344 * structures as well.
346 if (rel->has_eclass_joins)
348 add_child_rel_equivalences(root, appinfo, rel, childrel);
349 childrel->has_eclass_joins = true;
353 * Copy the parent's attr_needed data as well, with appropriate
354 * adjustment of relids and attribute numbers.
356 pfree(childrel->attr_needed);
357 childrel->attr_needed =
358 adjust_appendrel_attr_needed(rel, appinfo,
363 * Compute the child's access paths, and add the cheapest one to the
364 * Append path we are constructing for the parent.
366 * It's possible that the child is itself an appendrel, in which case
367 * we can "cut out the middleman" and just add its child paths to our
368 * own list. (We don't try to do this earlier because we need to
369 * apply both levels of transformation to the quals.)
371 set_rel_pathlist(root, childrel, childRTindex, childRTE);
373 childpath = childrel->cheapest_total_path;
374 if (IsA(childpath, AppendPath))
375 subpaths = list_concat(subpaths,
376 ((AppendPath *) childpath)->subpaths);
378 subpaths = lappend(subpaths, childpath);
381 * Propagate size information from the child back to the parent. For
382 * simplicity, we use the largest widths from any child as the parent
383 * estimates. (If you want to change this, beware of child
384 * attr_widths[] entries that haven't been set and are still 0.)
386 rel->rows += childrel->rows;
387 if (childrel->width > rel->width)
388 rel->width = childrel->width;
390 forboth(parentvars, rel->reltargetlist,
391 childvars, childrel->reltargetlist)
393 Var *parentvar = (Var *) lfirst(parentvars);
394 Var *childvar = (Var *) lfirst(childvars);
396 if (IsA(parentvar, Var) &&
399 int pndx = parentvar->varattno - rel->min_attr;
400 int cndx = childvar->varattno - childrel->min_attr;
402 if (childrel->attr_widths[cndx] > rel->attr_widths[pndx])
403 rel->attr_widths[pndx] = childrel->attr_widths[cndx];
409 * Set "raw tuples" count equal to "rows" for the appendrel; needed
410 * because some places assume rel->tuples is valid for any baserel.
412 rel->tuples = rel->rows;
415 * Finally, build Append path and install it as the only access path for
416 * the parent rel. (Note: this is correct even if we have zero or one
417 * live subpath due to constraint exclusion.)
419 add_path(rel, (Path *) create_append_path(rel, subpaths));
421 /* Select cheapest path (pretty easy in this case...) */
426 * set_dummy_rel_pathlist
427 * Build a dummy path for a relation that's been excluded by constraints
429 * Rather than inventing a special "dummy" path type, we represent this as an
430 * AppendPath with no members.
433 set_dummy_rel_pathlist(RelOptInfo *rel)
435 /* Set dummy size estimates --- we leave attr_widths[] as zeroes */
439 add_path(rel, (Path *) create_append_path(rel, NIL));
441 /* Select cheapest path (pretty easy in this case...) */
445 /* quick-and-dirty test to see if any joining is needed */
447 has_multiple_baserels(PlannerInfo *root)
449 int num_base_rels = 0;
452 for (rti = 1; rti < root->simple_rel_array_size; rti++)
454 RelOptInfo *brel = root->simple_rel_array[rti];
459 /* ignore RTEs that are "other rels" */
460 if (brel->reloptkind == RELOPT_BASEREL)
461 if (++num_base_rels > 1)
468 * set_subquery_pathlist
469 * Build the (single) access path for a subquery RTE
472 set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
473 Index rti, RangeTblEntry *rte)
475 Query *parse = root->parse;
476 Query *subquery = rte->subquery;
477 bool *differentTypes;
478 double tuple_fraction;
479 PlannerInfo *subroot;
482 /* We need a workspace for keeping track of set-op type coercions */
483 differentTypes = (bool *)
484 palloc0((list_length(subquery->targetList) + 1) * sizeof(bool));
487 * If there are any restriction clauses that have been attached to the
488 * subquery relation, consider pushing them down to become WHERE or HAVING
489 * quals of the subquery itself. This transformation is useful because it
490 * may allow us to generate a better plan for the subquery than evaluating
491 * all the subquery output rows and then filtering them.
493 * There are several cases where we cannot push down clauses. Restrictions
494 * involving the subquery are checked by subquery_is_pushdown_safe().
495 * Restrictions on individual clauses are checked by
496 * qual_is_pushdown_safe(). Also, we don't want to push down
497 * pseudoconstant clauses; better to have the gating node above the
500 * Non-pushed-down clauses will get evaluated as qpquals of the
503 * XXX Are there any cases where we want to make a policy decision not to
504 * push down a pushable qual, because it'd result in a worse plan?
506 if (rel->baserestrictinfo != NIL &&
507 subquery_is_pushdown_safe(subquery, subquery, differentTypes))
509 /* OK to consider pushing down individual quals */
510 List *upperrestrictlist = NIL;
513 foreach(l, rel->baserestrictinfo)
515 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
516 Node *clause = (Node *) rinfo->clause;
518 if (!rinfo->pseudoconstant &&
519 qual_is_pushdown_safe(subquery, rti, clause, differentTypes))
522 subquery_push_qual(subquery, rte, rti, clause);
526 /* Keep it in the upper query */
527 upperrestrictlist = lappend(upperrestrictlist, rinfo);
530 rel->baserestrictinfo = upperrestrictlist;
533 pfree(differentTypes);
536 * We can safely pass the outer tuple_fraction down to the subquery if the
537 * outer level has no joining, aggregation, or sorting to do. Otherwise
538 * we'd better tell the subquery to plan for full retrieval. (XXX This
539 * could probably be made more intelligent ...)
541 if (parse->hasAggs ||
542 parse->groupClause ||
544 parse->distinctClause ||
546 has_multiple_baserels(root))
547 tuple_fraction = 0.0; /* default case */
549 tuple_fraction = root->tuple_fraction;
551 /* Generate the plan for the subquery */
552 rel->subplan = subquery_planner(root->glob, subquery,
553 root->query_level + 1,
556 rel->subrtable = subroot->parse->rtable;
558 /* Copy number of output rows from subplan */
559 rel->tuples = rel->subplan->plan_rows;
561 /* Mark rel with estimated output rows, width, etc */
562 set_baserel_size_estimates(root, rel);
564 /* Convert subquery pathkeys to outer representation */
565 pathkeys = convert_subquery_pathkeys(root, rel, subroot->query_pathkeys);
567 /* Generate appropriate path */
568 add_path(rel, create_subqueryscan_path(rel, pathkeys));
570 /* Select cheapest path (pretty easy in this case...) */
575 * set_function_pathlist
576 * Build the (single) access path for a function RTE
579 set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
581 /* Mark rel with estimated output rows, width, etc */
582 set_function_size_estimates(root, rel);
584 /* Generate appropriate path */
585 add_path(rel, create_functionscan_path(root, rel));
587 /* Select cheapest path (pretty easy in this case...) */
592 * set_values_pathlist
593 * Build the (single) access path for a VALUES RTE
596 set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
598 /* Mark rel with estimated output rows, width, etc */
599 set_values_size_estimates(root, rel);
601 /* Generate appropriate path */
602 add_path(rel, create_valuesscan_path(root, rel));
604 /* Select cheapest path (pretty easy in this case...) */
609 * make_rel_from_joinlist
610 * Build access paths using a "joinlist" to guide the join path search.
612 * See comments for deconstruct_jointree() for definition of the joinlist
616 make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
623 * Count the number of child joinlist nodes. This is the depth of the
624 * dynamic-programming algorithm we must employ to consider all ways of
625 * joining the child nodes.
627 levels_needed = list_length(joinlist);
629 if (levels_needed <= 0)
630 return NULL; /* nothing to do? */
633 * Construct a list of rels corresponding to the child joinlist nodes.
634 * This may contain both base rels and rels constructed according to
638 foreach(jl, joinlist)
640 Node *jlnode = (Node *) lfirst(jl);
643 if (IsA(jlnode, RangeTblRef))
645 int varno = ((RangeTblRef *) jlnode)->rtindex;
647 thisrel = find_base_rel(root, varno);
649 else if (IsA(jlnode, List))
651 /* Recurse to handle subproblem */
652 thisrel = make_rel_from_joinlist(root, (List *) jlnode);
656 elog(ERROR, "unrecognized joinlist node type: %d",
657 (int) nodeTag(jlnode));
658 thisrel = NULL; /* keep compiler quiet */
661 initial_rels = lappend(initial_rels, thisrel);
664 if (levels_needed == 1)
667 * Single joinlist node, so we're done.
669 return (RelOptInfo *) linitial(initial_rels);
674 * Consider the different orders in which we could join the rels,
675 * using either GEQO or regular optimizer.
677 if (enable_geqo && levels_needed >= geqo_threshold)
678 return geqo(root, levels_needed, initial_rels);
680 return make_one_rel_by_joins(root, levels_needed, initial_rels);
685 * make_one_rel_by_joins
686 * Find all possible joinpaths for a query by successively finding ways
687 * to join component relations into join relations.
689 * 'levels_needed' is the number of iterations needed, ie, the number of
690 * independent jointree items in the query. This is > 1.
692 * 'initial_rels' is a list of RelOptInfo nodes for each independent
693 * jointree item. These are the components to be joined together.
695 * Returns the final level of join relations, i.e., the relation that is
696 * the result of joining all the original relations together.
699 make_one_rel_by_joins(PlannerInfo *root, int levels_needed, List *initial_rels)
706 * We employ a simple "dynamic programming" algorithm: we first find all
707 * ways to build joins of two jointree items, then all ways to build joins
708 * of three items (from two-item joins and single items), then four-item
709 * joins, and so on until we have considered all ways to join all the
710 * items into one rel.
712 * joinitems[j] is a list of all the j-item rels. Initially we set
713 * joinitems[1] to represent all the single-jointree-item relations.
715 joinitems = (List **) palloc0((levels_needed + 1) * sizeof(List *));
717 joinitems[1] = initial_rels;
719 for (lev = 2; lev <= levels_needed; lev++)
724 * Determine all possible pairs of relations to be joined at this
725 * level, and build paths for making each one from every available
726 * pair of lower-level relations.
728 joinitems[lev] = make_rels_by_joins(root, lev, joinitems);
731 * Do cleanup work on each just-processed rel.
733 foreach(x, joinitems[lev])
735 rel = (RelOptInfo *) lfirst(x);
737 /* Find and save the cheapest paths for this rel */
740 #ifdef OPTIMIZER_DEBUG
741 debug_print_rel(root, rel);
747 * We should have a single rel at the final level.
749 if (joinitems[levels_needed] == NIL)
750 elog(ERROR, "failed to build any %d-way joins", levels_needed);
751 Assert(list_length(joinitems[levels_needed]) == 1);
753 rel = (RelOptInfo *) linitial(joinitems[levels_needed]);
758 /*****************************************************************************
759 * PUSHING QUALS DOWN INTO SUBQUERIES
760 *****************************************************************************/
763 * subquery_is_pushdown_safe - is a subquery safe for pushing down quals?
765 * subquery is the particular component query being checked. topquery
766 * is the top component of a set-operations tree (the same Query if no
767 * set-op is involved).
769 * Conditions checked here:
771 * 1. If the subquery has a LIMIT clause, we must not push down any quals,
772 * since that could change the set of rows returned.
774 * 2. If the subquery contains EXCEPT or EXCEPT ALL set ops we cannot push
775 * quals into it, because that would change the results.
777 * 3. For subqueries using UNION/UNION ALL/INTERSECT/INTERSECT ALL, we can
778 * push quals into each component query, but the quals can only reference
779 * subquery columns that suffer no type coercions in the set operation.
780 * Otherwise there are possible semantic gotchas. So, we check the
781 * component queries to see if any of them have different output types;
782 * differentTypes[k] is set true if column k has different type in any
786 subquery_is_pushdown_safe(Query *subquery, Query *topquery,
787 bool *differentTypes)
789 SetOperationStmt *topop;
792 if (subquery->limitOffset != NULL || subquery->limitCount != NULL)
795 /* Are we at top level, or looking at a setop component? */
796 if (subquery == topquery)
798 /* Top level, so check any component queries */
799 if (subquery->setOperations != NULL)
800 if (!recurse_pushdown_safe(subquery->setOperations, topquery,
806 /* Setop component must not have more components (too weird) */
807 if (subquery->setOperations != NULL)
809 /* Check whether setop component output types match top level */
810 topop = (SetOperationStmt *) topquery->setOperations;
811 Assert(topop && IsA(topop, SetOperationStmt));
812 compare_tlist_datatypes(subquery->targetList,
820 * Helper routine to recurse through setOperations tree
823 recurse_pushdown_safe(Node *setOp, Query *topquery,
824 bool *differentTypes)
826 if (IsA(setOp, RangeTblRef))
828 RangeTblRef *rtr = (RangeTblRef *) setOp;
829 RangeTblEntry *rte = rt_fetch(rtr->rtindex, topquery->rtable);
830 Query *subquery = rte->subquery;
832 Assert(subquery != NULL);
833 return subquery_is_pushdown_safe(subquery, topquery, differentTypes);
835 else if (IsA(setOp, SetOperationStmt))
837 SetOperationStmt *op = (SetOperationStmt *) setOp;
839 /* EXCEPT is no good */
840 if (op->op == SETOP_EXCEPT)
843 if (!recurse_pushdown_safe(op->larg, topquery, differentTypes))
845 if (!recurse_pushdown_safe(op->rarg, topquery, differentTypes))
850 elog(ERROR, "unrecognized node type: %d",
851 (int) nodeTag(setOp));
857 * Compare tlist's datatypes against the list of set-operation result types.
858 * For any items that are different, mark the appropriate element of
859 * differentTypes[] to show that this column will have type conversions.
861 * We don't have to care about typmods here: the only allowed difference
862 * between set-op input and output typmods is input is a specific typmod
863 * and output is -1, and that does not require a coercion.
866 compare_tlist_datatypes(List *tlist, List *colTypes,
867 bool *differentTypes)
870 ListCell *colType = list_head(colTypes);
874 TargetEntry *tle = (TargetEntry *) lfirst(l);
877 continue; /* ignore resjunk columns */
879 elog(ERROR, "wrong number of tlist entries");
880 if (exprType((Node *) tle->expr) != lfirst_oid(colType))
881 differentTypes[tle->resno] = true;
882 colType = lnext(colType);
885 elog(ERROR, "wrong number of tlist entries");
889 * qual_is_pushdown_safe - is a particular qual safe to push down?
891 * qual is a restriction clause applying to the given subquery (whose RTE
892 * has index rti in the parent query).
894 * Conditions checked here:
896 * 1. The qual must not contain any subselects (mainly because I'm not sure
897 * it will work correctly: sublinks will already have been transformed into
898 * subplans in the qual, but not in the subquery).
900 * 2. The qual must not refer to the whole-row output of the subquery
901 * (since there is no easy way to name that within the subquery itself).
903 * 3. The qual must not refer to any subquery output columns that were
904 * found to have inconsistent types across a set operation tree by
905 * subquery_is_pushdown_safe().
907 * 4. If the subquery uses DISTINCT ON, we must not push down any quals that
908 * refer to non-DISTINCT output columns, because that could change the set
909 * of rows returned. This condition is vacuous for DISTINCT, because then
910 * there are no non-DISTINCT output columns, but unfortunately it's fairly
911 * expensive to tell the difference between DISTINCT and DISTINCT ON in the
912 * parsetree representation. It's cheaper to just make sure all the Vars
913 * in the qual refer to DISTINCT columns.
915 * 5. We must not push down any quals that refer to subselect outputs that
916 * return sets, else we'd introduce functions-returning-sets into the
917 * subquery's WHERE/HAVING quals.
919 * 6. We must not push down any quals that refer to subselect outputs that
920 * contain volatile functions, for fear of introducing strange results due
921 * to multiple evaluation of a volatile function.
924 qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
925 bool *differentTypes)
930 Bitmapset *tested = NULL;
932 /* Refuse subselects (point 1) */
933 if (contain_subplans(qual))
937 * Examine all Vars used in clause; since it's a restriction clause, all
938 * such Vars must refer to subselect output columns.
940 vars = pull_var_clause(qual, false);
943 Var *var = (Var *) lfirst(vl);
946 Assert(var->varno == rti);
949 if (var->varattno == 0)
956 * We use a bitmapset to avoid testing the same attno more than once.
957 * (NB: this only works because subquery outputs can't have negative
960 if (bms_is_member(var->varattno, tested))
962 tested = bms_add_member(tested, var->varattno);
965 if (differentTypes[var->varattno])
971 /* Must find the tlist element referenced by the Var */
972 tle = get_tle_by_resno(subquery->targetList, var->varattno);
974 Assert(!tle->resjunk);
976 /* If subquery uses DISTINCT or DISTINCT ON, check point 4 */
977 if (subquery->distinctClause != NIL &&
978 !targetIsInSortList(tle, InvalidOid, subquery->distinctClause))
980 /* non-DISTINCT column, so fail */
985 /* Refuse functions returning sets (point 5) */
986 if (expression_returns_set((Node *) tle->expr))
992 /* Refuse volatile functions (point 6) */
993 if (contain_volatile_functions((Node *) tle->expr))
1007 * subquery_push_qual - push down a qual that we have determined is safe
1010 subquery_push_qual(Query *subquery, RangeTblEntry *rte, Index rti, Node *qual)
1012 if (subquery->setOperations != NULL)
1014 /* Recurse to push it separately to each component query */
1015 recurse_push_qual(subquery->setOperations, subquery,
1021 * We need to replace Vars in the qual (which must refer to outputs of
1022 * the subquery) with copies of the subquery's targetlist expressions.
1023 * Note that at this point, any uplevel Vars in the qual should have
1024 * been replaced with Params, so they need no work.
1026 * This step also ensures that when we are pushing into a setop tree,
1027 * each component query gets its own copy of the qual.
1029 qual = ResolveNew(qual, rti, 0, rte,
1030 subquery->targetList,
1034 * Now attach the qual to the proper place: normally WHERE, but if the
1035 * subquery uses grouping or aggregation, put it in HAVING (since the
1036 * qual really refers to the group-result rows).
1038 if (subquery->hasAggs || subquery->groupClause || subquery->havingQual)
1039 subquery->havingQual = make_and_qual(subquery->havingQual, qual);
1041 subquery->jointree->quals =
1042 make_and_qual(subquery->jointree->quals, qual);
1045 * We need not change the subquery's hasAggs or hasSublinks flags,
1046 * since we can't be pushing down any aggregates that weren't there
1047 * before, and we don't push down subselects at all.
1053 * Helper routine to recurse through setOperations tree
1056 recurse_push_qual(Node *setOp, Query *topquery,
1057 RangeTblEntry *rte, Index rti, Node *qual)
1059 if (IsA(setOp, RangeTblRef))
1061 RangeTblRef *rtr = (RangeTblRef *) setOp;
1062 RangeTblEntry *subrte = rt_fetch(rtr->rtindex, topquery->rtable);
1063 Query *subquery = subrte->subquery;
1065 Assert(subquery != NULL);
1066 subquery_push_qual(subquery, rte, rti, qual);
1068 else if (IsA(setOp, SetOperationStmt))
1070 SetOperationStmt *op = (SetOperationStmt *) setOp;
1072 recurse_push_qual(op->larg, topquery, rte, rti, qual);
1073 recurse_push_qual(op->rarg, topquery, rte, rti, qual);
1077 elog(ERROR, "unrecognized node type: %d",
1078 (int) nodeTag(setOp));
1082 /*****************************************************************************
1084 *****************************************************************************/
1086 #ifdef OPTIMIZER_DEBUG
1089 print_relids(Relids relids)
1095 tmprelids = bms_copy(relids);
1096 while ((x = bms_first_member(tmprelids)) >= 0)
1103 bms_free(tmprelids);
1107 print_restrictclauses(PlannerInfo *root, List *clauses)
1113 RestrictInfo *c = lfirst(l);
1115 print_expr((Node *) c->clause, root->parse->rtable);
1122 print_path(PlannerInfo *root, Path *path, int indent)
1126 Path *subpath = NULL;
1129 switch (nodeTag(path))
1137 case T_BitmapHeapPath:
1138 ptype = "BitmapHeapScan";
1140 case T_BitmapAndPath:
1141 ptype = "BitmapAndPath";
1143 case T_BitmapOrPath:
1144 ptype = "BitmapOrPath";
1155 case T_MaterialPath:
1157 subpath = ((MaterialPath *) path)->subpath;
1161 subpath = ((UniquePath *) path)->subpath;
1168 ptype = "MergeJoin";
1180 for (i = 0; i < indent; i++)
1182 printf("%s", ptype);
1187 print_relids(path->parent->relids);
1188 printf(") rows=%.0f", path->parent->rows);
1190 printf(" cost=%.2f..%.2f\n", path->startup_cost, path->total_cost);
1194 for (i = 0; i < indent; i++)
1196 printf(" pathkeys: ");
1197 print_pathkeys(path->pathkeys, root->parse->rtable);
1202 JoinPath *jp = (JoinPath *) path;
1204 for (i = 0; i < indent; i++)
1206 printf(" clauses: ");
1207 print_restrictclauses(root, jp->joinrestrictinfo);
1210 if (IsA(path, MergePath))
1212 MergePath *mp = (MergePath *) path;
1214 if (mp->outersortkeys || mp->innersortkeys)
1216 for (i = 0; i < indent; i++)
1218 printf(" sortouter=%d sortinner=%d\n",
1219 ((mp->outersortkeys) ? 1 : 0),
1220 ((mp->innersortkeys) ? 1 : 0));
1224 print_path(root, jp->outerjoinpath, indent + 1);
1225 print_path(root, jp->innerjoinpath, indent + 1);
1229 print_path(root, subpath, indent + 1);
1233 debug_print_rel(PlannerInfo *root, RelOptInfo *rel)
1237 printf("RELOPTINFO (");
1238 print_relids(rel->relids);
1239 printf("): rows=%.0f width=%d\n", rel->rows, rel->width);
1241 if (rel->baserestrictinfo)
1243 printf("\tbaserestrictinfo: ");
1244 print_restrictclauses(root, rel->baserestrictinfo);
1250 printf("\tjoininfo: ");
1251 print_restrictclauses(root, rel->joininfo);
1255 printf("\tpath list:\n");
1256 foreach(l, rel->pathlist)
1257 print_path(root, lfirst(l), 1);
1258 printf("\n\tcheapest startup path:\n");
1259 print_path(root, rel->cheapest_startup_path, 1);
1260 printf("\n\tcheapest total path:\n");
1261 print_path(root, rel->cheapest_total_path, 1);
1266 #endif /* OPTIMIZER_DEBUG */