public inbox for [email protected]
help / color / mirror / Atom feedFrom: Heikki Linnakangas <[email protected]>
To: Matthias van de Meent <[email protected]>
To: PostgreSQL Hackers <[email protected]>
To: Peter Geoghegan <[email protected]>
To: Dilip Kumar <[email protected]>
To: David Christensen <[email protected]>
Subject: Re: btree: downlink right separator/HIKEY optimization
Date: Tue, 5 Dec 2023 09:43:20 +0200
Message-ID: <[email protected]> (raw)
In-Reply-To: <CAEze2WijWhCQy_nZVP4Ye5Hwj=YW=3rqv+hbMJGcOHtrYQmyKw@mail.gmail.com>
References: <CAEze2Wh9b9iu0APbrpAcBFuVSfcAzgO665cObS+WZgn3tWD5VA@mail.gmail.com>
<CAEze2WijWhCQy_nZVP4Ye5Hwj=YW=3rqv+hbMJGcOHtrYQmyKw@mail.gmail.com>
On 01/11/2023 00:08, Matthias van de Meent wrote:
> calling _bt_compare in _bt_moveright in many common cases. This patch,
> when stacked on top of the prefix truncation patch, improves INSERT
> performance by an additional 2-9%pt, with an extreme case of 45% in
> the worscase index tests at [0].
>
> The optimization is that we now recognze that our page split algorithm
> all but guarantees that the HIKEY matches this page's downlink's right
> separator key bytewise, excluding the data stored in the
> IndexTupleData struct.
Good observation.
> By caching the right separator index tuple in _bt_search, we can
> compare the downlink's right separator and the HIKEY, and when they
> are equal (memcmp() == 0) we don't have to call _bt_compare - the
> HIKEY is known to be larger than the scan key, because our key is
> smaller than the right separator, and thus transitively also smaller
> than the HIKEY because it contains the same data. As _bt_compare can
> call expensive user-provided functions, this can be a large
> performance boon, especially when there are only a small number of
> column getting compared on each page (e.g. index tuples of many 100s
> of bytes, or dynamic prefix truncation is enabled).
What would be the worst case scenario for this? One situation where the
memcmp() would not match is when there is a concurrent page split. I
think it's OK to pessimize that case. Are there any other situations?
When the memcmp() matches, I think this is almost certainly not slower
than calling the datatype's comparison function.
> 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;
> }
This could use a one-line comment above this, something like "Remember
the right separator of the downlink we follow, to speed up the next
_bt_moveright call".
Should there be an "else rightsep = NULL;" here? Is it possible that we
follow the non-rightmost downlink on a higher level and rightmost
downlink on next level? Concurrent page deletion?
Please update the comment above _bt_moveright to describe the new
argument. Perhaps the text from README should go there, this feels like
a detail specific to _bt_search and _bt_moveright.
--
Heikki Linnakangas
Neon (https://neon.tech)
view thread (5+ messages) latest in thread
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: <[email protected]>
* 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