Reverse order of newitem nbtree candidate splits

Enterprise / PostgreSQL - Peter Geoghegan [bowt.ie] - 15 May 2019 19:22 EDT

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.

7505da2f45 Reverse order of newitem nbtree candidate splits.
src/backend/access/nbtree/nbtsplitloc.c | 37 ++++++++++++++++++++-------------
1 file changed, 22 insertions(+), 15 deletions(-)

Upstream: git.postgresql.org


  • Share