agora inbox for pgsql-hackers@postgresql.org
help / color / mirror / Atom feedFrom: Dmitry Dolgov <9erthalion6@gmail.com>
To: pgsql-hackers@postgresql.org
Subject: Randomize B-Tree page split location to avoid oscillating patterns
Date: Mon, 27 Apr 2026 18:24:13 +0200
Message-ID: <d6do2mtjcsagn37jf6pjywzhlzyokqja6jlnvcs4ypkvnnuu32@llwuuyxxomc3> (raw)
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
view thread (13+ messages) latest in thread
Message-ID: <d6do2mtjcsagn37jf6pjywzhlzyokqja6jlnvcs4ypkvnnuu32@llwuuyxxomc3>
Permalink: ../d6do2mtjcsagn37jf6pjywzhlzyokqja6jlnvcs4ypkvnnuu32@llwuuyxxomc3/
Also on: postgresql.org/message-id/d6do2mtjcsagn37jf6pjywzhlzyokqja6jlnvcs4ypkvnnuu32@llwuuyxxomc3
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: 9erthalion6@gmail.com
Subject: Re: Randomize B-Tree page split location to avoid oscillating patterns
In-Reply-To: <d6do2mtjcsagn37jf6pjywzhlzyokqja6jlnvcs4ypkvnnuu32@llwuuyxxomc3>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox