Performance issue in foreign-key-aware join estimation

In connection with David Rowley's proposal to change bitmapset.c to use
64-bit words, I dug out an old test case I had for a complex-to-plan query
(attached). Andres Freund posted this to the lists perhaps ten years ago,
though I can't locate the original posting right now.

I was distressed to discover via perf that 69% of the runtime of this
test now goes into match_eclasses_to_foreign_key_col(). That seems
clearly unacceptable. There aren't an unreasonable number of foreign key
constraints in the underlying schema --- mostly one per table, and there's
only one table with as many as 3. However, poking around in the planner
data structures, it turns out there are:

888 base relations

1005 EquivalenceClasses

167815 fkey_list entries initially

690 fkey_list entries after match_foreign_keys_to_quals trims them

So the reason match_eclasses_to_foreign_key_col is so dominant in the
runtime is it's invoked 167815 times and has to scan a thousand
EquivalenceClasses (unsuccessfully) on most of those calls.

How did the fkey_list get that big? I think the issue is that the
query touches the same tables many many times (888 baserels, but
there are only 20 distinct tables in the schema) and we get an
O(N^2) growth in the apparent number of FKs.

Clearly, we ought to rethink that data structure. I'm not sure
offhand how to make it better, but this is pretty awful.

Perhaps there'd also be some use in having better indexing for
the EquivalenceClass list, but again I'm not sure what that'd
look like.

regards, tom lane