Re: add_path optimization

[ This patch is on the 2009-First commitfest list, but there was earlier
discussion to the effect that it might be a good idea to include in 8.4,
so I made some time to look at it. ]

Robert Haas <robertmhaas@gmail.com> writes:
> 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:

I got around to testing this patch a bit today, and I'm afraid it
doesn't look very good from here.  The test case I used was a psql
script with 10000 repetitions of

explain select * from information_schema.table_constraints join information_schema.referential_constraints using
(constraint_catalog,constraint_schema,constraint_name);

which isn't terribly creative, but those two views incorporate multiple
joins so I figured this was a reasonably middle-of-the-road planner
exercise.

I first tried just the compare_fuzzy_path_costs() change and really
couldn't measure any reliable difference.  oprofile output for CVS HEAD
looks like

PU: P4 / Xeon with 2 hyper-threads, speed 2792.99 MHz (estimated)
Counted GLOBAL_POWER_EVENTS events (time during which processor is not stopped) 
with a unit mask of 0x01 (mandatory) count 100000
samples  %        image name               symbol name
149294    9.7519  postgres                 AllocSetAlloc
85437     5.5808  postgres                 SearchCatCache
45520     2.9734  postgres                 copyObject
39525     2.5818  postgres                 add_path
35878     2.3436  postgres                 expression_tree_walker
29733     1.9422  libc-2.8.so              memcpy
25560     1.6696  postgres                 MemoryContextAllocZeroAligned
20879     1.3638  libc-2.8.so              strlen
20521     1.3404  postgres                 add_paths_to_joinrel
20054     1.3099  postgres                 AllocSetFree
20023     1.3079  postgres                 cost_mergejoin
19363     1.2648  postgres                 nocachegetattr
17689     1.1554  libc-2.8.so              vfprintf
17335     1.1323  postgres                 generate_join_implied_equalities
16085     1.0507  postgres                 MemoryContextAlloc

and with the compare_fuzzy_path_costs() change

CPU: P4 / Xeon with 2 hyper-threads, speed 2792.99 MHz (estimated)
Counted GLOBAL_POWER_EVENTS events (time during which processor is not stopped) 
with a unit mask of 0x01 (mandatory) count 100000
samples  %        image name               symbol name
144882    9.6951  postgres                 AllocSetAlloc
84205     5.6348  postgres                 SearchCatCache
43956     2.9414  postgres                 copyObject
37418     2.5039  postgres                 add_path
34865     2.3331  postgres                 expression_tree_walker
28718     1.9217  libc-2.8.so              memcpy
23643     1.5821  postgres                 MemoryContextAllocZeroAligned
20835     1.3942  libc-2.8.so              strlen
20065     1.3427  postgres                 cost_mergejoin
19672     1.3164  postgres                 AllocSetFree
18992     1.2709  postgres                 add_paths_to_joinrel
18802     1.2582  postgres                 nocachegetattr
17109     1.1449  libc-2.8.so              __printf_fp
16901     1.1310  libc-2.8.so              vfprintf
16159     1.0813  postgres                 hash_search_with_hash_value
16039     1.0733  postgres                 generate_join_implied_equalities
15554     1.0408  postgres                 MemoryContextAlloc
14981     1.0025  postgres                 expression_tree_mutator

Note that the compiler is inlining compare_fuzzy_path_costs in both
cases.

I then added the add_similar_paths change, and got this:

CPU: P4 / Xeon with 2 hyper-threads, speed 2792.99 MHz (estimated)
Counted GLOBAL_POWER_EVENTS events (time during which processor is not stopped) 
with a unit mask of 0x01 (mandatory) count 100000
samples  %        image name               symbol name
142645    9.6668  postgres                 AllocSetAlloc
83161     5.6357  postgres                 SearchCatCache
44660     3.0265  postgres                 copyObject
35762     2.4235  postgres                 expression_tree_walker
28427     1.9264  postgres                 add_path
27970     1.8955  libc-2.8.so              memcpy
23317     1.5801  postgres                 MemoryContextAllocZeroAligned
20685     1.4018  libc-2.8.so              strlen
19646     1.3314  postgres                 add_paths_to_joinrel
19129     1.2963  postgres                 AllocSetFree
18065     1.2242  postgres                 cost_mergejoin
17768     1.2041  postgres                 nocachegetattr
17249     1.1689  postgres                 generate_join_implied_equalities
16784     1.1374  libc-2.8.so              vfprintf
15740     1.0667  libc-2.8.so              __printf_fp
15642     1.0600  postgres                 MemoryContextAlloc
15194     1.0297  postgres                 expression_tree_mutator
15009     1.0171  postgres                 hash_search_with_hash_value
...
7746      0.5249  postgres                 add_similar_paths

where at least you can see a change in add_path's percentage, although
overall runtime did not change measurably; and in any case whatever was
saved seems to have gone into add_similar_paths.

It gets worse though: add_similar_paths is flat *wrong*.  It compares
each successive path to only the current cheapest-total candidate,
and thus is quite likely to seize on the wrong cheapest-startup path.
I tried fixing its loop logic like so:
   for (i = 1; i < npath; ++i)   {       if (compare_fuzzy_path_costs(cheapest_total, paths[i], TOTAL_COST) > 0)
  cheapest_total = paths[i];       if (compare_fuzzy_path_costs(cheapest_startup, paths[i], STARTUP_COST) > 0)
cheapest_startup = paths[i];   }
 

(obviously, this is with compare_fuzzy_path_costs reverted to its form
in HEAD) and got this:

CPU: P4 / Xeon with 2 hyper-threads, speed 2792.99 MHz (estimated)
Counted GLOBAL_POWER_EVENTS events (time during which processor is not stopped) 
with a unit mask of 0x01 (mandatory) count 100000
samples  %        image name               symbol name
143675    9.6105  postgres                 AllocSetAlloc
83809     5.6060  postgres                 SearchCatCache
43837     2.9323  postgres                 copyObject
35790     2.3940  postgres                 expression_tree_walker
29870     1.9980  postgres                 compare_fuzzy_path_costs
28521     1.9078  libc-2.8.so              memcpy
23448     1.5685  postgres                 MemoryContextAllocZeroAligned
21049     1.4080  libc-2.8.so              strlen
18343     1.2270  postgres                 add_path
18154     1.2143  postgres                 AllocSetFree
18119     1.2120  postgres                 cost_mergejoin
18036     1.2064  postgres                 add_paths_to_joinrel
17791     1.1901  postgres                 nocachegetattr
17277     1.1557  postgres                 generate_join_implied_equalities
16956     1.1342  libc-2.8.so              vfprintf
16125     1.0786  postgres                 hash_search_with_hash_value
15733     1.0524  libc-2.8.so              __printf_fp
15387     1.0292  postgres                 MemoryContextAlloc
...
5759      0.3852  postgres                 add_similar_paths

Here we have a total of 3.6% spent in code that had used ~2.5% before
we started.  Not very promising.

Now, maybe if we could force the compiler to inline
compare_fuzzy_path_costs we could buy some of that back.  Another
possibility is to contort add_similar_path some more so that it avoids
double comparisons so long as cheapest_total and cheapest_startup are
the same path; I have a feeling that's not going to win much though.

So it's kind of looking like a dead end from here.  But in any case the
patch isn't acceptable as-is with that fundamental logic error in
add_similar_paths, so I'm bouncing it back for rework.
        regards, tom lane