Small optimization with expanding dynamic hash table

Hi,

If I understand correctly, we only need to check the specific bit
to determine whether a hash element needs relocation:

diff --git a/src/backend/utils/hash/dynahash.c
b/src/backend/utils/hash/dynahash.c
index 1ad155d446e..32fbae71995 100644
--- a/src/backend/utils/hash/dynahash.c
+++ b/src/backend/utils/hash/dynahash.c
@@ -1626,7 +1626,7 @@ expand_table(HTAB *hashp)
currElement = nextElement)
{
nextElement = currElement->link;
-               if ((long) calc_bucket(hctl, currElement->hashvalue) ==
old_bucket)
+               if (!(currElement->hashvalue & (hctl->low_mask + 1)))
{
*oldlink = currElement;
oldlink = &currElement->link;

Will this still work if new_bucket is not equal to hctl->low_mask + 1?

The above situation seems possible because we increment new_bucket every
time expand_table is called,
but we only update low_mask when new_bucket exceeds high_mask.

This change has successfully passed the tests on Github CI. According to
[1]: LCOV - PostgreSQL 19devel - src/backend/utils/hash/dynahash.c <https://coverage.postgresql.org/src/backend/utils/hash/dynahash.c.gcov.html&gt;
but I'm not certain if the specific case mentioned above is included in the
tests.

[1]: LCOV - PostgreSQL 19devel - src/backend/utils/hash/dynahash.c <https://coverage.postgresql.org/src/backend/utils/hash/dynahash.c.gcov.html&gt;
<https://coverage.postgresql.org/src/backend/utils/hash/dynahash.c.gcov.html&gt;

Thank you,
Rahila Syed

&gt;&nbsp;Will this still work if new_bucket is not equal to hctl-&gt;low_mask + 1?Yes, for example:

low_mask: 0x011, high_mask: 0x111, old_bucket: 0x010, new_bucket: 0x110

The old_bucket's hash value like 0x***010 or 0x***110, the later is in the old_bucket is because we didn't have new_bucket before, so only hash value like 0x***110 needs&nbsp;relocation: hashvalue &amp; (low_mask + 1) != 0

--
Regards,
ChangAo Chen

Hi,

Yes, for example:

low_mask: 0x011, high_mask: 0x111, old_bucket: 0x010, new_bucket: 0x110

The old_bucket's hash value like 0x***010 or 0x***110, the later is in the
old_bucket is because we didn't have new_bucket before, so only hash value
like 0x***110 needs relocation: hashvalue & (low_mask + 1) != 0

Thanks for explaining, that clarifies things for me.
It may be worthwhile to check if this change has led to any performance
improvements.

Thank you,
Rahila syed

Hi,

Yes, for example:

low_mask: 0x011, high_mask: 0x111, old_bucket: 0x010, new_bucket: 0x110

The old_bucket's hash value like 0x***010 or 0x***110, the later is in
the old_bucket is because we didn't have new_bucket before, so only hash
value like 0x***110 needs relocation: hashvalue & (low_mask + 1) != 0

Thanks for explaining, that clarifies things for me.
It may be worthwhile to check if this change has led to any performance
improvements.

One thing to note is that in this scenario, there is no safeguard if the
hashvalue is 0x111 and new_bucket is 0x110.
This means max_bucket is 0x110, but with your change, even 0x111 would meet
the condition for relocation
to the new bucket, which would be incorrect.
Although it’s unlikely that 0x111 would be passed into this check, if it is
passed, there is currently no check to
prevent it from being relocated to the new bucket. In the current code,
however, we do have such a check in
place in calc_bucket, specifically: if (bucket > hctl->max_bucket)

Thank you,
Rahila Syed

&gt;&nbsp;One thing to note is that in this scenario, there is no safeguard if the&nbsp;hashvalue is 0x111 and new_bucket is 0x110.

But the hash table is already&nbsp;corrupted if the hashvalue 0x111 in old_bucket 0x010, all hashvalue in old_bucket should have: hashvalue &amp; low_mask == old_bucket's no.

--
Regards,
ChangAo Chen

Hi,

The v2 patch maybe more clear:

We can calc bucket just by hashvalue &amp; high_mask when expanding table because the if condition in calc_bucket() must be false.

--
Regards,
ChangAo Chen

Hi

The v2 patch maybe more clear:
We can calc bucket just by hashvalue & high_mask when expanding table

because the if condition in calc_bucket() must be false.
I think you may add a comment to this path so that code reviewers can
clearly see your optimization.

Thanks

On Thu, Jul 10, 2025 at 10:46 AM cca5507 <cca5507@qq.com> wrote:

Hi,

The v3 patch attached. (Add some comment in commit msg)

--
Regards,
ChangAo Chen