Re: [HACKERS] Dead code in _bt_split?

This piece of code in _bt_split, starting at line 859, looks curious to me:

> /* cope with possibility that newitem goes at the end */
> if (i <= newitemoff)
> {
> if (newitemonleft)
> {
> _bt_pgaddtup(rel, leftpage, newitemsz, newitem, leftoff,
> "left sibling");
> itup_off = leftoff;
> itup_blkno = BufferGetBlockNumber(buf);
> leftoff = OffsetNumberNext(leftoff);
> }
> else
> {
> _bt_pgaddtup(rel, rightpage, newitemsz, newitem, rightoff,
> "right sibling");
> itup_off = rightoff;
> itup_blkno = BufferGetBlockNumber(rbuf);
> rightoff = OffsetNumberNext(rightoff);
> }
> }

This is right after a for-loop, which exits when i = maxoff + 1. So the
first if-statement could be written as "if (newitemoff > maxoff)". If
that's true, newitemonleft shouldn't be true, because that would mean
that we've split a page so that all items went to the left page, and the
right page is empty.

Is that really dead code, or am I missing something? How about putting
an Assert in there instead?

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

"Heikki Linnakangas" <heikki(at)enterprisedb(dot)com> writes:
> This is right after a for-loop, which exits when i = maxoff + 1. So the
> first if-statement could be written as "if (newitemoff > maxoff)". If
> that's true, newitemonleft shouldn't be true, because that would mean
> that we've split a page so that all items went to the left page, and the
> right page is empty.

No, it would mean that we split the page in such a way that only the new
item is going to the right page. Probably not hard to duplicate if you
use near-maximal-sized keys.

regards, tom lane

Tom Lane wrote:
> "Heikki Linnakangas" <heikki(at)enterprisedb(dot)com> writes:
>> This is right after a for-loop, which exits when i = maxoff + 1. So the
>> first if-statement could be written as "if (newitemoff > maxoff)". If
>> that's true, newitemonleft shouldn't be true, because that would mean
>> that we've split a page so that all items went to the left page, and the
>> right page is empty.
>
> No, it would mean that we split the page in such a way that only the new
> item is going to the right page. Probably not hard to duplicate if you
> use near-maximal-sized keys.

In that case, newitemleft would be false, right?

I'm saying the piece marked with X> below is unreachable:

> /* cope with possibility that newitem goes at the end */
> if (i <= newitemoff)
> {
> if (newitemonleft)
> {
X> _bt_pgaddtup(rel, leftpage, newitemsz, newitem, leftoff,
X> "left sibling");
X> itup_off = leftoff;
X> itup_blkno = BufferGetBlockNumber(buf);
X> leftoff = OffsetNumberNext(leftoff);
> }
> else
> {
> _bt_pgaddtup(rel, rightpage, newitemsz, newitem, rightoff,
> "right sibling");
> itup_off = rightoff;
> itup_blkno = BufferGetBlockNumber(rbuf);
> rightoff = OffsetNumberNext(rightoff);
> }
> }

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
> In that case, newitemleft would be false, right?
> I'm saying the piece marked with X> below is unreachable:

Oh, I see. Hmm ... probably so, I think that chunk of code was just
copied and pasted from where it occurs within the loop.

regards, tom lane

Heikki, did this code cleanup get included in your recent btree split
fix?

---------------------------------------------------------------------------

Tom Lane wrote:
> Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
> > In that case, newitemleft would be false, right?
> > I'm saying the piece marked with X> below is unreachable:
>
> Oh, I see. Hmm ... probably so, I think that chunk of code was just
> copied and pasted from where it occurs within the loop.
>
> regards, tom lane
>
> ---------------------------(end of broadcast)---------------------------
> TIP 6: explain analyze is your friend

--
Bruce Momjian bruce(at)momjian(dot)us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Bruce Momjian wrote:
> Heikki, did this code cleanup get included in your recent btree split
> fix?

No.

> ---------------------------------------------------------------------------
>
> Tom Lane wrote:
>> Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
>>> In that case, newitemleft would be false, right?
>>> I'm saying the piece marked with X> below is unreachable:
>> Oh, I see. Hmm ... probably so, I think that chunk of code was just
>> copied and pasted from where it occurs within the loop.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas wrote:
> Bruce Momjian wrote:
> > Heikki, did this code cleanup get included in your recent btree split
> > fix?
>
> No.

OK, would you please send a patch to remove the unused code. Thanks.

--
Bruce Momjian bruce(at)momjian(dot)us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Bruce Momjian wrote:
> Heikki Linnakangas wrote:
>> Bruce Momjian wrote:
>>> Heikki, did this code cleanup get included in your recent btree split
>>> fix?
>> No.
>
> OK, would you please send a patch to remove the unused code. Thanks.

Ok, here you are.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
> Bruce Momjian wrote:
>> OK, would you please send a patch to remove the unused code. Thanks.

> Ok, here you are.

Applied with an added comment and Assert.

While testing it I realized that there seems to be a nearby bug in
_bt_findsplitloc: it fails to consider the possibility of moving all the
extant items to the left side. It will always return a firstright <=
maxoff. ISTM this would mean that it could choose a bad split if the
incoming item goes at the end and both it and the last extant item are
large: in this case they should be split apart, but they won't be.

Heikki, do you feel like looking at that, or shall I?

regards, tom lane

Tom Lane wrote:
> Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
>> Bruce Momjian wrote:
>>> OK, would you please send a patch to remove the unused code. Thanks.
>
>> Ok, here you are.
>
> Applied with an added comment and Assert.
>
> While testing it I realized that there seems to be a nearby bug in
> _bt_findsplitloc: it fails to consider the possibility of moving all the
> extant items to the left side. It will always return a firstright <=
> maxoff. ISTM this would mean that it could choose a bad split if the
> incoming item goes at the end and both it and the last extant item are
> large: in this case they should be split apart, but they won't be.
>
> Heikki, do you feel like looking at that, or shall I?

I'll take a look at it.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Tom Lane wrote:
> While testing it I realized that there seems to be a nearby bug in
> _bt_findsplitloc: it fails to consider the possibility of moving all the
> extant items to the left side. It will always return a firstright <=
> maxoff. ISTM this would mean that it could choose a bad split if the
> incoming item goes at the end and both it and the last extant item are
> large: in this case they should be split apart, but they won't be.
>
> Heikki, do you feel like looking at that, or shall I?

I refactored findsplitloc and checksplitloc so that the division of
labor is more clear IMO. I pushed all the space calculation inside the
loop to checksplitloc.

I also fixed the off by 4 in free space calculation caused by
PageGetFreeSpace subtracting sizeof(ItemIdData), even though it was
harmless, because it was distracting and I felt it might come back to
bite us in the future if we change the page layout or alignments.
There's now a new function PageGetExactFreeSpace that doesn't do the
subtraction.

findsplitloc now tries the "just the new item to right page" split as
well. If people don't like the refactoring, I can write a patch to just
add that.

Some of the long variable names look ugly. camelCase or underscores
between words would be more readable, but I retained the old style for
the sake of consistency.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Your patch has been added to the PostgreSQL unapplied patches list at:

http://momjian.postgresql.org/cgi-bin/pgpatches

It will be applied as soon as one of the PostgreSQL committers reviews
and approves it.

---------------------------------------------------------------------------

Heikki Linnakangas wrote:
> Tom Lane wrote:
> > While testing it I realized that there seems to be a nearby bug in
> > _bt_findsplitloc: it fails to consider the possibility of moving all the
> > extant items to the left side. It will always return a firstright <=
> > maxoff. ISTM this would mean that it could choose a bad split if the
> > incoming item goes at the end and both it and the last extant item are
> > large: in this case they should be split apart, but they won't be.
> >
> > Heikki, do you feel like looking at that, or shall I?
>
> I refactored findsplitloc and checksplitloc so that the division of
> labor is more clear IMO. I pushed all the space calculation inside the
> loop to checksplitloc.
>
> I also fixed the off by 4 in free space calculation caused by
> PageGetFreeSpace subtracting sizeof(ItemIdData), even though it was
> harmless, because it was distracting and I felt it might come back to
> bite us in the future if we change the page layout or alignments.
> There's now a new function PageGetExactFreeSpace that doesn't do the
> subtraction.
>
> findsplitloc now tries the "just the new item to right page" split as
> well. If people don't like the refactoring, I can write a patch to just
> add that.
>
> Some of the long variable names look ugly. camelCase or underscores
> between words would be more readable, but I retained the old style for
> the sake of consistency.
>
> --
> Heikki Linnakangas
> EnterpriseDB http://www.enterprisedb.com

>
> ---------------------------(end of broadcast)---------------------------
> TIP 4: Have you searched our list archives?
>
> http://archives.postgresql.org

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Patch applied. Thanks.

---------------------------------------------------------------------------

Heikki Linnakangas wrote:
> Tom Lane wrote:
> > While testing it I realized that there seems to be a nearby bug in
> > _bt_findsplitloc: it fails to consider the possibility of moving all the
> > extant items to the left side. It will always return a firstright <=
> > maxoff. ISTM this would mean that it could choose a bad split if the
> > incoming item goes at the end and both it and the last extant item are
> > large: in this case they should be split apart, but they won't be.
> >
> > Heikki, do you feel like looking at that, or shall I?
>
> I refactored findsplitloc and checksplitloc so that the division of
> labor is more clear IMO. I pushed all the space calculation inside the
> loop to checksplitloc.
>
> I also fixed the off by 4 in free space calculation caused by
> PageGetFreeSpace subtracting sizeof(ItemIdData), even though it was
> harmless, because it was distracting and I felt it might come back to
> bite us in the future if we change the page layout or alignments.
> There's now a new function PageGetExactFreeSpace that doesn't do the
> subtraction.
>
> findsplitloc now tries the "just the new item to right page" split as
> well. If people don't like the refactoring, I can write a patch to just
> add that.
>
> Some of the long variable names look ugly. camelCase or underscores
> between words would be more readable, but I retained the old style for
> the sake of consistency.
>
> --
> Heikki Linnakangas
> EnterpriseDB http://www.enterprisedb.com

>
> ---------------------------(end of broadcast)---------------------------
> TIP 4: Have you searched our list archives?
>
> http://archives.postgresql.org

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +