MIME-Version: 1.0
From: lakshmi <lakshmigcdac@gmail.com>
Date: Tue, 28 Apr 2026 12:21:14 +0530
Message-ID: 
 <CAEvyyTj7oUqzh4sKpSm3urV1=kKO6TtdRucBFSD0Z6w_g1Ot+w@mail.gmail.com>
Subject: [PATCH] Improve HASH overflow page reuse for better locality
To: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Cc: Kirill Reshke <reshkekirill@gmail.com>,
 Robert Haas <robertmhaas@gmail.com>
Content-Type: multipart/mixed; boundary="0000000000005bfb2b06507f99b4"
Archived-At: 
 <https://www.postgresql.org/message-id/CAEvyyTj7oUqzh4sKpSm3urV1%3DkKO6TtdRucBFSD0Z6w_g1Ot%2Bw%40mail.gmail.com>
Precedence: bulk

--0000000000005bfb2b06507f99b4
Content-Type: multipart/alternative; boundary="0000000000005bfb2a06507f99b2"

--0000000000005bfb2a06507f99b2
Content-Type: text/plain; charset="UTF-8"

Hi all,

Based on the suggestion in the previous discussion [1], I am starting a
separate thread to propose this as an enhancement.

While testing the HASH index build improvements, I worked on a follow-up
change to improve overflow page reuse. Currently, any free overflow page
may be reused, which can scatter overflow chains and affect cache locality.
This patch introduces a simple improvement where recently freed overflow
pages are preferred during allocation.

The change is backend-local and affects only page allocation. It does not
introduce any WAL changes or modify the on-disk format.

I have verified correctness using index build, drop, and VACUUM cycles.
Initial checks also confirm that WAL behavior remains unchanged.

I am currently working on collecting detailed performance results,
including both favorable and unfavorable scenarios, and will share them
shortly in this thread.

The patch is attached for review. Feedback and suggestions are welcome.

Regards,
Lakshmi G

reference

[1]
https://www.postgresql.org/message-id/flat/CALdSSPgu6fnoOYzgiFF4_Etr96zEHvSwvYJDemc3o%2B%2BEZbUQMA%40mail.gmail.com

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

<div dir=3D"ltr"><p class=3D"gmail-isSelectedEnd">Hi all,</p><p class=3D"gm=
ail-isSelectedEnd">Based on the suggestion in the previous discussion [1], =
I am starting a separate thread to propose this as an enhancement.</p><p cl=
ass=3D"gmail-isSelectedEnd">While testing the HASH index build improvements=
, I worked on a follow-up change to improve overflow page reuse. Currently,=
 any free overflow page may be reused, which can scatter overflow chains an=
d affect cache locality. This patch introduces a simple improvement where r=
ecently freed overflow pages are preferred during allocation.</p><p class=
=3D"gmail-isSelectedEnd">The change is backend-local and affects only page =
allocation. It does not introduce any WAL changes or modify the on-disk for=
mat.</p><p class=3D"gmail-isSelectedEnd">I have verified correctness using =
index build, drop, and VACUUM cycles. Initial checks also confirm that WAL =
behavior remains unchanged.</p><p class=3D"gmail-isSelectedEnd">I am curren=
tly working on collecting detailed performance results, including both favo=
rable and unfavorable scenarios, and will share them shortly in this thread=
.</p><p class=3D"gmail-isSelectedEnd">The patch is attached for review. Fee=
dback and suggestions are welcome.</p><p>Regards,<br>Lakshmi G</p><p>refere=
nce</p><p>[1]=C2=A0<a href=3D"https://www.postgresql.org/message-id/flat/CA=
LdSSPgu6fnoOYzgiFF4_Etr96zEHvSwvYJDemc3o%2B%2BEZbUQMA%40mail.gmail.com">htt=
ps://www.postgresql.org/message-id/flat/CALdSSPgu6fnoOYzgiFF4_Etr96zEHvSwvY=
JDemc3o%2B%2BEZbUQMA%40mail.gmail.com</a></p></div>

--0000000000005bfb2a06507f99b2--

--0000000000005bfb2b06507f99b4
Content-Type: text/x-patch; charset="US-ASCII";
	name="0001-hash-reuse-recently-freed-overflow-pages.patch"
Content-Disposition: attachment;
	filename="0001-hash-reuse-recently-freed-overflow-pages.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_moi9jeuc0>
X-Attachment-Id: f_moi9jeuc0

RnJvbSAzNGQ0ZDk5YmFhNTM3N2E0ZGFiYjhjZjljNGJjZDBlOWJiMmM2Mzc2IE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBMYWtzaG1pIDxiaGFyYXRkYnBnQGdtYWlsLmNvbT4KRGF0ZTog
TW9uLCA1IEphbiAyMDI2IDEwOjM4OjIzICswNTMwClN1YmplY3Q6IFtQQVRDSF0gaGFzaDogcmV1
c2UgcmVjZW50bHkgZnJlZWQgb3ZlcmZsb3cgcGFnZXMKCi0tLQogc3JjL2JhY2tlbmQvYWNjZXNz
L2hhc2gvaGFzaG92ZmwuYyB8IDc3ICsrKysrKysrKysrKysrKysrKysrKysrKysrKysrKwogMSBm
aWxlIGNoYW5nZWQsIDc3IGluc2VydGlvbnMoKykKCmRpZmYgLS1naXQgYS9zcmMvYmFja2VuZC9h
Y2Nlc3MvaGFzaC9oYXNob3ZmbC5jIGIvc3JjL2JhY2tlbmQvYWNjZXNzL2hhc2gvaGFzaG92Zmwu
YwppbmRleCAzMjc3ZGExOTg0MC4uYzY2ZjhhZGMwNTYgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5k
L2FjY2Vzcy9oYXNoL2hhc2hvdmZsLmMKKysrIGIvc3JjL2JhY2tlbmQvYWNjZXNzL2hhc2gvaGFz
aG92ZmwuYwpAQCAtMjIsNiArMjIsNjMgQEAKICNpbmNsdWRlICJhY2Nlc3MveGxvZ2luc2VydC5o
IgogI2luY2x1ZGUgIm1pc2NhZG1pbi5oIgogI2luY2x1ZGUgInV0aWxzL3JlbC5oIgorLyotLS0t
LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t
LS0tLS0tLS0tLS0tCisgKiBCYWNrZW5kLWxvY2FsIHJldXNlIGNhY2hlIGZvciByZWNlbnRseSBm
cmVlZCBvdmVyZmxvdyBwYWdlcy4KKyAqIEJlc3QtZWZmb3J0IGhpbnQgb25seTogbm8gY29ycmVj
dG5lc3Mgb3IgV0FMIGRlcGVuZGVuY3kuCisgKi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t
LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KKyAqLworI2RlZmlu
ZSBIQVNIX09WRkxfUkVVU0VfQ0FDSEVfU0laRSAzMgorCit0eXBlZGVmIHN0cnVjdCBIYXNoT3Zm
bFJldXNlQ2FjaGUKK3sKKwlCbG9ja051bWJlciBibG9ja3NbSEFTSF9PVkZMX1JFVVNFX0NBQ0hF
X1NJWkVdOworCWludAkJCWhlYWQ7CisJaW50CQkJY291bnQ7Cit9CQkJSGFzaE92ZmxSZXVzZUNh
Y2hlOworCitzdGF0aWMgSGFzaE92ZmxSZXVzZUNhY2hlIG92ZmxfcmV1c2VfY2FjaGU7CisKKy8q
IFJlY29yZCBhIGZyZWVkIG92ZXJmbG93IHBhZ2UgKi8KK3N0YXRpYyB2b2lkCitoYXNoX3JlY29y
ZF9mcmVlZF9vdmZscGFnZShCbG9ja051bWJlciBibGtubykKK3sKKwlvdmZsX3JldXNlX2NhY2hl
LmJsb2Nrc1tvdmZsX3JldXNlX2NhY2hlLmhlYWRdID0gYmxrbm87CisJb3ZmbF9yZXVzZV9jYWNo
ZS5oZWFkID0KKwkJKG92ZmxfcmV1c2VfY2FjaGUuaGVhZCArIDEpICUgSEFTSF9PVkZMX1JFVVNF
X0NBQ0hFX1NJWkU7CisKKwlpZiAob3ZmbF9yZXVzZV9jYWNoZS5jb3VudCA8IEhBU0hfT1ZGTF9S
RVVTRV9DQUNIRV9TSVpFKQorCQlvdmZsX3JldXNlX2NhY2hlLmNvdW50Kys7Cit9CisKKy8qIFRy
eSB0byByZXVzZSBhIHJlY2VudGx5IGZyZWVkIG92ZXJmbG93IHBhZ2UgKi8KK3N0YXRpYyBib29s
CitoYXNoX3RyeV9yZXVzZV9jYWNoZWRfb3ZmbHBhZ2UoUmVsYXRpb24gcmVsLCBCdWZmZXIgbWV0
YWJ1ZiwKKwkJCQkJCQkgICBCbG9ja051bWJlciAqcmV1c2VfYmxrbm8pCit7CisJSGFzaE1ldGFQ
YWdlIG1ldGFwID0gSGFzaFBhZ2VHZXRNZXRhKEJ1ZmZlckdldFBhZ2UobWV0YWJ1ZikpOworCWlu
dAkJCWk7CisKKwlmb3IgKGkgPSAwOyBpIDwgb3ZmbF9yZXVzZV9jYWNoZS5jb3VudDsgaSsrKQor
CXsKKwkJaW50CQkJaWR4ID0KKwkJCShvdmZsX3JldXNlX2NhY2hlLmhlYWQgLSAxIC0gaSArIEhB
U0hfT1ZGTF9SRVVTRV9DQUNIRV9TSVpFKQorCQkJJSBIQVNIX09WRkxfUkVVU0VfQ0FDSEVfU0la
RTsKKworCQlCbG9ja051bWJlciBibGtubyA9IG92ZmxfcmV1c2VfY2FjaGUuYmxvY2tzW2lkeF07
CisJCXVpbnQzMgkJYml0bm8gPSBfaGFzaF9vdmZsYmxrbm9fdG9fYml0bm8obWV0YXAsIGJsa25v
KTsKKworCQkvKiBCaXRtYXAgaXMgYXV0aG9yaXRhdGl2ZSAqLworCQlpZiAoX2hhc2hfaXNiaXRz
ZXQobWV0YXAtPmhhc2htX21hcHAsIGJpdG5vKSkKKwkJeworCQkJX2hhc2hfY2xyYml0KG1ldGFw
LT5oYXNobV9tYXBwLCBiaXRubyk7CisJCQkqcmV1c2VfYmxrbm8gPSBibGtubzsKKwkJCXJldHVy
biB0cnVlOworCQl9CisJfQorCisJcmV0dXJuIGZhbHNlOworfQorCiAKIAogc3RhdGljIHVpbnQz
MiBfaGFzaF9maXJzdGZyZWViaXQodWludDMyIG1hcCk7CkBAIC0xMzIsNiArMTg5LDEwIEBAIF9o
YXNoX2FkZG92ZmxwYWdlKFJlbGF0aW9uIHJlbCwgQnVmZmVyIG1ldGFidWYsIEJ1ZmZlciBidWYs
IGJvb2wgcmV0YWluX3BpbiwgYm9vCiAJdWludDMyCQlpLAogCQkJCWo7CiAJYm9vbAkJcGFnZV9m
b3VuZCA9IGZhbHNlOworCUJsb2NrTnVtYmVyIHJldXNlX2Jsa25vOworCisKKwogCiAJLyoKIAkg
KiBXcml0ZS1sb2NrIHRoZSB0YWlsIHBhZ2UuICBIZXJlLCB3ZSBuZWVkIHRvIG1haW50YWluIGxv
Y2tpbmcgb3JkZXIgc3VjaApAQCAtMTg2LDYgKzI0NywxNiBAQCBfaGFzaF9hZGRvdmZscGFnZShS
ZWxhdGlvbiByZWwsIEJ1ZmZlciBtZXRhYnVmLCBCdWZmZXIgYnVmLCBib29sIHJldGFpbl9waW4s
IGJvbwogCV9oYXNoX2NoZWNrcGFnZShyZWwsIG1ldGFidWYsIExIX01FVEFfUEFHRSk7CiAJbWV0
YXAgPSBIYXNoUGFnZUdldE1ldGEoQnVmZmVyR2V0UGFnZShtZXRhYnVmKSk7CiAKKwkvKgorCSAq
IE5FVzogVHJ5IHJldXNlIGNhY2hlIGJlZm9yZSBzY2FubmluZyBiaXRtYXAKKwkgKi8KKwlpZiAo
aGFzaF90cnlfcmV1c2VfY2FjaGVkX292ZmxwYWdlKHJlbCwgbWV0YWJ1ZiwgJnJldXNlX2Jsa25v
KSkKKwl7CisJCW92ZmxidWYgPSBfaGFzaF9nZXRpbml0YnVmKHJlbCwgcmV1c2VfYmxrbm8pOwor
CQlwYWdlX2ZvdW5kID0gdHJ1ZTsKKwkJZ290byBmb3VuZDsKKwl9CisKIAkvKiBzdGFydCBzZWFy
Y2ggYXQgaGFzaG1fZmlyc3RmcmVlICovCiAJb3JpZ19maXJzdGZyZWUgPSBtZXRhcC0+aGFzaG1f
Zmlyc3RmcmVlOwogCWZpcnN0X3BhZ2UgPSBvcmlnX2ZpcnN0ZnJlZSA+PiBCTVBHX1NISUZUKG1l
dGFwKTsKQEAgLTYzMyw2ICs3MDQsMTIgQEAgX2hhc2hfZnJlZW92ZmxwYWdlKFJlbGF0aW9uIHJl
bCwgQnVmZmVyIGJ1Y2tldGJ1ZiwgQnVmZmVyIG92ZmxidWYsCiAJQ0xSQklUKGZyZWVwLCBiaXRt
YXBiaXQpOwogCU1hcmtCdWZmZXJEaXJ0eShtYXBidWYpOwogCisJLyoKKwkgKiBORVc6IFJlbWVt
YmVyIHRoaXMgb3ZlcmZsb3cgcGFnZSBmb3IgcmV1c2UKKwkgKi8KKworCWhhc2hfcmVjb3JkX2Zy
ZWVkX292ZmxwYWdlKG92ZmxibGtubyk7CisKIAkvKiBpZiB0aGlzIGlzIG5vdyB0aGUgZmlyc3Qg
ZnJlZSBwYWdlLCB1cGRhdGUgaGFzaG1fZmlyc3RmcmVlICovCiAJaWYgKG92ZmxiaXRubyA8IG1l
dGFwLT5oYXNobV9maXJzdGZyZWUpCiAJewotLSAKMi4zOS41Cgo=
--0000000000005bfb2b06507f99b4--