pgsql: Optimize btree insertions for common case of increasing values

Optimize btree insertions for common case of increasing values

Remember the last page of an index insert if it's the rightmost leaf
page. If the next entry belongs on and can fit in the remembered page,
insert the new entry there as long as we can get a lock on the page.
Otherwise, fall back on the more expensive method of searching for
the right place to insert the entry.

This provides a performance improvement for the common case where an
index entry is for monotonically increasing or nearly monotonically
increasing value such as an identity field or a current timestamp.

Pavan Deolasee
Reviewed by Claudio Freire, Simon Riggs and Peter Geoghegan

Discussion: https://postgr.es/m/CABOikdM9DrupjyKZZFM5k8-0RCDs1wk6JzEkg7UgSW6QzOwMZw@mail.gmail.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/2b27273435392d1606f0ffc95d73a439a457f08e

Modified Files
--------------
src/backend/access/nbtree/nbtinsert.c | 138 +++++++++++++++---
src/test/regress/expected/indexing.out | 249 +++++++++++++++++++++++++++++++++
src/test/regress/sql/indexing.sql | 116 +++++++++++++++
3 files changed, 484 insertions(+), 19 deletions(-)