1 /*-------------------------------------------------------------------------
4 * Routines to create the desired plan for processing a query.
5 * Planning is complete, we just need to convert the selected
8 * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
9 * Portions Copyright (c) 1994, Regents of the University of California
13 * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.226 2007/02/22 22:00:24 tgl Exp $
15 *-------------------------------------------------------------------------
21 #include "nodes/makefuncs.h"
22 #include "optimizer/clauses.h"
23 #include "optimizer/cost.h"
24 #include "optimizer/plancat.h"
25 #include "optimizer/planmain.h"
26 #include "optimizer/predtest.h"
27 #include "optimizer/restrictinfo.h"
28 #include "optimizer/tlist.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 "utils/lsyscache.h"
36 static Plan *create_scan_plan(PlannerInfo *root, Path *best_path);
37 static List *build_relation_tlist(RelOptInfo *rel);
38 static bool use_physical_tlist(RelOptInfo *rel);
39 static void disuse_physical_tlist(Plan *plan, Path *path);
40 static Plan *create_gating_plan(PlannerInfo *root, Plan *plan, List *quals);
41 static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path);
42 static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path);
43 static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
44 static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path);
45 static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path);
46 static SeqScan *create_seqscan_plan(PlannerInfo *root, Path *best_path,
47 List *tlist, List *scan_clauses);
48 static IndexScan *create_indexscan_plan(PlannerInfo *root, IndexPath *best_path,
49 List *tlist, List *scan_clauses,
50 List **nonlossy_clauses);
51 static BitmapHeapScan *create_bitmap_scan_plan(PlannerInfo *root,
52 BitmapHeapPath *best_path,
53 List *tlist, List *scan_clauses);
54 static Plan *create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
55 List **qual, List **indexqual);
56 static TidScan *create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
57 List *tlist, List *scan_clauses);
58 static SubqueryScan *create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
59 List *tlist, List *scan_clauses);
60 static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path,
61 List *tlist, List *scan_clauses);
62 static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path,
63 List *tlist, List *scan_clauses);
64 static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path,
65 Plan *outer_plan, Plan *inner_plan);
66 static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path,
67 Plan *outer_plan, Plan *inner_plan);
68 static HashJoin *create_hashjoin_plan(PlannerInfo *root, HashPath *best_path,
69 Plan *outer_plan, Plan *inner_plan);
70 static void fix_indexqual_references(List *indexquals, IndexPath *index_path,
71 List **fixed_indexquals,
72 List **nonlossy_indexquals,
75 static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index,
77 static List *get_switched_clauses(List *clauses, Relids outerrelids);
78 static List *order_qual_clauses(PlannerInfo *root, List *clauses);
79 static void copy_path_costsize(Plan *dest, Path *src);
80 static void copy_plan_costsize(Plan *dest, Plan *src);
81 static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
82 static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
83 Oid indexid, List *indexqual, List *indexqualorig,
84 List *indexstrategy, List *indexsubtype,
85 ScanDirection indexscandir);
86 static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
91 static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
96 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
98 static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
99 Index scanrelid, Node *funcexpr, List *funccolnames,
100 List *funccoltypes, List *funccoltypmods);
101 static ValuesScan *make_valuesscan(List *qptlist, List *qpqual,
102 Index scanrelid, List *values_lists);
103 static BitmapAnd *make_bitmap_and(List *bitmapplans);
104 static BitmapOr *make_bitmap_or(List *bitmapplans);
105 static NestLoop *make_nestloop(List *tlist,
106 List *joinclauses, List *otherclauses,
107 Plan *lefttree, Plan *righttree,
109 static HashJoin *make_hashjoin(List *tlist,
110 List *joinclauses, List *otherclauses,
112 Plan *lefttree, Plan *righttree,
114 static Hash *make_hash(Plan *lefttree);
115 static MergeJoin *make_mergejoin(List *tlist,
116 List *joinclauses, List *otherclauses,
119 int *mergestrategies,
120 bool *mergenullsfirst,
121 Plan *lefttree, Plan *righttree,
123 static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
124 AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst);
129 * Creates the access plan for a query by tracing backwards through the
130 * desired chain of pathnodes, starting at the node 'best_path'. For
131 * every pathnode found, we create a corresponding plan node containing
132 * appropriate id, target list, and qualification information.
134 * The tlists and quals in the plan tree are still in planner format,
135 * ie, Vars still correspond to the parser's numbering. This will be
136 * fixed later by setrefs.c.
138 * best_path is the best access path
140 * Returns a Plan tree.
143 create_plan(PlannerInfo *root, Path *best_path)
147 switch (best_path->pathtype)
151 case T_BitmapHeapScan:
156 plan = create_scan_plan(root, best_path);
161 plan = create_join_plan(root,
162 (JoinPath *) best_path);
165 plan = create_append_plan(root,
166 (AppendPath *) best_path);
169 plan = (Plan *) create_result_plan(root,
170 (ResultPath *) best_path);
173 plan = (Plan *) create_material_plan(root,
174 (MaterialPath *) best_path);
177 plan = create_unique_plan(root,
178 (UniquePath *) best_path);
181 elog(ERROR, "unrecognized node type: %d",
182 (int) best_path->pathtype);
183 plan = NULL; /* keep compiler quiet */
192 * Create a scan plan for the parent relation of 'best_path'.
195 create_scan_plan(PlannerInfo *root, Path *best_path)
197 RelOptInfo *rel = best_path->parent;
203 * For table scans, rather than using the relation targetlist (which is
204 * only those Vars actually needed by the query), we prefer to generate a
205 * tlist containing all Vars in order. This will allow the executor to
206 * optimize away projection of the table tuples, if possible. (Note that
207 * planner.c may replace the tlist we generate here, forcing projection to
210 if (use_physical_tlist(rel))
212 tlist = build_physical_tlist(root, rel);
213 /* if fail because of dropped cols, use regular method */
215 tlist = build_relation_tlist(rel);
218 tlist = build_relation_tlist(rel);
221 * Extract the relevant restriction clauses from the parent relation. The
222 * executor must apply all these restrictions during the scan, except for
223 * pseudoconstants which we'll take care of below.
225 scan_clauses = rel->baserestrictinfo;
227 switch (best_path->pathtype)
230 plan = (Plan *) create_seqscan_plan(root,
237 plan = (Plan *) create_indexscan_plan(root,
238 (IndexPath *) best_path,
244 case T_BitmapHeapScan:
245 plan = (Plan *) create_bitmap_scan_plan(root,
246 (BitmapHeapPath *) best_path,
252 plan = (Plan *) create_tidscan_plan(root,
253 (TidPath *) best_path,
259 plan = (Plan *) create_subqueryscan_plan(root,
266 plan = (Plan *) create_functionscan_plan(root,
273 plan = (Plan *) create_valuesscan_plan(root,
280 elog(ERROR, "unrecognized node type: %d",
281 (int) best_path->pathtype);
282 plan = NULL; /* keep compiler quiet */
287 * If there are any pseudoconstant clauses attached to this node, insert a
288 * gating Result node that evaluates the pseudoconstants as one-time
291 if (root->hasPseudoConstantQuals)
292 plan = create_gating_plan(root, plan, scan_clauses);
298 * Build a target list (ie, a list of TargetEntry) for a relation.
301 build_relation_tlist(RelOptInfo *rel)
307 foreach(v, rel->reltargetlist)
309 /* Do we really need to copy here? Not sure */
310 Var *var = (Var *) copyObject(lfirst(v));
312 tlist = lappend(tlist, makeTargetEntry((Expr *) var,
323 * Decide whether to use a tlist matching relation structure,
324 * rather than only those Vars actually referenced.
327 use_physical_tlist(RelOptInfo *rel)
332 * We can do this for real relation scans, subquery scans, function scans,
333 * and values scans (but not for, eg, joins).
335 if (rel->rtekind != RTE_RELATION &&
336 rel->rtekind != RTE_SUBQUERY &&
337 rel->rtekind != RTE_FUNCTION &&
338 rel->rtekind != RTE_VALUES)
342 * Can't do it with inheritance cases either (mainly because Append
345 if (rel->reloptkind != RELOPT_BASEREL)
349 * Can't do it if any system columns or whole-row Vars are requested,
350 * either. (This could possibly be fixed but would take some fragile
351 * assumptions in setrefs.c, I think.)
353 for (i = rel->min_attr; i <= 0; i++)
355 if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
363 * disuse_physical_tlist
364 * Switch a plan node back to emitting only Vars actually referenced.
366 * If the plan node immediately above a scan would prefer to get only
367 * needed Vars and not a physical tlist, it must call this routine to
368 * undo the decision made by use_physical_tlist(). Currently, Hash, Sort,
369 * and Material nodes want this, so they don't have to store useless columns.
372 disuse_physical_tlist(Plan *plan, Path *path)
374 /* Only need to undo it for path types handled by create_scan_plan() */
375 switch (path->pathtype)
379 case T_BitmapHeapScan:
384 plan->targetlist = build_relation_tlist(path->parent);
393 * Deal with pseudoconstant qual clauses
395 * If the node's quals list includes any pseudoconstant quals, put them
396 * into a gating Result node atop the already-built plan. Otherwise,
397 * return the plan as-is.
399 * Note that we don't change cost or size estimates when doing gating.
400 * The costs of qual eval were already folded into the plan's startup cost.
401 * Leaving the size alone amounts to assuming that the gating qual will
402 * succeed, which is the conservative estimate for planning upper queries.
403 * We certainly don't want to assume the output size is zero (unless the
404 * gating qual is actually constant FALSE, and that case is dealt with in
405 * clausesel.c). Interpolating between the two cases is silly, because
406 * it doesn't reflect what will really happen at runtime, and besides which
407 * in most cases we have only a very bad idea of the probability of the gating
411 create_gating_plan(PlannerInfo *root, Plan *plan, List *quals)
413 List *pseudoconstants;
415 /* Sort into desirable execution order while still in RestrictInfo form */
416 quals = order_qual_clauses(root, quals);
418 /* Pull out any pseudoconstant quals from the RestrictInfo list */
419 pseudoconstants = extract_actual_clauses(quals, true);
421 if (!pseudoconstants)
424 return (Plan *) make_result(root,
426 (Node *) pseudoconstants,
432 * Create a join plan for 'best_path' and (recursively) plans for its
433 * inner and outer paths.
436 create_join_plan(PlannerInfo *root, JoinPath *best_path)
442 outer_plan = create_plan(root, best_path->outerjoinpath);
443 inner_plan = create_plan(root, best_path->innerjoinpath);
445 switch (best_path->path.pathtype)
448 plan = (Plan *) create_mergejoin_plan(root,
449 (MergePath *) best_path,
454 plan = (Plan *) create_hashjoin_plan(root,
455 (HashPath *) best_path,
460 plan = (Plan *) create_nestloop_plan(root,
461 (NestPath *) best_path,
466 elog(ERROR, "unrecognized node type: %d",
467 (int) best_path->path.pathtype);
468 plan = NULL; /* keep compiler quiet */
473 * If there are any pseudoconstant clauses attached to this node, insert a
474 * gating Result node that evaluates the pseudoconstants as one-time
477 if (root->hasPseudoConstantQuals)
478 plan = create_gating_plan(root, plan, best_path->joinrestrictinfo);
483 * * Expensive function pullups may have pulled local predicates * into
484 * this path node. Put them in the qpqual of the plan node. * JMH,
487 if (get_loc_restrictinfo(best_path) != NIL)
488 set_qpqual((Plan) plan,
489 list_concat(get_qpqual((Plan) plan),
490 get_actual_clauses(get_loc_restrictinfo(best_path))));
498 * Create an Append plan for 'best_path' and (recursively) plans
501 * Returns a Plan node.
504 create_append_plan(PlannerInfo *root, AppendPath *best_path)
507 List *tlist = build_relation_tlist(best_path->path.parent);
508 List *subplans = NIL;
512 * It is possible for the subplans list to contain only one entry, or even
513 * no entries. Handle these cases specially.
515 * XXX ideally, if there's just one entry, we'd not bother to generate an
516 * Append node but just return the single child. At the moment this does
517 * not work because the varno of the child scan plan won't match the
518 * parent-rel Vars it'll be asked to emit.
520 if (best_path->subpaths == NIL)
522 /* Generate a Result plan with constant-FALSE gating qual */
523 return (Plan *) make_result(root,
525 (Node *) list_make1(makeBoolConst(false,
530 /* Normal case with multiple subpaths */
531 foreach(subpaths, best_path->subpaths)
533 Path *subpath = (Path *) lfirst(subpaths);
535 subplans = lappend(subplans, create_plan(root, subpath));
538 plan = make_append(subplans, false, tlist);
540 return (Plan *) plan;
545 * Create a Result plan for 'best_path'.
546 * This is only used for the case of a query with an empty jointree.
548 * Returns a Plan node.
551 create_result_plan(PlannerInfo *root, ResultPath *best_path)
556 /* The tlist will be installed later, since we have no RelOptInfo */
557 Assert(best_path->path.parent == NULL);
560 /* best_path->quals is just bare clauses */
562 quals = order_qual_clauses(root, best_path->quals);
564 return make_result(root, tlist, (Node *) quals, NULL);
568 * create_material_plan
569 * Create a Material plan for 'best_path' and (recursively) plans
572 * Returns a Plan node.
575 create_material_plan(PlannerInfo *root, MaterialPath *best_path)
580 subplan = create_plan(root, best_path->subpath);
582 /* We don't want any excess columns in the materialized tuples */
583 disuse_physical_tlist(subplan, best_path->subpath);
585 plan = make_material(subplan);
587 copy_path_costsize(&plan->plan, (Path *) best_path);
594 * Create a Unique plan for 'best_path' and (recursively) plans
597 * Returns a Plan node.
600 create_unique_plan(PlannerInfo *root, UniquePath *best_path)
610 AttrNumber *groupColIdx;
614 subplan = create_plan(root, best_path->subpath);
616 /* Done if we don't need to do any actual unique-ifying */
617 if (best_path->umethod == UNIQUE_PATH_NOOP)
621 * As constructed, the subplan has a "flat" tlist containing just the
622 * Vars needed here and at upper levels. The values we are supposed
623 * to unique-ify may be expressions in these variables. We have to
624 * add any such expressions to the subplan's tlist.
626 * The subplan may have a "physical" tlist if it is a simple scan plan.
627 * This should be left as-is if we don't need to add any expressions;
628 * but if we do have to add expressions, then a projection step will be
629 * needed at runtime anyway, and so we may as well remove unneeded items.
630 * Therefore newtlist starts from build_relation_tlist() not just a
631 * copy of the subplan's tlist; and we don't install it into the subplan
632 * unless stuff has to be added.
634 * To find the correct list of values to unique-ify, we look in the
635 * information saved for IN expressions. If this code is ever used in
636 * other scenarios, some other way of finding what to unique-ify will
637 * be needed. The IN clause's operators are needed too, since they
638 * determine what the meaning of "unique" is in this context.
641 uniq_exprs = NIL; /* just to keep compiler quiet */
643 foreach(l, root->in_info_list)
645 InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
647 if (bms_equal(ininfo->righthand, best_path->path.parent->relids))
649 uniq_exprs = ininfo->sub_targetlist;
650 in_operators = ininfo->in_operators;
654 if (l == NULL) /* fell out of loop? */
655 elog(ERROR, "could not find UniquePath in in_info_list");
657 /* initialize modified subplan tlist as just the "required" vars */
658 newtlist = build_relation_tlist(best_path->path.parent);
659 nextresno = list_length(newtlist) + 1;
662 foreach(l, uniq_exprs)
664 Node *uniqexpr = lfirst(l);
667 tle = tlist_member(uniqexpr, newtlist);
670 tle = makeTargetEntry((Expr *) uniqexpr,
674 newtlist = lappend(newtlist, tle);
683 * If the top plan node can't do projections, we need to add a Result
684 * node to help it along.
686 if (!is_projection_capable_plan(subplan))
687 subplan = (Plan *) make_result(root, newtlist, NULL, subplan);
689 subplan->targetlist = newtlist;
693 * Build control information showing which subplan output columns are to
694 * be examined by the grouping step. Unfortunately we can't merge this
695 * with the previous loop, since we didn't then know which version of the
696 * subplan tlist we'd end up using.
698 newtlist = subplan->targetlist;
699 numGroupCols = list_length(uniq_exprs);
700 groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));
703 foreach(l, uniq_exprs)
705 Node *uniqexpr = lfirst(l);
708 tle = tlist_member(uniqexpr, newtlist);
709 if (!tle) /* shouldn't happen */
710 elog(ERROR, "failed to find unique expression in subplan tlist");
711 groupColIdx[groupColPos++] = tle->resno;
714 if (best_path->umethod == UNIQUE_PATH_HASH)
719 numGroups = (long) Min(best_path->rows, (double) LONG_MAX);
722 * Get the hashable equality operators for the Agg node to use.
723 * Normally these are the same as the IN clause operators, but if
724 * those are cross-type operators then the equality operators are
725 * the ones for the IN clause operators' RHS datatype.
727 groupOperators = (Oid *) palloc(numGroupCols * sizeof(Oid));
729 foreach(l, in_operators)
731 Oid in_oper = lfirst_oid(l);
734 if (!get_compatible_hash_operators(in_oper, NULL, &eq_oper))
735 elog(ERROR, "could not find compatible hash operator for operator %u",
737 groupOperators[groupColPos++] = eq_oper;
741 * Since the Agg node is going to project anyway, we can give it the
742 * minimum output tlist, without any stuff we might have added to the
745 plan = (Plan *) make_agg(root,
746 build_relation_tlist(best_path->path.parent),
758 List *sortList = NIL;
760 /* Create an ORDER BY list to sort the input compatibly */
762 foreach(l, in_operators)
764 Oid in_oper = lfirst_oid(l);
769 sortop = get_ordering_op_for_equality_op(in_oper, false);
770 if (!OidIsValid(sortop)) /* shouldn't happen */
771 elog(ERROR, "could not find ordering operator for equality operator %u",
773 tle = get_tle_by_resno(subplan->targetlist,
774 groupColIdx[groupColPos]);
776 sortcl = makeNode(SortClause);
777 sortcl->tleSortGroupRef = assignSortGroupRef(tle,
778 subplan->targetlist);
779 sortcl->sortop = sortop;
780 sortcl->nulls_first = false;
781 sortList = lappend(sortList, sortcl);
784 plan = (Plan *) make_sort_from_sortclauses(root, sortList, subplan);
785 plan = (Plan *) make_unique(plan, sortList);
788 /* Adjust output size estimate (other fields should be OK already) */
789 plan->plan_rows = best_path->rows;
795 /*****************************************************************************
797 * BASE-RELATION SCAN METHODS
799 *****************************************************************************/
803 * create_seqscan_plan
804 * Returns a seqscan plan for the base relation scanned by 'best_path'
805 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
808 create_seqscan_plan(PlannerInfo *root, Path *best_path,
809 List *tlist, List *scan_clauses)
812 Index scan_relid = best_path->parent->relid;
814 /* it should be a base rel... */
815 Assert(scan_relid > 0);
816 Assert(best_path->parent->rtekind == RTE_RELATION);
818 /* Sort clauses into best execution order */
819 scan_clauses = order_qual_clauses(root, scan_clauses);
821 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
822 scan_clauses = extract_actual_clauses(scan_clauses, false);
824 scan_plan = make_seqscan(tlist,
828 copy_path_costsize(&scan_plan->plan, best_path);
834 * create_indexscan_plan
835 * Returns an indexscan plan for the base relation scanned by 'best_path'
836 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
838 * The indexquals list of the path contains implicitly-ANDed qual conditions.
839 * The list can be empty --- then no index restrictions will be applied during
842 * If nonlossy_clauses isn't NULL, *nonlossy_clauses receives a list of the
843 * nonlossy indexquals.
846 create_indexscan_plan(PlannerInfo *root,
847 IndexPath *best_path,
850 List **nonlossy_clauses)
852 List *indexquals = best_path->indexquals;
853 Index baserelid = best_path->path.parent->relid;
854 Oid indexoid = best_path->indexinfo->indexoid;
856 List *stripped_indexquals;
857 List *fixed_indexquals;
858 List *nonlossy_indexquals;
862 IndexScan *scan_plan;
864 /* it should be a base rel... */
865 Assert(baserelid > 0);
866 Assert(best_path->path.parent->rtekind == RTE_RELATION);
869 * Build "stripped" indexquals structure (no RestrictInfos) to pass to
870 * executor as indexqualorig
872 stripped_indexquals = get_actual_clauses(indexquals);
875 * The executor needs a copy with the indexkey on the left of each clause
876 * and with index attr numbers substituted for table ones. This pass also
877 * gets strategy info and looks for "lossy" operators.
879 fix_indexqual_references(indexquals, best_path,
881 &nonlossy_indexquals,
885 /* pass back nonlossy quals if caller wants 'em */
886 if (nonlossy_clauses)
887 *nonlossy_clauses = nonlossy_indexquals;
890 * If this is an innerjoin scan, the indexclauses will contain join
891 * clauses that are not present in scan_clauses (since the passed-in value
892 * is just the rel's baserestrictinfo list). We must add these clauses to
893 * scan_clauses to ensure they get checked. In most cases we will remove
894 * the join clauses again below, but if a join clause contains a special
895 * operator, we need to make sure it gets into the scan_clauses.
897 * Note: pointer comparison should be enough to determine RestrictInfo
900 if (best_path->isjoininner)
901 scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses);
904 * The qpqual list must contain all restrictions not automatically handled
905 * by the index. All the predicates in the indexquals will be checked
906 * (either by the index itself, or by nodeIndexscan.c), but if there are
907 * any "special" operators involved then they must be included in qpqual.
908 * Also, any lossy index operators must be rechecked in the qpqual. The
909 * upshot is that qpqual must contain scan_clauses minus whatever appears
910 * in nonlossy_indexquals.
912 * In normal cases simple pointer equality checks will be enough to spot
913 * duplicate RestrictInfos, so we try that first. In some situations
914 * (particularly with OR'd index conditions) we may have scan_clauses that
915 * are not equal to, but are logically implied by, the index quals; so we
916 * also try a predicate_implied_by() check to see if we can discard quals
917 * that way. (predicate_implied_by assumes its first input contains only
918 * immutable functions, so we have to check that.)
920 * We can also discard quals that are implied by a partial index's
921 * predicate, but only in a plain SELECT; when scanning a target relation
922 * of UPDATE/DELETE/SELECT FOR UPDATE, we must leave such quals in the
923 * plan so that they'll be properly rechecked by EvalPlanQual testing.
926 foreach(l, scan_clauses)
928 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
930 Assert(IsA(rinfo, RestrictInfo));
931 if (rinfo->pseudoconstant)
932 continue; /* we may drop pseudoconstants here */
933 if (list_member_ptr(nonlossy_indexquals, rinfo))
935 if (!contain_mutable_functions((Node *) rinfo->clause))
937 List *clausel = list_make1(rinfo->clause);
939 if (predicate_implied_by(clausel, nonlossy_indexquals))
941 if (best_path->indexinfo->indpred)
943 if (baserelid != root->parse->resultRelation &&
944 get_rowmark(root->parse, baserelid) == NULL)
945 if (predicate_implied_by(clausel,
946 best_path->indexinfo->indpred))
950 qpqual = lappend(qpqual, rinfo);
953 /* Sort clauses into best execution order */
954 qpqual = order_qual_clauses(root, qpqual);
956 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
957 qpqual = extract_actual_clauses(qpqual, false);
959 /* Finally ready to build the plan node */
960 scan_plan = make_indexscan(tlist,
968 best_path->indexscandir);
970 copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
971 /* use the indexscan-specific rows estimate, not the parent rel's */
972 scan_plan->scan.plan.plan_rows = best_path->rows;
978 * create_bitmap_scan_plan
979 * Returns a bitmap scan plan for the base relation scanned by 'best_path'
980 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
982 static BitmapHeapScan *
983 create_bitmap_scan_plan(PlannerInfo *root,
984 BitmapHeapPath *best_path,
988 Index baserelid = best_path->path.parent->relid;
989 Plan *bitmapqualplan;
990 List *bitmapqualorig;
994 BitmapHeapScan *scan_plan;
996 /* it should be a base rel... */
997 Assert(baserelid > 0);
998 Assert(best_path->path.parent->rtekind == RTE_RELATION);
1000 /* Process the bitmapqual tree into a Plan tree and qual lists */
1001 bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual,
1002 &bitmapqualorig, &indexquals);
1004 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1005 scan_clauses = extract_actual_clauses(scan_clauses, false);
1008 * If this is a innerjoin scan, the indexclauses will contain join clauses
1009 * that are not present in scan_clauses (since the passed-in value is just
1010 * the rel's baserestrictinfo list). We must add these clauses to
1011 * scan_clauses to ensure they get checked. In most cases we will remove
1012 * the join clauses again below, but if a join clause contains a special
1013 * operator, we need to make sure it gets into the scan_clauses.
1015 if (best_path->isjoininner)
1017 scan_clauses = list_concat_unique(scan_clauses, bitmapqualorig);
1021 * The qpqual list must contain all restrictions not automatically handled
1022 * by the index. All the predicates in the indexquals will be checked
1023 * (either by the index itself, or by nodeBitmapHeapscan.c), but if there
1024 * are any "special" or lossy operators involved then they must be added
1025 * to qpqual. The upshot is that qpqual must contain scan_clauses minus
1026 * whatever appears in indexquals.
1028 * In normal cases simple equal() checks will be enough to spot duplicate
1029 * clauses, so we try that first. In some situations (particularly with
1030 * OR'd index conditions) we may have scan_clauses that are not equal to,
1031 * but are logically implied by, the index quals; so we also try a
1032 * predicate_implied_by() check to see if we can discard quals that way.
1033 * (predicate_implied_by assumes its first input contains only immutable
1034 * functions, so we have to check that.)
1036 * Unlike create_indexscan_plan(), we need take no special thought here
1037 * for partial index predicates; this is because the predicate conditions
1038 * are already listed in bitmapqualorig and indexquals. Bitmap scans have
1039 * to do it that way because predicate conditions need to be rechecked if
1040 * the scan becomes lossy.
1043 foreach(l, scan_clauses)
1045 Node *clause = (Node *) lfirst(l);
1047 if (list_member(indexquals, clause))
1049 if (!contain_mutable_functions(clause))
1051 List *clausel = list_make1(clause);
1053 if (predicate_implied_by(clausel, indexquals))
1056 qpqual = lappend(qpqual, clause);
1059 /* Sort clauses into best execution order */
1060 qpqual = order_qual_clauses(root, qpqual);
1063 * When dealing with special or lossy operators, we will at this point
1064 * have duplicate clauses in qpqual and bitmapqualorig. We may as well
1065 * drop 'em from bitmapqualorig, since there's no point in making the
1068 bitmapqualorig = list_difference_ptr(bitmapqualorig, qpqual);
1070 /* Finally ready to build the plan node */
1071 scan_plan = make_bitmap_heapscan(tlist,
1077 copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1078 /* use the indexscan-specific rows estimate, not the parent rel's */
1079 scan_plan->scan.plan.plan_rows = best_path->rows;
1085 * Given a bitmapqual tree, generate the Plan tree that implements it
1087 * As byproducts, we also return in *qual and *indexqual the qual lists
1088 * (in implicit-AND form, without RestrictInfos) describing the original index
1089 * conditions and the generated indexqual conditions. The latter is made to
1090 * exclude lossy index operators. Both lists include partial-index predicates,
1091 * because we have to recheck predicates as well as index conditions if the
1092 * bitmap scan becomes lossy.
1094 * Note: if you find yourself changing this, you probably need to change
1095 * make_restrictinfo_from_bitmapqual too.
1098 create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
1099 List **qual, List **indexqual)
1103 if (IsA(bitmapqual, BitmapAndPath))
1105 BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
1106 List *subplans = NIL;
1107 List *subquals = NIL;
1108 List *subindexquals = NIL;
1112 * There may well be redundant quals among the subplans, since a
1113 * top-level WHERE qual might have gotten used to form several
1114 * different index quals. We don't try exceedingly hard to eliminate
1115 * redundancies, but we do eliminate obvious duplicates by using
1116 * list_concat_unique.
1118 foreach(l, apath->bitmapquals)
1124 subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1125 &subqual, &subindexqual);
1126 subplans = lappend(subplans, subplan);
1127 subquals = list_concat_unique(subquals, subqual);
1128 subindexquals = list_concat_unique(subindexquals, subindexqual);
1130 plan = (Plan *) make_bitmap_and(subplans);
1131 plan->startup_cost = apath->path.startup_cost;
1132 plan->total_cost = apath->path.total_cost;
1134 clamp_row_est(apath->bitmapselectivity * apath->path.parent->tuples);
1135 plan->plan_width = 0; /* meaningless */
1137 *indexqual = subindexquals;
1139 else if (IsA(bitmapqual, BitmapOrPath))
1141 BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
1142 List *subplans = NIL;
1143 List *subquals = NIL;
1144 List *subindexquals = NIL;
1145 bool const_true_subqual = false;
1146 bool const_true_subindexqual = false;
1150 * Here, we only detect qual-free subplans. A qual-free subplan would
1151 * cause us to generate "... OR true ..." which we may as well reduce
1152 * to just "true". We do not try to eliminate redundant subclauses
1153 * because (a) it's not as likely as in the AND case, and (b) we might
1154 * well be working with hundreds or even thousands of OR conditions,
1155 * perhaps from a long IN list. The performance of list_append_unique
1156 * would be unacceptable.
1158 foreach(l, opath->bitmapquals)
1164 subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1165 &subqual, &subindexqual);
1166 subplans = lappend(subplans, subplan);
1168 const_true_subqual = true;
1169 else if (!const_true_subqual)
1170 subquals = lappend(subquals,
1171 make_ands_explicit(subqual));
1172 if (subindexqual == NIL)
1173 const_true_subindexqual = true;
1174 else if (!const_true_subindexqual)
1175 subindexquals = lappend(subindexquals,
1176 make_ands_explicit(subindexqual));
1180 * In the presence of ScalarArrayOpExpr quals, we might have built
1181 * BitmapOrPaths with just one subpath; don't add an OR step.
1183 if (list_length(subplans) == 1)
1185 plan = (Plan *) linitial(subplans);
1189 plan = (Plan *) make_bitmap_or(subplans);
1190 plan->startup_cost = opath->path.startup_cost;
1191 plan->total_cost = opath->path.total_cost;
1193 clamp_row_est(opath->bitmapselectivity * opath->path.parent->tuples);
1194 plan->plan_width = 0; /* meaningless */
1198 * If there were constant-TRUE subquals, the OR reduces to constant
1199 * TRUE. Also, avoid generating one-element ORs, which could happen
1200 * due to redundancy elimination or ScalarArrayOpExpr quals.
1202 if (const_true_subqual)
1204 else if (list_length(subquals) <= 1)
1207 *qual = list_make1(make_orclause(subquals));
1208 if (const_true_subindexqual)
1210 else if (list_length(subindexquals) <= 1)
1211 *indexqual = subindexquals;
1213 *indexqual = list_make1(make_orclause(subindexquals));
1215 else if (IsA(bitmapqual, IndexPath))
1217 IndexPath *ipath = (IndexPath *) bitmapqual;
1219 List *nonlossy_clauses;
1222 /* Use the regular indexscan plan build machinery... */
1223 iscan = create_indexscan_plan(root, ipath, NIL, NIL,
1225 /* then convert to a bitmap indexscan */
1226 plan = (Plan *) make_bitmap_indexscan(iscan->scan.scanrelid,
1229 iscan->indexqualorig,
1230 iscan->indexstrategy,
1231 iscan->indexsubtype);
1232 plan->startup_cost = 0.0;
1233 plan->total_cost = ipath->indextotalcost;
1235 clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
1236 plan->plan_width = 0; /* meaningless */
1237 *qual = get_actual_clauses(ipath->indexclauses);
1238 *indexqual = get_actual_clauses(nonlossy_clauses);
1239 foreach(l, ipath->indexinfo->indpred)
1241 Expr *pred = (Expr *) lfirst(l);
1244 * We know that the index predicate must have been implied by the
1245 * query condition as a whole, but it may or may not be implied by
1246 * the conditions that got pushed into the bitmapqual. Avoid
1247 * generating redundant conditions.
1249 if (!predicate_implied_by(list_make1(pred), ipath->indexclauses))
1251 *qual = lappend(*qual, pred);
1252 *indexqual = lappend(*indexqual, pred);
1258 elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
1259 plan = NULL; /* keep compiler quiet */
1266 * create_tidscan_plan
1267 * Returns a tidscan plan for the base relation scanned by 'best_path'
1268 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1271 create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
1272 List *tlist, List *scan_clauses)
1275 Index scan_relid = best_path->path.parent->relid;
1278 /* it should be a base rel... */
1279 Assert(scan_relid > 0);
1280 Assert(best_path->path.parent->rtekind == RTE_RELATION);
1282 /* Sort clauses into best execution order */
1283 scan_clauses = order_qual_clauses(root, scan_clauses);
1285 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1286 scan_clauses = extract_actual_clauses(scan_clauses, false);
1289 * Remove any clauses that are TID quals. This is a bit tricky since the
1290 * tidquals list has implicit OR semantics.
1292 ortidquals = best_path->tidquals;
1293 if (list_length(ortidquals) > 1)
1294 ortidquals = list_make1(make_orclause(ortidquals));
1295 scan_clauses = list_difference(scan_clauses, ortidquals);
1297 scan_plan = make_tidscan(tlist,
1300 best_path->tidquals);
1302 copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1308 * create_subqueryscan_plan
1309 * Returns a subqueryscan plan for the base relation scanned by 'best_path'
1310 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1312 static SubqueryScan *
1313 create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
1314 List *tlist, List *scan_clauses)
1316 SubqueryScan *scan_plan;
1317 Index scan_relid = best_path->parent->relid;
1319 /* it should be a subquery base rel... */
1320 Assert(scan_relid > 0);
1321 Assert(best_path->parent->rtekind == RTE_SUBQUERY);
1323 /* Sort clauses into best execution order */
1324 scan_clauses = order_qual_clauses(root, scan_clauses);
1326 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1327 scan_clauses = extract_actual_clauses(scan_clauses, false);
1329 scan_plan = make_subqueryscan(tlist,
1332 best_path->parent->subplan,
1333 best_path->parent->subrtable);
1335 copy_path_costsize(&scan_plan->scan.plan, best_path);
1341 * create_functionscan_plan
1342 * Returns a functionscan plan for the base relation scanned by 'best_path'
1343 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1345 static FunctionScan *
1346 create_functionscan_plan(PlannerInfo *root, Path *best_path,
1347 List *tlist, List *scan_clauses)
1349 FunctionScan *scan_plan;
1350 Index scan_relid = best_path->parent->relid;
1353 /* it should be a function base rel... */
1354 Assert(scan_relid > 0);
1355 rte = rt_fetch(scan_relid, root->parse->rtable);
1356 Assert(rte->rtekind == RTE_FUNCTION);
1358 /* Sort clauses into best execution order */
1359 scan_clauses = order_qual_clauses(root, scan_clauses);
1361 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1362 scan_clauses = extract_actual_clauses(scan_clauses, false);
1364 scan_plan = make_functionscan(tlist, scan_clauses, scan_relid,
1366 rte->eref->colnames,
1368 rte->funccoltypmods);
1370 copy_path_costsize(&scan_plan->scan.plan, best_path);
1376 * create_valuesscan_plan
1377 * Returns a valuesscan plan for the base relation scanned by 'best_path'
1378 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1381 create_valuesscan_plan(PlannerInfo *root, Path *best_path,
1382 List *tlist, List *scan_clauses)
1384 ValuesScan *scan_plan;
1385 Index scan_relid = best_path->parent->relid;
1388 /* it should be a values base rel... */
1389 Assert(scan_relid > 0);
1390 rte = rt_fetch(scan_relid, root->parse->rtable);
1391 Assert(rte->rtekind == RTE_VALUES);
1393 /* Sort clauses into best execution order */
1394 scan_clauses = order_qual_clauses(root, scan_clauses);
1396 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1397 scan_clauses = extract_actual_clauses(scan_clauses, false);
1399 scan_plan = make_valuesscan(tlist, scan_clauses, scan_relid,
1402 copy_path_costsize(&scan_plan->scan.plan, best_path);
1407 /*****************************************************************************
1411 *****************************************************************************/
1414 create_nestloop_plan(PlannerInfo *root,
1415 NestPath *best_path,
1419 List *tlist = build_relation_tlist(best_path->path.parent);
1420 List *joinrestrictclauses = best_path->joinrestrictinfo;
1423 NestLoop *join_plan;
1425 if (IsA(best_path->innerjoinpath, IndexPath))
1428 * An index is being used to reduce the number of tuples scanned in
1429 * the inner relation. If there are join clauses being used with the
1430 * index, we may remove those join clauses from the list of clauses
1431 * that have to be checked as qpquals at the join node.
1433 * We can also remove any join clauses that are redundant with those
1434 * being used in the index scan; this check is needed because
1435 * find_eclass_clauses_for_index_join() may emit different clauses
1436 * than generate_join_implied_equalities() did.
1438 * We can skip this if the index path is an ordinary indexpath and not
1439 * a special innerjoin path, since it then wouldn't be using any join
1442 IndexPath *innerpath = (IndexPath *) best_path->innerjoinpath;
1444 if (innerpath->isjoininner)
1445 joinrestrictclauses =
1446 select_nonredundant_join_clauses(root,
1447 joinrestrictclauses,
1448 innerpath->indexclauses);
1450 else if (IsA(best_path->innerjoinpath, BitmapHeapPath))
1453 * Same deal for bitmapped index scans.
1455 * Note: both here and above, we ignore any implicit index
1456 * restrictions associated with the use of partial indexes. This is
1457 * OK because we're only trying to prove we can dispense with some
1458 * join quals; failing to prove that doesn't result in an incorrect
1459 * plan. It is the right way to proceed because adding more quals to
1460 * the stuff we got from the original query would just make it harder
1461 * to detect duplication. (Also, to change this we'd have to be wary
1462 * of UPDATE/DELETE/SELECT FOR UPDATE target relations; see notes
1463 * above about EvalPlanQual.)
1465 BitmapHeapPath *innerpath = (BitmapHeapPath *) best_path->innerjoinpath;
1467 if (innerpath->isjoininner)
1469 List *bitmapclauses;
1472 make_restrictinfo_from_bitmapqual(innerpath->bitmapqual,
1475 joinrestrictclauses =
1476 select_nonredundant_join_clauses(root,
1477 joinrestrictclauses,
1482 /* Sort join qual clauses into best execution order */
1483 joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
1485 /* Get the join qual clauses (in plain expression form) */
1486 /* Any pseudoconstant clauses are ignored here */
1487 if (IS_OUTER_JOIN(best_path->jointype))
1489 extract_actual_join_clauses(joinrestrictclauses,
1490 &joinclauses, &otherclauses);
1494 /* We can treat all clauses alike for an inner join */
1495 joinclauses = extract_actual_clauses(joinrestrictclauses, false);
1499 join_plan = make_nestloop(tlist,
1504 best_path->jointype);
1506 copy_path_costsize(&join_plan->join.plan, &best_path->path);
1512 create_mergejoin_plan(PlannerInfo *root,
1513 MergePath *best_path,
1517 List *tlist = build_relation_tlist(best_path->jpath.path.parent);
1521 List *outerpathkeys;
1522 List *innerpathkeys;
1525 int *mergestrategies;
1526 bool *mergenullsfirst;
1527 MergeJoin *join_plan;
1529 EquivalenceClass *lastoeclass;
1530 EquivalenceClass *lastieclass;
1537 /* Sort join qual clauses into best execution order */
1538 /* NB: do NOT reorder the mergeclauses */
1539 joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
1541 /* Get the join qual clauses (in plain expression form) */
1542 /* Any pseudoconstant clauses are ignored here */
1543 if (IS_OUTER_JOIN(best_path->jpath.jointype))
1545 extract_actual_join_clauses(joinclauses,
1546 &joinclauses, &otherclauses);
1550 /* We can treat all clauses alike for an inner join */
1551 joinclauses = extract_actual_clauses(joinclauses, false);
1556 * Remove the mergeclauses from the list of join qual clauses, leaving the
1557 * list of quals that must be checked as qpquals.
1559 mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
1560 joinclauses = list_difference(joinclauses, mergeclauses);
1563 * Rearrange mergeclauses, if needed, so that the outer variable is always
1564 * on the left; mark the mergeclause restrictinfos with correct
1565 * outer_is_left status.
1567 mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
1568 best_path->jpath.outerjoinpath->parent->relids);
1571 * Create explicit sort nodes for the outer and inner join paths if
1572 * necessary. The sort cost was already accounted for in the path. Make
1573 * sure there are no excess columns in the inputs if sorting.
1575 if (best_path->outersortkeys)
1577 disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
1578 outer_plan = (Plan *)
1579 make_sort_from_pathkeys(root,
1581 best_path->outersortkeys);
1582 outerpathkeys = best_path->outersortkeys;
1585 outerpathkeys = best_path->jpath.outerjoinpath->pathkeys;
1587 if (best_path->innersortkeys)
1589 disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1590 inner_plan = (Plan *)
1591 make_sort_from_pathkeys(root,
1593 best_path->innersortkeys);
1594 innerpathkeys = best_path->innersortkeys;
1597 innerpathkeys = best_path->jpath.innerjoinpath->pathkeys;
1600 * Compute the opfamily/strategy/nullsfirst arrays needed by the executor.
1601 * The information is in the pathkeys for the two inputs, but we need to
1602 * be careful about the possibility of mergeclauses sharing a pathkey
1603 * (compare find_mergeclauses_for_pathkeys()).
1605 nClauses = list_length(mergeclauses);
1606 Assert(nClauses == list_length(best_path->path_mergeclauses));
1607 mergefamilies = (Oid *) palloc(nClauses * sizeof(Oid));
1608 mergestrategies = (int *) palloc(nClauses * sizeof(int));
1609 mergenullsfirst = (bool *) palloc(nClauses * sizeof(bool));
1615 lop = list_head(outerpathkeys);
1616 lip = list_head(innerpathkeys);
1618 foreach(lc, best_path->path_mergeclauses)
1620 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1621 EquivalenceClass *oeclass;
1622 EquivalenceClass *ieclass;
1624 /* fetch outer/inner eclass from mergeclause */
1625 Assert(IsA(rinfo, RestrictInfo));
1626 if (rinfo->outer_is_left)
1628 oeclass = rinfo->left_ec;
1629 ieclass = rinfo->right_ec;
1633 oeclass = rinfo->right_ec;
1634 ieclass = rinfo->left_ec;
1636 Assert(oeclass != NULL);
1637 Assert(ieclass != NULL);
1639 /* should match current or next pathkeys */
1640 /* we check this carefully for debugging reasons */
1641 if (oeclass != lastoeclass)
1644 elog(ERROR, "too few pathkeys for mergeclauses");
1645 opathkey = (PathKey *) lfirst(lop);
1647 lastoeclass = opathkey->pk_eclass;
1648 if (oeclass != lastoeclass)
1649 elog(ERROR, "outer pathkeys do not match mergeclause");
1651 if (ieclass != lastieclass)
1654 elog(ERROR, "too few pathkeys for mergeclauses");
1655 ipathkey = (PathKey *) lfirst(lip);
1657 lastieclass = ipathkey->pk_eclass;
1658 if (ieclass != lastieclass)
1659 elog(ERROR, "inner pathkeys do not match mergeclause");
1661 /* pathkeys should match each other too (more debugging) */
1662 if (opathkey->pk_opfamily != ipathkey->pk_opfamily ||
1663 opathkey->pk_strategy != ipathkey->pk_strategy ||
1664 opathkey->pk_nulls_first != ipathkey->pk_nulls_first)
1665 elog(ERROR, "left and right pathkeys do not match in mergejoin");
1667 /* OK, save info for executor */
1668 mergefamilies[i] = opathkey->pk_opfamily;
1669 mergestrategies[i] = opathkey->pk_strategy;
1670 mergenullsfirst[i] = opathkey->pk_nulls_first;
1676 * Now we can build the mergejoin node.
1678 join_plan = make_mergejoin(tlist,
1687 best_path->jpath.jointype);
1689 copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1695 create_hashjoin_plan(PlannerInfo *root,
1696 HashPath *best_path,
1700 List *tlist = build_relation_tlist(best_path->jpath.path.parent);
1704 HashJoin *join_plan;
1707 /* Sort join qual clauses into best execution order */
1708 joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
1709 /* There's no point in sorting the hash clauses ... */
1711 /* Get the join qual clauses (in plain expression form) */
1712 /* Any pseudoconstant clauses are ignored here */
1713 if (IS_OUTER_JOIN(best_path->jpath.jointype))
1715 extract_actual_join_clauses(joinclauses,
1716 &joinclauses, &otherclauses);
1720 /* We can treat all clauses alike for an inner join */
1721 joinclauses = extract_actual_clauses(joinclauses, false);
1726 * Remove the hashclauses from the list of join qual clauses, leaving the
1727 * list of quals that must be checked as qpquals.
1729 hashclauses = get_actual_clauses(best_path->path_hashclauses);
1730 joinclauses = list_difference(joinclauses, hashclauses);
1733 * Rearrange hashclauses, if needed, so that the outer variable is always
1736 hashclauses = get_switched_clauses(best_path->path_hashclauses,
1737 best_path->jpath.outerjoinpath->parent->relids);
1739 /* We don't want any excess columns in the hashed tuples */
1740 disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1743 * Build the hash node and hash join node.
1745 hash_plan = make_hash(inner_plan);
1746 join_plan = make_hashjoin(tlist,
1752 best_path->jpath.jointype);
1754 copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1760 /*****************************************************************************
1762 * SUPPORTING ROUTINES
1764 *****************************************************************************/
1767 * fix_indexqual_references
1768 * Adjust indexqual clauses to the form the executor's indexqual
1769 * machinery needs, and check for recheckable (lossy) index conditions.
1771 * We have five tasks here:
1772 * * Remove RestrictInfo nodes from the input clauses.
1773 * * Index keys must be represented by Var nodes with varattno set to the
1774 * index's attribute number, not the attribute number in the original rel.
1775 * * If the index key is on the right, commute the clause to put it on the
1777 * * We must construct lists of operator strategy numbers and subtypes
1778 * for the top-level operators of each index clause.
1779 * * We must detect any lossy index operators. The API is that we return
1780 * a list of the input clauses whose operators are NOT lossy.
1782 * fixed_indexquals receives a modified copy of the indexquals list --- the
1783 * original is not changed. Note also that the copy shares no substructure
1784 * with the original; this is needed in case there is a subplan in it (we need
1785 * two separate copies of the subplan tree, or things will go awry).
1787 * nonlossy_indexquals receives a list of the original input clauses (with
1788 * RestrictInfos) that contain non-lossy operators.
1790 * indexstrategy receives an integer list of strategy numbers.
1791 * indexsubtype receives an OID list of strategy subtypes.
1794 fix_indexqual_references(List *indexquals, IndexPath *index_path,
1795 List **fixed_indexquals,
1796 List **nonlossy_indexquals,
1797 List **indexstrategy,
1798 List **indexsubtype)
1800 IndexOptInfo *index = index_path->indexinfo;
1803 *fixed_indexquals = NIL;
1804 *nonlossy_indexquals = NIL;
1805 *indexstrategy = NIL;
1806 *indexsubtype = NIL;
1809 * For each qual clause, commute if needed to put the indexkey operand on
1810 * the left, and then fix its varattno. (We do not need to change the
1811 * other side of the clause.) Then determine the operator's strategy
1812 * number and subtype number, and check for lossy index behavior.
1814 foreach(l, indexquals)
1816 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1825 Assert(IsA(rinfo, RestrictInfo));
1828 * Make a copy that will become the fixed clause.
1830 * We used to try to do a shallow copy here, but that fails if there
1831 * is a subplan in the arguments of the opclause. So just do a full
1834 clause = (Expr *) copyObject((Node *) rinfo->clause);
1836 if (IsA(clause, OpExpr))
1838 OpExpr *op = (OpExpr *) clause;
1840 if (list_length(op->args) != 2)
1841 elog(ERROR, "indexqual clause is not binary opclause");
1844 * Check to see if the indexkey is on the right; if so, commute
1845 * the clause. The indexkey should be the side that refers to
1846 * (only) the base relation.
1848 if (!bms_equal(rinfo->left_relids, index->rel->relids))
1852 * Now, determine which index attribute this is, change the
1853 * indexkey operand as needed, and get the index opfamily.
1855 linitial(op->args) = fix_indexqual_operand(linitial(op->args),
1858 clause_op = op->opno;
1860 else if (IsA(clause, RowCompareExpr))
1862 RowCompareExpr *rc = (RowCompareExpr *) clause;
1866 * Check to see if the indexkey is on the right; if so, commute
1867 * the clause. The indexkey should be the side that refers to
1868 * (only) the base relation.
1870 if (!bms_overlap(pull_varnos(linitial(rc->largs)),
1871 index->rel->relids))
1872 CommuteRowCompareExpr(rc);
1875 * For each column in the row comparison, determine which index
1876 * attribute this is and change the indexkey operand as needed.
1878 * Save the index opfamily for only the first column. We will
1879 * return the operator and opfamily info for just the first column
1880 * of the row comparison; the executor will have to look up the
1881 * rest if it needs them.
1883 foreach(lc, rc->largs)
1887 lfirst(lc) = fix_indexqual_operand(lfirst(lc),
1890 if (lc == list_head(rc->largs))
1891 opfamily = tmp_opfamily;
1893 clause_op = linitial_oid(rc->opnos);
1895 else if (IsA(clause, ScalarArrayOpExpr))
1897 ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
1899 /* Never need to commute... */
1902 * Now, determine which index attribute this is, change the
1903 * indexkey operand as needed, and get the index opfamily.
1905 linitial(saop->args) = fix_indexqual_operand(linitial(saop->args),
1908 clause_op = saop->opno;
1912 elog(ERROR, "unsupported indexqual type: %d",
1913 (int) nodeTag(clause));
1914 continue; /* keep compiler quiet */
1917 *fixed_indexquals = lappend(*fixed_indexquals, clause);
1920 * Look up the (possibly commuted) operator in the operator family to
1921 * get its strategy number and the recheck indicator. This also
1922 * double-checks that we found an operator matching the index.
1924 get_op_opfamily_properties(clause_op, opfamily,
1930 *indexstrategy = lappend_int(*indexstrategy, stratno);
1931 *indexsubtype = lappend_oid(*indexsubtype, stratrighttype);
1933 /* If it's not lossy, add to nonlossy_indexquals */
1935 *nonlossy_indexquals = lappend(*nonlossy_indexquals, rinfo);
1940 fix_indexqual_operand(Node *node, IndexOptInfo *index, Oid *opfamily)
1943 * We represent index keys by Var nodes having the varno of the base table
1944 * but varattno equal to the index's attribute number (index column
1945 * position). This is a bit hokey ... would be cleaner to use a
1946 * special-purpose node type that could not be mistaken for a regular Var.
1947 * But it will do for now.
1951 ListCell *indexpr_item;
1954 * Remove any binary-compatible relabeling of the indexkey
1956 if (IsA(node, RelabelType))
1957 node = (Node *) ((RelabelType *) node)->arg;
1959 if (IsA(node, Var) &&
1960 ((Var *) node)->varno == index->rel->relid)
1962 /* Try to match against simple index columns */
1963 int varatt = ((Var *) node)->varattno;
1967 for (pos = 0; pos < index->ncolumns; pos++)
1969 if (index->indexkeys[pos] == varatt)
1971 result = (Var *) copyObject(node);
1972 result->varattno = pos + 1;
1973 /* return the correct opfamily, too */
1974 *opfamily = index->opfamily[pos];
1975 return (Node *) result;
1981 /* Try to match against index expressions */
1982 indexpr_item = list_head(index->indexprs);
1983 for (pos = 0; pos < index->ncolumns; pos++)
1985 if (index->indexkeys[pos] == 0)
1989 if (indexpr_item == NULL)
1990 elog(ERROR, "too few entries in indexprs list");
1991 indexkey = (Node *) lfirst(indexpr_item);
1992 if (indexkey && IsA(indexkey, RelabelType))
1993 indexkey = (Node *) ((RelabelType *) indexkey)->arg;
1994 if (equal(node, indexkey))
1997 result = makeVar(index->rel->relid, pos + 1,
1998 exprType(lfirst(indexpr_item)), -1,
2000 /* return the correct opfamily, too */
2001 *opfamily = index->opfamily[pos];
2002 return (Node *) result;
2004 indexpr_item = lnext(indexpr_item);
2009 elog(ERROR, "node is not an index attribute");
2010 *opfamily = InvalidOid; /* keep compiler quiet */
2015 * get_switched_clauses
2016 * Given a list of merge or hash joinclauses (as RestrictInfo nodes),
2017 * extract the bare clauses, and rearrange the elements within the
2018 * clauses, if needed, so the outer join variable is on the left and
2019 * the inner is on the right. The original clause data structure is not
2020 * touched; a modified list is returned. We do, however, set the transient
2021 * outer_is_left field in each RestrictInfo to show which side was which.
2024 get_switched_clauses(List *clauses, Relids outerrelids)
2031 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2032 OpExpr *clause = (OpExpr *) restrictinfo->clause;
2034 Assert(is_opclause(clause));
2035 if (bms_is_subset(restrictinfo->right_relids, outerrelids))
2038 * Duplicate just enough of the structure to allow commuting the
2039 * clause without changing the original list. Could use
2040 * copyObject, but a complete deep copy is overkill.
2042 OpExpr *temp = makeNode(OpExpr);
2044 temp->opno = clause->opno;
2045 temp->opfuncid = InvalidOid;
2046 temp->opresulttype = clause->opresulttype;
2047 temp->opretset = clause->opretset;
2048 temp->args = list_copy(clause->args);
2049 /* Commute it --- note this modifies the temp node in-place. */
2050 CommuteOpExpr(temp);
2051 t_list = lappend(t_list, temp);
2052 restrictinfo->outer_is_left = false;
2056 Assert(bms_is_subset(restrictinfo->left_relids, outerrelids));
2057 t_list = lappend(t_list, clause);
2058 restrictinfo->outer_is_left = true;
2065 * order_qual_clauses
2066 * Given a list of qual clauses that will all be evaluated at the same
2067 * plan node, sort the list into the order we want to check the quals
2070 * Ideally the order should be driven by a combination of execution cost and
2071 * selectivity, but it's not immediately clear how to account for both,
2072 * and given the uncertainty of the estimates the reliability of the decisions
2073 * would be doubtful anyway. So we just order by estimated per-tuple cost,
2074 * being careful not to change the order when (as is often the case) the
2075 * estimates are identical.
2077 * Although this will work on either bare clauses or RestrictInfos, it's
2078 * much faster to apply it to RestrictInfos, since it can re-use cost
2079 * information that is cached in RestrictInfos.
2081 * Note: some callers pass lists that contain entries that will later be
2082 * removed; this is the easiest way to let this routine see RestrictInfos
2083 * instead of bare clauses. It's OK because we only sort by cost, but
2084 * a cost/selectivity combination would likely do the wrong thing.
2087 order_qual_clauses(PlannerInfo *root, List *clauses)
2094 int nitems = list_length(clauses);
2100 /* No need to work hard for 0 or 1 clause */
2105 * Collect the items and costs into an array. This is to avoid repeated
2106 * cost_qual_eval work if the inputs aren't RestrictInfos.
2108 items = (QualItem *) palloc(nitems * sizeof(QualItem));
2110 foreach(lc, clauses)
2112 Node *clause = (Node *) lfirst(lc);
2115 cost_qual_eval_node(&qcost, clause, root);
2116 items[i].clause = clause;
2117 items[i].cost = qcost.per_tuple;
2122 * Sort. We don't use qsort() because it's not guaranteed stable for
2123 * equal keys. The expected number of entries is small enough that
2124 * a simple insertion sort should be good enough.
2126 for (i = 1; i < nitems; i++)
2128 QualItem newitem = items[i];
2131 /* insert newitem into the already-sorted subarray */
2132 for (j = i; j > 0; j--)
2134 if (newitem.cost >= items[j-1].cost)
2136 items[j] = items[j-1];
2141 /* Convert back to a list */
2143 for (i = 0; i < nitems; i++)
2144 result = lappend(result, items[i].clause);
2150 * Copy cost and size info from a Path node to the Plan node created from it.
2151 * The executor won't use this info, but it's needed by EXPLAIN.
2154 copy_path_costsize(Plan *dest, Path *src)
2158 dest->startup_cost = src->startup_cost;
2159 dest->total_cost = src->total_cost;
2160 dest->plan_rows = src->parent->rows;
2161 dest->plan_width = src->parent->width;
2165 dest->startup_cost = 0;
2166 dest->total_cost = 0;
2167 dest->plan_rows = 0;
2168 dest->plan_width = 0;
2173 * Copy cost and size info from a lower plan node to an inserted node.
2174 * This is not critical, since the decisions have already been made,
2175 * but it helps produce more reasonable-looking EXPLAIN output.
2176 * (Some callers alter the info after copying it.)
2179 copy_plan_costsize(Plan *dest, Plan *src)
2183 dest->startup_cost = src->startup_cost;
2184 dest->total_cost = src->total_cost;
2185 dest->plan_rows = src->plan_rows;
2186 dest->plan_width = src->plan_width;
2190 dest->startup_cost = 0;
2191 dest->total_cost = 0;
2192 dest->plan_rows = 0;
2193 dest->plan_width = 0;
2198 /*****************************************************************************
2200 * PLAN NODE BUILDING ROUTINES
2202 * Some of these are exported because they are called to build plan nodes
2203 * in contexts where we're not deriving the plan node from a path node.
2205 *****************************************************************************/
2208 make_seqscan(List *qptlist,
2212 SeqScan *node = makeNode(SeqScan);
2213 Plan *plan = &node->plan;
2215 /* cost should be inserted by caller */
2216 plan->targetlist = qptlist;
2217 plan->qual = qpqual;
2218 plan->lefttree = NULL;
2219 plan->righttree = NULL;
2220 node->scanrelid = scanrelid;
2226 make_indexscan(List *qptlist,
2231 List *indexqualorig,
2232 List *indexstrategy,
2234 ScanDirection indexscandir)
2236 IndexScan *node = makeNode(IndexScan);
2237 Plan *plan = &node->scan.plan;
2239 /* cost should be inserted by caller */
2240 plan->targetlist = qptlist;
2241 plan->qual = qpqual;
2242 plan->lefttree = NULL;
2243 plan->righttree = NULL;
2244 node->scan.scanrelid = scanrelid;
2245 node->indexid = indexid;
2246 node->indexqual = indexqual;
2247 node->indexqualorig = indexqualorig;
2248 node->indexstrategy = indexstrategy;
2249 node->indexsubtype = indexsubtype;
2250 node->indexorderdir = indexscandir;
2255 static BitmapIndexScan *
2256 make_bitmap_indexscan(Index scanrelid,
2259 List *indexqualorig,
2260 List *indexstrategy,
2263 BitmapIndexScan *node = makeNode(BitmapIndexScan);
2264 Plan *plan = &node->scan.plan;
2266 /* cost should be inserted by caller */
2267 plan->targetlist = NIL; /* not used */
2268 plan->qual = NIL; /* not used */
2269 plan->lefttree = NULL;
2270 plan->righttree = NULL;
2271 node->scan.scanrelid = scanrelid;
2272 node->indexid = indexid;
2273 node->indexqual = indexqual;
2274 node->indexqualorig = indexqualorig;
2275 node->indexstrategy = indexstrategy;
2276 node->indexsubtype = indexsubtype;
2281 static BitmapHeapScan *
2282 make_bitmap_heapscan(List *qptlist,
2285 List *bitmapqualorig,
2288 BitmapHeapScan *node = makeNode(BitmapHeapScan);
2289 Plan *plan = &node->scan.plan;
2291 /* cost should be inserted by caller */
2292 plan->targetlist = qptlist;
2293 plan->qual = qpqual;
2294 plan->lefttree = lefttree;
2295 plan->righttree = NULL;
2296 node->scan.scanrelid = scanrelid;
2297 node->bitmapqualorig = bitmapqualorig;
2303 make_tidscan(List *qptlist,
2308 TidScan *node = makeNode(TidScan);
2309 Plan *plan = &node->scan.plan;
2311 /* cost should be inserted by caller */
2312 plan->targetlist = qptlist;
2313 plan->qual = qpqual;
2314 plan->lefttree = NULL;
2315 plan->righttree = NULL;
2316 node->scan.scanrelid = scanrelid;
2317 node->tidquals = tidquals;
2323 make_subqueryscan(List *qptlist,
2329 SubqueryScan *node = makeNode(SubqueryScan);
2330 Plan *plan = &node->scan.plan;
2333 * Cost is figured here for the convenience of prepunion.c. Note this is
2334 * only correct for the case where qpqual is empty; otherwise caller
2335 * should overwrite cost with a better estimate.
2337 copy_plan_costsize(plan, subplan);
2338 plan->total_cost += cpu_tuple_cost * subplan->plan_rows;
2340 plan->targetlist = qptlist;
2341 plan->qual = qpqual;
2342 plan->lefttree = NULL;
2343 plan->righttree = NULL;
2344 node->scan.scanrelid = scanrelid;
2345 node->subplan = subplan;
2346 node->subrtable = subrtable;
2351 static FunctionScan *
2352 make_functionscan(List *qptlist,
2358 List *funccoltypmods)
2360 FunctionScan *node = makeNode(FunctionScan);
2361 Plan *plan = &node->scan.plan;
2363 /* cost should be inserted by caller */
2364 plan->targetlist = qptlist;
2365 plan->qual = qpqual;
2366 plan->lefttree = NULL;
2367 plan->righttree = NULL;
2368 node->scan.scanrelid = scanrelid;
2369 node->funcexpr = funcexpr;
2370 node->funccolnames = funccolnames;
2371 node->funccoltypes = funccoltypes;
2372 node->funccoltypmods = funccoltypmods;
2378 make_valuesscan(List *qptlist,
2383 ValuesScan *node = makeNode(ValuesScan);
2384 Plan *plan = &node->scan.plan;
2386 /* cost should be inserted by caller */
2387 plan->targetlist = qptlist;
2388 plan->qual = qpqual;
2389 plan->lefttree = NULL;
2390 plan->righttree = NULL;
2391 node->scan.scanrelid = scanrelid;
2392 node->values_lists = values_lists;
2398 make_append(List *appendplans, bool isTarget, List *tlist)
2400 Append *node = makeNode(Append);
2401 Plan *plan = &node->plan;
2405 * Compute cost as sum of subplan costs. We charge nothing extra for the
2406 * Append itself, which perhaps is too optimistic, but since it doesn't do
2407 * any selection or projection, it is a pretty cheap node.
2409 plan->startup_cost = 0;
2410 plan->total_cost = 0;
2411 plan->plan_rows = 0;
2412 plan->plan_width = 0;
2413 foreach(subnode, appendplans)
2415 Plan *subplan = (Plan *) lfirst(subnode);
2417 if (subnode == list_head(appendplans)) /* first node? */
2418 plan->startup_cost = subplan->startup_cost;
2419 plan->total_cost += subplan->total_cost;
2420 plan->plan_rows += subplan->plan_rows;
2421 if (plan->plan_width < subplan->plan_width)
2422 plan->plan_width = subplan->plan_width;
2425 plan->targetlist = tlist;
2427 plan->lefttree = NULL;
2428 plan->righttree = NULL;
2429 node->appendplans = appendplans;
2430 node->isTarget = isTarget;
2436 make_bitmap_and(List *bitmapplans)
2438 BitmapAnd *node = makeNode(BitmapAnd);
2439 Plan *plan = &node->plan;
2441 /* cost should be inserted by caller */
2442 plan->targetlist = NIL;
2444 plan->lefttree = NULL;
2445 plan->righttree = NULL;
2446 node->bitmapplans = bitmapplans;
2452 make_bitmap_or(List *bitmapplans)
2454 BitmapOr *node = makeNode(BitmapOr);
2455 Plan *plan = &node->plan;
2457 /* cost should be inserted by caller */
2458 plan->targetlist = NIL;
2460 plan->lefttree = NULL;
2461 plan->righttree = NULL;
2462 node->bitmapplans = bitmapplans;
2468 make_nestloop(List *tlist,
2475 NestLoop *node = makeNode(NestLoop);
2476 Plan *plan = &node->join.plan;
2478 /* cost should be inserted by caller */
2479 plan->targetlist = tlist;
2480 plan->qual = otherclauses;
2481 plan->lefttree = lefttree;
2482 plan->righttree = righttree;
2483 node->join.jointype = jointype;
2484 node->join.joinqual = joinclauses;
2490 make_hashjoin(List *tlist,
2498 HashJoin *node = makeNode(HashJoin);
2499 Plan *plan = &node->join.plan;
2501 /* cost should be inserted by caller */
2502 plan->targetlist = tlist;
2503 plan->qual = otherclauses;
2504 plan->lefttree = lefttree;
2505 plan->righttree = righttree;
2506 node->hashclauses = hashclauses;
2507 node->join.jointype = jointype;
2508 node->join.joinqual = joinclauses;
2514 make_hash(Plan *lefttree)
2516 Hash *node = makeNode(Hash);
2517 Plan *plan = &node->plan;
2519 copy_plan_costsize(plan, lefttree);
2522 * For plausibility, make startup & total costs equal total cost of input
2523 * plan; this only affects EXPLAIN display not decisions.
2525 plan->startup_cost = plan->total_cost;
2526 plan->targetlist = lefttree->targetlist;
2528 plan->lefttree = lefttree;
2529 plan->righttree = NULL;
2535 make_mergejoin(List *tlist,
2540 int *mergestrategies,
2541 bool *mergenullsfirst,
2546 MergeJoin *node = makeNode(MergeJoin);
2547 Plan *plan = &node->join.plan;
2549 /* cost should be inserted by caller */
2550 plan->targetlist = tlist;
2551 plan->qual = otherclauses;
2552 plan->lefttree = lefttree;
2553 plan->righttree = righttree;
2554 node->mergeclauses = mergeclauses;
2555 node->mergeFamilies = mergefamilies;
2556 node->mergeStrategies = mergestrategies;
2557 node->mergeNullsFirst = mergenullsfirst;
2558 node->join.jointype = jointype;
2559 node->join.joinqual = joinclauses;
2565 * make_sort --- basic routine to build a Sort plan node
2567 * Caller must have built the sortColIdx, sortOperators, and nullsFirst
2571 make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
2572 AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst)
2574 Sort *node = makeNode(Sort);
2575 Plan *plan = &node->plan;
2576 Path sort_path; /* dummy for result of cost_sort */
2578 copy_plan_costsize(plan, lefttree); /* only care about copying size */
2579 cost_sort(&sort_path, root, NIL,
2580 lefttree->total_cost,
2581 lefttree->plan_rows,
2582 lefttree->plan_width);
2583 plan->startup_cost = sort_path.startup_cost;
2584 plan->total_cost = sort_path.total_cost;
2585 plan->targetlist = lefttree->targetlist;
2587 plan->lefttree = lefttree;
2588 plan->righttree = NULL;
2589 node->numCols = numCols;
2590 node->sortColIdx = sortColIdx;
2591 node->sortOperators = sortOperators;
2592 node->nullsFirst = nullsFirst;
2598 * add_sort_column --- utility subroutine for building sort info arrays
2600 * We need this routine because the same column might be selected more than
2601 * once as a sort key column; if so, the extra mentions are redundant.
2603 * Caller is assumed to have allocated the arrays large enough for the
2604 * max possible number of columns. Return value is the new column count.
2607 add_sort_column(AttrNumber colIdx, Oid sortOp, bool nulls_first,
2608 int numCols, AttrNumber *sortColIdx,
2609 Oid *sortOperators, bool *nullsFirst)
2613 for (i = 0; i < numCols; i++)
2616 * Note: we check sortOp because it's conceivable that "ORDER BY
2617 * foo USING <, foo USING <<<" is not redundant, if <<< distinguishes
2618 * values that < considers equal. We need not check nulls_first
2619 * however because a lower-order column with the same sortop but
2620 * opposite nulls direction is redundant.
2622 if (sortColIdx[i] == colIdx &&
2623 sortOperators[numCols] == sortOp)
2625 /* Already sorting by this col, so extra sort key is useless */
2630 /* Add the column */
2631 sortColIdx[numCols] = colIdx;
2632 sortOperators[numCols] = sortOp;
2633 nullsFirst[numCols] = nulls_first;
2638 * make_sort_from_pathkeys
2639 * Create sort plan to sort according to given pathkeys
2641 * 'lefttree' is the node which yields input tuples
2642 * 'pathkeys' is the list of pathkeys by which the result is to be sorted
2644 * We must convert the pathkey information into arrays of sort key column
2645 * numbers and sort operator OIDs.
2647 * If the pathkeys include expressions that aren't simple Vars, we will
2648 * usually need to add resjunk items to the input plan's targetlist to
2649 * compute these expressions (since the Sort node itself won't do it).
2650 * If the input plan type isn't one that can do projections, this means
2651 * adding a Result node just to do the projection.
2654 make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys)
2656 List *tlist = lefttree->targetlist;
2659 AttrNumber *sortColIdx;
2664 * We will need at most list_length(pathkeys) sort columns; possibly less
2666 numsortkeys = list_length(pathkeys);
2667 sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2668 sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2669 nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
2673 foreach(i, pathkeys)
2675 PathKey *pathkey = (PathKey *) lfirst(i);
2676 TargetEntry *tle = NULL;
2677 Oid pk_datatype = InvalidOid;
2682 * We can sort by any non-constant expression listed in the pathkey's
2683 * EquivalenceClass. For now, we take the first one that corresponds
2684 * to an available Var in the tlist. If there isn't any, use the first
2685 * one that is an expression in the input's vars. (The non-const
2686 * restriction only matters if the EC is below_outer_join; but if it
2687 * isn't, it won't contain consts anyway, else we'd have discarded
2688 * the pathkey as redundant.)
2690 * XXX if we have a choice, is there any way of figuring out which
2691 * might be cheapest to execute? (For example, int4lt is likely much
2692 * cheaper to execute than numericlt, but both might appear in the
2693 * same equivalence class...) Not clear that we ever will have an
2694 * interesting choice in practice, so it may not matter.
2696 foreach(j, pathkey->pk_eclass->ec_members)
2698 EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
2700 if (em->em_is_const || em->em_is_child)
2702 tle = tlist_member((Node *) em->em_expr, tlist);
2705 pk_datatype = em->em_datatype;
2706 break; /* found expr already in tlist */
2711 /* No matching Var; look for a computable expression */
2712 Expr *sortexpr = NULL;
2714 foreach(j, pathkey->pk_eclass->ec_members)
2716 EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
2720 if (em->em_is_const || em->em_is_child)
2722 sortexpr = em->em_expr;
2723 exprvars = pull_var_clause((Node *) sortexpr, false);
2724 foreach(k, exprvars)
2726 if (!tlist_member(lfirst(k), tlist))
2729 list_free(exprvars);
2732 pk_datatype = em->em_datatype;
2733 break; /* found usable expression */
2737 elog(ERROR, "could not find pathkey item to sort");
2740 * Do we need to insert a Result node?
2742 if (!is_projection_capable_plan(lefttree))
2743 lefttree = (Plan *) make_result(root, tlist, NULL, lefttree);
2746 * Add resjunk entry to input's tlist
2748 tle = makeTargetEntry(sortexpr,
2749 list_length(tlist) + 1,
2752 tlist = lappend(tlist, tle);
2753 lefttree->targetlist = tlist; /* just in case NIL before */
2757 * Look up the correct sort operator from the PathKey's slightly
2758 * abstracted representation.
2760 sortop = get_opfamily_member(pathkey->pk_opfamily,
2763 pathkey->pk_strategy);
2764 if (!OidIsValid(sortop)) /* should not happen */
2765 elog(ERROR, "could not find member %d(%u,%u) of opfamily %u",
2766 pathkey->pk_strategy, pk_datatype, pk_datatype,
2767 pathkey->pk_opfamily);
2770 * The column might already be selected as a sort key, if the pathkeys
2771 * contain duplicate entries. (This can happen in scenarios where
2772 * multiple mergejoinable clauses mention the same var, for example.)
2773 * So enter it only once in the sort arrays.
2775 numsortkeys = add_sort_column(tle->resno,
2777 pathkey->pk_nulls_first,
2779 sortColIdx, sortOperators, nullsFirst);
2782 Assert(numsortkeys > 0);
2784 return make_sort(root, lefttree, numsortkeys,
2785 sortColIdx, sortOperators, nullsFirst);
2789 * make_sort_from_sortclauses
2790 * Create sort plan to sort according to given sortclauses
2792 * 'sortcls' is a list of SortClauses
2793 * 'lefttree' is the node which yields input tuples
2796 make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
2798 List *sub_tlist = lefttree->targetlist;
2801 AttrNumber *sortColIdx;
2806 * We will need at most list_length(sortcls) sort columns; possibly less
2808 numsortkeys = list_length(sortcls);
2809 sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2810 sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2811 nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
2817 SortClause *sortcl = (SortClause *) lfirst(l);
2818 TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist);
2821 * Check for the possibility of duplicate order-by clauses --- the
2822 * parser should have removed 'em, but no point in sorting
2825 numsortkeys = add_sort_column(tle->resno, sortcl->sortop,
2826 sortcl->nulls_first,
2828 sortColIdx, sortOperators, nullsFirst);
2831 Assert(numsortkeys > 0);
2833 return make_sort(root, lefttree, numsortkeys,
2834 sortColIdx, sortOperators, nullsFirst);
2838 * make_sort_from_groupcols
2839 * Create sort plan to sort based on grouping columns
2841 * 'groupcls' is the list of GroupClauses
2842 * 'grpColIdx' gives the column numbers to use
2844 * This might look like it could be merged with make_sort_from_sortclauses,
2845 * but presently we *must* use the grpColIdx[] array to locate sort columns,
2846 * because the child plan's tlist is not marked with ressortgroupref info
2847 * appropriate to the grouping node. So, only the sort ordering info
2848 * is used from the GroupClause entries.
2851 make_sort_from_groupcols(PlannerInfo *root,
2853 AttrNumber *grpColIdx,
2856 List *sub_tlist = lefttree->targetlist;
2860 AttrNumber *sortColIdx;
2865 * We will need at most list_length(groupcls) sort columns; possibly less
2867 numsortkeys = list_length(groupcls);
2868 sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2869 sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2870 nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
2874 foreach(l, groupcls)
2876 GroupClause *grpcl = (GroupClause *) lfirst(l);
2877 TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[grpno]);
2880 * Check for the possibility of duplicate group-by clauses --- the
2881 * parser should have removed 'em, but no point in sorting
2884 numsortkeys = add_sort_column(tle->resno, grpcl->sortop,
2887 sortColIdx, sortOperators, nullsFirst);
2891 Assert(numsortkeys > 0);
2893 return make_sort(root, lefttree, numsortkeys,
2894 sortColIdx, sortOperators, nullsFirst);
2898 make_material(Plan *lefttree)
2900 Material *node = makeNode(Material);
2901 Plan *plan = &node->plan;
2903 /* cost should be inserted by caller */
2904 plan->targetlist = lefttree->targetlist;
2906 plan->lefttree = lefttree;
2907 plan->righttree = NULL;
2913 * materialize_finished_plan: stick a Material node atop a completed plan
2915 * There are a couple of places where we want to attach a Material node
2916 * after completion of subquery_planner(). This currently requires hackery.
2917 * Since subquery_planner has already run SS_finalize_plan on the subplan
2918 * tree, we have to kluge up parameter lists for the Material node.
2919 * Possibly this could be fixed by postponing SS_finalize_plan processing
2920 * until setrefs.c is run?
2923 materialize_finished_plan(Plan *subplan)
2926 Path matpath; /* dummy for result of cost_material */
2928 matplan = (Plan *) make_material(subplan);
2931 cost_material(&matpath,
2932 subplan->total_cost,
2934 subplan->plan_width);
2935 matplan->startup_cost = matpath.startup_cost;
2936 matplan->total_cost = matpath.total_cost;
2937 matplan->plan_rows = subplan->plan_rows;
2938 matplan->plan_width = subplan->plan_width;
2940 /* parameter kluge --- see comments above */
2941 matplan->extParam = bms_copy(subplan->extParam);
2942 matplan->allParam = bms_copy(subplan->allParam);
2948 make_agg(PlannerInfo *root, List *tlist, List *qual,
2949 AggStrategy aggstrategy,
2950 int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators,
2951 long numGroups, int numAggs,
2954 Agg *node = makeNode(Agg);
2955 Plan *plan = &node->plan;
2956 Path agg_path; /* dummy for result of cost_agg */
2959 node->aggstrategy = aggstrategy;
2960 node->numCols = numGroupCols;
2961 node->grpColIdx = grpColIdx;
2962 node->grpOperators = grpOperators;
2963 node->numGroups = numGroups;
2965 copy_plan_costsize(plan, lefttree); /* only care about copying size */
2966 cost_agg(&agg_path, root,
2967 aggstrategy, numAggs,
2968 numGroupCols, numGroups,
2969 lefttree->startup_cost,
2970 lefttree->total_cost,
2971 lefttree->plan_rows);
2972 plan->startup_cost = agg_path.startup_cost;
2973 plan->total_cost = agg_path.total_cost;
2976 * We will produce a single output tuple if not grouping, and a tuple per
2979 if (aggstrategy == AGG_PLAIN)
2980 plan->plan_rows = 1;
2982 plan->plan_rows = numGroups;
2985 * We also need to account for the cost of evaluation of the qual (ie, the
2986 * HAVING clause) and the tlist. Note that cost_qual_eval doesn't charge
2987 * anything for Aggref nodes; this is okay since they are really
2988 * comparable to Vars.
2990 * See notes in grouping_planner about why this routine and make_group are
2991 * the only ones in this file that worry about tlist eval cost.
2995 cost_qual_eval(&qual_cost, qual, root);
2996 plan->startup_cost += qual_cost.startup;
2997 plan->total_cost += qual_cost.startup;
2998 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
3000 cost_qual_eval(&qual_cost, tlist, root);
3001 plan->startup_cost += qual_cost.startup;
3002 plan->total_cost += qual_cost.startup;
3003 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
3006 plan->targetlist = tlist;
3007 plan->lefttree = lefttree;
3008 plan->righttree = NULL;
3014 make_group(PlannerInfo *root,
3018 AttrNumber *grpColIdx,
3023 Group *node = makeNode(Group);
3024 Plan *plan = &node->plan;
3025 Path group_path; /* dummy for result of cost_group */
3028 node->numCols = numGroupCols;
3029 node->grpColIdx = grpColIdx;
3030 node->grpOperators = grpOperators;
3032 copy_plan_costsize(plan, lefttree); /* only care about copying size */
3033 cost_group(&group_path, root,
3034 numGroupCols, numGroups,
3035 lefttree->startup_cost,
3036 lefttree->total_cost,
3037 lefttree->plan_rows);
3038 plan->startup_cost = group_path.startup_cost;
3039 plan->total_cost = group_path.total_cost;
3041 /* One output tuple per estimated result group */
3042 plan->plan_rows = numGroups;
3045 * We also need to account for the cost of evaluation of the qual (ie, the
3046 * HAVING clause) and the tlist.
3048 * XXX this double-counts the cost of evaluation of any expressions used
3049 * for grouping, since in reality those will have been evaluated at a
3050 * lower plan level and will only be copied by the Group node. Worth
3053 * See notes in grouping_planner about why this routine and make_agg are
3054 * the only ones in this file that worry about tlist eval cost.
3058 cost_qual_eval(&qual_cost, qual, root);
3059 plan->startup_cost += qual_cost.startup;
3060 plan->total_cost += qual_cost.startup;
3061 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
3063 cost_qual_eval(&qual_cost, tlist, root);
3064 plan->startup_cost += qual_cost.startup;
3065 plan->total_cost += qual_cost.startup;
3066 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
3069 plan->targetlist = tlist;
3070 plan->lefttree = lefttree;
3071 plan->righttree = NULL;
3077 * distinctList is a list of SortClauses, identifying the targetlist items
3078 * that should be considered by the Unique filter. The input path must
3079 * already be sorted accordingly.
3082 make_unique(Plan *lefttree, List *distinctList)
3084 Unique *node = makeNode(Unique);
3085 Plan *plan = &node->plan;
3086 int numCols = list_length(distinctList);
3088 AttrNumber *uniqColIdx;
3092 copy_plan_costsize(plan, lefttree);
3095 * Charge one cpu_operator_cost per comparison per input tuple. We assume
3096 * all columns get compared at most of the tuples. (XXX probably this is
3099 plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
3102 * plan->plan_rows is left as a copy of the input subplan's plan_rows; ie,
3103 * we assume the filter removes nothing. The caller must alter this if he
3104 * has a better idea.
3107 plan->targetlist = lefttree->targetlist;
3109 plan->lefttree = lefttree;
3110 plan->righttree = NULL;
3113 * convert SortClause list into arrays of attr indexes and equality
3114 * operators, as wanted by executor
3116 Assert(numCols > 0);
3117 uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
3118 uniqOperators = (Oid *) palloc(sizeof(Oid) * numCols);
3120 foreach(slitem, distinctList)
3122 SortClause *sortcl = (SortClause *) lfirst(slitem);
3123 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
3125 uniqColIdx[keyno] = tle->resno;
3126 uniqOperators[keyno] = get_equality_op_for_ordering_op(sortcl->sortop);
3127 if (!OidIsValid(uniqOperators[keyno])) /* shouldn't happen */
3128 elog(ERROR, "could not find equality operator for ordering operator %u",
3133 node->numCols = numCols;
3134 node->uniqColIdx = uniqColIdx;
3135 node->uniqOperators = uniqOperators;
3141 * distinctList is a list of SortClauses, identifying the targetlist items
3142 * that should be considered by the SetOp filter. The input path must
3143 * already be sorted accordingly.
3146 make_setop(SetOpCmd cmd, Plan *lefttree,
3147 List *distinctList, AttrNumber flagColIdx)
3149 SetOp *node = makeNode(SetOp);
3150 Plan *plan = &node->plan;
3151 int numCols = list_length(distinctList);
3153 AttrNumber *dupColIdx;
3157 copy_plan_costsize(plan, lefttree);
3160 * Charge one cpu_operator_cost per comparison per input tuple. We assume
3161 * all columns get compared at most of the tuples.
3163 plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
3166 * We make the unsupported assumption that there will be 10% as many
3167 * tuples out as in. Any way to do better?
3169 plan->plan_rows *= 0.1;
3170 if (plan->plan_rows < 1)
3171 plan->plan_rows = 1;
3173 plan->targetlist = lefttree->targetlist;
3175 plan->lefttree = lefttree;
3176 plan->righttree = NULL;
3179 * convert SortClause list into arrays of attr indexes and equality
3180 * operators, as wanted by executor
3182 Assert(numCols > 0);
3183 dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
3184 dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
3186 foreach(slitem, distinctList)
3188 SortClause *sortcl = (SortClause *) lfirst(slitem);
3189 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
3191 dupColIdx[keyno] = tle->resno;
3192 dupOperators[keyno] = get_equality_op_for_ordering_op(sortcl->sortop);
3193 if (!OidIsValid(dupOperators[keyno])) /* shouldn't happen */
3194 elog(ERROR, "could not find equality operator for ordering operator %u",
3200 node->numCols = numCols;
3201 node->dupColIdx = dupColIdx;
3202 node->dupOperators = dupOperators;
3203 node->flagColIdx = flagColIdx;
3209 * Note: offset_est and count_est are passed in to save having to repeat
3210 * work already done to estimate the values of the limitOffset and limitCount
3211 * expressions. Their values are as returned by preprocess_limit (0 means
3212 * "not relevant", -1 means "couldn't estimate"). Keep the code below in sync
3213 * with that function!
3216 make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount,
3217 int64 offset_est, int64 count_est)
3219 Limit *node = makeNode(Limit);
3220 Plan *plan = &node->plan;
3222 copy_plan_costsize(plan, lefttree);
3225 * Adjust the output rows count and costs according to the offset/limit.
3226 * This is only a cosmetic issue if we are at top level, but if we are
3227 * building a subquery then it's important to report correct info to the
3230 * When the offset or count couldn't be estimated, use 10% of the
3231 * estimated number of rows emitted from the subplan.
3233 if (offset_est != 0)
3238 offset_rows = (double) offset_est;
3240 offset_rows = clamp_row_est(lefttree->plan_rows * 0.10);
3241 if (offset_rows > plan->plan_rows)
3242 offset_rows = plan->plan_rows;
3243 if (plan->plan_rows > 0)
3244 plan->startup_cost +=
3245 (plan->total_cost - plan->startup_cost)
3246 * offset_rows / plan->plan_rows;
3247 plan->plan_rows -= offset_rows;
3248 if (plan->plan_rows < 1)
3249 plan->plan_rows = 1;
3257 count_rows = (double) count_est;
3259 count_rows = clamp_row_est(lefttree->plan_rows * 0.10);
3260 if (count_rows > plan->plan_rows)
3261 count_rows = plan->plan_rows;
3262 if (plan->plan_rows > 0)
3263 plan->total_cost = plan->startup_cost +
3264 (plan->total_cost - plan->startup_cost)
3265 * count_rows / plan->plan_rows;
3266 plan->plan_rows = count_rows;
3267 if (plan->plan_rows < 1)
3268 plan->plan_rows = 1;
3271 plan->targetlist = lefttree->targetlist;
3273 plan->lefttree = lefttree;
3274 plan->righttree = NULL;
3276 node->limitOffset = limitOffset;
3277 node->limitCount = limitCount;
3284 * Build a Result plan node
3286 * If we have a subplan, assume that any evaluation costs for the gating qual
3287 * were already factored into the subplan's startup cost, and just copy the
3288 * subplan cost. If there's no subplan, we should include the qual eval
3289 * cost. In either case, tlist eval cost is not to be included here.
3292 make_result(PlannerInfo *root,
3294 Node *resconstantqual,
3297 Result *node = makeNode(Result);
3298 Plan *plan = &node->plan;
3301 copy_plan_costsize(plan, subplan);
3304 plan->startup_cost = 0;
3305 plan->total_cost = cpu_tuple_cost;
3306 plan->plan_rows = 1; /* wrong if we have a set-valued function? */
3307 plan->plan_width = 0; /* XXX is it worth being smarter? */
3308 if (resconstantqual)
3312 cost_qual_eval(&qual_cost, (List *) resconstantqual, root);
3313 /* resconstantqual is evaluated once at startup */
3314 plan->startup_cost += qual_cost.startup + qual_cost.per_tuple;
3315 plan->total_cost += qual_cost.startup + qual_cost.per_tuple;
3319 plan->targetlist = tlist;
3321 plan->lefttree = subplan;
3322 plan->righttree = NULL;
3323 node->resconstantqual = resconstantqual;
3329 * is_projection_capable_plan
3330 * Check whether a given Plan node is able to do projection.
3333 is_projection_capable_plan(Plan *plan)
3335 /* Most plan types can project, so just list the ones that can't */
3336 switch (nodeTag(plan))