*** a/src/backend/optimizer/path/joinpath.c --- b/src/backend/optimizer/path/joinpath.c *************** *** 473,478 **** match_unsorted_outer(PlannerInfo *root, --- 473,481 ---- if (nestjoinOK) { + Path *paths[5]; + int npath = 0; + /* * Always consider a nestloop join with this outer and * cheapest-total-cost inner. When appropriate, also consider *************** *** 480,486 **** match_unsorted_outer(PlannerInfo *root, * cheapest-startup-cost inner path, and the cheapest innerjoin * indexpaths. */ ! add_path(joinrel, (Path *) create_nestloop_path(root, joinrel, jointype, --- 483,489 ---- * cheapest-startup-cost inner path, and the cheapest innerjoin * indexpaths. */ ! paths[npath++] = (Path *) create_nestloop_path(root, joinrel, jointype, *************** *** 488,496 **** match_unsorted_outer(PlannerInfo *root, outerpath, inner_cheapest_total, restrictlist, ! merge_pathkeys)); if (matpath != NULL) ! add_path(joinrel, (Path *) create_nestloop_path(root, joinrel, jointype, --- 491,499 ---- outerpath, inner_cheapest_total, restrictlist, ! merge_pathkeys); if (matpath != NULL) ! paths[npath++] = (Path *) create_nestloop_path(root, joinrel, jointype, *************** *** 498,506 **** match_unsorted_outer(PlannerInfo *root, outerpath, matpath, restrictlist, ! merge_pathkeys)); if (inner_cheapest_startup != inner_cheapest_total) ! add_path(joinrel, (Path *) create_nestloop_path(root, joinrel, jointype, --- 501,509 ---- outerpath, matpath, restrictlist, ! merge_pathkeys); if (inner_cheapest_startup != inner_cheapest_total) ! paths[npath++] = (Path *) create_nestloop_path(root, joinrel, jointype, *************** *** 508,516 **** match_unsorted_outer(PlannerInfo *root, outerpath, inner_cheapest_startup, restrictlist, ! merge_pathkeys)); if (index_cheapest_total != NULL) ! add_path(joinrel, (Path *) create_nestloop_path(root, joinrel, jointype, --- 511,519 ---- outerpath, inner_cheapest_startup, restrictlist, ! merge_pathkeys); if (index_cheapest_total != NULL) ! paths[npath++] = (Path *) create_nestloop_path(root, joinrel, jointype, *************** *** 518,527 **** match_unsorted_outer(PlannerInfo *root, outerpath, index_cheapest_total, restrictlist, ! merge_pathkeys)); if (index_cheapest_startup != NULL && index_cheapest_startup != index_cheapest_total) ! add_path(joinrel, (Path *) create_nestloop_path(root, joinrel, jointype, --- 521,530 ---- outerpath, index_cheapest_total, restrictlist, ! merge_pathkeys); if (index_cheapest_startup != NULL && index_cheapest_startup != index_cheapest_total) ! paths[npath++] = (Path *) create_nestloop_path(root, joinrel, jointype, *************** *** 529,535 **** match_unsorted_outer(PlannerInfo *root, outerpath, index_cheapest_startup, restrictlist, ! merge_pathkeys)); } /* Can't do anything else if outer path needs to be unique'd */ --- 532,540 ---- outerpath, index_cheapest_startup, restrictlist, ! merge_pathkeys); ! ! add_similar_paths(joinrel, paths, npath); } /* Can't do anything else if outer path needs to be unique'd */ *** a/src/backend/optimizer/util/pathnode.c --- b/src/backend/optimizer/util/pathnode.c *************** *** 86,138 **** compare_path_costs(Path *path1, Path *path2, CostSelector criterion) /* * compare_fuzzy_path_costs * Return -1, 0, or +1 according as path1 is cheaper, the same cost, ! * or more expensive than path2 for the specified criterion. * * This differs from compare_path_costs in that we consider the costs the * same if they agree to within a "fuzz factor". This is used by add_path * to avoid keeping both of a pair of paths that really have insignificantly * different cost. */ static int ! compare_fuzzy_path_costs(Path *path1, Path *path2, CostSelector criterion) { /* * We use a fuzz factor of 1% of the smaller cost. * * XXX does this percentage need to be user-configurable? */ ! if (criterion == STARTUP_COST) ! { ! if (path1->startup_cost > path2->startup_cost * 1.01) ! return +1; ! if (path2->startup_cost > path1->startup_cost * 1.01) ! return -1; ! /* ! * If paths have the same startup cost (not at all unlikely), order ! * them by total cost. ! */ ! if (path1->total_cost > path2->total_cost * 1.01) ! return +1; ! if (path2->total_cost > path1->total_cost * 1.01) ! return -1; ! } else ! { ! if (path1->total_cost > path2->total_cost * 1.01) ! return +1; ! if (path2->total_cost > path1->total_cost * 1.01) ! return -1; ! /* ! * If paths have the same total cost, order them by startup cost. ! */ ! if (path1->startup_cost > path2->startup_cost * 1.01) ! return +1; ! if (path2->startup_cost > path1->startup_cost * 1.01) ! return -1; ! } ! return 0; } /* --- 86,134 ---- /* * compare_fuzzy_path_costs * Return -1, 0, or +1 according as path1 is cheaper, the same cost, ! * or more expensive than path2 based on total cost. Returns a similar ! * value for startup cost via third argument. * * This differs from compare_path_costs in that we consider the costs the * same if they agree to within a "fuzz factor". This is used by add_path * to avoid keeping both of a pair of paths that really have insignificantly * different cost. + * + * It turns out that this function is a hot spot for query planning, and + * we nearly always need to know both the result of the total cost comparison + * and the result of the startup cost comparison. So it pays to work out + * both results in a a single call. */ static int ! compare_fuzzy_path_costs(Path *path1, Path *path2, int *startup_cost) { + int t, s; + /* * We use a fuzz factor of 1% of the smaller cost. * * XXX does this percentage need to be user-configurable? */ ! if (path1->startup_cost > path2->startup_cost * 1.01) ! s = +1; ! else if (path2->startup_cost > path1->startup_cost * 1.01) ! s = -1; ! else ! s = 0; ! /* ! * If paths have the same startup cost (not at all unlikely), order ! * them by total cost. ! */ ! if (path1->total_cost > path2->total_cost * 1.01) ! t = +1; ! else if (path2->total_cost > path1->total_cost * 1.01) ! t = -1; else ! t = s; ! *startup_cost = (s == 0) ? t : s; ! return t; } /* *************** *** 272,285 **** add_path(RelOptInfo *parent_rel, Path *new_path) { Path *old_path = (Path *) lfirst(p1); bool remove_old = false; /* unless new proves superior */ ! int costcmp; /* * As of Postgres 8.0, we use fuzzy cost comparison to avoid wasting * cycles keeping paths that are really not significantly different in * cost. */ ! costcmp = compare_fuzzy_path_costs(new_path, old_path, TOTAL_COST); /* * If the two paths compare differently for startup and total cost, --- 268,282 ---- { Path *old_path = (Path *) lfirst(p1); bool remove_old = false; /* unless new proves superior */ ! int costcmp, startup_costcmp; /* * As of Postgres 8.0, we use fuzzy cost comparison to avoid wasting * cycles keeping paths that are really not significantly different in * cost. */ ! costcmp = compare_fuzzy_path_costs(new_path, old_path, ! &startup_costcmp); /* * If the two paths compare differently for startup and total cost, *************** *** 290,298 **** add_path(RelOptInfo *parent_rel, Path *new_path) * effectively equal (and, therefore, there's no need to call it twice * in that case). */ ! if (costcmp == 0 || ! costcmp == compare_fuzzy_path_costs(new_path, old_path, ! STARTUP_COST)) { switch (compare_pathkeys(new_path->pathkeys, old_path->pathkeys)) { --- 287,293 ---- * effectively equal (and, therefore, there's no need to call it twice * in that case). */ ! if (costcmp == 0 || costcmp == startup_costcmp) { switch (compare_pathkeys(new_path->pathkeys, old_path->pathkeys)) { *************** *** 383,388 **** add_path(RelOptInfo *parent_rel, Path *new_path) --- 378,419 ---- } } + /* + * add_similar_paths + * Consider a number of similar paths, as add_path. The paths should all + * have the same pathkeys. This is more efficient than calling add_path + * on each one individually. + */ + void + add_similar_paths(RelOptInfo *parent_rel, Path **paths, int npath) + { + int i, j; + Path *cheapest_total, *cheapest_startup; + + /* Decide on best candidates. */ + cheapest_total = paths[0]; + cheapest_startup = paths[0]; + for (i = 1; i < npath; ++i) + { + int startup_costcmp; + if (compare_fuzzy_path_costs(cheapest_total, paths[i], + &startup_costcmp) > 0) + cheapest_total = paths[i]; + if (startup_costcmp > 0) + cheapest_startup = paths[i]; + } + + /* Discard losers (except IndexPaths) as per comments in add_path())). */ + for (j = 0; j < npath; ++j) + if (paths[j] != cheapest_total && paths[j] != cheapest_startup + && !IsA(paths[j], IndexPath)) + pfree(paths[j]); + + /* Consider winners further. */ + add_path(parent_rel, cheapest_total); + if (cheapest_total != cheapest_startup) + add_path(parent_rel, cheapest_startup); + } /***************************************************************************** * PATH NODE CREATION ROUTINES *** a/src/include/optimizer/pathnode.h --- b/src/include/optimizer/pathnode.h *************** *** 26,31 **** extern int compare_fractional_path_costs(Path *path1, Path *path2, --- 26,33 ---- double fraction); extern void set_cheapest(RelOptInfo *parent_rel); extern void add_path(RelOptInfo *parent_rel, Path *new_path); + extern void add_similar_paths(RelOptInfo *parent_rel, Path **new_paths, + int npath); extern Path *create_seqscan_path(PlannerInfo *root, RelOptInfo *rel); extern IndexPath *create_index_path(PlannerInfo *root,