agora inbox for pgsql-hackers@postgresql.org
help / color / mirror / Atom feedRandomize B-Tree page split location to avoid oscillating patterns
13+ messages / 4 participants
[nested] [flat]
* Randomize B-Tree page split location to avoid oscillating patterns
@ 2026-04-27 16:24 Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
0 siblings, 1 reply; 13+ messages in thread
From: Dmitry Dolgov @ 2026-04-27 16:24 UTC (permalink / raw)
To: pgsql-hackers
TL;DR There seems to be a known phenomenon, where a data ingestion into a
B-Tree produces page splits following an oscillating pattern, which in turn
affects IO and buffer contention, impacting the performance. It turns out that
PostgreSQL is not an exception, but it should be possible to randomize a split
location a bit to mitigate the issue.
Hi,
Some time ago while working on models for PostgreSQL performance [1] I've
stumbled upon an interesting oscillating patters around various B-Tree metrics
(number of page splits, index size, etc). This turned out to be a known thing
described in a catchy way as "Waves of misery" [2], and boils down to the fact
that a fixed split location is usually chosen for a page split -- in this case
probabilities of page split lead to oscillating solutions under certain
workloads. Looks like the only pre-condition is that the data to be ingested
has the same distribution as the data already existing in the tree, in
particular UUIDs are in a bad position for this. And of course it's possible to
reproduce this with PostgreSQL.
Such an oscillation can lead to variability in IO and buffer contention,
negatively impacting performance. The fillfactor only shifts the waves, but do
not cancel them. One of the proposed remediation for this is to do suffix
truncation, which will "spread" split locations across some range. While we do
column suffix truncation, it turns out to be not enough for many workloads.
Another option is to randomize the split location, e.g. pick the actual
location from a range of 20% around the best one. In our case it's easy to do
randomization based on the split state, as all the possible split locations are
sorted by delta -- and all what's needed is to add a shift to the lowsplit from
a range, based on the number of split locations.
I've done few experiments with this, here is how it looks like:
* The first one is synthetic: a single column table with integer values, a
B-Tree index over it with the fillfactor=100, inserting new values one by one
from a uniform distribution via PGBench. In the graph "split.png" you can see
the number of page splits over time for the main branch and the patch (named
"Main" and "Rand" correspondingly), and the oscillating is clear for the
former one.
* Another one is following a data schema from one real projects out there, with
UUIDs as index values and very large records, with the default fillfactor=90.
The data ingestion is happening in large batches. The graph "split_batch.png"
represent the data for this case, with the main branch oscillating much more
than the randomized.
The unfortunate part is that I couldn't get clear numbers for the performance
impact. Turns out the disk in my experimental setup is not good enough to get a
sufficient number of inserts to trigger the issue, and to get nice graphs I was
running everything either on a RAM disk or on an unlogged table -- in both
cases it's easy to observe oscillations of page splits, but their impact is not
large enough since only so much IO is happening.
But anyway, any thoughts / commentaries on that?
[1]: https://zenodo.org/records/15786156
[2]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After Index
Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
From 888f70eae66f65e57399d2d0d61d8e664af90541 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 27 Apr 2026 16:53:14 +0200
Subject: [PATCH v1 1/2] Add a USDT for tracing nbtree page splits
Add a new USDT nbtree__page__split with a single argument BlockNumber to
trace page splits, which is usefull for experimenting.
---
src/backend/access/nbtree/nbtinsert.c | 3 +++
src/backend/utils/probes.d | 2 ++
2 files changed, 5 insertions(+)
diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index c8af97dd23d..ddb7b47118e 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -24,6 +24,7 @@
#include "common/pg_prng.h"
#include "lib/qunique.h"
#include "miscadmin.h"
+#include "pg_trace.h"
#include "storage/lmgr.h"
#include "storage/predicate.h"
#include "utils/injection_point.h"
@@ -2107,6 +2108,8 @@ _bt_split(Relation rel, Relation heaprel, BTScanInsert itup_key, Buffer buf,
pfree(lefthighkey);
/* split's done */
+ TRACE_POSTGRESQL_NBTREE_PAGE_SPLIT(origpagenumber);
+
return rbuf;
}
diff --git a/src/backend/utils/probes.d b/src/backend/utils/probes.d
index 1929521c6a5..521b76ec59e 100644
--- a/src/backend/utils/probes.d
+++ b/src/backend/utils/probes.d
@@ -91,4 +91,6 @@ provider postgresql {
probe wal__switch();
probe wal__buffer__write__dirty__start();
probe wal__buffer__write__dirty__done();
+
+ probe nbtree__page__split(BlockNumber);
};
base-commit: 1a51ec16db7aa1688d0083911db78e17ff7f26ba
--
2.52.0
From 4eb6062d5a5d5b0b79363bc986f14d595f9cc826 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 27 Apr 2026 16:54:36 +0200
Subject: [PATCH v1 2/2] Randomize nbtree split location to avoid oscillating
patterns
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
The way nbtree page split works can lead to the same split location
chosen over and over under certain workloads. To simplify it, as long as
the data to be ingested follows the same distribution as already
existing data, in particular it's true for an empty tree. According to
[1] (and some one-off experiments) this could lead to the number of
splits following an oscillating pattern, meaning some intrinsic
variability in performance.
The easiest workaround is to introduce a range around the best split
location, and pick up the actual split location at random from this
range. Introduce such randomization, based on the split status
containing list of possible locations. The whitepaper mentioned above
recommends range of 20%, so we stick with this range. A list of possible
split locations is sorted by delta, meaning that it's not exactly
equivalent to a "range around the best split location", but looks like
it's close enough.
[1]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After
Index Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
---
src/backend/access/nbtree/nbtsplitloc.c | 21 ++++++++++++++++++++-
1 file changed, 20 insertions(+), 1 deletion(-)
diff --git a/src/backend/access/nbtree/nbtsplitloc.c b/src/backend/access/nbtree/nbtsplitloc.c
index de9eca3c8b2..71becf0257e 100644
--- a/src/backend/access/nbtree/nbtsplitloc.c
+++ b/src/backend/access/nbtree/nbtsplitloc.c
@@ -17,6 +17,7 @@
#include "access/nbtree.h"
#include "access/tableam.h"
#include "common/int.h"
+#include "common/pg_prng.h"
typedef enum
{
@@ -792,6 +793,7 @@ _bt_bestsplitloc(FindSplitData *state, int perfectpenalty,
int bestpenalty,
lowsplit;
int highsplit = Min(state->interval, state->nsplits);
+ int rand_offset = 0;
SplitPoint *final;
bestpenalty = INT_MAX;
@@ -812,7 +814,24 @@ _bt_bestsplitloc(FindSplitData *state, int perfectpenalty,
break;
}
- final = &state->splits[lowsplit];
+ /*
+ * There are workloads, where we would find the same best split location
+ * over and over, even with the suffix truncation introducing some
+ * variability. According to [1] this leads to the number of splits
+ * following oscillating pattern, and the easiest workaround is to
+ * introduce some randomness in chosing split location.
+ *
+ * To achieve that add a random shift to the lowsplit, corresponding to the
+ * 20% of the all possible split locations. Since splits are sorted by
+ * delta (see _bt_deltasortsplits), it should be close enough to
+ * introducing a range around the split point.
+ *
+ * [1]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After
+ * Index Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
+ */
+ rand_offset = pg_prng_uint64_range(
+ &pg_global_prng_state, 0, state->nsplits * 0.2);
+ final = &state->splits[lowsplit + rand_offset];
/*
* There is a risk that the "many duplicates" strategy will repeatedly do
--
2.52.0
Attachments:
[text/plain] v1-0001-Add-a-USDT-for-tracing-nbtree-page-splits.patch (1.5K, ../../d6do2mtjcsagn37jf6pjywzhlzyokqja6jlnvcs4ypkvnnuu32@llwuuyxxomc3/2-v1-0001-Add-a-USDT-for-tracing-nbtree-page-splits.patch)
download | inline diff:
From 888f70eae66f65e57399d2d0d61d8e664af90541 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 27 Apr 2026 16:53:14 +0200
Subject: [PATCH v1 1/2] Add a USDT for tracing nbtree page splits
Add a new USDT nbtree__page__split with a single argument BlockNumber to
trace page splits, which is usefull for experimenting.
---
src/backend/access/nbtree/nbtinsert.c | 3 +++
src/backend/utils/probes.d | 2 ++
2 files changed, 5 insertions(+)
diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index c8af97dd23d..ddb7b47118e 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -24,6 +24,7 @@
#include "common/pg_prng.h"
#include "lib/qunique.h"
#include "miscadmin.h"
+#include "pg_trace.h"
#include "storage/lmgr.h"
#include "storage/predicate.h"
#include "utils/injection_point.h"
@@ -2107,6 +2108,8 @@ _bt_split(Relation rel, Relation heaprel, BTScanInsert itup_key, Buffer buf,
pfree(lefthighkey);
/* split's done */
+ TRACE_POSTGRESQL_NBTREE_PAGE_SPLIT(origpagenumber);
+
return rbuf;
}
diff --git a/src/backend/utils/probes.d b/src/backend/utils/probes.d
index 1929521c6a5..521b76ec59e 100644
--- a/src/backend/utils/probes.d
+++ b/src/backend/utils/probes.d
@@ -91,4 +91,6 @@ provider postgresql {
probe wal__switch();
probe wal__buffer__write__dirty__start();
probe wal__buffer__write__dirty__done();
+
+ probe nbtree__page__split(BlockNumber);
};
base-commit: 1a51ec16db7aa1688d0083911db78e17ff7f26ba
--
2.52.0
[text/plain] v1-0002-Randomize-nbtree-split-location-to-avoid-oscillat.patch (3.2K, ../../d6do2mtjcsagn37jf6pjywzhlzyokqja6jlnvcs4ypkvnnuu32@llwuuyxxomc3/3-v1-0002-Randomize-nbtree-split-location-to-avoid-oscillat.patch)
download | inline diff:
From 4eb6062d5a5d5b0b79363bc986f14d595f9cc826 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 27 Apr 2026 16:54:36 +0200
Subject: [PATCH v1 2/2] Randomize nbtree split location to avoid oscillating
patterns
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
The way nbtree page split works can lead to the same split location
chosen over and over under certain workloads. To simplify it, as long as
the data to be ingested follows the same distribution as already
existing data, in particular it's true for an empty tree. According to
[1] (and some one-off experiments) this could lead to the number of
splits following an oscillating pattern, meaning some intrinsic
variability in performance.
The easiest workaround is to introduce a range around the best split
location, and pick up the actual split location at random from this
range. Introduce such randomization, based on the split status
containing list of possible locations. The whitepaper mentioned above
recommends range of 20%, so we stick with this range. A list of possible
split locations is sorted by delta, meaning that it's not exactly
equivalent to a "range around the best split location", but looks like
it's close enough.
[1]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After
Index Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
---
src/backend/access/nbtree/nbtsplitloc.c | 21 ++++++++++++++++++++-
1 file changed, 20 insertions(+), 1 deletion(-)
diff --git a/src/backend/access/nbtree/nbtsplitloc.c b/src/backend/access/nbtree/nbtsplitloc.c
index de9eca3c8b2..71becf0257e 100644
--- a/src/backend/access/nbtree/nbtsplitloc.c
+++ b/src/backend/access/nbtree/nbtsplitloc.c
@@ -17,6 +17,7 @@
#include "access/nbtree.h"
#include "access/tableam.h"
#include "common/int.h"
+#include "common/pg_prng.h"
typedef enum
{
@@ -792,6 +793,7 @@ _bt_bestsplitloc(FindSplitData *state, int perfectpenalty,
int bestpenalty,
lowsplit;
int highsplit = Min(state->interval, state->nsplits);
+ int rand_offset = 0;
SplitPoint *final;
bestpenalty = INT_MAX;
@@ -812,7 +814,24 @@ _bt_bestsplitloc(FindSplitData *state, int perfectpenalty,
break;
}
- final = &state->splits[lowsplit];
+ /*
+ * There are workloads, where we would find the same best split location
+ * over and over, even with the suffix truncation introducing some
+ * variability. According to [1] this leads to the number of splits
+ * following oscillating pattern, and the easiest workaround is to
+ * introduce some randomness in chosing split location.
+ *
+ * To achieve that add a random shift to the lowsplit, corresponding to the
+ * 20% of the all possible split locations. Since splits are sorted by
+ * delta (see _bt_deltasortsplits), it should be close enough to
+ * introducing a range around the split point.
+ *
+ * [1]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After
+ * Index Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
+ */
+ rand_offset = pg_prng_uint64_range(
+ &pg_global_prng_state, 0, state->nsplits * 0.2);
+ final = &state->splits[lowsplit + rand_offset];
/*
* There is a risk that the "many duplicates" strategy will repeatedly do
--
2.52.0
[image/png] split.png (47.0K, ../../d6do2mtjcsagn37jf6pjywzhlzyokqja6jlnvcs4ypkvnnuu32@llwuuyxxomc3/4-split.png)
download | view image
[image/png] split_batch.png (55.2K, ../../d6do2mtjcsagn37jf6pjywzhlzyokqja6jlnvcs4ypkvnnuu32@llwuuyxxomc3/5-split_batch.png)
download | view image
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Randomize B-Tree page split location to avoid oscillating patterns
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
@ 2026-04-27 18:07 ` Peter Geoghegan <pg@bowt.ie>
2026-04-27 19:49 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andres Freund <andres@anarazel.de>
2026-05-06 17:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
0 siblings, 2 replies; 13+ messages in thread
From: Peter Geoghegan @ 2026-04-27 18:07 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: pgsql-hackers
On Mon, Apr 27, 2026 at 12:24 PM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> Some time ago while working on models for PostgreSQL performance [1] I've
> stumbled upon an interesting oscillating patters around various B-Tree metrics
> (number of page splits, index size, etc). This turned out to be a known thing
> described in a catchy way as "Waves of misery" [2], and boils down to the fact
> that a fixed split location is usually chosen for a page split -- in this case
> probabilities of page split lead to oscillating solutions under certain
> workloads.
I'm quite familiar with the paper, and find its argument convincing.
I'm not sure of the overall importance of the issues that they
describe, but the phenomenon is obviously real.
> Such an oscillation can lead to variability in IO and buffer contention,
> negatively impacting performance. The fillfactor only shifts the waves, but do
> not cancel them. One of the proposed remediation for this is to do suffix
> truncation, which will "spread" split locations across some range. While we do
> column suffix truncation, it turns out to be not enough for many workloads.
> Another option is to randomize the split location, e.g. pick the actual
> location from a range of 20% around the best one. In our case it's easy to do
> randomization based on the split state, as all the possible split locations are
> sorted by delta -- and all what's needed is to add a shift to the lowsplit from
> a range, based on the number of split locations.
My interpretation is that randomization can be combined with the usual
suffix truncation split point choosing heuristics; the paper even
recommends this at one point. That is, you randomly pick from a small
number of candidate split points that are all approximately equally
good according to the traditional criteria. It looks like your patch
doesn't account for suffix truncation at all, though.
Your patch should initially look for several split points that are
approximately equal in quality according to the current criteria -- a
separate, initial pass. You'd then randomly pick a final split point
from those gathered during this initial pass -- not from the original
fillfactormult-sorted list of split points. What you have in v1 will
make suffix truncation much less effective, which seems unacceptable.
Another issue is that nbtsort.c doesn't have any ability to pick among
split points; it focuses entirely on keeping free space balanced. To
get much benefit from this, I think you'd have to teach nbtsort.c to
also pick split points using approximately the same algorithm as
nbtsplitloc.c would (assuming retail inserts in ascending key space
order). I've been meaning to add proper suffix truncation to the
CREATE INDEX case.
> I've done few experiments with this, here is how it looks like:
>
> * The first one is synthetic: a single column table with integer values, a
> B-Tree index over it with the fillfactor=100, inserting new values one by one
> from a uniform distribution via PGBench. In the graph "split.png" you can see
> the number of page splits over time for the main branch and the patch (named
> "Main" and "Rand" correspondingly), and the oscillating is clear for the
> former one.
I don't think that fillfactor=100 is very interesting in general.
> The unfortunate part is that I couldn't get clear numbers for the performance
> impact. Turns out the disk in my experimental setup is not good enough to get a
> sufficient number of inserts to trigger the issue, and to get nice graphs I was
> running everything either on a RAM disk or on an unlogged table -- in both
> cases it's easy to observe oscillations of page splits, but their impact is not
> large enough since only so much IO is happening.
>
> But anyway, any thoughts / commentaries on that?
I wouldn't expect the patch to increase absolute throughput
significantly, if at all. Its value comes from making the *rate* of
splits over time more consistent, for a given fixed workload. You
might notice a more interesting effect if you look at latency,
particularly worst case latency.
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Randomize B-Tree page split location to avoid oscillating patterns
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
@ 2026-04-27 19:49 ` Andres Freund <andres@anarazel.de>
1 sibling, 0 replies; 13+ messages in thread
From: Andres Freund @ 2026-04-27 19:49 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: Dmitry Dolgov <9erthalion6@gmail.com>; pgsql-hackers
Hi,
On 2026-04-27 14:07:14 -0400, Peter Geoghegan wrote:
> On Mon, Apr 27, 2026 at 12:24 PM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> > The unfortunate part is that I couldn't get clear numbers for the performance
> > impact. Turns out the disk in my experimental setup is not good enough to get a
> > sufficient number of inserts to trigger the issue, and to get nice graphs I was
> > running everything either on a RAM disk or on an unlogged table -- in both
> > cases it's easy to observe oscillations of page splits, but their impact is not
> > large enough since only so much IO is happening.
> >
> > But anyway, any thoughts / commentaries on that?
>
> I wouldn't expect the patch to increase absolute throughput
> significantly, if at all. Its value comes from making the *rate* of
> splits over time more consistent, for a given fixed workload. You
> might notice a more interesting effect if you look at latency,
> particularly worst case latency.
Possibly somewhat orthogonal, but the worst case latency point reminded me of
something around this:
It seems like it's not great for contention avoidance / concurrency that right
now btree splits will often do IO - to write out a victim buffer and then to
extend the relation - while holding an exclusive lock on a page.
Couldn't we instead release the lock on the page, acquire an empty page,
reacquire the lock, recheck that the split is still needed and, if so, split
the page without needing to do IO while holding the lock?
Greetings,
Andres Freund
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Randomize B-Tree page split location to avoid oscillating patterns
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
@ 2026-05-06 17:10 ` Dmitry Dolgov <9erthalion6@gmail.com>
2026-05-06 17:49 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
1 sibling, 1 reply; 13+ messages in thread
From: Dmitry Dolgov @ 2026-05-06 17:10 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: pgsql-hackers
> On Mon, Apr 27, 2026 at 02:07:14PM -0400, Peter Geoghegan wrote:
Sorry for the delay.
> My interpretation is that randomization can be combined with the usual
> suffix truncation split point choosing heuristics; the paper even
> recommends this at one point. That is, you randomly pick from a small
> number of candidate split points that are all approximately equally
> good according to the traditional criteria. It looks like your patch
> doesn't account for suffix truncation at all, though.
>
> Your patch should initially look for several split points that are
> approximately equal in quality according to the current criteria -- a
> separate, initial pass. You'd then randomly pick a final split point
> from those gathered during this initial pass -- not from the original
> fillfactormult-sorted list of split points. What you have in v1 will
> make suffix truncation much less effective, which seems unacceptable.
The paper suggest combining randomization and suffix truncation via
randomly shifting the interval for truncation. I'm not sure a separate
pass is needed for that, looks like it should be enough to add random
shift to lowsplit / highsplit in _bt_bestsplitloc, when the penalty is
calculated.
The interesting part here is that it seems the current split interval
might be too small for such randomization to make a significant impact
-- few experiments show that with the current value the result looks
more like changing the fillfactor, waves are just shifting to the right.
Increasing the split interval helps in this case.
Such approach (randomized suffix truncation interval) produces the same
effect in a test with single column index as in the patch above. In a
test with a wider index and significant impact of truncation, there is
no visible degradation (and no oscillations either, as expected suffix
truncation introduces some randomness on it's own).
> Another issue is that nbtsort.c doesn't have any ability to pick among
> split points; it focuses entirely on keeping free space balanced. To
> get much benefit from this, I think you'd have to teach nbtsort.c to
> also pick split points using approximately the same algorithm as
> nbtsplitloc.c would (assuming retail inserts in ascending key space
> order). I've been meaning to add proper suffix truncation to the
> CREATE INDEX case.
Good point, I need to look into this.
> > The unfortunate part is that I couldn't get clear numbers for the performance
> > impact. Turns out the disk in my experimental setup is not good enough to get a
> > sufficient number of inserts to trigger the issue, and to get nice graphs I was
> > running everything either on a RAM disk or on an unlogged table -- in both
> > cases it's easy to observe oscillations of page splits, but their impact is not
> > large enough since only so much IO is happening.
> >
> > But anyway, any thoughts / commentaries on that?
>
> I wouldn't expect the patch to increase absolute throughput
> significantly, if at all. Its value comes from making the *rate* of
> splits over time more consistent, for a given fixed workload. You
> might notice a more interesting effect if you look at latency,
> particularly worst case latency.
That's exactly what I'm talking about. In those experiments I was trying
to get any visible changes in latency variability, but in this
particular setup I could spot nothing beyond regular noise, while the
number of page splits was obviously heavily oscillating.
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Randomize B-Tree page split location to avoid oscillating patterns
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-06 17:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
@ 2026-05-06 17:49 ` Peter Geoghegan <pg@bowt.ie>
2026-05-07 18:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
0 siblings, 1 reply; 13+ messages in thread
From: Peter Geoghegan @ 2026-05-06 17:49 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: pgsql-hackers
On Wed, May 6, 2026 at 1:10 PM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> > On Mon, Apr 27, 2026 at 02:07:14PM -0400, Peter Geoghegan wrote:
> > Your patch should initially look for several split points that are
> > approximately equal in quality according to the current criteria -- a
> > separate, initial pass. You'd then randomly pick a final split point
> > from those gathered during this initial pass -- not from the original
> > fillfactormult-sorted list of split points. What you have in v1 will
> > make suffix truncation much less effective, which seems unacceptable.
>
> The paper suggest combining randomization and suffix truncation via
> randomly shifting the interval for truncation. I'm not sure a separate
> pass is needed for that, looks like it should be enough to add random
> shift to lowsplit / highsplit in _bt_bestsplitloc, when the penalty is
> calculated.
I can't see why that would make much difference. Increasing the split
interval usually won't affect the final chosen split point at all.
Decreasing is more likely to change the split point, but that's
*precisely* because it makes suffix truncation less effective.
In general it's quite unlikely that an expanded interval (e.g.,
doubling LEAF_SPLIT_DISTANCE) will include a split point that
truncates additional index attributes compared to the best split point
available within the current calculated split interval/current
LEAF_SPLIT_DISTANCE. For example, with the TPC-C indexes, I'd expect
only a tiny minority of all page splits to be affected by doubling
LEAF_SPLIT_DISTANCE to make nbtsplitloc.c consider ~20% of all
possible split points around the middle of the page. Whereas *halving*
LEAF_SPLIT_DISTANCE will indeed make suffix truncation worse.
This asymmetry matters. I believe that it'll make it impossible for
space utilization to average out to the target leaffillfactor% over
time. After all, this approach doesn't actually target space
utilization. This is also why it will make literally no difference at
all with a single column unique index.
> The interesting part here is that it seems the current split interval
> might be too small for such randomization to make a significant impact
> -- few experiments show that with the current value the result looks
> more like changing the fillfactor, waves are just shifting to the right.
> Increasing the split interval helps in this case.
The point of gathering a list of "equally good" split points in an
initial pass is that it removes the danger of making the split
interval less effective in terms of final split penalty. The random
choice becomes a choice among split points that all truncate away the
same number of suffix attributes (all of which must still be
sufficiently close to the space-optimal split location to ensure that
no split is ever wildly unbalanced). This prevents the variable/random
choice from affecting the suffix truncation/split penalty.
With a single column unique index, all split points will have an equal
penalty under this scheme (implying that suffix truncation will be
equally effective). The initial list gathered in the first pass is
exactly all of the split points within the split interval in that
case. Whereas with other types of indexes the initial list gathered is
some subset of all the split points within the interval, without
regard for how balanced the post-split space utilization will be (all
splits within the interval are assumed to be "good enough" from a
space utilization perspective). Over time, space utilization should
reach fillfactor% -- without it negatively affecting suffix truncation.
It's possible that increasing the split interval would also make
sense. That seems like a follow-up question to me.
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Randomize B-Tree page split location to avoid oscillating patterns
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-06 17:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-05-06 17:49 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
@ 2026-05-07 18:10 ` Dmitry Dolgov <9erthalion6@gmail.com>
2026-06-16 10:13 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
0 siblings, 1 reply; 13+ messages in thread
From: Dmitry Dolgov @ 2026-05-07 18:10 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: pgsql-hackers
> On Wed, May 06, 2026 at 01:49:10PM -0400, Peter Geoghegan wrote:
> On Wed, May 6, 2026 at 1:10 PM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> > > On Mon, Apr 27, 2026 at 02:07:14PM -0400, Peter Geoghegan wrote:
> > > Your patch should initially look for several split points that are
> > > approximately equal in quality according to the current criteria -- a
> > > separate, initial pass. You'd then randomly pick a final split point
> > > from those gathered during this initial pass -- not from the original
> > > fillfactormult-sorted list of split points. What you have in v1 will
> > > make suffix truncation much less effective, which seems unacceptable.
> >
> > The paper suggest combining randomization and suffix truncation via
> > randomly shifting the interval for truncation. I'm not sure a separate
> > pass is needed for that, looks like it should be enough to add random
> > shift to lowsplit / highsplit in _bt_bestsplitloc, when the penalty is
> > calculated.
>
> I can't see why that would make much difference. Increasing the split
> interval usually won't affect the final chosen split point at all.
> Decreasing is more likely to change the split point, but that's
> *precisely* because it makes suffix truncation less effective.
I assume by increasing/decreasing the split interval you mean increase/decrease
around the split point, but I was talking about shifting the interval to the
right. More about this in the next part.
> The point of gathering a list of "equally good" split points in an
> initial pass is that it removes the danger of making the split
> interval less effective in terms of final split penalty. The random
> choice becomes a choice among split points that all truncate away the
> same number of suffix attributes (all of which must still be
> sufficiently close to the space-optimal split location to ensure that
> no split is ever wildly unbalanced). This prevents the variable/random
> choice from affecting the suffix truncation/split penalty.
I see what you mean, but I'm concerned about the resulting overhead. Here is my
understanding of how it would work, let me know if something is missing in the
chain of thoughts:
* What happens currently is we collect all possible split points, sort them by
delta, calculate the split interval. Then we iterate over the possible split
points in the interval [0, split interval), trying to find the one causing
the lowest penalty. If what we found is the best possible penalty, we stop --
for unique indexes it means that virtually all the time everything is over
after a single iteration, since the first attribute is enough to
distinguish the split.
* If we're going to pick at random from a list of "equally good" split points,
everything up to the split interval is the same. Then we iterate over the
possible split points in the interval [0, split interval), and search for all
the points with penalty equal or lower than the current lowest value (the
list is reset if we found a lower value). We search this way until we found
enough for the chosen randomization interval (those 20% from the paper) or
until we're out of split points. In the end we've got a list of split points,
each has equally low penalty, and we choose a split point at random from this
list. For a unique index it means we have to do at least as many iterations
as the size of randomization interval, instead of one iteration as before --
this is the overhead I'm concerned about.
* If we're going to shift the split interval, everything is also the same up to
the split interval calculation. Now we introduce a
delta = random from (0, randomization interval)
and consider two intervals of available split points:
[0, delta) and [delta, split interval + delta)
We first search in [0, delta) as before for lowest possible penalty, just to
make sure we're not missing it, if it's not present in the second interval.
The main part is search in [delta, split interval + delta) for a split point
with the same or lower penalty as found in the first interval and use it as
the final result. There are few possible outcomes:
1. There are one or more lowest penalty split point in [0, delta) and one or
more in [delta, split interval + delta). Since delta is randomized, we pick
one of the "equally good" split points at random.
2. There are one or more lowest penalty split points in [0, delta) and for
some reason none in [delta, split interval + delta). In this case we forgo
randomization and go with the lowest penalty split point, using the point
from the [0, delta).
3. There are none lowest penalty split points in [0, delta) and one or more
in [delta, split interval + delta). In this case we still pick up one of the
"equally good" split points, still with some randomization.
4. There are none lowest penalty split points in [0, randomization interval)
and one or more in [randomization interval, split interval + randomization
interval). In this case we still pick up one of the "equally good" split
points, but without randomization, since the best point lays beyond the
allowed randomization range, and we hit it all the time.
Ultimately we would like to apply randomization of split point for mostly
unique indexes, since otherwise suffix truncation already does the job. With
this approach the randomization interval serves as a threshold to distinguish
such indexes -- if the index has mostly unique values, the optimal split
point would be located close to the start of the interval and multiple
"equally good" points will fall within the randomization interval. If on the
other hand the index has many duplicating values, the optimal split point may
be located outside the randomization interval and we would choose it all
the time -- but thanks to suffix truncation it doesn't matter.
From the overhead perspective, with this approach we do:
- one search in [0, delta), which will end after one iteration for unique
indexes.
- then do a "jump" of random distance and do one search in [delta, split
interval + delta) on the same conditions. It will end after one iteration
for unique index, and will process a similar number of iteration otherwise.
To summarize, in comparison with the second approach the third one seems to
have less overhead, the same guarantees regarding penalty, and more complex
implementation. I'm fine going with the second approach, but first would like
to discuss the alternatives and make sure we're on the same page.
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Randomize B-Tree page split location to avoid oscillating patterns
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-06 17:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-05-06 17:49 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-07 18:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
@ 2026-06-16 10:13 ` Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-24 11:22 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andrey Borodin <x4mmm@yandex-team.ru>
0 siblings, 1 reply; 13+ messages in thread
From: Dmitry Dolgov @ 2026-06-16 10:13 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: pgsql-hackers
> On Thu, May 07, 2026 at 08:10:30PM +0200, Dmitry Dolgov wrote:
>
> To summarize, in comparison with the second approach the third one seems to
> have less overhead, the same guarantees regarding penalty, and more complex
> implementation. I'm fine going with the second approach, but first would like
> to discuss the alternatives and make sure we're on the same page.
Here is a sketch of what I had in mind. First two patches are metrics
only (adding USDT, I think 0001 makes sense to have in general, 0002 is
purely for benchmarking). The third patch implements strategy of
collecting equally good split points and choosing from them, and an
alternative version does the same via shifting the search interval
(attached with the txt suffix to not confuse the CF bot, whatever it
does nowadays).
I've managed to perform the same test as before (a best case scenario,
single column unique index) with a bit more throughput, and both
versions showed the same improvement over the main branch (see the
splits.png, where the patch versions are marked as "Rand (best loc)" and
"Rand (shifted)" for searching equally good split points and shifted
search interval correspondingly). It was also enough to produce visible
improvement for latency stddev as reported by pgbench (see stddev.png).
Measuring latency between newly introduced USDT inside _bt_findsplitloc
in this test shows that the latter version (shifted interval) is marginally
faster, probably due to the former needing to remember new data (equally good
split points):
// Time spent in _bt_findsplitloc for "shifted" version
@nsecs:
[4, 8) 2 | |
[8, 16) 9433 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ |
[16, 32) 11365 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[32, 64) 3940 |@@@@@@@@@@@@@@@@@@ |
[64, 128) 1255 |@@@@@ |
[128, 256) 595 |@@ |
[256, 512) 72 | |
[512, 1K) 0 | |
[1K, 2K) 0 | |
[2K, 4K) 1 | |
// Time spent in _bt_findsplitloc for "equally good points" version
@nsecs:
[4, 8) 1 | |
[8, 16) 8265 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ |
[16, 32) 10391 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[32, 64) 4982 |@@@@@@@@@@@@@@@@@@@@@@@@ |
[64, 128) 1155 |@@@@@ |
[128, 256) 698 |@@@ |
[256, 512) 79 | |
[512, 1K) 2 | |
[1K, 2K) 0 | |
[2K, 4K) 10 | |
From c4fc8e0ac8ff8846b7a7363b84ca31c3a30f2ae7 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Thu, 11 Jun 2026 22:03:07 +0200
Subject: [PATCH v2 1/3] Add USDT for nbtree page splits and suffix truncation
Add new USDT for nbtree:
* nbtree__page__split with a single argument BlockNumber to trace page
splits, which is usefull for understanding B-Tree performance.
* nbtree__page__truncate with a single integer argument representing
number of truncated columns, which tells ups truncation effectiveness.
---
src/backend/access/nbtree/nbtinsert.c | 3 +++
src/backend/access/nbtree/nbtutils.c | 2 ++
src/backend/utils/probes.d | 3 +++
3 files changed, 8 insertions(+)
diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index c8af97dd23d..ddb7b47118e 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -24,6 +24,7 @@
#include "common/pg_prng.h"
#include "lib/qunique.h"
#include "miscadmin.h"
+#include "pg_trace.h"
#include "storage/lmgr.h"
#include "storage/predicate.h"
#include "utils/injection_point.h"
@@ -2107,6 +2108,8 @@ _bt_split(Relation rel, Relation heaprel, BTScanInsert itup_key, Buffer buf,
pfree(lefthighkey);
/* split's done */
+ TRACE_POSTGRESQL_NBTREE_PAGE_SPLIT(origpagenumber);
+
return rbuf;
}
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 014faa1622f..e384354acee 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -24,6 +24,7 @@
#include "common/int.h"
#include "lib/qunique.h"
#include "miscadmin.h"
+#include "pg_trace.h"
#include "storage/lwlock.h"
#include "storage/subsystems.h"
#include "utils/datum.h"
@@ -737,6 +738,7 @@ _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright,
if (keepnatts <= nkeyatts)
{
BTreeTupleSetNAtts(pivot, keepnatts, false);
+ TRACE_POSTGRESQL_NBTREE_PAGE_TRUNCATE(nkeyatts - keepnatts);
return pivot;
}
diff --git a/src/backend/utils/probes.d b/src/backend/utils/probes.d
index 1929521c6a5..d827ed0201c 100644
--- a/src/backend/utils/probes.d
+++ b/src/backend/utils/probes.d
@@ -91,4 +91,7 @@ provider postgresql {
probe wal__switch();
probe wal__buffer__write__dirty__start();
probe wal__buffer__write__dirty__done();
+
+ probe nbtree__page__split(BlockNumber);
+ probe nbtree__page__truncate(int);
};
base-commit: 298bdd379552148f6043b4595374a7a6fbdd13c3
--
2.52.0
From f8f1f91af5cefcfa4cf2103194a53468faba0af9 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 15 Jun 2026 16:39:29 +0200
Subject: [PATCH v2 2/3] Add USDT for split location benchmarking
Add new USDTs probe nbtree__page__findsplit__(start / done) for
benchmarking of split logic.
---
src/backend/access/nbtree/nbtsplitloc.c | 5 +++++
src/backend/utils/probes.d | 3 +++
2 files changed, 8 insertions(+)
diff --git a/src/backend/access/nbtree/nbtsplitloc.c b/src/backend/access/nbtree/nbtsplitloc.c
index de9eca3c8b2..c64fef5ab27 100644
--- a/src/backend/access/nbtree/nbtsplitloc.c
+++ b/src/backend/access/nbtree/nbtsplitloc.c
@@ -17,6 +17,7 @@
#include "access/nbtree.h"
#include "access/tableam.h"
#include "common/int.h"
+#include "pg_trace.h"
typedef enum
{
@@ -152,6 +153,8 @@ _bt_findsplitloc(Relation rel,
SplitPoint leftpage,
rightpage;
+ TRACE_POSTGRESQL_NBTREE_PAGE_FINDSPLIT_START(origpage);
+
opaque = BTPageGetOpaque(origpage);
maxoff = PageGetMaxOffsetNumber(origpage);
@@ -425,6 +428,8 @@ _bt_findsplitloc(Relation rel,
strategy);
pfree(state.splits);
+ TRACE_POSTGRESQL_NBTREE_PAGE_FINDSPLIT_DONE(origpage);
+
return firstrightoff;
}
diff --git a/src/backend/utils/probes.d b/src/backend/utils/probes.d
index d827ed0201c..b90b708d862 100644
--- a/src/backend/utils/probes.d
+++ b/src/backend/utils/probes.d
@@ -94,4 +94,7 @@ provider postgresql {
probe nbtree__page__split(BlockNumber);
probe nbtree__page__truncate(int);
+
+ probe nbtree__page__findsplit__start(Page);
+ probe nbtree__page__findsplit__done(Page);
};
--
2.52.0
From 99c5d176c7e9958ced99405b8caa47f39745fff0 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 27 Apr 2026 16:54:36 +0200
Subject: [PATCH v2 3/3] Randomize nbtree split location to avoid oscillating
patterns
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
The way nbtree page split works can lead to the same split location
chosen over and over under certain workloads. To simplify it, as long as
the data to be ingested follows the same distribution as already
existing data, in particular it's true for an empty tree. According to
[1] (and some one-off experiments) this could lead to the number of
splits following an oscillating pattern, meaning some intrinsic
variability in performance.
A possible workaround is to find some number of equally good split locations,
and choose one of them at random. This brings some randomization, while keeping
the suffix truncation benefits. The whitepaper mentioned above recommends range
of 20%, so we stick with this value as the number of split location to search
for.
[1]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After
Index Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
---
src/backend/access/nbtree/nbtsplitloc.c | 53 +++++++++++++++++++++++--
1 file changed, 49 insertions(+), 4 deletions(-)
diff --git a/src/backend/access/nbtree/nbtsplitloc.c b/src/backend/access/nbtree/nbtsplitloc.c
index c64fef5ab27..919a0340f19 100644
--- a/src/backend/access/nbtree/nbtsplitloc.c
+++ b/src/backend/access/nbtree/nbtsplitloc.c
@@ -18,6 +18,7 @@
#include "access/tableam.h"
#include "common/int.h"
#include "pg_trace.h"
+#include "common/pg_prng.h"
typedef enum
{
@@ -778,7 +779,8 @@ _bt_adjacenthtid(const ItemPointerData *lowhtid, const ItemPointerData *highhtid
* points that fall within current/final split interval. Penalty is an
* abstract score, with a definition that varies depending on whether we're
* splitting a leaf page or an internal page. See _bt_split_penalty() for
- * details.
+ * details. If there are multiple equally good split points, pick up one at
+ * random to spread the choice.
*
* "perfectpenalty" is assumed to be the lowest possible penalty among
* candidate split points. This allows us to return early without wasting
@@ -797,27 +799,70 @@ _bt_bestsplitloc(FindSplitData *state, int perfectpenalty,
int bestpenalty,
lowsplit;
int highsplit = Min(state->interval, state->nsplits);
+ int rand_offset = 0;
+ int j = 0;
SplitPoint *final;
+ /*
+ * We're going to collect equally good split points to later pick up one
+ * from this set.
+ */
+ int *best_locs = palloc_array(int, state->maxsplits);
+
bestpenalty = INT_MAX;
lowsplit = 0;
+
for (int i = lowsplit; i < highsplit; i++)
{
int penalty;
penalty = _bt_split_penalty(state, state->splits + i);
- if (penalty < bestpenalty)
+ if (penalty == bestpenalty)
{
+ best_locs[j] = i;
+ j++;
+ }
+ else if (penalty < bestpenalty)
+ {
+ /*
+ * If we found a better split point, reset the list of already
+ * found ones and start anew.
+ */
+ j = 0;
+
bestpenalty = penalty;
lowsplit = i;
+
+ best_locs[j] = i;
+ j++;
}
- if (penalty <= perfectpenalty)
+ /*
+ * We search either until all the split points are evaluated, or we've
+ * collected 20% of all possible locations in the list of equally good
+ * split points.
+ */
+ if (j > state->nsplits * 0.2)
break;
}
- final = &state->splits[lowsplit];
+ /*
+ * There are workloads, where we would find the same best split location
+ * over and over, even with the suffix truncation introducing some
+ * variability. According to [1] this leads to the number of splits
+ * following oscillating pattern, and the easiest workaround is to
+ * introduce some randomness in chosing split location.
+ *
+ * To achieve that we pick up a split point at random among the list of
+ * equally good ones. Note that at this moment j points to an available
+ * spot in the list, so we need to reduce it by one.
+ *
+ * [1]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After
+ * Index Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
+ */
+ rand_offset = pg_prng_uint64_range(&pg_global_prng_state, 0, j - 1);
+ final = &state->splits[best_locs[rand_offset]];
/*
* There is a risk that the "many duplicates" strategy will repeatedly do
--
2.52.0
From d59e12b13cc06807ff622673acbfd681dc244afd Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 27 Apr 2026 16:54:36 +0200
Subject: [PATCH v2 3/3] Randomize nbtree split location to avoid oscillating
patterns
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
The way nbtree page split works can lead to the same split location
chosen over and over under certain workloads. To simplify it, as long as
the data to be ingested follows the same distribution as already
existing data, in particular it's true for an empty tree. According to
[1] (and some one-off experiments) this could lead to the number of
splits following an oscillating pattern, meaning some intrinsic
variability in performance.
A possible workaround is to introduce a random shift to the interval for
searching the best split location as suggested in [1]. This brings some
randomization, while keeping the suffix truncation benefits. The
whitepaper mentioned above recommends range of 20%, so we stick with
this value for the shift.
[1]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After
Index Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
---
src/backend/access/nbtree/nbtsplitloc.c | 50 ++++++++++++++++++++++++-
1 file changed, 48 insertions(+), 2 deletions(-)
diff --git a/src/backend/access/nbtree/nbtsplitloc.c b/src/backend/access/nbtree/nbtsplitloc.c
index c64fef5ab27..f61d55346fc 100644
--- a/src/backend/access/nbtree/nbtsplitloc.c
+++ b/src/backend/access/nbtree/nbtsplitloc.c
@@ -18,6 +18,7 @@
#include "access/tableam.h"
#include "common/int.h"
#include "pg_trace.h"
+#include "common/pg_prng.h"
typedef enum
{
@@ -778,7 +779,8 @@ _bt_adjacenthtid(const ItemPointerData *lowhtid, const ItemPointerData *highhtid
* points that fall within current/final split interval. Penalty is an
* abstract score, with a definition that varies depending on whether we're
* splitting a leaf page or an internal page. See _bt_split_penalty() for
- * details.
+ * details. The range of candidate split points is shifted by a random delta to
+ * the right to spread the choice of split point among equally good candidates.
*
* "perfectpenalty" is assumed to be the lowest possible penalty among
* candidate split points. This allows us to return early without wasting
@@ -797,11 +799,35 @@ _bt_bestsplitloc(FindSplitData *state, int perfectpenalty,
int bestpenalty,
lowsplit;
int highsplit = Min(state->interval, state->nsplits);
+ int rand_offset = 0;
SplitPoint *final;
bestpenalty = INT_MAX;
lowsplit = 0;
- for (int i = lowsplit; i < highsplit; i++)
+
+ /*
+ * There are workloads, where we would find the same best split location
+ * over and over, even with the suffix truncation introducing some
+ * variability. According to [1] this leads to the number of splits
+ * following oscillating pattern, and the easiest workaround is to
+ * introduce some randomness in chosing split location.
+ *
+ * To achieve that add a random shift to the search interval, corresponding
+ * to the 20% of the all possible split locations. For the sake of not
+ * degrading suffix truncation performance, search [0, rand shift) interval
+ * first, in case if it contains the only available best split point. Then
+ * search the main interval [rand shift, highsplit + rand shift), and pick
+ * up a split point from it if found. In the best case (a single column
+ * unique index) this leads to a single iteration of the first loop, then a
+ * random jump and a single iteration of the second loop.
+ *
+ * [1]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After
+ * Index Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
+ */
+ rand_offset = pg_prng_uint64_range(
+ &pg_global_prng_state, 0, state->nsplits * 0.2);
+
+ for (int i = lowsplit; i < rand_offset; i++)
{
int penalty;
@@ -817,6 +843,26 @@ _bt_bestsplitloc(FindSplitData *state, int perfectpenalty,
break;
}
+ for (int i = lowsplit + rand_offset; i < highsplit + rand_offset; i++)
+ {
+ int penalty;
+
+ penalty = _bt_split_penalty(state, state->splits + i);
+
+ /*
+ * We have already updated best penalty in the previous loop, so it's
+ * important to search for lower or equal penalties here.
+ */
+ if (penalty <= bestpenalty)
+ {
+ bestpenalty = penalty;
+ lowsplit = i;
+ }
+
+ if (penalty <= perfectpenalty)
+ break;
+ }
+
final = &state->splits[lowsplit];
/*
--
2.52.0
Attachments:
[text/plain] v2-0001-Add-USDT-for-nbtree-page-splits-and-suffix-trunca.patch (2.5K, ../../jotfal6422zpqvux4add7xcyftaujjiksscfcc5uuibaldw4sv@pzriktpx4gyl/2-v2-0001-Add-USDT-for-nbtree-page-splits-and-suffix-trunca.patch)
download | inline diff:
From c4fc8e0ac8ff8846b7a7363b84ca31c3a30f2ae7 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Thu, 11 Jun 2026 22:03:07 +0200
Subject: [PATCH v2 1/3] Add USDT for nbtree page splits and suffix truncation
Add new USDT for nbtree:
* nbtree__page__split with a single argument BlockNumber to trace page
splits, which is usefull for understanding B-Tree performance.
* nbtree__page__truncate with a single integer argument representing
number of truncated columns, which tells ups truncation effectiveness.
---
src/backend/access/nbtree/nbtinsert.c | 3 +++
src/backend/access/nbtree/nbtutils.c | 2 ++
src/backend/utils/probes.d | 3 +++
3 files changed, 8 insertions(+)
diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index c8af97dd23d..ddb7b47118e 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -24,6 +24,7 @@
#include "common/pg_prng.h"
#include "lib/qunique.h"
#include "miscadmin.h"
+#include "pg_trace.h"
#include "storage/lmgr.h"
#include "storage/predicate.h"
#include "utils/injection_point.h"
@@ -2107,6 +2108,8 @@ _bt_split(Relation rel, Relation heaprel, BTScanInsert itup_key, Buffer buf,
pfree(lefthighkey);
/* split's done */
+ TRACE_POSTGRESQL_NBTREE_PAGE_SPLIT(origpagenumber);
+
return rbuf;
}
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 014faa1622f..e384354acee 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -24,6 +24,7 @@
#include "common/int.h"
#include "lib/qunique.h"
#include "miscadmin.h"
+#include "pg_trace.h"
#include "storage/lwlock.h"
#include "storage/subsystems.h"
#include "utils/datum.h"
@@ -737,6 +738,7 @@ _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright,
if (keepnatts <= nkeyatts)
{
BTreeTupleSetNAtts(pivot, keepnatts, false);
+ TRACE_POSTGRESQL_NBTREE_PAGE_TRUNCATE(nkeyatts - keepnatts);
return pivot;
}
diff --git a/src/backend/utils/probes.d b/src/backend/utils/probes.d
index 1929521c6a5..d827ed0201c 100644
--- a/src/backend/utils/probes.d
+++ b/src/backend/utils/probes.d
@@ -91,4 +91,7 @@ provider postgresql {
probe wal__switch();
probe wal__buffer__write__dirty__start();
probe wal__buffer__write__dirty__done();
+
+ probe nbtree__page__split(BlockNumber);
+ probe nbtree__page__truncate(int);
};
base-commit: 298bdd379552148f6043b4595374a7a6fbdd13c3
--
2.52.0
[text/plain] v2-0002-Add-USDT-for-split-location-benchmarking.patch (1.6K, ../../jotfal6422zpqvux4add7xcyftaujjiksscfcc5uuibaldw4sv@pzriktpx4gyl/3-v2-0002-Add-USDT-for-split-location-benchmarking.patch)
download | inline diff:
From f8f1f91af5cefcfa4cf2103194a53468faba0af9 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 15 Jun 2026 16:39:29 +0200
Subject: [PATCH v2 2/3] Add USDT for split location benchmarking
Add new USDTs probe nbtree__page__findsplit__(start / done) for
benchmarking of split logic.
---
src/backend/access/nbtree/nbtsplitloc.c | 5 +++++
src/backend/utils/probes.d | 3 +++
2 files changed, 8 insertions(+)
diff --git a/src/backend/access/nbtree/nbtsplitloc.c b/src/backend/access/nbtree/nbtsplitloc.c
index de9eca3c8b2..c64fef5ab27 100644
--- a/src/backend/access/nbtree/nbtsplitloc.c
+++ b/src/backend/access/nbtree/nbtsplitloc.c
@@ -17,6 +17,7 @@
#include "access/nbtree.h"
#include "access/tableam.h"
#include "common/int.h"
+#include "pg_trace.h"
typedef enum
{
@@ -152,6 +153,8 @@ _bt_findsplitloc(Relation rel,
SplitPoint leftpage,
rightpage;
+ TRACE_POSTGRESQL_NBTREE_PAGE_FINDSPLIT_START(origpage);
+
opaque = BTPageGetOpaque(origpage);
maxoff = PageGetMaxOffsetNumber(origpage);
@@ -425,6 +428,8 @@ _bt_findsplitloc(Relation rel,
strategy);
pfree(state.splits);
+ TRACE_POSTGRESQL_NBTREE_PAGE_FINDSPLIT_DONE(origpage);
+
return firstrightoff;
}
diff --git a/src/backend/utils/probes.d b/src/backend/utils/probes.d
index d827ed0201c..b90b708d862 100644
--- a/src/backend/utils/probes.d
+++ b/src/backend/utils/probes.d
@@ -94,4 +94,7 @@ provider postgresql {
probe nbtree__page__split(BlockNumber);
probe nbtree__page__truncate(int);
+
+ probe nbtree__page__findsplit__start(Page);
+ probe nbtree__page__findsplit__done(Page);
};
--
2.52.0
[text/plain] v2-0003-Randomize-nbtree-split-location-to-avoid-oscillat.patch (4.4K, ../../jotfal6422zpqvux4add7xcyftaujjiksscfcc5uuibaldw4sv@pzriktpx4gyl/4-v2-0003-Randomize-nbtree-split-location-to-avoid-oscillat.patch)
download | inline diff:
From 99c5d176c7e9958ced99405b8caa47f39745fff0 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 27 Apr 2026 16:54:36 +0200
Subject: [PATCH v2 3/3] Randomize nbtree split location to avoid oscillating
patterns
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
The way nbtree page split works can lead to the same split location
chosen over and over under certain workloads. To simplify it, as long as
the data to be ingested follows the same distribution as already
existing data, in particular it's true for an empty tree. According to
[1] (and some one-off experiments) this could lead to the number of
splits following an oscillating pattern, meaning some intrinsic
variability in performance.
A possible workaround is to find some number of equally good split locations,
and choose one of them at random. This brings some randomization, while keeping
the suffix truncation benefits. The whitepaper mentioned above recommends range
of 20%, so we stick with this value as the number of split location to search
for.
[1]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After
Index Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
---
src/backend/access/nbtree/nbtsplitloc.c | 53 +++++++++++++++++++++++--
1 file changed, 49 insertions(+), 4 deletions(-)
diff --git a/src/backend/access/nbtree/nbtsplitloc.c b/src/backend/access/nbtree/nbtsplitloc.c
index c64fef5ab27..919a0340f19 100644
--- a/src/backend/access/nbtree/nbtsplitloc.c
+++ b/src/backend/access/nbtree/nbtsplitloc.c
@@ -18,6 +18,7 @@
#include "access/tableam.h"
#include "common/int.h"
#include "pg_trace.h"
+#include "common/pg_prng.h"
typedef enum
{
@@ -778,7 +779,8 @@ _bt_adjacenthtid(const ItemPointerData *lowhtid, const ItemPointerData *highhtid
* points that fall within current/final split interval. Penalty is an
* abstract score, with a definition that varies depending on whether we're
* splitting a leaf page or an internal page. See _bt_split_penalty() for
- * details.
+ * details. If there are multiple equally good split points, pick up one at
+ * random to spread the choice.
*
* "perfectpenalty" is assumed to be the lowest possible penalty among
* candidate split points. This allows us to return early without wasting
@@ -797,27 +799,70 @@ _bt_bestsplitloc(FindSplitData *state, int perfectpenalty,
int bestpenalty,
lowsplit;
int highsplit = Min(state->interval, state->nsplits);
+ int rand_offset = 0;
+ int j = 0;
SplitPoint *final;
+ /*
+ * We're going to collect equally good split points to later pick up one
+ * from this set.
+ */
+ int *best_locs = palloc_array(int, state->maxsplits);
+
bestpenalty = INT_MAX;
lowsplit = 0;
+
for (int i = lowsplit; i < highsplit; i++)
{
int penalty;
penalty = _bt_split_penalty(state, state->splits + i);
- if (penalty < bestpenalty)
+ if (penalty == bestpenalty)
{
+ best_locs[j] = i;
+ j++;
+ }
+ else if (penalty < bestpenalty)
+ {
+ /*
+ * If we found a better split point, reset the list of already
+ * found ones and start anew.
+ */
+ j = 0;
+
bestpenalty = penalty;
lowsplit = i;
+
+ best_locs[j] = i;
+ j++;
}
- if (penalty <= perfectpenalty)
+ /*
+ * We search either until all the split points are evaluated, or we've
+ * collected 20% of all possible locations in the list of equally good
+ * split points.
+ */
+ if (j > state->nsplits * 0.2)
break;
}
- final = &state->splits[lowsplit];
+ /*
+ * There are workloads, where we would find the same best split location
+ * over and over, even with the suffix truncation introducing some
+ * variability. According to [1] this leads to the number of splits
+ * following oscillating pattern, and the easiest workaround is to
+ * introduce some randomness in chosing split location.
+ *
+ * To achieve that we pick up a split point at random among the list of
+ * equally good ones. Note that at this moment j points to an available
+ * spot in the list, so we need to reduce it by one.
+ *
+ * [1]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After
+ * Index Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
+ */
+ rand_offset = pg_prng_uint64_range(&pg_global_prng_state, 0, j - 1);
+ final = &state->splits[best_locs[rand_offset]];
/*
* There is a risk that the "many duplicates" strategy will repeatedly do
--
2.52.0
[text/plain] v2-0003-Randomize-nbtree-split-location-to-avoid-oscillat.patch.txt (4.5K, ../../jotfal6422zpqvux4add7xcyftaujjiksscfcc5uuibaldw4sv@pzriktpx4gyl/5-v2-0003-Randomize-nbtree-split-location-to-avoid-oscillat.patch.txt)
download | inline diff:
From d59e12b13cc06807ff622673acbfd681dc244afd Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 27 Apr 2026 16:54:36 +0200
Subject: [PATCH v2 3/3] Randomize nbtree split location to avoid oscillating
patterns
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
The way nbtree page split works can lead to the same split location
chosen over and over under certain workloads. To simplify it, as long as
the data to be ingested follows the same distribution as already
existing data, in particular it's true for an empty tree. According to
[1] (and some one-off experiments) this could lead to the number of
splits following an oscillating pattern, meaning some intrinsic
variability in performance.
A possible workaround is to introduce a random shift to the interval for
searching the best split location as suggested in [1]. This brings some
randomization, while keeping the suffix truncation benefits. The
whitepaper mentioned above recommends range of 20%, so we stick with
this value for the shift.
[1]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After
Index Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
---
src/backend/access/nbtree/nbtsplitloc.c | 50 ++++++++++++++++++++++++-
1 file changed, 48 insertions(+), 2 deletions(-)
diff --git a/src/backend/access/nbtree/nbtsplitloc.c b/src/backend/access/nbtree/nbtsplitloc.c
index c64fef5ab27..f61d55346fc 100644
--- a/src/backend/access/nbtree/nbtsplitloc.c
+++ b/src/backend/access/nbtree/nbtsplitloc.c
@@ -18,6 +18,7 @@
#include "access/tableam.h"
#include "common/int.h"
#include "pg_trace.h"
+#include "common/pg_prng.h"
typedef enum
{
@@ -778,7 +779,8 @@ _bt_adjacenthtid(const ItemPointerData *lowhtid, const ItemPointerData *highhtid
* points that fall within current/final split interval. Penalty is an
* abstract score, with a definition that varies depending on whether we're
* splitting a leaf page or an internal page. See _bt_split_penalty() for
- * details.
+ * details. The range of candidate split points is shifted by a random delta to
+ * the right to spread the choice of split point among equally good candidates.
*
* "perfectpenalty" is assumed to be the lowest possible penalty among
* candidate split points. This allows us to return early without wasting
@@ -797,11 +799,35 @@ _bt_bestsplitloc(FindSplitData *state, int perfectpenalty,
int bestpenalty,
lowsplit;
int highsplit = Min(state->interval, state->nsplits);
+ int rand_offset = 0;
SplitPoint *final;
bestpenalty = INT_MAX;
lowsplit = 0;
- for (int i = lowsplit; i < highsplit; i++)
+
+ /*
+ * There are workloads, where we would find the same best split location
+ * over and over, even with the suffix truncation introducing some
+ * variability. According to [1] this leads to the number of splits
+ * following oscillating pattern, and the easiest workaround is to
+ * introduce some randomness in chosing split location.
+ *
+ * To achieve that add a random shift to the search interval, corresponding
+ * to the 20% of the all possible split locations. For the sake of not
+ * degrading suffix truncation performance, search [0, rand shift) interval
+ * first, in case if it contains the only available best split point. Then
+ * search the main interval [rand shift, highsplit + rand shift), and pick
+ * up a split point from it if found. In the best case (a single column
+ * unique index) this leads to a single iteration of the first loop, then a
+ * random jump and a single iteration of the second loop.
+ *
+ * [1]: Glombiewski N., Seeger B., Graefe G. (2019). Waves of Misery After
+ * Index Creation. BTW 2019. Gesellschaft für Informatik. doi:10.18420/btw2019-06
+ */
+ rand_offset = pg_prng_uint64_range(
+ &pg_global_prng_state, 0, state->nsplits * 0.2);
+
+ for (int i = lowsplit; i < rand_offset; i++)
{
int penalty;
@@ -817,6 +843,26 @@ _bt_bestsplitloc(FindSplitData *state, int perfectpenalty,
break;
}
+ for (int i = lowsplit + rand_offset; i < highsplit + rand_offset; i++)
+ {
+ int penalty;
+
+ penalty = _bt_split_penalty(state, state->splits + i);
+
+ /*
+ * We have already updated best penalty in the previous loop, so it's
+ * important to search for lower or equal penalties here.
+ */
+ if (penalty <= bestpenalty)
+ {
+ bestpenalty = penalty;
+ lowsplit = i;
+ }
+
+ if (penalty <= perfectpenalty)
+ break;
+ }
+
final = &state->splits[lowsplit];
/*
--
2.52.0
[image/png] splits.png (59.0K, ../../jotfal6422zpqvux4add7xcyftaujjiksscfcc5uuibaldw4sv@pzriktpx4gyl/6-splits.png)
download | view image
[image/png] stddev.png (47.8K, ../../jotfal6422zpqvux4add7xcyftaujjiksscfcc5uuibaldw4sv@pzriktpx4gyl/7-stddev.png)
download | view image
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Randomize B-Tree page split location to avoid oscillating patterns
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-06 17:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-05-06 17:49 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-07 18:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-06-16 10:13 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
@ 2026-08-24 11:22 ` Andrey Borodin <x4mmm@yandex-team.ru>
2026-08-24 20:03 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
0 siblings, 1 reply; 13+ messages in thread
From: Andrey Borodin @ 2026-08-24 11:22 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: Peter Geoghegan <pg@bowt.ie>; pgsql-hackers; Andres Freund <andres@anarazel.de>
Hi Dmitry, Peter, Andres,
On Tue, Jun 16, 2026 at 10:13 AM Dmitry Dolgov wrote:
> We search either until all the split points are evaluated, or we've
> collected 20% of all possible locations in the list of equally good
> split points.
I like Peter's formulation that the random choice should only be among
split points that are equally good according to the existing criteria.
I do not think v2 quite guarantees that yet.
state->splits is ordered by distance from the desired space balance, not
by _bt_split_penalty(). The loop can collect 20% of locations with the
best penalty seen so far and stop before reaching a lower penalty later
in the interval. The existing early exit is safe because it only stops
at perfectpenalty, which is a known lower bound.
There is also a special case in SPLIT_MANY_DUPLICATES. That strategy
widens the interval to the whole page, but still relies on delta order to
pick the nearest location with the required penalty. Randomizing among
equal-penalty locations changes that policy and might also avoid the
existing protection against repeatedly leaving unusable free space.
Would it be simpler to initially restrict randomization to
SPLIT_DEFAULT leaf splits, examine the whole existing interval, and use
reservoir sampling among locations with the true minimum penalty? That
would need no extra array and would preserve suffix truncation exactly.
The existing default interval is deliberately narrow, so I would first
measure the cost of scanning it completely before adding an early exit.
On Mon, Apr 27, 2026 at 7:49 PM Andres Freund wrote:
> Couldn't we instead release the lock on the page, acquire an empty page,
> reacquire the lock, recheck that the split is still needed and, if so,
> split the page without needing to do IO while holding the lock?
Releasing and reacquiring the page lock sounds somewhat risky to me. A
concurrent inserter may change the page or split it, so this turns into a
restart protocol, with an acquired page that may no longer be needed.
Could we instead keep a small reserve of pages that can be acquired
without victim writeback or relation extension, replenished in the
background or in batches? Heap already uses ExtendBufferedRelBy() to
extend by multiple blocks and makes the extra pages available through a
BulkInsertState or the FSM, while _bt_allocbuf() requests exactly one
page. I am not sure whether a reserve belongs in bufmgr, the FSM, or the
access method, but it might avoid changing the B-tree locking protocol.
Thank you!
Best regards, Andrey Borodin.
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Randomize B-Tree page split location to avoid oscillating patterns
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-06 17:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-05-06 17:49 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-07 18:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-06-16 10:13 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-24 11:22 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andrey Borodin <x4mmm@yandex-team.ru>
@ 2026-08-24 20:03 ` Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-25 11:27 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andrey Borodin <x4mmm@yandex-team.ru>
0 siblings, 1 reply; 13+ messages in thread
From: Dmitry Dolgov @ 2026-08-24 20:03 UTC (permalink / raw)
To: Andrey Borodin <x4mmm@yandex-team.ru>; +Cc: Peter Geoghegan <pg@bowt.ie>; pgsql-hackers; Andres Freund <andres@anarazel.de>
> On Mon, Aug 24, 2026 at 02:22:46PM +0300, Andrey Borodin wrote:
Thanks for looking into it.
> state->splits is ordered by distance from the desired space balance, not
> by _bt_split_penalty(). The loop can collect 20% of locations with the
> best penalty seen so far and stop before reaching a lower penalty later
> in the interval. The existing early exit is safe because it only stops
> at perfectpenalty, which is a known lower bound.
v2 does not rely on the split points being sorted anymore, but reaching
20% before finding even better split location is indeed a bug in the
algorithm. I have to adjust the last condition to be something like
"we've reached 20% and it's a perfectpenalty", which will be equivalent
to the original implementation. Btw, I think the second approach,
nicknamed "shifted interval", is not affected by this since it uses very
same logic as in the original loop.
> There is also a special case in SPLIT_MANY_DUPLICATES. That strategy
> widens the interval to the whole page, but still relies on delta order to
> pick the nearest location with the required penalty. Randomizing among
> equal-penalty locations changes that policy and might also avoid the
> existing protection against repeatedly leaving unusable free space.
>
> Would it be simpler to initially restrict randomization to
> SPLIT_DEFAULT leaf splits,
Yeah, I've actually concentrated my efforts on SPLIT_DEFAULT and haven't
tested other strategies, so it sounds reasonable to apply randomization
only to this strategy.
> examine the whole existing interval, and use
> reservoir sampling among locations with the true minimum penalty? That
> would need no extra array and would preserve suffix truncation exactly.
If I got you correct, we still would need to keep locations with the
true minimum penalty, so this part sounds similar to what already
happens in the v2.
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Randomize B-Tree page split location to avoid oscillating patterns
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-06 17:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-05-06 17:49 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-07 18:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-06-16 10:13 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-24 11:22 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andrey Borodin <x4mmm@yandex-team.ru>
2026-08-24 20:03 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
@ 2026-08-25 11:27 ` Andrey Borodin <x4mmm@yandex-team.ru>
2026-08-28 20:39 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
0 siblings, 1 reply; 13+ messages in thread
From: Andrey Borodin @ 2026-08-25 11:27 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: Peter Geoghegan <pg@bowt.ie>; pgsql-hackers; Andres Freund <andres@anarazel.de>
Hi Dmitry,
On Mon, Aug 24, 2026 at 11:03 PM Dmitry Dolgov wrote:
> Btw, I think the second approach, nicknamed "shifted interval", is not
> affected by this since it uses very same logic as in the original loop.
Right, the early-stop problem does not apply to the shifted-interval
variant. Its two loops together scan
[0, rand_offset)
[rand_offset, highsplit + rand_offset)
rather than the original [0, highsplit) interval. The new upper bound is
not capped at state->nsplits and, even when capped, extends the search
beyond the original balance interval.
> If I got you correct, we still would need to keep locations with the
> true minimum penalty, so this part sounds similar to what already
> happens in the v2.
We only need to keep one selected location and the number of equally
good locations seen so far. In pseudocode:
if (penalty < bestpenalty)
bestpenalty = penalty, selected = i, nmatches = 1;
else if (penalty == bestpenalty)
if (random(++nmatches) == 0)
selected = i;
After a full scan, this produces the same random choice among locations
with the true minimum penalty as collecting those locations in an array
and choosing an element at the end, without storing the array.
Separately, I followed up on my suggestion in response to Andres and
tried extending B-tree indexes in batches. PFA a prototype.
When _bt_allocbuf() exhausts the FSM, it extends the index by several
pages, returns the first page to the split, and records the rest in the
FSM. The batch grows geometrically for small indexes and is capped at
16 pages. This amortizes relation extension without changing the
B-tree locking protocol.
The act of extending a relation is not WAL-logged directly.
FSM updates are hints, but MarkBufferDirtyHint() can emit an
XLOG_FPI_FOR_HINT record, so an FSM page can reach a standby. The standby
can therefore have an FSM entry past the end of its main fork. This is
the issue exposed by heap bulk extension [0]. The prototype relies on
the later FSM fix [1], which rejects such entries. Its test covers the
length difference and continued index use after promotion.
In a custom fixed-work pgbench test, 32 clients each performed 50,000
prepared single-row inserts with increasing int8 keys into an unlogged
table with a 3-million-entry B-tree. Batches of 16 reduced extension
calls from about 5,635 to 354 and extension time from about 96 ms to 9
ms. The three paired TPS changes were +4.5%, +1.9%, and +1.3%; p99
latency improved by about 12%. One client showed no throughput change,
while its p99.99 became worse, as expected for a rarer but larger
extension.
Best regards, Andrey Borodin.
[0] https://postgr.es/m/20221029025420.eplyow6k7tgu6he3@awork3.anarazel.de
[1] https://postgr.es/m/1878547.tdWV9SEqCh@aivenlaptop
Attachments:
[application/octet-stream] 0001-Extend-B-tree-indexes-in-batches.patch (8.0K, ../../15C0FA35-AF17-4166-B2F7-22253034468E@yandex-team.ru/2-0001-Extend-B-tree-indexes-in-batches.patch)
download | inline diff:
From 80b8ed85259bd160ab8ce1a589e6fae8caef1af7 Mon Sep 17 00:00:00 2001
From: Andrey Borodin <amborodin@acm.org>
Date: Tue, 25 Aug 2026 11:21:17 +0500
Subject: [PATCH v1] Extend B-tree indexes in batches
B-tree page splits can have to extend the index while holding an
exclusive lock on the page being split. Extending one page at a time
makes this potentially expensive path recur for every split once the FSM
is empty.
Use ExtendBufferedRelBy() to grow geometrically up to a batch of 16
pages. Return the first page to the split and make the remaining zero
pages available through the index FSM.
Relation extension is not WAL-logged. FSM updates normally aren't
either, but an FSM page can reach a standby in a hint full-page image.
The standby can therefore have a shorter main fork and FSM entries beyond
its end. The existing FSM main-fork length check makes those entries
safe. Add a recovery test that exercises the different relation lengths
and subsequent use after promotion.
Discussion: https://postgr.es/m/d6do2mtjcsagn37jf6pjywzhlzyokqja6jlnvcs4ypkvnnuu32@llwuuyxxomc3
---
src/backend/access/nbtree/nbtpage.c | 32 ++++++++-
src/backend/storage/freespace/indexfsm.c | 15 +++++
src/include/storage/indexfsm.h | 2 +
src/test/recovery/meson.build | 1 +
.../recovery/t/056_btree_bulk_extension.pl | 67 +++++++++++++++++++
5 files changed, 115 insertions(+), 2 deletions(-)
create mode 100644 src/test/recovery/t/056_btree_bulk_extension.pl
diff --git a/src/backend/access/nbtree/nbtpage.c b/src/backend/access/nbtree/nbtpage.c
index ff7d2a93948..bf30b14bb9c 100644
--- a/src/backend/access/nbtree/nbtpage.c
+++ b/src/backend/access/nbtree/nbtpage.c
@@ -38,6 +38,8 @@
#include "utils/memutils.h"
#include "utils/snapmgr.h"
+#define BTREE_MAX_EXTEND_BY 16
+
static BTMetaPageData *_bt_getmeta(Relation rel, Buffer metabuf);
static void _bt_delitems_delete(Relation rel, Buffer buf,
TransactionId snapshotConflictHorizon,
@@ -853,9 +855,11 @@ _bt_getbuf(Relation rel, BlockNumber blkno, int access)
Buffer
_bt_allocbuf(Relation rel, Relation heaprel)
{
+ Buffer buffers[BTREE_MAX_EXTEND_BY];
Buffer buf;
BlockNumber blkno;
Page page;
+ uint32 extend_by;
Assert(heaprel != NULL);
@@ -954,13 +958,37 @@ _bt_allocbuf(Relation rel, Relation heaprel)
}
/*
- * Extend the relation by one page. Need to use RBM_ZERO_AND_LOCK or we
+ * Extend the relation by several pages, retaining the first page for this
+ * allocation and making the rest available through the FSM. This
+ * amortizes relation extension and buffer replacement across several
+ * page splits. Grow geometrically at first, so that this doesn't bloat
+ * small indexes, and cap the batch to limit the number of buffers pinned
+ * at once.
+ *
+ * Relation extension is not WAL-logged. FSM updates normally aren't
+ * either, but an FSM page can reach a standby in a hint full-page image.
+ * The standby can therefore have FSM entries for reserved pages beyond the
+ * end of its main fork. GetFreeIndexPage() verifies the main fork's
+ * length before returning such an entry.
+ *
+ * Need to use RBM_ZERO_AND_LOCK for the first page or we
* risk a race condition against btvacuumscan --- see comments therein.
* This forces us to repeat the valgrind request that _bt_lockbuf()
* otherwise would make, as we can't use _bt_lockbuf() without introducing
* a race.
*/
- buf = ExtendBufferedRel(BMR_REL(rel), MAIN_FORKNUM, NULL, EB_LOCK_FIRST);
+ extend_by = Min(RelationGetNumberOfBlocks(rel), BTREE_MAX_EXTEND_BY);
+ extend_by = Max(extend_by, 1);
+ blkno = ExtendBufferedRelBy(BMR_REL(rel), MAIN_FORKNUM, NULL,
+ EB_LOCK_FIRST, extend_by, buffers, &extend_by);
+ buf = buffers[0];
+
+ for (uint32 i = 1; i < extend_by; i++)
+ ReleaseBuffer(buffers[i]);
+
+ if (extend_by > 1)
+ RecordFreeIndexPages(rel, blkno + 1, extend_by - 1);
+
if (!RelationUsesLocalBuffers(rel))
VALGRIND_MAKE_MEM_DEFINED(BufferGetPage(buf), BLCKSZ);
diff --git a/src/backend/storage/freespace/indexfsm.c b/src/backend/storage/freespace/indexfsm.c
index 85fbbab6c9c..7bc390fd235 100644
--- a/src/backend/storage/freespace/indexfsm.c
+++ b/src/backend/storage/freespace/indexfsm.c
@@ -54,6 +54,21 @@ RecordFreeIndexPage(Relation rel, BlockNumber freeBlock)
RecordPageWithFreeSpace(rel, freeBlock, BLCKSZ - 1);
}
+/*
+ * RecordFreeIndexPages - mark a range of pages as free in the FSM
+ */
+void
+RecordFreeIndexPages(Relation rel, BlockNumber firstBlock, uint32 nblocks)
+{
+ BlockNumber lastBlock = firstBlock + nblocks;
+
+ Assert(nblocks > 0);
+
+ for (BlockNumber blkno = firstBlock; blkno < lastBlock; blkno++)
+ RecordFreeIndexPage(rel, blkno);
+
+ FreeSpaceMapVacuumRange(rel, firstBlock, lastBlock);
+}
/*
* RecordUsedIndexPage - mark a page as used in the FSM
diff --git a/src/include/storage/indexfsm.h b/src/include/storage/indexfsm.h
index 7174bcdff99..830b7585e79 100644
--- a/src/include/storage/indexfsm.h
+++ b/src/include/storage/indexfsm.h
@@ -19,6 +19,8 @@
extern BlockNumber GetFreeIndexPage(Relation rel);
extern void RecordFreeIndexPage(Relation rel, BlockNumber freeBlock);
+extern void RecordFreeIndexPages(Relation rel, BlockNumber firstBlock,
+ uint32 nblocks);
extern void RecordUsedIndexPage(Relation rel, BlockNumber usedBlock);
extern void IndexFreeSpaceMapVacuum(Relation rel);
diff --git a/src/test/recovery/meson.build b/src/test/recovery/meson.build
index 39ec8c4946d..2c6cf344681 100644
--- a/src/test/recovery/meson.build
+++ b/src/test/recovery/meson.build
@@ -64,6 +64,7 @@ tests += {
't/053_standby_login_event_trigger.pl',
't/054_unlogged_sequence_promotion.pl',
't/055_cascade_reconnect.pl',
+ 't/056_btree_bulk_extension.pl',
],
},
}
diff --git a/src/test/recovery/t/056_btree_bulk_extension.pl b/src/test/recovery/t/056_btree_bulk_extension.pl
new file mode 100644
index 00000000000..3484b318b08
--- /dev/null
+++ b/src/test/recovery/t/056_btree_bulk_extension.pl
@@ -0,0 +1,67 @@
+# Copyright (c) 2026, PostgreSQL Global Development Group
+
+# Test recovery when B-tree bulk extension makes the primary's main fork
+# longer than the standby's. Relation extension is not WAL-logged, while an
+# index FSM page can reach the standby in a hint full-page image. The standby
+# may therefore have FSM entries for reserved pages that do not exist in its
+# main fork.
+use strict;
+use warnings FATAL => 'all';
+
+use PostgreSQL::Test::Cluster;
+use PostgreSQL::Test::Utils;
+use Test::More;
+
+my $primary = PostgreSQL::Test::Cluster->new('primary');
+$primary->init(allows_streaming => 1, data_checksums => 1);
+$primary->append_conf(
+ 'postgresql.conf', qq{
+autovacuum = off
+shared_buffers = '16MB'
+});
+$primary->start;
+
+$primary->backup('backup');
+my $standby = PostgreSQL::Test::Cluster->new('standby');
+$standby->init_from_backup($primary, 'backup', has_streaming => 1);
+$standby->start;
+
+$primary->safe_psql(
+ 'postgres', q{
+CREATE TABLE btree_bulk_extension_test (i integer);
+CREATE INDEX btree_bulk_extension_idx ON btree_bulk_extension_test (i);
+INSERT INTO btree_bulk_extension_test SELECT i FROM generate_series(1, 10000) i;
+});
+
+$primary->wait_for_replay_catchup($standby);
+
+my $primary_pages = $primary->safe_psql(
+ 'postgres',
+ q{SELECT pg_relation_size('btree_bulk_extension_idx') /
+ current_setting('block_size')::integer});
+my $standby_pages = $standby->safe_psql(
+ 'postgres',
+ q{SELECT pg_relation_size('btree_bulk_extension_idx') /
+ current_setting('block_size')::integer});
+
+cmp_ok($primary_pages, '>', $standby_pages,
+ 'reserved B-tree pages are not replayed on standby');
+
+$standby->promote;
+$standby->restart;
+
+$standby->safe_psql(
+ 'postgres', q{
+INSERT INTO btree_bulk_extension_test SELECT i FROM generate_series(10001, 20000) i;
+});
+
+is(
+ $standby->safe_psql(
+ 'postgres', q{
+SET enable_seqscan = off;
+SELECT count(*) FROM btree_bulk_extension_test WHERE i BETWEEN 1 AND 20000;
+}),
+ '20000',
+ 'promoted standby can extend and scan the B-tree');
+
+done_testing();
--
That's all, folks. May the source be with you.
=
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Randomize B-Tree page split location to avoid oscillating patterns
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-06 17:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-05-06 17:49 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-07 18:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-06-16 10:13 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-24 11:22 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andrey Borodin <x4mmm@yandex-team.ru>
2026-08-24 20:03 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-25 11:27 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andrey Borodin <x4mmm@yandex-team.ru>
@ 2026-08-28 20:39 ` Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-29 17:37 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andrey Borodin <x4mmm@yandex-team.ru>
0 siblings, 1 reply; 13+ messages in thread
From: Dmitry Dolgov @ 2026-08-28 20:39 UTC (permalink / raw)
To: Andrey Borodin <x4mmm@yandex-team.ru>; +Cc: Peter Geoghegan <pg@bowt.ie>; pgsql-hackers; Andres Freund <andres@anarazel.de>
> On Tue, Aug 25, 2026 at 04:27:25PM +0500, Andrey Borodin wrote:
> > If I got you correct, we still would need to keep locations with the
> > true minimum penalty, so this part sounds similar to what already
> > happens in the v2.
>
> We only need to keep one selected location and the number of equally
> good locations seen so far. In pseudocode:
>
> if (penalty < bestpenalty)
> bestpenalty = penalty, selected = i, nmatches = 1;
> else if (penalty == bestpenalty)
> if (random(++nmatches) == 0)
> selected = i;
>
> After a full scan, this produces the same random choice among locations
> with the true minimum penalty as collecting those locations in an array
> and choosing an element at the end, without storing the array.
I see, but it will also require more calls of random number generation,
and it's not obvious to me that this would have less overhead. Let me
experiment with this part, but otherwise I assume you find the patch
idea sound?
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Randomize B-Tree page split location to avoid oscillating patterns
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-06 17:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-05-06 17:49 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-07 18:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-06-16 10:13 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-24 11:22 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andrey Borodin <x4mmm@yandex-team.ru>
2026-08-24 20:03 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-25 11:27 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andrey Borodin <x4mmm@yandex-team.ru>
2026-08-28 20:39 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
@ 2026-08-29 17:37 ` Andrey Borodin <x4mmm@yandex-team.ru>
2026-08-29 17:57 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
0 siblings, 1 reply; 13+ messages in thread
From: Andrey Borodin @ 2026-08-29 17:37 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: Peter Geoghegan <pg@bowt.ie>; pgsql-hackers; Andres Freund <andres@anarazel.de>
Hi Dmitry,
> I see, but it will also require more calls of random number generation,
> and it's not obvious to me that this would have less overhead.
Right. Reservoir sampling avoids the candidate array, but does not
necessarily use less CPU. My guess is that a xoroshiro128** call is cheaper
than another _bt_split_penalty() calculation, although the difference is
probably too small to matter here. Keeping the array is also fine once the
whole interval is examined and the candidates are reset whenever a lower
penalty is found.
> Let me experiment with this part, but otherwise I assume you find the
> patch idea sound?
Yes. The idea makes sense to me in general, with the initial scope restricted
to SPLIT_DEFAULT leaf splits. Picking randomly only among locations with the
true minimum penalty preserves the existing suffix-truncation criterion,
while the existing balance interval keeps every candidate reasonably close
to the target occupancy.
I would leave SPLIT_MANY_DUPLICATES and internal pages unchanged until we
have evidence that randomization helps them without weakening their current
policies. I think the important cost here is not a few random calls or a
short second pass, but additional complexity in nbtree, which already has
many interacting policies. From a large set of small possible improvements,
we should prefer a small set that are simple and orthogonal, particularly to
avoid bugs where their policies interact. So I would choose whichever
implementation keeps both this patch and its interaction with the existing
strategies simplest. The remaining question for the initial patch is
empirical. Randomization deliberately lets some pages reach their next split
earlier, spreading that work over time. The reduction in tail latency should
be statistically significant, while the resulting reduction in average page
occupancy should be statistically insignificant. The idea makes sense to me.
Best regards, Andrey Borodin.
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Randomize B-Tree page split location to avoid oscillating patterns
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-06 17:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-05-06 17:49 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Peter Geoghegan <pg@bowt.ie>
2026-05-07 18:10 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-06-16 10:13 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-24 11:22 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andrey Borodin <x4mmm@yandex-team.ru>
2026-08-24 20:03 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-25 11:27 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andrey Borodin <x4mmm@yandex-team.ru>
2026-08-28 20:39 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-29 17:37 ` Re: Randomize B-Tree page split location to avoid oscillating patterns Andrey Borodin <x4mmm@yandex-team.ru>
@ 2026-08-29 17:57 ` Peter Geoghegan <pg@bowt.ie>
0 siblings, 0 replies; 13+ messages in thread
From: Peter Geoghegan @ 2026-08-29 17:57 UTC (permalink / raw)
To: Andrey Borodin <x4mmm@yandex-team.ru>; +Cc: Dmitry Dolgov <9erthalion6@gmail.com>; pgsql-hackers; Andres Freund <andres@anarazel.de>
On Sat, Aug 29, 2026 at 1:38 PM Andrey Borodin <x4mmm@yandex-team.ru> wrote:
> Yes. The idea makes sense to me in general, with the initial scope restricted
> to SPLIT_DEFAULT leaf splits. Picking randomly only among locations with the
> true minimum penalty preserves the existing suffix-truncation criterion,
> while the existing balance interval keeps every candidate reasonably close
> to the target occupancy.
+1
> I would leave SPLIT_MANY_DUPLICATES and internal pages unchanged until we
> have evidence that randomization helps them without weakening their current
> policies.
+1. I doubt that SPLIT_MANY_DUPLICATES is a good candidate for any
kind of randomized choice. It's only used when we have no choice but
to accept a lopsided split to keep a large group of duplicates
together on the same leaf page. Using an *even more* lopsided split
point is very risky because there's no reason to believe we'll
converge on fillfactor% utilization over time.
> The remaining question for the initial patch is
> empirical. Randomization deliberately lets some pages reach their next split
> earlier, spreading that work over time. The reduction in tail latency should
> be statistically significant, while the resulting reduction in average page
> occupancy should be statistically insignificant. The idea makes sense to me.
When I developed the parts of nbtsplitloc.c that deal with suffix
truncation (including the related handling of large groups of
duplicates), I found it useful to mostly ignore fixed CPU costs
earlier on. It was more important to develop the right general
approach, based on a set of realistic-ish benchmarks. The test results
were perfectly deterministic, and I only cared about space
utilization, so iterating was fairly easy. I was able to deal with
added fixed costs later on (actually, I don't think that they were
ever really a problem).
My guess is that a similar approach will work best here. The only
notable difference is that the primary goal here is to make the rate
of page splits steady over time (where the unit of time is each
inserted tuple). Space utilization will still matter, and it is
something to keep an eye on early, but only to avoid regressions;
there's no reason to expect it to improve.
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 13+ messages in thread
end of thread, other threads:[~2026-08-29 17:57 UTC | newest]
Thread overview: 13+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-04-27 16:24 Randomize B-Tree page split location to avoid oscillating patterns Dmitry Dolgov <9erthalion6@gmail.com>
2026-04-27 18:07 ` Peter Geoghegan <pg@bowt.ie>
2026-04-27 19:49 ` Andres Freund <andres@anarazel.de>
2026-05-06 17:10 ` Dmitry Dolgov <9erthalion6@gmail.com>
2026-05-06 17:49 ` Peter Geoghegan <pg@bowt.ie>
2026-05-07 18:10 ` Dmitry Dolgov <9erthalion6@gmail.com>
2026-06-16 10:13 ` Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-24 11:22 ` Andrey Borodin <x4mmm@yandex-team.ru>
2026-08-24 20:03 ` Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-25 11:27 ` Andrey Borodin <x4mmm@yandex-team.ru>
2026-08-28 20:39 ` Dmitry Dolgov <9erthalion6@gmail.com>
2026-08-29 17:37 ` Andrey Borodin <x4mmm@yandex-team.ru>
2026-08-29 17:57 ` Peter Geoghegan <pg@bowt.ie>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox