I've been doing some benchmarking and profiling on the PostgreSQL query analyzer, and it seems that (at least for the sorts of queries that I typically run) the dominant cost is add_path(). I've been able to find two optimizations that seem to help significantly:
1. add_path() often calls compare_fuzzy_path_costs() twice on the same pair of paths, and when the paths compare equal on one criterion, some comparisons are duplicated. I've refactored this function to return the results of both calculations without repeating any floating-point arithmetic. 2. match_unsorted_outer() adds as many as 5 nested loop joins at a time with the same set of pathkeys. In my tests, it tended to be ~3 - cheapest inner, cheapest inner materialized, and cheapest inner index. Since these all have the same pathkeys, clearly only the one with the cheapest total cost is in the running for cheapest total cost for that set of pathkeys, and likewise for startup cost (and the two may be the same). Yet we compare all of them against the whole pathlist, one after the other, including (for the most part) the rather expensive pathkey comparison. I've added a function add_similar_paths() and refactored match_unsorted_outer() to use it. On a couple of complex (and proprietary) queries with 12+ joins each, I measure a planning time improvement of 8-12% with the attached patch applied. It would be interesting to try to replicate this on a publicly available data set, but I don't know of a good one to use. Suggestions welcome - results of performance testing on your own favorite big queries even more welcome. Simple test harness also attached. I took the approach of dropping caches, starting the server, and then running this 5 times each on several queries, dropping top and bottom results. ...Robert
*** 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,
explain_loop.pl
Description: Perl program
-- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
