Support specialized B-tree page searches
Hackorum builds and tests every patch posted to the lists, not only commitfest submissions. This is Hackorum's own CI rather than the PostgreSQL project's, and it is still under testing - please report anything that looks wrong.
You can run a PostgreSQL built from this patch straight from Docker, with no checkout and no build:
docker run --rm -p 5432:5432 ghcr.io/hackorum-dev/postgres-patch:t253318psql -h localhost -U postgresBuilt from patchset v1 (message #1), August 23, 2026 at 08:33 AM.
Every patchset is also pushed to a branch of our PostgreSQL fork, so you can check out the same tree CI built. Without a PostgreSQL checkout:
git clone --branch t253318_1 https://github.com/hackorum-dev/postgres.gitIn a checkout you already have, add the fork once:
git remote add hackorum https://github.com/hackorum-dev/postgres.gitthen, for this patchset and every later one:
git fetch hackorum t253318_1 && git checkout t253318_1Patchset v1 (message #1) is on t253318_1
Hi hackers,
B-tree page searches repeatedly call the comparison function through
fmgr and deform index tuples. For simple fixed-width types, this can
cost much more than the comparison itself.
I first presented this idea at PGConf.dev 2024, but only recently found
the time to hack it properly.
The attached patch set adds an optional opclass support procedure for
searching a page interval. The first patch implements it for
single-column int4 indexes, including searches and insertions. The
second patch uses the first and last int4 keys to try an interpolation
probe. It accept that probe only after checking the adjacent tuple
proves the exact boundary, otherwise it continues with binary search.
The fast path is limited to same-type, single-key operations that it can
handle. Everything else falls back to the existing code.
For one million successful parameterized index-only lookups over five
million int4 keys, six interleaved runs gave these median times on an
AMD EPYC Genoa machine. The table contained the integers 1 through
5,000,000 with a non-unique B-tree index. The query visited one million
distinct existing keys in a deterministic pseudorandom order:
SELECT count(*)
FROM generate_series(1, 1000000) g
WHERE (SELECT i
FROM layout_t
WHERE i = ((g::bigint * 15485863) % 5000000 + 1)::int
LIMIT 1) IS NOT NULL;
This dense key distribution is deliberately a favorable case for
interpolation search. It's realistic, though.
The median times were:
master 2.245 s
patched 1.470 s
That is 35% less elapsed time, or 53% more throughput. Standard
pgbench -S did not show a measurable difference.
WDYT?
Best regards, Andrey Borodin.
Attachments:
t253318_1v1-0002-Use-interpolation-for-specialized-int4-page-searc.patchapplication/octet-stream; name=v1-0002-Use-interpolation-for-specialized-int4-page-searc.patch; x-unix-mode=0644Download+182-12
v1-0001-Add-B-tree-support-for-specialized-page-searches.patchapplication/octet-stream; name=v1-0001-Add-B-tree-support-for-specialized-page-searches.patch; x-unix-mode=0644Download+524-9
On 5 Aug 2026, at 11:49, Andrey Borodin <x4mmm@yandex-team.ru> wrote:
That is 35% less elapsed time, or 53% more throughput. Standard
pgbench -S did not show a measurable difference.
Нi hackers,
Here's the benchmarking followup.
I ran a broader set of benchmarks to look for both favorable and
unfavorable cases. I compared master , the first patch with specialized
int4 binary search, and the full patch set.
These are median throughput changes from seven interleaved runs of one
million server-side index lookups:
specialized/master full/specialized full/master
dense hits +8% +34% +46%
dense misses +12% +32% +47%
uniform random hits +8% +25% +35%
clustered hits +9% +5% +14%
deduplicated duplicates +3% +3% +6%
misses in large gaps +7% +1% +7%
misses outside the range +6..11% -2% +4..9%
Thus, specialization itself seems robust. Interpolation provides a
large additional gain for approximately linear page contents, degrades
gracefully for clustered keys and duplicates, and costs about 2% over
specialized binary search for probes outside the indexed range.
Regular pgbench point lookups gained about 2.5-3%, where executor and
client overhead dilute the page-search improvement. One case, duplicate
lookups with 16 clients, regressed by about 1.3%, I'm investigating this.
The insertion test also improved by about 6% with the first patch and
10% with the full patch set. Interpolation is not used for insertion
bounds, however, and the second patch also refactors fixed-width tuple
extraction. I will move that refactoring into the first patch and
repeat the focused insertion and adverse-case measurements. The gain
there is not from the interpolation.
I also tried the same approach for text and UUID. Apart from about 1.3%
for densely packed UUID values, I found no convincing improvement, so I
do not plan to include those opclasses in the patch set.
Do these results make the opclass support procedure and the separate
interpolation callback look like a reasonable direction? In
particular, is the distribution-dependent tradeoff acceptable when the
opclass retains the ability to fall back to binary search?
Best regards, Andrey Borodin.