• Peter Geoghegan's avatar
    Reverse order of newitem nbtree candidate splits. · 7505da2f
    Peter Geoghegan authored
    Commit fab25024, which taught nbtree to choose candidate split points
    more carefully, had _bt_findsplitloc() record all possible split points
    in an initial pass over a page that is about to be split.  The order
    that candidate split points were processed and stored in was assumed to
    match the offset number order of split points on an imaginary version of
    the page that contains the same items as the original, but also fits
    newitem (the item that provoked the split precisely because it didn't
    fit).
    
    However, the order of split points in the final array was not quite what
    was expected: the split point that makes newitem the firstright item
    came after the split point that makes newitem the lastleft item -- not
    before.  As a result, _bt_findsplitloc() could get confused about the
    leftmost and rightmost tuples among all possible split points recorded
    for the page.  This seems to have no appreciable impact on the quality
    of the final split point chosen by _bt_findsplitloc(), but it's still
    wrong.
    
    To fix, switch the order in which newitem candidate splits are recorded
    in.  This also makes it possible to describe candidate split points in
    terms of which pair of adjoining tuples enclose the split point within
    _bt_findsplitloc(), making it clearer why it's generally safe for
    _bt_split() to expect lastleft and firstright tuples.
    7505da2f
nbtsplitloc.c 36.2 KB