Re: Reducing memory consumed by RestrictInfo list translations in partitionwise join planning

On Mon, Mar 31, 2025 at 7:00 PM Ashutosh Bapat
<ashutosh(dot)bapat(dot)oss(at)gmail(dot)com> wrote:
> On Mon, Mar 31, 2025 at 8:27 AM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> >
> > On Sat, 29 Mar 2025 at 05:46, Ashutosh Bapat
> > <ashutosh(dot)bapat(dot)oss(at)gmail(dot)com> wrote:
> > > PFA patches. 0001 and 0002 are the same as the previous set. 0003
> > > changes the initial hash table size to the length of ec_derives.
> >
> > I'm just not following the logic in making it the length of the
> > ec_derives List. If you have 32 buckets and try to insert 32 elements,
> > you're guaranteed to need a resize after inserting 28 elements. See
> > the grow_threshold logic SH_UPDATE_PARAMETERS(). The point of making
> > it 64 was to ensure the table is never unnecessarily sparse and to
> > also ensure we make it at least big enough for the minimum number of
> > ec_derives that we're about to insert.
>
> If I am reading SH_CREATE correctly, it will initially set the size to
> 32/.9 = 36 and in SH_UPDATE_PARAMETERS will set grow_threshold to 36 *
> .9 = 32. So it will leave some room even after inserting the initial
> elements. But looking at SH_INSERT_HASH_INTERNAL(), it will soon
> expand the table even if there's space. We certainly need a size much
> more than 32. 32 is an arbitrary/empirical threshold to create a hash
> table. Using that threshold as initial hash table size means the table
> size would be arbitrary too. Using twice the length of
> ec_derives_list seems more reasonable since the length will decide the
> initial number of entries.

I think David’s suggestion to use 64 as the fixed initial size is
simpler and more predictable. Since list_length * 2 will always be >=
64 anyway, unless we expect clause counts to grow significantly right
after the threshold, the fixed size avoids the need to reason about
sizing heuristics and keeps the logic clearer.

It also lines up well with David’s point -- 64 strikes a good balance
for both memory usage and CPU efficiency. Unless there’s a strong
reason to favor dynamic sizing, I’d prefer to stick with the fixed 64.

> > I think you'd be better off coming up with some logic like putting the
> > lowest pointer value'd EM first in the key and ensure that all lookups
> > do that too by wrapping the lookups in some helper function. That'll
> > half the number of hash table entries at the cost of some very cheap
> > comparisons.
>
> That's a good suggestion. I searched for C standard documentation
> which specifies that the pointer comparison, especially inequality, is
> stable and safe to use. But I didn't find any. While according to the
> C standard, the result
> of comparison between pointers within the same array or a struct is
> specified, that between pointers from two different objects is
> unspecified. The existing code relies on the EM pointers being stable
> and also relies on equality between
> them to be stable. It has withstood the test of time and a variety of
> compilers. Hence I think it should be safe to rely on pointer
> comparisons being stable. But since I didn't find any documentation
> which confirms it, I have left those changes as a separate patch. Some
> internet sources discussing pointer comparison can be found at [1],
> [2] (which mentions the C standard but doesn't provide a link).
>
> PFA the next patchset
>
> 0001, 0002 are same as in the previous set
> 0003 changes the initial hash table size to
> length(ec->ec_derives_list) * 4 to accomodate for commuted entries.
> 0004 uses canonical keys per your suggestion and also reduces the
> initial hash table size to length(ec->ec_derives_list) * 2.

Thanks for the new patches.

As David suggested off-list, it seems better to have a static inline
function for the key canonicalization logic than to duplicate it in
the insert and lookup paths, as done in your 0004.

Also, using macros for the ec_derives_hash threshold and initial size
seems cleaner than hardcoding the values.

I’ve combined your 0003 and 0004 into the attached 0003, which:

* Adds the canonicalization logic via fill_ec_derives_key().

* Replaces literal values for threshold and initial size with macros,
defined near the key and entry types.

* Updates code comments to reflect the new design.

I wasn’t sure why you removed this comment:

- * We do not attempt a second lookup with EMs swapped when using the hash
- * table; such clauses are inserted under both orderings at the time of
- * insertion.

We still avoid the second lookup, but the reason has changed -- we now
canonicalize keys during both insertion and lookup, which makes the
second probe unnecessary. So I rewrote it as:

+ * We do not attempt a second lookup with EMs swapped, because the key is
+ * canonicalized during both insertion and lookup.

0003’s commit message includes a blurb I plan to paste into the main
patch’s message (with minor tweaks) when we squash the patches.

--
Thanks, Amit Langote