PostgreSQL Source Code  git master
planmain.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * planmain.c
4  * Routines to plan a single query
5  *
6  * What's in a name, anyway? The top-level entry point of the planner/
7  * optimizer is over in planner.c, not here as you might think from the
8  * file name. But this is the main code for planning a basic join operation,
9  * shorn of features like subselects, inheritance, aggregates, grouping,
10  * and so on. (Those are the things planner.c deals with.)
11  *
12  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
13  * Portions Copyright (c) 1994, Regents of the University of California
14  *
15  *
16  * IDENTIFICATION
17  * src/backend/optimizer/plan/planmain.c
18  *
19  *-------------------------------------------------------------------------
20  */
21 #include "postgres.h"
22 
23 #include "optimizer/appendinfo.h"
24 #include "optimizer/clauses.h"
25 #include "optimizer/inherit.h"
26 #include "optimizer/optimizer.h"
27 #include "optimizer/orclauses.h"
28 #include "optimizer/pathnode.h"
29 #include "optimizer/paths.h"
30 #include "optimizer/placeholder.h"
31 #include "optimizer/planmain.h"
32 
33 
34 /*
35  * query_planner
36  * Generate a path (that is, a simplified plan) for a basic query,
37  * which may involve joins but not any fancier features.
38  *
39  * Since query_planner does not handle the toplevel processing (grouping,
40  * sorting, etc) it cannot select the best path by itself. Instead, it
41  * returns the RelOptInfo for the top level of joining, and the caller
42  * (grouping_planner) can choose among the surviving paths for the rel.
43  *
44  * root describes the query to plan
45  * qp_callback is a function to compute query_pathkeys once it's safe to do so
46  * qp_extra is optional extra data to pass to qp_callback
47  *
48  * Note: the PlannerInfo node also includes a query_pathkeys field, which
49  * tells query_planner the sort order that is desired in the final output
50  * plan. This value is *not* available at call time, but is computed by
51  * qp_callback once we have completed merging the query's equivalence classes.
52  * (We cannot construct canonical pathkeys until that's done.)
53  */
54 RelOptInfo *
56  query_pathkeys_callback qp_callback, void *qp_extra)
57 {
58  Query *parse = root->parse;
59  List *joinlist;
60  RelOptInfo *final_rel;
61 
62  /*
63  * Init planner lists to empty.
64  *
65  * NOTE: append_rel_list was set up by subquery_planner, so do not touch
66  * here.
67  */
68  root->join_rel_list = NIL;
69  root->join_rel_hash = NULL;
70  root->join_rel_level = NULL;
71  root->join_cur_level = 0;
72  root->canon_pathkeys = NIL;
73  root->left_join_clauses = NIL;
74  root->right_join_clauses = NIL;
75  root->full_join_clauses = NIL;
76  root->join_info_list = NIL;
77  root->placeholder_list = NIL;
78  root->fkey_list = NIL;
79  root->initial_rels = NIL;
80 
81  /*
82  * Set up arrays for accessing base relations and AppendRelInfos.
83  */
85 
86  /*
87  * In the trivial case where the jointree is a single RTE_RESULT relation,
88  * bypass all the rest of this function and just make a RelOptInfo and its
89  * one access path. This is worth optimizing because it applies for
90  * common cases like "SELECT expression" and "INSERT ... VALUES()".
91  */
92  Assert(parse->jointree->fromlist != NIL);
93  if (list_length(parse->jointree->fromlist) == 1)
94  {
95  Node *jtnode = (Node *) linitial(parse->jointree->fromlist);
96 
97  if (IsA(jtnode, RangeTblRef))
98  {
99  int varno = ((RangeTblRef *) jtnode)->rtindex;
100  RangeTblEntry *rte = root->simple_rte_array[varno];
101 
102  Assert(rte != NULL);
103  if (rte->rtekind == RTE_RESULT)
104  {
105  /* Make the RelOptInfo for it directly */
106  final_rel = build_simple_rel(root, varno, NULL);
107 
108  /*
109  * If query allows parallelism in general, check whether the
110  * quals are parallel-restricted. (We need not check
111  * final_rel->reltarget because it's empty at this point.
112  * Anything parallel-restricted in the query tlist will be
113  * dealt with later.) This is normally pretty silly, because
114  * a Result-only plan would never be interesting to
115  * parallelize. However, if force_parallel_mode is on, then
116  * we want to execute the Result in a parallel worker if
117  * possible, so we must do this.
118  */
119  if (root->glob->parallelModeOK &&
121  final_rel->consider_parallel =
122  is_parallel_safe(root, parse->jointree->quals);
123 
124  /*
125  * The only path for it is a trivial Result path. We cheat a
126  * bit here by using a GroupResultPath, because that way we
127  * can just jam the quals into it without preprocessing them.
128  * (But, if you hold your head at the right angle, a FROM-less
129  * SELECT is a kind of degenerate-grouping case, so it's not
130  * that much of a cheat.)
131  */
132  add_path(final_rel, (Path *)
133  create_group_result_path(root, final_rel,
134  final_rel->reltarget,
135  (List *) parse->jointree->quals));
136 
137  /* Select cheapest path (pretty easy in this case...) */
138  set_cheapest(final_rel);
139 
140  /*
141  * We don't need to run generate_base_implied_equalities, but
142  * we do need to pretend that EC merging is complete.
143  */
144  root->ec_merging_done = true;
145 
146  /*
147  * We still are required to call qp_callback, in case it's
148  * something like "SELECT 2+2 ORDER BY 1".
149  */
150  (*qp_callback) (root, qp_extra);
151 
152  return final_rel;
153  }
154  }
155  }
156 
157  /*
158  * Construct RelOptInfo nodes for all base relations used in the query.
159  * Appendrel member relations ("other rels") will be added later.
160  *
161  * Note: the reason we find the baserels by searching the jointree, rather
162  * than scanning the rangetable, is that the rangetable may contain RTEs
163  * for rels not actively part of the query, for example views. We don't
164  * want to make RelOptInfos for them.
165  */
166  add_base_rels_to_query(root, (Node *) parse->jointree);
167 
168  /*
169  * Examine the targetlist and join tree, adding entries to baserel
170  * targetlists for all referenced Vars, and generating PlaceHolderInfo
171  * entries for all referenced PlaceHolderVars. Restrict and join clauses
172  * are added to appropriate lists belonging to the mentioned relations. We
173  * also build EquivalenceClasses for provably equivalent expressions. The
174  * SpecialJoinInfo list is also built to hold information about join order
175  * restrictions. Finally, we form a target joinlist for make_one_rel() to
176  * work from.
177  */
179 
181 
183 
184  joinlist = deconstruct_jointree(root);
185 
186  /*
187  * Reconsider any postponed outer-join quals now that we have built up
188  * equivalence classes. (This could result in further additions or
189  * mergings of classes.)
190  */
192 
193  /*
194  * If we formed any equivalence classes, generate additional restriction
195  * clauses as appropriate. (Implied join clauses are formed on-the-fly
196  * later.)
197  */
199 
200  /*
201  * We have completed merging equivalence sets, so it's now possible to
202  * generate pathkeys in canonical form; so compute query_pathkeys and
203  * other pathkeys fields in PlannerInfo.
204  */
205  (*qp_callback) (root, qp_extra);
206 
207  /*
208  * Examine any "placeholder" expressions generated during subquery pullup.
209  * Make sure that the Vars they need are marked as needed at the relevant
210  * join level. This must be done before join removal because it might
211  * cause Vars or placeholders to be needed above a join when they weren't
212  * so marked before.
213  */
215 
216  /*
217  * Remove any useless outer joins. Ideally this would be done during
218  * jointree preprocessing, but the necessary information isn't available
219  * until we've built baserel data structures and classified qual clauses.
220  */
221  joinlist = remove_useless_joins(root, joinlist);
222 
223  /*
224  * Also, reduce any semijoins with unique inner rels to plain inner joins.
225  * Likewise, this can't be done until now for lack of needed info.
226  */
228 
229  /*
230  * Now distribute "placeholders" to base rels as needed. This has to be
231  * done after join removal because removal could change whether a
232  * placeholder is evaluable at a base rel.
233  */
235 
236  /*
237  * Construct the lateral reference sets now that we have finalized
238  * PlaceHolderVar eval levels.
239  */
241 
242  /*
243  * Match foreign keys to equivalence classes and join quals. This must be
244  * done after finalizing equivalence classes, and it's useful to wait till
245  * after join removal so that we can skip processing foreign keys
246  * involving removed relations.
247  */
249 
250  /*
251  * Look for join OR clauses that we can extract single-relation
252  * restriction OR clauses from.
253  */
255 
256  /*
257  * Now expand appendrels by adding "otherrels" for their children. We
258  * delay this to the end so that we have as much information as possible
259  * available for each baserel, including all restriction clauses. That
260  * let us prune away partitions that don't satisfy a restriction clause.
261  * Also note that some information such as lateral_relids is propagated
262  * from baserels to otherrels here, so we must have computed it already.
263  */
265 
266  /*
267  * Ready to do the primary planning.
268  */
269  final_rel = make_one_rel(root, joinlist);
270 
271  /* Check that we got at least one usable path */
272  if (!final_rel || !final_rel->cheapest_total_path ||
273  final_rel->cheapest_total_path->param_info != NULL)
274  elog(ERROR, "failed to construct the join relation");
275 
276  return final_rel;
277 }
#define NIL
Definition: pg_list.h:65
int join_cur_level
Definition: pathnodes.h:255
RelOptInfo * make_one_rel(PlannerInfo *root, List *joinlist)
Definition: allpaths.c:152
#define IsA(nodeptr, _type_)
Definition: nodes.h:576
Query * parse
Definition: pathnodes.h:177
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:423
void reduce_unique_semijoins(PlannerInfo *root)
Definition: analyzejoins.c:508
bool ec_merging_done
Definition: pathnodes.h:266
void add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
Definition: initsplan.c:106
List * join_info_list
Definition: pathnodes.h:281
FromExpr * jointree
Definition: parsenodes.h:138
void extract_restriction_or_clauses(PlannerInfo *root)
Definition: orclauses.c:76
List * deconstruct_jointree(PlannerInfo *root)
Definition: initsplan.c:687
ParamPathInfo * param_info
Definition: pathnodes.h:1117
Definition: nodes.h:525
RelOptInfo * query_planner(PlannerInfo *root, query_pathkeys_callback qp_callback, void *qp_extra)
Definition: planmain.c:55
List * join_rel_list
Definition: pathnodes.h:244
List * fromlist
Definition: primnodes.h:1496
List * fkey_list
Definition: pathnodes.h:294
void add_placeholders_to_base_rels(PlannerInfo *root)
Definition: placeholder.c:379
Node * quals
Definition: primnodes.h:1497
void add_other_rels_to_query(PlannerInfo *root)
Definition: initsplan.c:144
bool is_parallel_safe(PlannerInfo *root, Node *node)
Definition: clauses.c:854
#define linitial(l)
Definition: pg_list.h:195
#define ERROR
Definition: elog.h:43
bool parallelModeOK
Definition: pathnodes.h:141
struct Path * cheapest_total_path
Definition: pathnodes.h:659
PlannerGlobal * glob
Definition: pathnodes.h:179
List * left_join_clauses
Definition: pathnodes.h:270
List * full_join_clauses
Definition: pathnodes.h:278
RelOptInfo * build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
Definition: relnode.c:185
List * canon_pathkeys
Definition: pathnodes.h:268
RangeTblEntry ** simple_rte_array
Definition: pathnodes.h:209
void fix_placeholder_input_needed_levels(PlannerInfo *root)
Definition: placeholder.c:350
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:245
void find_placeholders_in_jointree(PlannerInfo *root)
Definition: placeholder.c:144
void generate_base_implied_equalities(PlannerInfo *root)
Definition: equivclass.c:827
void reconsider_outer_join_clauses(PlannerInfo *root)
Definition: equivclass.c:1688
void(* query_pathkeys_callback)(PlannerInfo *root, void *extra)
Definition: planmain.h:25
int force_parallel_mode
Definition: planner.c:71
#define Assert(condition)
Definition: c.h:732
List ** join_rel_level
Definition: pathnodes.h:254
void setup_simple_rel_arrays(PlannerInfo *root)
Definition: relnode.c:74
List * remove_useless_joins(PlannerInfo *root, List *joinlist)
Definition: analyzejoins.c:61
static int list_length(const List *l)
Definition: pg_list.h:169
struct HTAB * join_rel_hash
Definition: pathnodes.h:245
void build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
Definition: initsplan.c:183
bool consider_parallel
Definition: pathnodes.h:649
RTEKind rtekind
Definition: parsenodes.h:974
void match_foreign_keys_to_quals(PlannerInfo *root)
Definition: initsplan.c:2412
#define elog(elevel,...)
Definition: elog.h:226
List * placeholder_list
Definition: pathnodes.h:292
GroupResultPath * create_group_result_path(PlannerInfo *root, RelOptInfo *rel, PathTarget *target, List *havingqual)
Definition: pathnode.c:1448
List * initial_rels
Definition: pathnodes.h:306
List * right_join_clauses
Definition: pathnodes.h:274
List * processed_tlist
Definition: pathnodes.h:323
Definition: pg_list.h:50
struct PathTarget * reltarget
Definition: pathnodes.h:652
void create_lateral_join_info(PlannerInfo *root)
Definition: initsplan.c:450
void find_lateral_references(PlannerInfo *root)
Definition: initsplan.c:304
static struct subre * parse(struct vars *, int, int, struct state *, struct state *)
Definition: regcomp.c:648