public inbox for [email protected]
help / color / mirror / Atom feedFrom: Matthias van de Meent <[email protected]>
To: Peter Geoghegan <[email protected]>
Cc: vignesh C <[email protected]>
Cc: PostgreSQL Hackers <[email protected]>
Cc: Dilip Kumar <[email protected]>
Cc: David Christensen <[email protected]>
Subject: Re: btree: downlink right separator/HIKEY optimization
Date: Mon, 11 Mar 2024 19:35:02 +0100
Message-ID: <CAEze2WgF+2yW1f+POrYLCWpTfOEgb28zEQX6tFPUPOziJ2tYmA@mail.gmail.com> (raw)
In-Reply-To: <CAH2-WzkooESsOa8DKXkuYR-wuj2hcvcN5VrCCkNzSuXwM6WDFA@mail.gmail.com>
References: <CAEze2Wh9b9iu0APbrpAcBFuVSfcAzgO665cObS+WZgn3tWD5VA@mail.gmail.com>
<CAEze2WijWhCQy_nZVP4Ye5Hwj=YW=3rqv+hbMJGcOHtrYQmyKw@mail.gmail.com>
<CALDaNm00LKEnFHUoRs5c1GVT6N1jL5x6LdKzvRQwC0368+wx=A@mail.gmail.com>
<CAEze2Wi8msRiSxNYoqejQKk_SBacsa3Z3GEtBAwS-A4+qJ7d9g@mail.gmail.com>
<CAH2-WzkooESsOa8DKXkuYR-wuj2hcvcN5VrCCkNzSuXwM6WDFA@mail.gmail.com>
On Fri, 8 Mar 2024 at 20:14, Peter Geoghegan <[email protected]> wrote:
>
> On Thu, Feb 22, 2024 at 10:42 AM Matthias van de Meent
> <[email protected]> wrote:
> > I forgot to address this in the previous patch, so here's v3 which
> > fixes the issue warning.
>
> What benchmarking have you done here?
I have benchmarked this atop various versions of master when it was
part of the btree specialization patchset, where it showed a 2-9%
increase in btree insert performance over the previous patch in the
patchset on the various index types in that set.
More recently, on an unlogged pgbench with foreign keys enabled (-s400
-j4 -c8) I can't find any obvious regressions (it gains 0-0.7% on
master across 5-minute runs), while being 4.5% faster on inserting
data on a table with an excessively bad index shape (single index of
10 columns of empty strings with the non-default "nl-BE-x-icu"
collation followed by 1 random uuid column, inserted from a 10M row
dataset. Extrapolation indicates this could indeed get over 7%
improvement when the index shape is 31 nondefault -collated nonnull
text columns and a single random ID index column).
> Have you tried just reordering things in _bt_search() instead? If we
> delay the check until after the binary search, then the result of the
> binary search is usually proof enough that we cannot possibly need to
> move right. That has the advantage of not requiring that we copy
> anything to the stack.
I've not tried that, because it would makes page-level prefix
truncation more expensive by ~50%: With this patch, we need only 2
full tuple _bt_compares per page before we can establish a prefix,
while without this patch (i.e. if we did a binsrch-first approach)
we'd need 3 on average (assuming linearly randomly distributed
accesses). Because full-key compares can be arbitrarily more expensive
than normal attribute compares, I'd rather not have that 50% overhead.
> > On Fri, Mar 8, 2024 at 2:14 PM Peter Geoghegan <[email protected]> wrote:
> > What benchmarking have you done here?
> I think that the memcmp() test is subtly wrong:
Good catch, it's been fixed in the attached version, using a new function.
Kind regards,
Matthias van de Meent.
Attachments:
[application/octet-stream] v3-0001-btree-optimize-_bt_moveright-using-downlink-s-rig.patch (8.7K, ../CAEze2WgF+2yW1f+POrYLCWpTfOEgb28zEQX6tFPUPOziJ2tYmA@mail.gmail.com/2-v3-0001-btree-optimize-_bt_moveright-using-downlink-s-rig.patch)
download | inline diff:
From e23e25c294d43679684919326f2ed3bc13f76b34 Mon Sep 17 00:00:00 2001
From: Matthias van de Meent <[email protected]>
Date: Sun, 29 Oct 2023 21:39:23 +0100
Subject: [PATCH v3] btree: optimize _bt_moveright using downlink's right
separator
Due to the inner workings of the btree, it is extremely likely that the
right separator of the btree page's downlink on the parent page matches
the downlinked page's HIKEY: Only when the page was split after we
accessed its parent page (and this split wasn't completed yet) the HIKEY
will not match.
So, instead of doing _bt_compare in _bt_moveright, we can store the
right separator key of the downlink, and check if it matches the HIKEY of
the linked page. If they match, we don't have to call the relatively
expensive _bt_compare, which allows us to reuse the _bt_compare result of
the right separator key.
This reduces the number of all-attribute _bt_compare operations
we need to do on a page by 1 flat, thus increasing performance
of indexes that have expensive compare operations.
In passing, move the declaration of _bt_moveright into nbtsearch.c - I
found no user of the function anywhere but in nbtsearch.c.
---
src/backend/access/nbtree/README | 20 +++++++
src/backend/access/nbtree/nbtsearch.c | 82 +++++++++++++++++++++++++--
src/include/access/nbtree.h | 3 -
3 files changed, 98 insertions(+), 7 deletions(-)
diff --git a/src/backend/access/nbtree/README b/src/backend/access/nbtree/README
index 52e646c7f7..c75793da5a 100644
--- a/src/backend/access/nbtree/README
+++ b/src/backend/access/nbtree/README
@@ -901,6 +901,26 @@ large groups of duplicates, maximizing space utilization. Note also that
deduplication more efficient. Deduplication can be performed infrequently,
without merging together existing posting list tuples too often.
+Notes about the right separator/HIKEY moveright optimization
+------------------------------------------------------------
+
+Page splits consistently cause the HIKEY of the split page to be inserted
+into the parent page as the right separator of the page's downlink (or,
+as the split page's new right sibling's left link), with the only
+difference between the HIKEY and the separator being the contents of the
+IndexTupleData struct of these tuples: the payloads are bit-identical.
+This allows us to reuse the _bt_compare result of the right separator key
+for the downlinked page's HIKEY, if we can determine that those are indeed
+bit-identical: Concurrent page splits and deletions may have caused the
+downlinked page to get a different HIKEY, which could have a different
+_bt_compare result. To make this work, in _bt_search we cache the
+current downlink's right separator key, to then in the _bt_moveright
+phase of the layer below use memcmp() to validate our assumptions about
+the HIKEY matching the downlink's right separator key. Only if the
+assumption is proven wrong (memcmp(HIKEY, right_sep) != 0), we call
+_bt_compare(), otherwise we can be certain that the parent page's result
+is unchanged, i.e. that _bt_compare would return "<".
+
Notes about deduplication
-------------------------
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 63ee9ba225..e0979f0c81 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -27,6 +27,9 @@
static void _bt_drop_lock_and_maybe_pin(IndexScanDesc scan, BTScanPos sp);
static OffsetNumber _bt_binsrch(Relation rel, BTScanInsert key, Buffer buf);
+static Buffer _bt_moveright(Relation rel, Relation heaprel, BTScanInsert key,
+ Buffer buf, bool forupdate, BTStack stack,
+ int access, IndexTuple rightsep);
static int _bt_binsrch_posting(BTScanInsert key, Page page,
OffsetNumber offnum);
static bool _bt_readpage(IndexScanDesc scan, ScanDirection dir,
@@ -47,6 +50,28 @@ static Buffer _bt_walk_left(Relation rel, Buffer buf);
static bool _bt_endpoint(IndexScanDesc scan, ScanDirection dir);
static inline void _bt_initialize_more_data(BTScanOpaque so, ScanDirection dir);
+static inline bool
+BTreeTupleDownlinkMatchesHikey(IndexTuple highkey, IndexTuple rightsep)
+{
+ int16 size = IndexTupleSize(highkey);
+ int alt_tid;
+
+ if (size != IndexTupleSize(rightsep))
+ return false;
+
+ alt_tid = highkey->t_info & INDEX_ALT_TID_MASK;
+ if (alt_tid != (rightsep->t_info & INDEX_ALT_TID_MASK))
+ return false;
+
+ if (alt_tid && (ItemPointerGetOffsetNumberNoCheck(&highkey->t_tid) !=
+ ItemPointerGetOffsetNumberNoCheck(&rightsep->t_tid)))
+ return false;
+
+ if (memcmp(highkey + 1, rightsep + 1, size - sizeof(IndexTupleData)) != 0)
+ return false;
+
+ return true;
+}
/*
* _bt_drop_lock_and_maybe_pin()
@@ -98,6 +123,15 @@ _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP,
{
BTStack stack_in = NULL;
int page_access = BT_READ;
+ union {
+#if defined(pg_attribute_aligned)
+ pg_attribute_aligned(MAXIMUM_ALIGNOF)
+#endif
+ char data[MAXALIGN_DOWN(BLCKSZ / 3)];
+ IndexTupleData tuple;
+ double force_align_d;
+ } rsepbuf;
+ IndexTuple rightsep = NULL;
/* heaprel must be set whenever _bt_allocbuf is reachable */
Assert(access == BT_READ || access == BT_WRITE);
@@ -134,7 +168,7 @@ _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP,
* opportunity to finish splits of internal pages too.
*/
*bufP = _bt_moveright(rel, heaprel, key, *bufP, (access == BT_WRITE),
- stack_in, page_access);
+ stack_in, page_access, rightsep);
/* if this is a leaf page, we're done */
page = BufferGetPage(*bufP);
@@ -152,6 +186,25 @@ _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP,
Assert(BTreeTupleIsPivot(itup) || !key->heapkeyspace);
child = BTreeTupleGetDownLink(itup);
+ if (offnum < PageGetMaxOffsetNumber(page))
+ {
+ ItemId rightsepitem = PageGetItemId(page, offnum + 1);
+ IndexTuple pagerightsep = (IndexTuple) PageGetItem(page, rightsepitem);
+ memcpy(rsepbuf.data, pagerightsep, ItemIdGetLength(rightsepitem));
+ rightsep = &rsepbuf.tuple;
+ }
+ else if (!P_RIGHTMOST(opaque))
+ {
+ /*
+ * The rightmost data tuple on inner page has P_HIKEY as its right
+ * separator.
+ */
+ ItemId rightsepitem = PageGetItemId(page, P_HIKEY);
+ IndexTuple pagerightsep = (IndexTuple) PageGetItem(page, rightsepitem);
+ memcpy(rsepbuf.data, pagerightsep, ItemIdGetLength(rightsepitem));
+ rightsep = &rsepbuf.tuple;
+ }
+
/*
* We need to save the location of the pivot tuple we chose in a new
* stack entry for this page/level. If caller ends up splitting a
@@ -194,7 +247,8 @@ _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP,
* but before we acquired a write lock. If it has, we may need to
* move right to its new sibling. Do that.
*/
- *bufP = _bt_moveright(rel, heaprel, key, *bufP, true, stack_in, BT_WRITE);
+ *bufP = _bt_moveright(rel, heaprel, key, *bufP, true, stack_in, BT_WRITE,
+ rightsep);
}
return stack_in;
@@ -238,7 +292,8 @@ _bt_moveright(Relation rel,
Buffer buf,
bool forupdate,
BTStack stack,
- int access)
+ int access,
+ IndexTuple rightsep)
{
Page page;
BTPageOpaque opaque;
@@ -297,7 +352,26 @@ _bt_moveright(Relation rel,
continue;
}
- if (P_IGNORE(opaque) || _bt_compare(rel, key, page, P_HIKEY) >= cmpval)
+ if (P_IGNORE(opaque))
+ {
+ buf = _bt_relandgetbuf(rel, buf, opaque->btpo_next, access);
+ continue;
+ }
+
+ if (PointerIsValid(rightsep))
+ {
+ /*
+ * Note: we're not in the rightmost page (see branchpoint earlier in
+ * the loop), so we always have a HIKEY on this page.
+ */
+ ItemId hikeyid = PageGetItemId(page, P_HIKEY);
+ IndexTuple highkey = (IndexTuple) PageGetItem(page, hikeyid);
+
+ if (BTreeTupleDownlinkMatchesHikey(highkey, rightsep))
+ break;
+ }
+
+ if (_bt_compare(rel, key, page, P_HIKEY) >= cmpval)
{
/* step right one page */
buf = _bt_relandgetbuf(rel, buf, opaque->btpo_next, access);
diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 6eb162052e..de524ed188 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -1229,9 +1229,6 @@ extern void _bt_pendingfsm_finalize(Relation rel, BTVacState *vstate);
*/
extern BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key,
Buffer *bufP, int access);
-extern Buffer _bt_moveright(Relation rel, Relation heaprel, BTScanInsert key,
- Buffer buf, bool forupdate, BTStack stack,
- int access);
extern OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate);
extern int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum);
extern bool _bt_first(IndexScanDesc scan, ScanDirection dir);
--
2.40.1
view thread (4+ messages)
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: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: btree: downlink right separator/HIKEY optimization
In-Reply-To: <CAEze2WgF+2yW1f+POrYLCWpTfOEgb28zEQX6tFPUPOziJ2tYmA@mail.gmail.com>
* 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