pgsql: Speed up finding EquivalenceClasses for a given set of rels

Speed up finding EquivalenceClasses for a given set of rels

Previously in order to determine which ECs a relation had members in, we
had to loop over all ECs stored in PlannerInfo's eq_classes and check if
ec_relids mentioned the relation. For the most part, this was fine, as
generally, unless queries were fairly complex, the overhead of performing
the lookup would have not been that significant. However, when queries
contained large numbers of joins and ECs, the overhead to find the set of
classes matching a given set of relations could become a significant
portion of the overall planning effort.

Here we allow a much more efficient method to access the ECs which match a
given relation or set of relations. A new Bitmapset field in RelOptInfo
now exists to store the indexes into PlannerInfo's eq_classes list which
each relation is mentioned in. This allows very fast lookups to find all
ECs belonging to a single relation. When we need to lookup ECs belonging
to a given pair of relations, we can simply bitwise-AND the Bitmapsets from
each relation and use the result to perform the lookup.

We also take the opportunity to write a new implementation of
generate_join_implied_equalities which makes use of the new indexes.
generate_join_implied_equalities_for_ecs must remain as is as it can be
given a custom list of ECs, which we can't easily determine the indexes of.

This was originally intended to fix the performance penalty of looking up
foreign keys matching a join condition which was introduced by 100340e2d.
However, we're speeding up much more than just that here.

Author: David Rowley, Tom Lane
Reviewed-by: Tom Lane, Tomas Vondra
Discussion: https://postgr.es/m/6970.1545327857@sss.pgh.pa.us

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/3373c7155350cf6fcd51dd090f29e1332901e329

Modified Files
--------------
src/backend/nodes/outfuncs.c | 2 +
src/backend/optimizer/path/equivclass.c | 352 +++++++++++++++++++++++-------
src/backend/optimizer/path/pathkeys.c | 8 +-
src/backend/optimizer/plan/planmain.c | 6 +
src/backend/optimizer/plan/planner.c | 1 +
src/backend/optimizer/prep/prepjointree.c | 1 +
src/backend/optimizer/prep/prepunion.c | 9 +
src/backend/optimizer/util/relnode.c | 3 +
src/include/nodes/pathnodes.h | 6 +
9 files changed, 306 insertions(+), 82 deletions(-)