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 * 55 query_planner(PlannerInfo *root, 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 * Make a flattened version of the rangetable for faster access (this is 83 * OK because the rangetable won't change any more), and set up an empty 84 * array for indexing base relations. 85 */ 86 setup_simple_rel_arrays(root); 87 88 /* 89 * In the trivial case where the jointree is a single RTE_RESULT relation, 90 * bypass all the rest of this function and just make a RelOptInfo and its 91 * one access path. This is worth optimizing because it applies for 92 * common cases like "SELECT expression" and "INSERT ... VALUES()". 93 */ 94 Assert(parse->jointree->fromlist != NIL); 95 if (list_length(parse->jointree->fromlist) == 1) 96 { 97 Node *jtnode = (Node *) linitial(parse->jointree->fromlist); 98 99 if (IsA(jtnode, RangeTblRef)) 100 { 101 int varno = ((RangeTblRef *) jtnode)->rtindex; 102 RangeTblEntry *rte = root->simple_rte_array[varno]; 103 104 Assert(rte != NULL); 105 if (rte->rtekind == RTE_RESULT) 106 { 107 /* Make the RelOptInfo for it directly */ 108 final_rel = build_simple_rel(root, varno, NULL); 109 110 /* 111 * If query allows parallelism in general, check whether the 112 * quals are parallel-restricted. (We need not check 113 * final_rel->reltarget because it's empty at this point. 114 * Anything parallel-restricted in the query tlist will be 115 * dealt with later.) This is normally pretty silly, because 116 * a Result-only plan would never be interesting to 117 * parallelize. However, if force_parallel_mode is on, then 118 * we want to execute the Result in a parallel worker if 119 * possible, so we must do this. 120 */ 121 if (root->glob->parallelModeOK && 122 force_parallel_mode != FORCE_PARALLEL_OFF) 123 final_rel->consider_parallel = 124 is_parallel_safe(root, parse->jointree->quals); 125 126 /* 127 * The only path for it is a trivial Result path. We cheat a 128 * bit here by using a GroupResultPath, because that way we 129 * can just jam the quals into it without preprocessing them. 130 * (But, if you hold your head at the right angle, a FROM-less 131 * SELECT is a kind of degenerate-grouping case, so it's not 132 * that much of a cheat.) 133 */ 134 add_path(final_rel, (Path *) 135 create_group_result_path(root, final_rel, 136 final_rel->reltarget, 137 (List *) parse->jointree->quals)); 138 139 /* Select cheapest path (pretty easy in this case...) */ 140 set_cheapest(final_rel); 141 142 /* 143 * We still are required to call qp_callback, in case it's 144 * something like "SELECT 2+2 ORDER BY 1". 145 */ 146 (*qp_callback) (root, qp_extra); 147 148 return final_rel; 149 } 150 } 151 } 152 153 /* 154 * Populate append_rel_array with each AppendRelInfo to allow direct 155 * lookups by child relid. 156 */ 157 setup_append_rel_array(root); 158 159 /* 160 * Construct RelOptInfo nodes for all base relations used in the query. 161 * Appendrel member relations ("other rels") will be added later. 162 * 163 * Note: the reason we find the baserels by searching the jointree, rather 164 * than scanning the rangetable, is that the rangetable may contain RTEs 165 * for rels not actively part of the query, for example views. We don't 166 * want to make RelOptInfos for them. 167 */ 168 add_base_rels_to_query(root, (Node *) parse->jointree); 169 170 /* 171 * Examine the targetlist and join tree, adding entries to baserel 172 * targetlists for all referenced Vars, and generating PlaceHolderInfo 173 * entries for all referenced PlaceHolderVars. Restrict and join clauses 174 * are added to appropriate lists belonging to the mentioned relations. We 175 * also build EquivalenceClasses for provably equivalent expressions. The 176 * SpecialJoinInfo list is also built to hold information about join order 177 * restrictions. Finally, we form a target joinlist for make_one_rel() to 178 * work from. 179 */ 180 build_base_rel_tlists(root, root->processed_tlist); 181 182 find_placeholders_in_jointree(root); 183 184 find_lateral_references(root); 185 186 joinlist = deconstruct_jointree(root); 187 188 /* 189 * Reconsider any postponed outer-join quals now that we have built up 190 * equivalence classes. (This could result in further additions or 191 * mergings of classes.) 192 */ 193 reconsider_outer_join_clauses(root); 194 195 /* 196 * If we formed any equivalence classes, generate additional restriction 197 * clauses as appropriate. (Implied join clauses are formed on-the-fly 198 * later.) 199 */ 200 generate_base_implied_equalities(root); 201 202 /* 203 * We have completed merging equivalence sets, so it's now possible to 204 * generate pathkeys in canonical form; so compute query_pathkeys and 205 * other pathkeys fields in PlannerInfo. 206 */ 207 (*qp_callback) (root, qp_extra); 208 209 /* 210 * Examine any "placeholder" expressions generated during subquery pullup. 211 * Make sure that the Vars they need are marked as needed at the relevant 212 * join level. This must be done before join removal because it might 213 * cause Vars or placeholders to be needed above a join when they weren't 214 * so marked before. 215 */ 216 fix_placeholder_input_needed_levels(root); 217 218 /* 219 * Remove any useless outer joins. Ideally this would be done during 220 * jointree preprocessing, but the necessary information isn't available 221 * until we've built baserel data structures and classified qual clauses. 222 */ 223 joinlist = remove_useless_joins(root, joinlist); 224 225 /* 226 * Also, reduce any semijoins with unique inner rels to plain inner joins. 227 * Likewise, this can't be done until now for lack of needed info. 228 */ 229 reduce_unique_semijoins(root); 230 231 /* 232 * Now distribute "placeholders" to base rels as needed. This has to be 233 * done after join removal because removal could change whether a 234 * placeholder is evaluable at a base rel. 235 */ 236 add_placeholders_to_base_rels(root); 237 238 /* 239 * Construct the lateral reference sets now that we have finalized 240 * PlaceHolderVar eval levels. 241 */ 242 create_lateral_join_info(root); 243 244 /* 245 * Match foreign keys to equivalence classes and join quals. This must be 246 * done after finalizing equivalence classes, and it's useful to wait till 247 * after join removal so that we can skip processing foreign keys 248 * involving removed relations. 249 */ 250 match_foreign_keys_to_quals(root); 251 252 /* 253 * Look for join OR clauses that we can extract single-relation 254 * restriction OR clauses from. 255 */ 256 extract_restriction_or_clauses(root); 257 258 /* 259 * Now expand appendrels by adding "otherrels" for their children. We 260 * delay this to the end so that we have as much information as possible 261 * available for each baserel, including all restriction clauses. That 262 * let us prune away partitions that don't satisfy a restriction clause. 263 * Also note that some information such as lateral_relids is propagated 264 * from baserels to otherrels here, so we must have computed it already. 265 */ 266 add_other_rels_to_query(root); 267 268 /* 269 * Ready to do the primary planning. 270 */ 271 final_rel = make_one_rel(root, joinlist); 272 273 /* Check that we got at least one usable path */ 274 if (!final_rel || !final_rel->cheapest_total_path || 275 final_rel->cheapest_total_path->param_info != NULL) 276 elog(ERROR, "failed to construct the join relation"); 277 278 return final_rel; 279 } 280