agora inbox for pgsql-hackers@postgresql.org
help / color / mirror / Atom feedFrom: Dmitry Dolgov <9erthalion6@gmail.com>
To: Peter Geoghegan <pg@bowt.ie>
Cc: pgsql-hackers@postgresql.org
Subject: Re: Randomize B-Tree page split location to avoid oscillating patterns
Date: Tue, 16 Jun 2026 12:13:47 +0200
Message-ID: <jotfal6422zpqvux4add7xcyftaujjiksscfcc5uuibaldw4sv@pzriktpx4gyl> (raw)
In-Reply-To: <noovhlxtwa64do7isbbvl2f6clqukujb7hexw3zi2rn3ssbmrw@3yvb4ghojg4b>
References: <d6do2mtjcsagn37jf6pjywzhlzyokqja6jlnvcs4ypkvnnuu32@llwuuyxxomc3>
<CAH2-Wz=Sy7=kAHrtNrDSoo+vj_QYAmNc8_GEYPh6r+0r-BbQ5w@mail.gmail.com>
<uqcsdatuokodytg7dcan75hbutv4erwdmzqaxjwhakmvfhy7vf@fxlpamb3opzr>
<CAH2-WznzR_q9Q+5kZ8xbjaqt0c0LmXnv_wqQfzOX-g5cVgZYbg@mail.gmail.com>
<noovhlxtwa64do7isbbvl2f6clqukujb7hexw3zi2rn3ssbmrw@3yvb4ghojg4b>
> 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
view thread (13+ messages) latest in thread
Message-ID: <jotfal6422zpqvux4add7xcyftaujjiksscfcc5uuibaldw4sv@pzriktpx4gyl>
Permalink: ../jotfal6422zpqvux4add7xcyftaujjiksscfcc5uuibaldw4sv@pzriktpx4gyl/
Also on: postgresql.org/message-id/jotfal6422zpqvux4add7xcyftaujjiksscfcc5uuibaldw4sv@pzriktpx4gyl
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, pg@bowt.ie
Subject: Re: Randomize B-Tree page split location to avoid oscillating patterns
In-Reply-To: <jotfal6422zpqvux4add7xcyftaujjiksscfcc5uuibaldw4sv@pzriktpx4gyl>
* 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