Line data Source code
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 *
54 25326 : query_planner(PlannerInfo *root, List *tlist,
55 : query_pathkeys_callback qp_callback, void *qp_extra)
56 : {
57 25326 : 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 25326 : if (parse->jointree->fromlist == NIL)
68 : {
69 : /* We need a dummy joinrel to describe the empty set of baserels */
70 11506 : 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 11506 : if (root->glob->parallelModeOK)
79 5125 : final_rel->consider_parallel =
80 5125 : is_parallel_safe(root, parse->jointree->quals);
81 :
82 : /* The only path for it is a trivial Result path */
83 11506 : add_path(final_rel, (Path *)
84 11506 : create_result_path(root, final_rel,
85 11506 : final_rel->reltarget,
86 11506 : (List *) parse->jointree->quals));
87 :
88 : /* Select cheapest path (pretty easy in this case...) */
89 11506 : 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 11506 : root->canon_pathkeys = NIL;
96 11506 : (*qp_callback) (root, qp_extra);
97 :
98 11506 : 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 13820 : root->join_rel_list = NIL;
108 13820 : root->join_rel_hash = NULL;
109 13820 : root->join_rel_level = NULL;
110 13820 : root->join_cur_level = 0;
111 13820 : root->canon_pathkeys = NIL;
112 13820 : root->left_join_clauses = NIL;
113 13820 : root->right_join_clauses = NIL;
114 13820 : root->full_join_clauses = NIL;
115 13820 : root->join_info_list = NIL;
116 13820 : root->placeholder_list = NIL;
117 13820 : root->fkey_list = NIL;
118 13820 : 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 : */
125 13820 : setup_simple_rel_arrays(root);
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 13820 : 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 13818 : build_base_rel_tlists(root, tlist);
151 :
152 13818 : find_placeholders_in_jointree(root);
153 :
154 13818 : find_lateral_references(root);
155 :
156 13818 : 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 : */
163 13818 : reconsider_outer_join_clauses(root);
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 : */
170 13818 : generate_base_implied_equalities(root);
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 13818 : (*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 : */
186 13818 : fix_placeholder_input_needed_levels(root);
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 13818 : 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 : */
199 13818 : reduce_unique_semijoins(root);
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 : */
206 13818 : add_placeholders_to_base_rels(root);
207 :
208 : /*
209 : * Construct the lateral reference sets now that we have finalized
210 : * PlaceHolderVar eval levels.
211 : */
212 13818 : create_lateral_join_info(root);
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 : */
220 13818 : match_foreign_keys_to_quals(root);
221 :
222 : /*
223 : * Look for join OR clauses that we can extract single-relation
224 : * restriction OR clauses from.
225 : */
226 13818 : extract_restriction_or_clauses(root);
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 13818 : total_pages = 0;
242 40855 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
243 : {
244 27037 : RelOptInfo *brel = root->simple_rel_array[rti];
245 :
246 27037 : if (brel == NULL)
247 7514 : continue;
248 :
249 19523 : Assert(brel->relid == rti); /* sanity check on array */
250 :
251 19523 : if (IS_SIMPLE_REL(brel))
252 19111 : total_pages += (double) brel->pages;
253 : }
254 13818 : root->total_table_pages = total_pages;
255 :
256 : /*
257 : * Ready to do the primary planning.
258 : */
259 13818 : final_rel = make_one_rel(root, joinlist);
260 :
261 : /* Check that we got at least one usable path */
262 27636 : if (!final_rel || !final_rel->cheapest_total_path ||
263 13818 : final_rel->cheapest_total_path->param_info != NULL)
264 0 : elog(ERROR, "failed to construct the join relation");
265 :
266 13818 : return final_rel;
267 : }
|
