diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index 4775acf..87304ba 100644 *** a/src/backend/nodes/outfuncs.c --- b/src/backend/nodes/outfuncs.c *************** _outRelOptInfo(StringInfo str, const Rel *** 1844,1849 **** --- 1844,1850 ---- WRITE_FLOAT_FIELD(rows, "%.0f"); WRITE_INT_FIELD(width); WRITE_BOOL_FIELD(consider_startup); + WRITE_BOOL_FIELD(consider_param_startup); WRITE_NODE_FIELD(reltargetlist); WRITE_NODE_FIELD(pathlist); WRITE_NODE_FIELD(ppilist); diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README index d51fd57..d1349aa 100644 *** a/src/backend/optimizer/README --- b/src/backend/optimizer/README *************** a nestloop that provides parameters to t *** 795,801 **** do not ignore merge joins entirely, joinpath.c does not fully explore the space of potential merge joins with parameterized inputs. Also, add_path treats parameterized paths as having no pathkeys, so that they compete ! only on total cost and rowcount; they don't get preference for producing a special sort order. This creates additional bias against merge joins, since we might discard a path that could have been useful for performing a merge without an explicit sort step. Since a parameterized path must --- 795,801 ---- do not ignore merge joins entirely, joinpath.c does not fully explore the space of potential merge joins with parameterized inputs. Also, add_path treats parameterized paths as having no pathkeys, so that they compete ! only on cost and rowcount; they don't get preference for producing a special sort order. This creates additional bias against merge joins, since we might discard a path that could have been useful for performing a merge without an explicit sort step. Since a parameterized path must *************** uninteresting, these choices do not affe *** 804,809 **** --- 804,817 ---- output order of a query --- they only make it harder to use a merge join at a lower level. The savings in planning work justifies that. + Similarly, parameterized paths do not normally get preference in add_path + for having cheap startup cost; that's seldom of much value when on the + inside of a nestloop, so it seems not worth keeping extra paths solely for + that. An exception occurs for parameterized paths for the RHS relation of + a SEMI or ANTI join: in those cases, we can stop the inner scan after the + first match, so that it's primarily startup not total cost that we care + about. + LATERAL subqueries ------------------ diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 4e6d90d..0b83189 100644 *** a/src/backend/optimizer/path/allpaths.c --- b/src/backend/optimizer/path/allpaths.c *************** set_rel_pathlist_hook_type set_rel_pathl *** 61,66 **** --- 61,67 ---- join_search_hook_type join_search_hook = NULL; + static void set_base_rel_consider_startup(PlannerInfo *root); static void set_base_rel_sizes(PlannerInfo *root); static void set_base_rel_pathlists(PlannerInfo *root); static void set_rel_size(PlannerInfo *root, RelOptInfo *rel, *************** make_one_rel(PlannerInfo *root, List *jo *** 152,157 **** --- 153,161 ---- root->all_baserels = bms_add_member(root->all_baserels, brel->relid); } + /* Mark base rels as to whether we care about fast-start plans */ + set_base_rel_consider_startup(root); + /* * Generate access paths for the base rels. */ *************** make_one_rel(PlannerInfo *root, List *jo *** 172,177 **** --- 176,224 ---- } /* + * set_base_rel_consider_startup + * Set the consider_[param_]startup flags for each base-relation entry. + * + * For the moment, we only deal with consider_param_startup here; because the + * logic for consider_startup is pretty trivial and is the same for every base + * relation, we just let build_simple_rel() initialize that flag correctly to + * start with. If that logic ever gets more complicated it would probably + * be better to move it here. + */ + static void + set_base_rel_consider_startup(PlannerInfo *root) + { + /* + * Since parameterized paths can only be used on the inside of a nestloop + * join plan, there is usually little value in considering fast-start + * plans for them. However, for relations that are on the RHS of a SEMI + * or ANTI join, a fast-start plan can be useful because we're only going + * to care about fetching one tuple anyway. + * + * To minimize growth of planning time, we currently restrict this to + * cases where the RHS is a single base relation, not a join; there is no + * provision for consider_param_startup to get set at all on joinrels. + * Also we don't worry about appendrels. costsize.c's costing rules for + * nestloop semi/antijoins don't consider such cases either. + */ + ListCell *lc; + + foreach(lc, root->join_info_list) + { + SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc); + int varno; + + if ((sjinfo->jointype == JOIN_SEMI || sjinfo->jointype == JOIN_ANTI) && + bms_get_singleton_member(sjinfo->syn_righthand, &varno)) + { + RelOptInfo *rel = find_base_rel(root, varno); + + rel->consider_param_startup = true; + } + } + } + + /* * set_base_rel_sizes * Set the size estimates (rows and widths) for each base-relation entry. * diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 7f7aa24..2afd59a 100644 *** a/src/backend/optimizer/util/pathnode.c --- b/src/backend/optimizer/util/pathnode.c *************** compare_fractional_path_costs(Path *path *** 138,156 **** * total cost, we just say that their costs are "different", since neither * dominates the other across the whole performance spectrum. * ! * If consider_startup is false, then we don't care about keeping paths with ! * good startup cost, so we'll never return COSTS_DIFFERENT. ! * ! * This function also includes special hacks to support a policy enforced ! * by its sole caller, add_path(): paths that have any parameterization ! * cannot win comparisons on the grounds of having cheaper startup cost, ! * since we deem only total cost to be of interest for a parameterized path. ! * (Unparameterized paths are more common, so we check for this case last.) */ static PathCostComparison ! compare_path_costs_fuzzily(Path *path1, Path *path2, double fuzz_factor, ! bool consider_startup) { /* * Check total cost first since it's more likely to be different; many * paths have zero startup cost. --- 138,154 ---- * total cost, we just say that their costs are "different", since neither * dominates the other across the whole performance spectrum. * ! * This function also enforces a policy rule that paths for which the relevant ! * one of parent->consider_startup and parent->consider_param_startup is false ! * cannot win comparisons on the grounds of good startup cost, so we never ! * return COSTS_DIFFERENT when that is true for the total-cost loser. */ static PathCostComparison ! compare_path_costs_fuzzily(Path *path1, Path *path2, double fuzz_factor) { + #define CONSIDER_PATH_STARTUP_COST(p) \ + ((p)->param_info == NULL ? (p)->parent->consider_startup : (p)->parent->consider_param_startup) + /* * Check total cost first since it's more likely to be different; many * paths have zero startup cost. *************** compare_path_costs_fuzzily(Path *path1, *** 158,166 **** if (path1->total_cost > path2->total_cost * fuzz_factor) { /* path1 fuzzily worse on total cost */ ! if (consider_startup && ! path2->startup_cost > path1->startup_cost * fuzz_factor && ! path1->param_info == NULL) { /* ... but path2 fuzzily worse on startup, so DIFFERENT */ return COSTS_DIFFERENT; --- 156,163 ---- if (path1->total_cost > path2->total_cost * fuzz_factor) { /* path1 fuzzily worse on total cost */ ! if (CONSIDER_PATH_STARTUP_COST(path1) && ! path2->startup_cost > path1->startup_cost * fuzz_factor) { /* ... but path2 fuzzily worse on startup, so DIFFERENT */ return COSTS_DIFFERENT; *************** compare_path_costs_fuzzily(Path *path1, *** 171,179 **** if (path2->total_cost > path1->total_cost * fuzz_factor) { /* path2 fuzzily worse on total cost */ ! if (consider_startup && ! path1->startup_cost > path2->startup_cost * fuzz_factor && ! path2->param_info == NULL) { /* ... but path1 fuzzily worse on startup, so DIFFERENT */ return COSTS_DIFFERENT; --- 168,175 ---- if (path2->total_cost > path1->total_cost * fuzz_factor) { /* path2 fuzzily worse on total cost */ ! if (CONSIDER_PATH_STARTUP_COST(path2) && ! path1->startup_cost > path2->startup_cost * fuzz_factor) { /* ... but path1 fuzzily worse on startup, so DIFFERENT */ return COSTS_DIFFERENT; *************** compare_path_costs_fuzzily(Path *path1, *** 181,188 **** /* else path1 dominates */ return COSTS_BETTER1; } ! /* fuzzily the same on total cost */ ! /* (so we may as well compare startup cost, even if !consider_startup) */ if (path1->startup_cost > path2->startup_cost * fuzz_factor && path2->param_info == NULL) { --- 177,189 ---- /* else path1 dominates */ return COSTS_BETTER1; } ! ! /* ! * Fuzzily the same on total cost (so we might as well compare startup ! * cost, even when that would otherwise be uninteresting; but ! * parameterized paths aren't allowed to win this way, we'd rather move on ! * to other comparison heuristics) ! */ if (path1->startup_cost > path2->startup_cost * fuzz_factor && path2->param_info == NULL) { *************** compare_path_costs_fuzzily(Path *path1, *** 197,202 **** --- 198,205 ---- } /* fuzzily the same on both costs */ return COSTS_EQUAL; + + #undef CONSIDER_PATH_STARTUP_COST } /* *************** compare_path_costs_fuzzily(Path *path1, *** 212,222 **** * * The cheapest_parameterized_paths list collects all parameterized paths * that have survived the add_path() tournament for this relation. (Since ! * add_path ignores pathkeys and startup cost for a parameterized path, ! * these will be paths that have best total cost or best row count for their ! * parameterization.) cheapest_parameterized_paths always includes the ! * cheapest-total unparameterized path, too, if there is one; the users of ! * that list find it more convenient if that's included. * * This is normally called only after we've finished constructing the path * list for the rel node. --- 215,225 ---- * * The cheapest_parameterized_paths list collects all parameterized paths * that have survived the add_path() tournament for this relation. (Since ! * add_path ignores pathkeys for a parameterized path, these will be paths ! * that have best cost or best row count for their parameterization.) ! * cheapest_parameterized_paths always includes the cheapest-total ! * unparameterized path, too, if there is one; the users of that list find ! * it more convenient if that's included. * * This is normally called only after we've finished constructing the path * list for the rel node. *************** set_cheapest(RelOptInfo *parent_rel) *** 361,374 **** * cases do arise, so we make the full set of checks anyway. * * There are two policy decisions embedded in this function, along with ! * its sibling add_path_precheck: we treat all parameterized paths as ! * having NIL pathkeys, and we ignore their startup costs, so that they ! * compete only on parameterization, total cost and rowcount. This is to ! * reduce the number of parameterized paths that are kept. See discussion ! * in src/backend/optimizer/README. * ! * Another policy that is enforced here is that we only consider cheap ! * startup cost to be interesting if parent_rel->consider_startup is true. * * The pathlist is kept sorted by total_cost, with cheaper paths * at the front. Within this routine, that's simply a speed hack: --- 364,378 ---- * cases do arise, so we make the full set of checks anyway. * * There are two policy decisions embedded in this function, along with ! * its sibling add_path_precheck. First, we treat all parameterized paths ! * as having NIL pathkeys, so that they cannot win comparisons on the ! * basis of sort order. This is to reduce the number of parameterized ! * paths that are kept; see discussion in src/backend/optimizer/README. * ! * Second, we only consider cheap startup cost to be interesting if ! * parent_rel->consider_startup is true for an unparameterized path, or ! * parent_rel->consider_param_startup is true for a parameterized one. ! * Again, this allows discarding useless paths sooner. * * The pathlist is kept sorted by total_cost, with cheaper paths * at the front. Within this routine, that's simply a speed hack: *************** add_path(RelOptInfo *parent_rel, Path *n *** 433,440 **** * Do a fuzzy cost comparison with 1% fuzziness limit. (XXX does this * percentage need to be user-configurable?) */ ! costcmp = compare_path_costs_fuzzily(new_path, old_path, 1.01, ! parent_rel->consider_startup); /* * If the two paths compare differently for startup and total cost, --- 437,443 ---- * Do a fuzzy cost comparison with 1% fuzziness limit. (XXX does this * percentage need to be user-configurable?) */ ! costcmp = compare_path_costs_fuzzily(new_path, old_path, 1.01); /* * If the two paths compare differently for startup and total cost, *************** add_path(RelOptInfo *parent_rel, Path *n *** 501,508 **** accept_new = false; /* old dominates new */ else if (compare_path_costs_fuzzily(new_path, old_path, ! 1.0000000001, ! parent_rel->consider_startup) == COSTS_BETTER1) remove_old = true; /* new dominates old */ else accept_new = false; /* old equals or --- 504,510 ---- accept_new = false; /* old dominates new */ else if (compare_path_costs_fuzzily(new_path, old_path, ! 1.0000000001) == COSTS_BETTER1) remove_old = true; /* new dominates old */ else accept_new = false; /* old equals or *************** add_path_precheck(RelOptInfo *parent_rel *** 622,632 **** --- 624,638 ---- List *pathkeys, Relids required_outer) { List *new_path_pathkeys; + bool consider_startup; ListCell *p1; /* Pretend parameterized paths have no pathkeys, per add_path policy */ new_path_pathkeys = required_outer ? NIL : pathkeys; + /* Decide whether new path's startup cost is interesting */ + consider_startup = required_outer ? parent_rel->consider_param_startup : parent_rel->consider_startup; + foreach(p1, parent_rel->pathlist) { Path *old_path = (Path *) lfirst(p1); *************** add_path_precheck(RelOptInfo *parent_rel *** 644,651 **** */ if (total_cost >= old_path->total_cost) { ! /* can win on startup cost only if unparameterized */ ! if (startup_cost >= old_path->startup_cost || required_outer) { /* new path does not win on cost, so check pathkeys... */ List *old_path_pathkeys; --- 650,657 ---- */ if (total_cost >= old_path->total_cost) { ! /* new path can win on startup cost only if consider_startup */ ! if (startup_cost >= old_path->startup_cost || !consider_startup) { /* new path does not win on cost, so check pathkeys... */ List *old_path_pathkeys; diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 1d635cd..be2ef3b 100644 *** a/src/backend/optimizer/util/relnode.c --- b/src/backend/optimizer/util/relnode.c *************** build_simple_rel(PlannerInfo *root, int *** 101,106 **** --- 101,107 ---- rel->width = 0; /* cheap startup cost is interesting iff not all tuples to be retrieved */ rel->consider_startup = (root->tuple_fraction > 0); + rel->consider_param_startup = false; /* might get changed later */ rel->reltargetlist = NIL; rel->pathlist = NIL; rel->ppilist = NIL; *************** build_join_rel(PlannerInfo *root, *** 361,366 **** --- 362,368 ---- joinrel->width = 0; /* cheap startup cost is interesting iff not all tuples to be retrieved */ joinrel->consider_startup = (root->tuple_fraction > 0); + joinrel->consider_param_startup = false; joinrel->reltargetlist = NIL; joinrel->pathlist = NIL; joinrel->ppilist = NIL; diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index 706b6d1..33b0874 100644 *** a/src/include/nodes/relation.h --- b/src/include/nodes/relation.h *************** typedef struct PlannerInfo *** 321,328 **** * clauses have been applied (ie, output rows of a plan for it) * width - avg. number of bytes per tuple in the relation after the * appropriate projections have been done (ie, output width) ! * consider_startup - true if there is any value in keeping paths for * this rel on the basis of having cheap startup cost * reltargetlist - List of Var and PlaceHolderVar nodes for the values * we need to output from this relation. * List is in no particular order, but all rels of an --- 321,329 ---- * clauses have been applied (ie, output rows of a plan for it) * width - avg. number of bytes per tuple in the relation after the * appropriate projections have been done (ie, output width) ! * consider_startup - true if there is any value in keeping plain paths for * this rel on the basis of having cheap startup cost + * consider_param_startup - the same for parameterized paths * reltargetlist - List of Var and PlaceHolderVar nodes for the values * we need to output from this relation. * List is in no particular order, but all rels of an *************** typedef struct RelOptInfo *** 437,442 **** --- 438,444 ---- /* per-relation planner control flags */ bool consider_startup; /* keep cheap-startup-cost paths? */ + bool consider_param_startup; /* ditto, for parameterized paths? */ /* materialization information */ List *reltargetlist; /* Vars to be output by scan of relation */