pgsql: Avoid creation of useless EquivalenceClasses during planning.

Avoid creation of useless EquivalenceClasses during planning.

Zoltan Boszormenyi exhibited a test case in which planning time was
dominated by construction of EquivalenceClasses and PathKeys that had no
actual relevance to the query (and in fact got discarded immediately).
This happened because we generated PathKeys describing the sort ordering of
every index on every table in the query, and only after that checked to see
if the sort ordering was relevant. The EC/PK construction code is O(N^2)
in the number of ECs, which is all right for the intended number of such
objects, but it gets out of hand if there are ECs for lots of irrelevant
indexes.

To fix, twiddle the handling of mergeclauses a little bit to ensure that
every interesting EC is created before we begin path generation. (This
doesn't cost anything --- in fact I think it's a bit cheaper than before
--- since we always eventually created those ECs anyway.) Then, if an
index column can't be found in any pre-existing EC, we know that that sort
ordering is irrelevant for the query. Instead of creating a useless EC,
we can just not build a pathkey for the index column in the first place.
The index will still be considered if it's useful for non-order-related
reasons, but we will think of its output as unsorted.

Branch
------
master

Details
-------
http://git.postgresql.org/gitweb?p=postgresql.git;a=commitdiff;h=14231a41a94b2345cc679ff67dbee1bf7dac7029

Modified Files
--------------
src/backend/optimizer/README | 36 ++++++-
src/backend/optimizer/path/equivclass.c | 45 +++++++--
src/backend/optimizer/path/joinpath.c | 2 +-
src/backend/optimizer/path/pathkeys.c | 170 ++++++++++++++++++++++---------
src/backend/optimizer/plan/initsplan.c | 22 ++++-
src/include/optimizer/paths.h | 7 +-
6 files changed, 220 insertions(+), 62 deletions(-)