PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, 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/clauses.h"
24 #include "optimizer/orclauses.h"
25 #include "optimizer/pathnode.h"
26 #include "optimizer/paths.h"
27 #include "optimizer/placeholder.h"
28 #include "optimizer/planmain.h"
29 
30 
31 /*
32  * query_planner
33  * Generate a path (that is, a simplified plan) for a basic query,
34  * which may involve joins but not any fancier features.
35  *
36  * Since query_planner does not handle the toplevel processing (grouping,
37  * sorting, etc) it cannot select the best path by itself. Instead, it
38  * returns the RelOptInfo for the top level of joining, and the caller
39  * (grouping_planner) can choose among the surviving paths for the rel.
40  *
41  * root describes the query to plan
42  * tlist is the target list the query should produce
43  * (this is NOT necessarily root->parse->targetList!)
44  * qp_callback is a function to compute query_pathkeys once it's safe to do so
45  * qp_extra is optional extra data to pass to qp_callback
46  *
47  * Note: the PlannerInfo node also includes a query_pathkeys field, which
48  * tells query_planner the sort order that is desired in the final output
49  * plan. This value is *not* available at call time, but is computed by
50  * qp_callback once we have completed merging the query's equivalence classes.
51  * (We cannot construct canonical pathkeys until that's done.)
52  */
53 RelOptInfo *
55  query_pathkeys_callback qp_callback, void *qp_extra)
56 {
57  Query *parse = root->parse;
58  List *joinlist;
59  RelOptInfo *final_rel;
60  Index rti;
61  double total_pages;
62 
63  /*
64  * If the query has an empty join tree, then it's something easy like
65  * "SELECT 2+2;" or "INSERT ... VALUES()". Fall through quickly.
66  */
67  if (parse->jointree->fromlist == NIL)
68  {
69  /* We need a dummy joinrel to describe the empty set of baserels */
70  final_rel = build_empty_join_rel(root);
71 
72  /*
73  * If query allows parallelism in general, check whether the quals are
74  * parallel-restricted. (We need not check final_rel->reltarget
75  * because it's empty at this point. Anything parallel-restricted in
76  * the query tlist will be dealt with later.)
77  */
78  if (root->glob->parallelModeOK)
79  final_rel->consider_parallel =
80  is_parallel_safe(root, parse->jointree->quals);
81 
82  /* The only path for it is a trivial Result path */
83  add_path(final_rel, (Path *)
84  create_result_path(root, final_rel,
85  final_rel->reltarget,
86  (List *) parse->jointree->quals));
87 
88  /* Select cheapest path (pretty easy in this case...) */
89  set_cheapest(final_rel);
90 
91  /*
92  * We still are required to call qp_callback, in case it's something
93  * like "SELECT 2+2 ORDER BY 1".
94  */
95  root->canon_pathkeys = NIL;
96  (*qp_callback) (root, qp_extra);
97 
98  return final_rel;
99  }
100 
101  /*
102  * Init planner lists to empty.
103  *
104  * NOTE: append_rel_list was set up by subquery_planner, so do not touch
105  * here.
106  */
107  root->join_rel_list = NIL;
108  root->join_rel_hash = NULL;
109  root->join_rel_level = NULL;
110  root->join_cur_level = 0;
111  root->canon_pathkeys = NIL;
112  root->left_join_clauses = NIL;
113  root->right_join_clauses = NIL;
114  root->full_join_clauses = NIL;
115  root->join_info_list = NIL;
116  root->placeholder_list = NIL;
117  root->fkey_list = NIL;
118  root->initial_rels = NIL;
119 
120  /*
121  * Make a flattened version of the rangetable for faster access (this is
122  * OK because the rangetable won't change any more), and set up an empty
123  * array for indexing base relations.
124  */
126 
127  /*
128  * Construct RelOptInfo nodes for all base relations in query, and
129  * indirectly for all appendrel member relations ("other rels"). This
130  * will give us a RelOptInfo for every "simple" (non-join) rel involved in
131  * the query.
132  *
133  * Note: the reason we find the rels by searching the jointree and
134  * appendrel list, rather than just scanning the rangetable, is that the
135  * rangetable may contain RTEs for rels not actively part of the query,
136  * for example views. We don't want to make RelOptInfos for them.
137  */
138  add_base_rels_to_query(root, (Node *) parse->jointree);
139 
140  /*
141  * Examine the targetlist and join tree, adding entries to baserel
142  * targetlists for all referenced Vars, and generating PlaceHolderInfo
143  * entries for all referenced PlaceHolderVars. Restrict and join clauses
144  * are added to appropriate lists belonging to the mentioned relations. We
145  * also build EquivalenceClasses for provably equivalent expressions. The
146  * SpecialJoinInfo list is also built to hold information about join order
147  * restrictions. Finally, we form a target joinlist for make_one_rel() to
148  * work from.
149  */
150  build_base_rel_tlists(root, tlist);
151 
153 
155 
156  joinlist = deconstruct_jointree(root);
157 
158  /*
159  * Reconsider any postponed outer-join quals now that we have built up
160  * equivalence classes. (This could result in further additions or
161  * mergings of classes.)
162  */
164 
165  /*
166  * If we formed any equivalence classes, generate additional restriction
167  * clauses as appropriate. (Implied join clauses are formed on-the-fly
168  * later.)
169  */
171 
172  /*
173  * We have completed merging equivalence sets, so it's now possible to
174  * generate pathkeys in canonical form; so compute query_pathkeys and
175  * other pathkeys fields in PlannerInfo.
176  */
177  (*qp_callback) (root, qp_extra);
178 
179  /*
180  * Examine any "placeholder" expressions generated during subquery pullup.
181  * Make sure that the Vars they need are marked as needed at the relevant
182  * join level. This must be done before join removal because it might
183  * cause Vars or placeholders to be needed above a join when they weren't
184  * so marked before.
185  */
187 
188  /*
189  * Remove any useless outer joins. Ideally this would be done during
190  * jointree preprocessing, but the necessary information isn't available
191  * until we've built baserel data structures and classified qual clauses.
192  */
193  joinlist = remove_useless_joins(root, joinlist);
194 
195  /*
196  * Also, reduce any semijoins with unique inner rels to plain inner joins.
197  * Likewise, this can't be done until now for lack of needed info.
198  */
200 
201  /*
202  * Now distribute "placeholders" to base rels as needed. This has to be
203  * done after join removal because removal could change whether a
204  * placeholder is evaluable at a base rel.
205  */
207 
208  /*
209  * Construct the lateral reference sets now that we have finalized
210  * PlaceHolderVar eval levels.
211  */
213 
214  /*
215  * Match foreign keys to equivalence classes and join quals. This must be
216  * done after finalizing equivalence classes, and it's useful to wait till
217  * after join removal so that we can skip processing foreign keys
218  * involving removed relations.
219  */
221 
222  /*
223  * Look for join OR clauses that we can extract single-relation
224  * restriction OR clauses from.
225  */
227 
228  /*
229  * We should now have size estimates for every actual table involved in
230  * the query, and we also know which if any have been deleted from the
231  * query by join removal; so we can compute total_table_pages.
232  *
233  * Note that appendrels are not double-counted here, even though we don't
234  * bother to distinguish RelOptInfos for appendrel parents, because the
235  * parents will still have size zero.
236  *
237  * XXX if a table is self-joined, we will count it once per appearance,
238  * which perhaps is the wrong thing ... but that's not completely clear,
239  * and detecting self-joins here is difficult, so ignore it for now.
240  */
241  total_pages = 0;
242  for (rti = 1; rti < root->simple_rel_array_size; rti++)
243  {
244  RelOptInfo *brel = root->simple_rel_array[rti];
245 
246  if (brel == NULL)
247  continue;
248 
249  Assert(brel->relid == rti); /* sanity check on array */
250 
251  if (IS_SIMPLE_REL(brel))
252  total_pages += (double) brel->pages;
253  }
254  root->total_table_pages = total_pages;
255 
256  /*
257  * Ready to do the primary planning.
258  */
259  final_rel = make_one_rel(root, joinlist);
260 
261  /* Check that we got at least one usable path */
262  if (!final_rel || !final_rel->cheapest_total_path ||
263  final_rel->cheapest_total_path->param_info != NULL)
264  elog(ERROR, "failed to construct the join relation");
265 
266  return final_rel;
267 }
#define NIL
Definition: pg_list.h:69
int join_cur_level
Definition: relation.h:226
RelOptInfo * make_one_rel(PlannerInfo *root, List *joinlist)
Definition: allpaths.c:146
Query * parse
Definition: relation.h:155
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
void reduce_unique_semijoins(PlannerInfo *root)
Definition: analyzejoins.c:512
void add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
Definition: initsplan.c:105
List * join_info_list
Definition: relation.h:250
FromExpr * jointree
Definition: parsenodes.h:136
RelOptInfo * query_planner(PlannerInfo *root, List *tlist, query_pathkeys_callback qp_callback, void *qp_extra)
Definition: planmain.c:54
void extract_restriction_or_clauses(PlannerInfo *root)
Definition: orclauses.c:73
List * deconstruct_jointree(PlannerInfo *root)
Definition: initsplan.c:713
ParamPathInfo * param_info
Definition: relation.h:1011
Definition: nodes.h:509
List * join_rel_list
Definition: relation.h:215
List * fromlist
Definition: primnodes.h:1471
List * fkey_list
Definition: relation.h:260
void add_placeholders_to_base_rels(PlannerInfo *root)
Definition: placeholder.c:379
Node * quals
Definition: primnodes.h:1472
#define IS_SIMPLE_REL(rel)
Definition: relation.h:551
bool is_parallel_safe(PlannerInfo *root, Node *node)
Definition: clauses.c:1087
#define ERROR
Definition: elog.h:43
bool parallelModeOK
Definition: relation.h:129
struct Path * cheapest_total_path
Definition: relation.h:589
PlannerGlobal * glob
Definition: relation.h:157
List * left_join_clauses
Definition: relation.h:239
List * full_join_clauses
Definition: relation.h:247
List * canon_pathkeys
Definition: relation.h:237
Index relid
Definition: relation.h:599
void fix_placeholder_input_needed_levels(PlannerInfo *root)
Definition: placeholder.c:350
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:234
void find_placeholders_in_jointree(PlannerInfo *root)
Definition: placeholder.c:144
void generate_base_implied_equalities(PlannerInfo *root)
Definition: equivclass.c:762
unsigned int Index
Definition: c.h:359
void reconsider_outer_join_clauses(PlannerInfo *root)
Definition: equivclass.c:1534
void(* query_pathkeys_callback)(PlannerInfo *root, void *extra)
Definition: planmain.h:34
BlockNumber pages
Definition: relation.h:610
#define Assert(condition)
Definition: c.h:664
RelOptInfo * build_empty_join_rel(PlannerInfo *root)
Definition: relnode.c:918
List ** join_rel_level
Definition: relation.h:225
void setup_simple_rel_arrays(PlannerInfo *root)
Definition: relnode.c:62
List * remove_useless_joins(PlannerInfo *root, List *joinlist)
Definition: analyzejoins.c:60
struct HTAB * join_rel_hash
Definition: relation.h:216
void build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
Definition: initsplan.c:151
bool consider_parallel
Definition: relation.h:579
void match_foreign_keys_to_quals(PlannerInfo *root)
Definition: initsplan.c:2433
List * placeholder_list
Definition: relation.h:258
ResultPath * create_result_path(PlannerInfo *root, RelOptInfo *rel, PathTarget *target, List *resconstantqual)
Definition: pathnode.c:1349
List * initial_rels
Definition: relation.h:272
List * right_join_clauses
Definition: relation.h:243
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
struct PathTarget * reltarget
Definition: relation.h:582
void create_lateral_join_info(PlannerInfo *root)
Definition: initsplan.c:418
void find_lateral_references(PlannerInfo *root)
Definition: initsplan.c:272
static struct subre * parse(struct vars *, int, int, struct state *, struct state *)
Definition: regcomp.c:649