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-2018, 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 query_planner(PlannerInfo *root, List *tlist, 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 */ 125 setup_simple_rel_arrays(root); 126 127 /* 128 * Populate append_rel_array with each AppendRelInfo to allow direct 129 * lookups by child relid. 130 */ 131 setup_append_rel_array(root); 132 133 /* 134 * Construct RelOptInfo nodes for all base relations in query, and 135 * indirectly for all appendrel member relations ("other rels"). This 136 * will give us a RelOptInfo for every "simple" (non-join) rel involved in 137 * the query. 138 * 139 * Note: the reason we find the rels by searching the jointree and 140 * appendrel list, rather than just scanning the rangetable, is that the 141 * rangetable may contain RTEs for rels not actively part of the query, 142 * for example views. We don't want to make RelOptInfos for them. 143 */ 144 add_base_rels_to_query(root, (Node *) parse->jointree); 145 146 /* 147 * Examine the targetlist and join tree, adding entries to baserel 148 * targetlists for all referenced Vars, and generating PlaceHolderInfo 149 * entries for all referenced PlaceHolderVars. Restrict and join clauses 150 * are added to appropriate lists belonging to the mentioned relations. We 151 * also build EquivalenceClasses for provably equivalent expressions. The 152 * SpecialJoinInfo list is also built to hold information about join order 153 * restrictions. Finally, we form a target joinlist for make_one_rel() to 154 * work from. 155 */ 156 build_base_rel_tlists(root, tlist); 157 158 find_placeholders_in_jointree(root); 159 160 find_lateral_references(root); 161 162 joinlist = deconstruct_jointree(root); 163 164 /* 165 * Reconsider any postponed outer-join quals now that we have built up 166 * equivalence classes. (This could result in further additions or 167 * mergings of classes.) 168 */ 169 reconsider_outer_join_clauses(root); 170 171 /* 172 * If we formed any equivalence classes, generate additional restriction 173 * clauses as appropriate. (Implied join clauses are formed on-the-fly 174 * later.) 175 */ 176 generate_base_implied_equalities(root); 177 178 /* 179 * We have completed merging equivalence sets, so it's now possible to 180 * generate pathkeys in canonical form; so compute query_pathkeys and 181 * other pathkeys fields in PlannerInfo. 182 */ 183 (*qp_callback) (root, qp_extra); 184 185 /* 186 * Examine any "placeholder" expressions generated during subquery pullup. 187 * Make sure that the Vars they need are marked as needed at the relevant 188 * join level. This must be done before join removal because it might 189 * cause Vars or placeholders to be needed above a join when they weren't 190 * so marked before. 191 */ 192 fix_placeholder_input_needed_levels(root); 193 194 /* 195 * Remove any useless outer joins. Ideally this would be done during 196 * jointree preprocessing, but the necessary information isn't available 197 * until we've built baserel data structures and classified qual clauses. 198 */ 199 joinlist = remove_useless_joins(root, joinlist); 200 201 /* 202 * Also, reduce any semijoins with unique inner rels to plain inner joins. 203 * Likewise, this can't be done until now for lack of needed info. 204 */ 205 reduce_unique_semijoins(root); 206 207 /* 208 * Now distribute "placeholders" to base rels as needed. This has to be 209 * done after join removal because removal could change whether a 210 * placeholder is evaluable at a base rel. 211 */ 212 add_placeholders_to_base_rels(root); 213 214 /* 215 * Construct the lateral reference sets now that we have finalized 216 * PlaceHolderVar eval levels. 217 */ 218 create_lateral_join_info(root); 219 220 /* 221 * Match foreign keys to equivalence classes and join quals. This must be 222 * done after finalizing equivalence classes, and it's useful to wait till 223 * after join removal so that we can skip processing foreign keys 224 * involving removed relations. 225 */ 226 match_foreign_keys_to_quals(root); 227 228 /* 229 * Look for join OR clauses that we can extract single-relation 230 * restriction OR clauses from. 231 */ 232 extract_restriction_or_clauses(root); 233 234 /* 235 * We should now have size estimates for every actual table involved in 236 * the query, and we also know which if any have been deleted from the 237 * query by join removal; so we can compute total_table_pages. 238 * 239 * Note that appendrels are not double-counted here, even though we don't 240 * bother to distinguish RelOptInfos for appendrel parents, because the 241 * parents will still have size zero. 242 * 243 * XXX if a table is self-joined, we will count it once per appearance, 244 * which perhaps is the wrong thing ... but that's not completely clear, 245 * and detecting self-joins here is difficult, so ignore it for now. 246 */ 247 total_pages = 0; 248 for (rti = 1; rti < root->simple_rel_array_size; rti++) 249 { 250 RelOptInfo *brel = root->simple_rel_array[rti]; 251 252 if (brel == NULL) 253 continue; 254 255 Assert(brel->relid == rti); /* sanity check on array */ 256 257 if (IS_SIMPLE_REL(brel)) 258 total_pages += (double) brel->pages; 259 } 260 root->total_table_pages = total_pages; 261 262 /* 263 * Ready to do the primary planning. 264 */ 265 final_rel = make_one_rel(root, joinlist); 266 267 /* Check that we got at least one usable path */ 268 if (!final_rel || !final_rel->cheapest_total_path || 269 final_rel->cheapest_total_path->param_info != NULL) 270 elog(ERROR, "failed to construct the join relation"); 271 272 return final_rel; 273 } 274