MIME-Version: 1.0
From: CharSyam <charsyam@gmail.com>
Date: Sat, 11 Apr 2026 01:09:33 +0900
Message-ID: 
 <CAMrLSE4JrhPB2XYMOMzbPSsgE+6kmDaKHKiF34NWdnbQts=Cpw@mail.gmail.com>
Subject: [PATCH] Use cached hash to skip unnecessary key comparisons in dshash
To: pgsql-hackers@lists.postgresql.org
Content-Type: multipart/mixed; boundary="00000000000089c145064f1d5c85"
Archived-At: 
 <https://www.postgresql.org/message-id/CAMrLSE4JrhPB2XYMOMzbPSsgE%2B6kmDaKHKiF34NWdnbQts%3DCpw%40mail.gmail.com>
Precedence: bulk

--00000000000089c145064f1d5c85
Content-Type: multipart/alternative; boundary="00000000000089c144064f1d5c83"

--00000000000089c144064f1d5c83
Content-Type: text/plain; charset="UTF-8"

Dear PostgreSQL Hackers,

  This email proposes a patch to optimize hash table lookups and
  deletions in dshash.  The patch file,
  0001-Use-cached-hash-to-skip-unnecessary-key-comparisons-.patch,
  is attached.

  Problem:

  Each dshash_table_item already stores the hash value in its 'hash'
  field, but find_in_bucket() and delete_key_from_bucket() never use
  it.  They unconditionally call the compare function for every item
  in the bucket chain, incurring unnecessary overhead from DSM address
  translation and key comparison on non-matching items.

  Solution:

  This patch adds a hash pre-check (item->hash == hash) before calling
  equal_keys() in both find_in_bucket() and delete_key_from_bucket().
  Items with non-matching hash values are skipped with a single integer
  comparison, avoiding the expensive key comparison entirely.

  All callers -- dshash_find(), dshash_find_or_insert_extended(), and
  dshash_delete_key() -- already have the hash value computed, so it
  is simply passed through as a new parameter.  Since both functions
  are static, there is no API change.

  Benchmark:

  I ran a benchmark using the test_dsm_registry extension with 10,000
  string-keyed entries (key = 'key_1' .. 'key_10000') on an Apple
  Silicon machine:

    Test                     | Before    | After     | Improvement
    -------------------------+-----------+-----------+------------
    INSERT 10000 entries     | 14.99 ms  |  9.46 ms  | ~37%
    LOOKUP 10000 hits        | 10.40 ms  |  5.52 ms  | ~47%
    LOOKUP 10000 misses      |  8.41 ms  |  4.95 ms  | ~41%
    LOOKUP 50000 hits (x5)   | 33.48 ms  | 26.44 ms  | ~21%

  The improvement is most significant when bucket chains are longer
  and key comparison is expensive (e.g., string keys).

  Testing & Compatibility:

  The patch compiles cleanly and passes all core regression tests
  (make check) on macOS (arm64).  The changes are limited to internal
  static functions in dshash.c and do not affect any public API, so
  full backward compatibility is maintained.

  I believe this patch is ready for review.  I look forward to any
  feedback and am happy to make revisions.

  Thank you,
  charsyam

--00000000000089c144064f1d5c83
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Dear PostgreSQL Hackers,<br><br>=C2=A0 This email proposes=
 a patch to optimize hash table lookups and<br>=C2=A0 deletions in dshash.=
=C2=A0 The patch file,<br>=C2=A0 0001-Use-cached-hash-to-skip-unnecessary-k=
ey-comparisons-.patch,<br>=C2=A0 is attached.<br><br>=C2=A0 Problem:<br><br=
>=C2=A0 Each dshash_table_item already stores the hash value in its &#39;ha=
sh&#39;<br>=C2=A0 field, but find_in_bucket() and delete_key_from_bucket() =
never use<br>=C2=A0 it.=C2=A0 They unconditionally call the compare functio=
n for every item<br>=C2=A0 in the bucket chain, incurring unnecessary overh=
ead from DSM address<br>=C2=A0 translation and key comparison on non-matchi=
ng items.<br><br>=C2=A0 Solution:<br><br>=C2=A0 This patch adds a hash pre-=
check (item-&gt;hash =3D=3D hash) before calling<br>=C2=A0 equal_keys() in =
both find_in_bucket() and delete_key_from_bucket().<br>=C2=A0 Items with no=
n-matching hash values are skipped with a single integer<br>=C2=A0 comparis=
on, avoiding the expensive key comparison entirely.<br><br>=C2=A0 All calle=
rs -- dshash_find(), dshash_find_or_insert_extended(), and<br>=C2=A0 dshash=
_delete_key() -- already have the hash value computed, so it<br>=C2=A0 is s=
imply passed through as a new parameter.=C2=A0 Since both functions<br>=C2=
=A0 are static, there is no API change.<br><br>=C2=A0 Benchmark:<br><br>=C2=
=A0 I ran a benchmark using the test_dsm_registry extension with 10,000<br>=
=C2=A0 string-keyed entries (key =3D &#39;key_1&#39; .. &#39;key_10000&#39;=
) on an Apple<br>=C2=A0 Silicon machine:<br><br>=C2=A0 =C2=A0 Test =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 | Before =C2=
=A0 =C2=A0| After =C2=A0 =C2=A0 | Improvement<br>=C2=A0 =C2=A0 ------------=
-------------+-----------+-----------+------------<br>=C2=A0 =C2=A0 INSERT =
10000 entries =C2=A0 =C2=A0 | 14.99 ms =C2=A0| =C2=A09.46 ms =C2=A0| ~37%<b=
r>=C2=A0 =C2=A0 LOOKUP 10000 hits =C2=A0 =C2=A0 =C2=A0 =C2=A0| 10.40 ms =C2=
=A0| =C2=A05.52 ms =C2=A0| ~47%<br>=C2=A0 =C2=A0 LOOKUP 10000 misses =C2=A0=
 =C2=A0 =C2=A0| =C2=A08.41 ms =C2=A0| =C2=A04.95 ms =C2=A0| ~41%<br>=C2=A0 =
=C2=A0 LOOKUP 50000 hits (x5) =C2=A0 | 33.48 ms =C2=A0| 26.44 ms =C2=A0| ~2=
1%<br><br>=C2=A0 The improvement is most significant when bucket chains are=
 longer<br>=C2=A0 and key comparison is expensive (e.g., string keys).<br><=
br>=C2=A0 Testing &amp; Compatibility:<br><br>=C2=A0 The patch compiles cle=
anly and passes all core regression tests<br>=C2=A0 (make check) on macOS (=
arm64).=C2=A0 The changes are limited to internal<br>=C2=A0 static function=
s in dshash.c and do not affect any public API, so<br>=C2=A0 full backward =
compatibility is maintained.<br><br>=C2=A0 I believe this patch is ready fo=
r review.=C2=A0 I look forward to any<br>=C2=A0 feedback and am happy to ma=
ke revisions.<br><br>=C2=A0 Thank you,<br>=C2=A0 charsyam</div>

--00000000000089c144064f1d5c83--

--00000000000089c145064f1d5c85
Content-Type: application/octet-stream;
	name="0001-Use-cached-hash-to-skip-unnecessary-key-comparisons-.patch"
Content-Disposition: attachment;
	filename="0001-Use-cached-hash-to-skip-unnecessary-key-comparisons-.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_mnt3pkop0>
X-Attachment-Id: f_mnt3pkop0

RnJvbSBjZjQ4YjBhNzc1Y2ZlYWRkMjkyODg2MzBiN2MxZmU3MDdlM2M3YWI1IE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBEYWVNeXVuZyBLYW5nIDxjaGFyc3lhbUBuYXZlci5jb20+CkRh
dGU6IFNhdCwgMTEgQXByIDIwMjYgMDA6NTI6NTYgKzA5MDAKU3ViamVjdDogW1BBVENIXSBVc2Ug
Y2FjaGVkIGhhc2ggdG8gc2tpcCB1bm5lY2Vzc2FyeSBrZXkgY29tcGFyaXNvbnMgaW4gZHNoYXNo
CgpFYWNoIGRzaGFzaF90YWJsZV9pdGVtIGFscmVhZHkgc3RvcmVzIHRoZSBoYXNoIHZhbHVlLCBi
dXQKZmluZF9pbl9idWNrZXQoKSBhbmQgZGVsZXRlX2tleV9mcm9tX2J1Y2tldCgpIHdlcmUgbm90
IHVzaW5nIGl0LAphbHdheXMgY2FsbGluZyB0aGUgZXhwZW5zaXZlIGNvbXBhcmUgZnVuY3Rpb24g
Zm9yIGV2ZXJ5IGl0ZW0gaW4gdGhlCmJ1Y2tldCBjaGFpbi4KCkFkZCBhIGhhc2ggcHJlLWNoZWNr
IGJlZm9yZSBjYWxsaW5nIGVxdWFsX2tleXMoKSBzbyB0aGF0IGl0ZW1zIHdpdGgKbm9uLW1hdGNo
aW5nIGhhc2ggdmFsdWVzIGFyZSBza2lwcGVkIHdpdGggYSBzaW1wbGUgaW50ZWdlciBjb21wYXJp
c29uLAphdm9pZGluZyB0aGUgb3ZlcmhlYWQgb2YgRFNNIGFkZHJlc3MgdHJhbnNsYXRpb24gYW5k
IGtleSBjb21wYXJpc29uLgoKQmVuY2htYXJrIHdpdGggMTAwMDAgc3RyaW5nLWtleWVkIGVudHJp
ZXMgdXNpbmcgdGVzdF9kc21fcmVnaXN0cnkKc2hvd3MgMjEtNDclIGltcHJvdmVtZW50IGFjcm9z
cyBpbnNlcnQsIGxvb2t1cC1oaXQsIGFuZCBsb29rdXAtbWlzcwpvcGVyYXRpb25zLgoKU2lnbmVk
LW9mZi1ieTogRGFlTXl1bmcgS2FuZyA8Y2hhcnN5YW1AbmF2ZXIuY29tPgotLS0KIHNyYy9iYWNr
ZW5kL2xpYi9kc2hhc2guYyB8IDIxICsrKysrKysrKysrKysrKy0tLS0tLQogMSBmaWxlIGNoYW5n
ZWQsIDE1IGluc2VydGlvbnMoKyksIDYgZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2Jh
Y2tlbmQvbGliL2RzaGFzaC5jIGIvc3JjL2JhY2tlbmQvbGliL2RzaGFzaC5jCmluZGV4IDE5OTk5
ODljMTRmLi41NWEzMjM1ZTA4YiAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvbGliL2RzaGFzaC5j
CisrKyBiL3NyYy9iYWNrZW5kL2xpYi9kc2hhc2guYwpAQCAtMTcyLDYgKzE3Miw3IEBAIHN0YXRp
YyBib29sIHJlc2l6ZShkc2hhc2hfdGFibGUgKmhhc2hfdGFibGUsIHNpemVfdCBuZXdfc2l6ZV9s
b2cyLAogc3RhdGljIGlubGluZSB2b2lkIGVuc3VyZV92YWxpZF9idWNrZXRfcG9pbnRlcnMoZHNo
YXNoX3RhYmxlICpoYXNoX3RhYmxlKTsKIHN0YXRpYyBpbmxpbmUgZHNoYXNoX3RhYmxlX2l0ZW0g
KmZpbmRfaW5fYnVja2V0KGRzaGFzaF90YWJsZSAqaGFzaF90YWJsZSwKIAkJCQkJCQkJCQkJCWNv
bnN0IHZvaWQgKmtleSwKKwkJCQkJCQkJCQkJCWRzaGFzaF9oYXNoIGhhc2gsCiAJCQkJCQkJCQkJ
CQlkc2FfcG9pbnRlciBpdGVtX3BvaW50ZXIpOwogc3RhdGljIHZvaWQgaW5zZXJ0X2l0ZW1faW50
b19idWNrZXQoZHNoYXNoX3RhYmxlICpoYXNoX3RhYmxlLAogCQkJCQkJCQkJZHNhX3BvaW50ZXIg
aXRlbV9wb2ludGVyLApAQCAtMTgzLDYgKzE4NCw3IEBAIHN0YXRpYyBkc2hhc2hfdGFibGVfaXRl
bSAqaW5zZXJ0X2ludG9fYnVja2V0KGRzaGFzaF90YWJsZSAqaGFzaF90YWJsZSwKIAkJCQkJCQkJ
CQkJIGludCBmbGFncyk7CiBzdGF0aWMgYm9vbCBkZWxldGVfa2V5X2Zyb21fYnVja2V0KGRzaGFz
aF90YWJsZSAqaGFzaF90YWJsZSwKIAkJCQkJCQkJICAgY29uc3Qgdm9pZCAqa2V5LAorCQkJCQkJ
CQkgICBkc2hhc2hfaGFzaCBoYXNoLAogCQkJCQkJCQkgICBkc2FfcG9pbnRlciAqYnVja2V0X2hl
YWQpOwogc3RhdGljIGJvb2wgZGVsZXRlX2l0ZW1fZnJvbV9idWNrZXQoZHNoYXNoX3RhYmxlICpo
YXNoX3RhYmxlLAogCQkJCQkJCQkJZHNoYXNoX3RhYmxlX2l0ZW0gKml0ZW0sCkBAIC00MDgsNyAr
NDEwLDcgQEAgZHNoYXNoX2ZpbmQoZHNoYXNoX3RhYmxlICpoYXNoX3RhYmxlLCBjb25zdCB2b2lk
ICprZXksIGJvb2wgZXhjbHVzaXZlKQogCWVuc3VyZV92YWxpZF9idWNrZXRfcG9pbnRlcnMoaGFz
aF90YWJsZSk7CiAKIAkvKiBTZWFyY2ggdGhlIGFjdGl2ZSBidWNrZXQuICovCi0JaXRlbSA9IGZp
bmRfaW5fYnVja2V0KGhhc2hfdGFibGUsIGtleSwgQlVDS0VUX0ZPUl9IQVNIKGhhc2hfdGFibGUs
IGhhc2gpKTsKKwlpdGVtID0gZmluZF9pbl9idWNrZXQoaGFzaF90YWJsZSwga2V5LCBoYXNoLCBC
VUNLRVRfRk9SX0hBU0goaGFzaF90YWJsZSwgaGFzaCkpOwogCiAJaWYgKCFpdGVtKQogCXsKQEAg
LTQ2Miw3ICs0NjQsNyBAQCByZXN0YXJ0OgogCWVuc3VyZV92YWxpZF9idWNrZXRfcG9pbnRlcnMo
aGFzaF90YWJsZSk7CiAKIAkvKiBTZWFyY2ggdGhlIGFjdGl2ZSBidWNrZXQuICovCi0JaXRlbSA9
IGZpbmRfaW5fYnVja2V0KGhhc2hfdGFibGUsIGtleSwgQlVDS0VUX0ZPUl9IQVNIKGhhc2hfdGFi
bGUsIGhhc2gpKTsKKwlpdGVtID0gZmluZF9pbl9idWNrZXQoaGFzaF90YWJsZSwga2V5LCBoYXNo
LCBCVUNLRVRfRk9SX0hBU0goaGFzaF90YWJsZSwgaGFzaCkpOwogCiAJaWYgKGl0ZW0pCiAJCSpm
b3VuZCA9IHRydWU7CkBAIC01MzYsNyArNTM4LDcgQEAgZHNoYXNoX2RlbGV0ZV9rZXkoZHNoYXNo
X3RhYmxlICpoYXNoX3RhYmxlLCBjb25zdCB2b2lkICprZXkpCiAJTFdMb2NrQWNxdWlyZShQQVJU
SVRJT05fTE9DSyhoYXNoX3RhYmxlLCBwYXJ0aXRpb24pLCBMV19FWENMVVNJVkUpOwogCWVuc3Vy
ZV92YWxpZF9idWNrZXRfcG9pbnRlcnMoaGFzaF90YWJsZSk7CiAKLQlpZiAoZGVsZXRlX2tleV9m
cm9tX2J1Y2tldChoYXNoX3RhYmxlLCBrZXksCisJaWYgKGRlbGV0ZV9rZXlfZnJvbV9idWNrZXQo
aGFzaF90YWJsZSwga2V5LCBoYXNoLAogCQkJCQkJCSAgICZCVUNLRVRfRk9SX0hBU0goaGFzaF90
YWJsZSwgaGFzaCkpKQogCXsKIAkJQXNzZXJ0KGhhc2hfdGFibGUtPmNvbnRyb2wtPnBhcnRpdGlv
bnNbcGFydGl0aW9uXS5jb3VudCA+IDApOwpAQCAtOTg1LDE3ICs5ODcsMjAgQEAgZW5zdXJlX3Zh
bGlkX2J1Y2tldF9wb2ludGVycyhkc2hhc2hfdGFibGUgKmhhc2hfdGFibGUpCiAKIC8qCiAgKiBT
Y2FuIGEgbG9ja2VkIGJ1Y2tldCBmb3IgYSBtYXRjaCwgdXNpbmcgdGhlIHByb3ZpZGVkIGNvbXBh
cmUgZnVuY3Rpb24uCisgKiBTa2lwcyBpdGVtcyB3aG9zZSBjYWNoZWQgaGFzaCB2YWx1ZXMgZG9u
J3QgbWF0Y2gsIGF2b2lkaW5nIGV4cGVuc2l2ZQorICoga2V5IGNvbXBhcmlzb25zLgogICovCiBz
dGF0aWMgaW5saW5lIGRzaGFzaF90YWJsZV9pdGVtICoKIGZpbmRfaW5fYnVja2V0KGRzaGFzaF90
YWJsZSAqaGFzaF90YWJsZSwgY29uc3Qgdm9pZCAqa2V5LAotCQkJICAgZHNhX3BvaW50ZXIgaXRl
bV9wb2ludGVyKQorCQkJICAgZHNoYXNoX2hhc2ggaGFzaCwgZHNhX3BvaW50ZXIgaXRlbV9wb2lu
dGVyKQogewogCXdoaWxlIChEc2FQb2ludGVySXNWYWxpZChpdGVtX3BvaW50ZXIpKQogCXsKIAkJ
ZHNoYXNoX3RhYmxlX2l0ZW0gKml0ZW07CiAKIAkJaXRlbSA9IGRzYV9nZXRfYWRkcmVzcyhoYXNo
X3RhYmxlLT5hcmVhLCBpdGVtX3BvaW50ZXIpOwotCQlpZiAoZXF1YWxfa2V5cyhoYXNoX3RhYmxl
LCBrZXksIEVOVFJZX0ZST01fSVRFTShpdGVtKSkpCisJCWlmIChpdGVtLT5oYXNoID09IGhhc2gg
JiYKKwkJCWVxdWFsX2tleXMoaGFzaF90YWJsZSwga2V5LCBFTlRSWV9GUk9NX0lURU0oaXRlbSkp
KQogCQkJcmV0dXJuIGl0ZW07CiAJCWl0ZW1fcG9pbnRlciA9IGl0ZW0tPm5leHQ7CiAJfQpAQCAt
MTA0NywxMCArMTA1MiwxMyBAQCBpbnNlcnRfaW50b19idWNrZXQoZHNoYXNoX3RhYmxlICpoYXNo
X3RhYmxlLAogCiAvKgogICogU2VhcmNoIGEgYnVja2V0IGZvciBhIG1hdGNoaW5nIGtleSBhbmQg
ZGVsZXRlIGl0LgorICogU2tpcHMgaXRlbXMgd2hvc2UgY2FjaGVkIGhhc2ggdmFsdWVzIGRvbid0
IG1hdGNoLCBhdm9pZGluZyBleHBlbnNpdmUKKyAqIGtleSBjb21wYXJpc29ucy4KICAqLwogc3Rh
dGljIGJvb2wKIGRlbGV0ZV9rZXlfZnJvbV9idWNrZXQoZHNoYXNoX3RhYmxlICpoYXNoX3RhYmxl
LAogCQkJCQkgICBjb25zdCB2b2lkICprZXksCisJCQkJCSAgIGRzaGFzaF9oYXNoIGhhc2gsCiAJ
CQkJCSAgIGRzYV9wb2ludGVyICpidWNrZXRfaGVhZCkKIHsKIAl3aGlsZSAoRHNhUG9pbnRlcklz
VmFsaWQoKmJ1Y2tldF9oZWFkKSkKQEAgLTEwNTksNyArMTA2Nyw4IEBAIGRlbGV0ZV9rZXlfZnJv
bV9idWNrZXQoZHNoYXNoX3RhYmxlICpoYXNoX3RhYmxlLAogCiAJCWl0ZW0gPSBkc2FfZ2V0X2Fk
ZHJlc3MoaGFzaF90YWJsZS0+YXJlYSwgKmJ1Y2tldF9oZWFkKTsKIAotCQlpZiAoZXF1YWxfa2V5
cyhoYXNoX3RhYmxlLCBrZXksIEVOVFJZX0ZST01fSVRFTShpdGVtKSkpCisJCWlmIChpdGVtLT5o
YXNoID09IGhhc2ggJiYKKwkJCWVxdWFsX2tleXMoaGFzaF90YWJsZSwga2V5LCBFTlRSWV9GUk9N
X0lURU0oaXRlbSkpKQogCQl7CiAJCQlkc2FfcG9pbnRlciBuZXh0OwogCi0tIAoyLjUwLjEgKEFw
cGxlIEdpdC0xNTUpCgo=
--00000000000089c145064f1d5c85--