Optimizer speed and GEQO (was: nested loops in joins)

I have been looking at optimizer runtime using Charles Hornberger's
example case, and what I find is that the number of tables involved in
the query is a very inadequate predictor of the optimizer's runtime.
Thus, it's not surprising that we are getting poor results from using
number of tables as the GEQO threshold measure.

I started with Charles' test case as presented, then simplified it by
removing indexes from the database.  This didn't change the final
plan, which was a straight nested loop over sequential scans anyway
(because the tables were so small).  But it drastically reduces the
number of cases that the optimizer looks at.

Original test case: query involves seven tables with a total of twelve
indexes (six on the primary table and one on each other table).

7-index test case: I removed all but one of the indexes on the primary
table, leaving one index per table.

No-index test case: I removed all indexes.

It took a certain amount of patience to run these cases with profiling
turned on :-(, but here are the results:
        7T+12I        7T+7I        7T

Runtime, sec        1800        457        59
equal() calls        585 mil        157 mil        21.7 mil
better_path() calls    72546        37418        14025
bp->path_is_cheaper    668        668        668
create_hashjoin_path    198        198        198
create_mergejoin_path    2358        723        198
create_nestloop_path    38227        20297        7765

Next, I removed the last table from Charles' query, producing these
cases:
        6T+11I        6T+6I        6T

Runtime, sec        34        12        2.3
equal() calls        14.3 mil    4.7 mil        0.65 mil
better_path() calls    10721        6172        2443
bp->path_is_cheaper    225        225        225
create_hashjoin_path    85        85        85
create_mergejoin_path    500        236        85
create_nestloop_path    5684        3344        1354

The 5T+10I case is down to a couple of seconds of runtime, so I
didn't bother to do profiles for 5 tables.

A fairly decent approximation is that the runtime varies as the
square of the number of create_nestloop_path calls.  That number
in turn seems to vary as the factorial of the number of tables,
with a weaker but still strong term involving the number of indexes.
I understand the square and the factorial terms, but the form of
the dependency on the index count isn't real clear.

It might be worthwhile to try a GEQO threshold based on the number of
tables plus half the number of indexes on those tables.  I have no idea
where to find the number of indexes, so I'll just offer the idea for
someone else to try.


The main thing that jumps out from the profiles is that on these complex
searches, the optimizer spends practically *all* of its time down inside
better_path, scanning the list of already known access paths to see if a
proposed new path is a duplicate of one already known.  (Most of the time
it is not, as shown by the small number of times path_is_cheaper gets
called from better_path.)  This scanning is O(N^2) in the number of paths
considered, whereas it seems that all the other work is no worse than O(N)
in the number of paths.  The bottom of the duplicate check is equal(),
which as you can see is getting called a horrendous number of times.

It would be worth our while to try to eliminate this mostly-unsuccessful
comparison operation.

I wonder whether it would work to simply always add the new path to the
list, and rely on the later "prune" step to get rid of duplicates?
The prune code is evidently far more efficient at getting rid of useless
entries than better_path is, because it's nowhere near the top of the
profile even though it's processing nearly as many paths.

Anybody here know much about how the optimizer works?  I'm hesitant to
hack on it myself.
        regards, tom lane