Re: [PoC] Reducing planning time when tables have many partitions

On Mon, 4 Jul 2022 at 09:28, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> For the bms_equal class of lookups, I wonder if we could get anywhere
> by adding an additional List field to every RelOptInfo that chains
> all EquivalenceMembers that match that RelOptInfo's relids.
> The trick here would be to figure out when to build those lists.
> The simple answer would be to do it lazily on-demand, but that
> would mean a separate scan of all the EquivalenceMembers for each
> RelOptInfo; I wonder if there's a way to do better?

How about, instead of EquivalenceClass having a List field named
ec_members, it has a Bitmapset field named ec_member_indexes and we
just keep a List of all EquivalenceMembers in PlannerInfo and mark
which ones are in the class by setting the bit in the class's
ec_member_indexes field.

That would be teamed up with a new eclass_member_indexes field in
RelOptInfo to store the index into PlannerInfo's List of
EquivalenceMembers that belong to the given RelOptInfo.

For searching:
If you want to get all EquivalenceMembers in an EquivalenceClass, you
bms_next_member loop over the EC's ec_member_indexes field.
If you want to get all EquivalenceMembers for a given RelOptInfo, you
bms_next_member loop over the RelOptInfo's eclass_member_indexes
field.
If you want to get all EquivalenceMembers for a given EquivalenceClass
and RelOptInfo you need to do some bms_intersect() calls for the rel's
eclass_member_indexes and EC's ec_member_indexes.

I'm unsure if we'd want to bms_union the RelOptInfo's
ec_member_indexes field for join rels. Looking at
get_eclass_indexes_for_relids() we didn't do it that way for
eclass_indexes. Maybe that's because we're receiving RelIds in a few
places without a RelOptInfo.

Certainly, the CPU cache locality is not going to be as good as if we
had a List with all elements together, but for simple queries, there's
not going to be many EquivalenceClasses anyway, and for complex
queries, this should be a win.

David