Re: Faster inserts with mostly-monotonically increasing values

On 31 December 2017 at 11:06, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> On Sun, Dec 31, 2017 at 6:44 AM, Pavan Deolasee
> <pavan(dot)deolasee(at)gmail(dot)com> wrote:
>> Here is a patch that implements the idea. If the last insert happens to be
>> in the rightmost block of an index, then we cache the block and check that
>> first for the next insert. For the cached block to be usable for the insert,
>> it should still be the rightmost, the to-be-inserted key should go into the
>> cached block and there is enough free space in the block. If any of these
>> conditions do not meet, we fall back to the regular code path, i.e. descent
>> down the index from the top.
>
> I'd be particularly concerned about page deletion/page recycling still
> being correct with the patch, especially because it's hard to test
> anything there. The P_ISLEAF() part of your fastpath's test hints at
> this -- why should it not *always* be a leaf page (surely you should
> be sure that the page cannot be recycled anyway)?

I don't see any issues related to these points.

We wouldn't be inserting into a deleted/recycled page, so no issues to
discuss. We're not allocating a new page, so no recycling issues.

The block is tested for whether it is an incomplete split and also
locked, so it cannot split while locked.

> I also have my
> doubts about unique index enforcement remaining correct with the patch
> when there are many physical duplicates, to the extent that more than
> a single leaf page is needed for a single value.

This isn't a problem either.

The patch only uses the cache when the value is higher than the
rightmost value. So by definition there are no duplicates in that
case.

Page splitting preserves the ordering property, so we are certain that
the rightmost block has the highest value.

We do need to check that the index is sorted ASC rather than DESC,
possibly with special action for NULL sorting.

> Maybe you should do something with page LSN here -- cache LSN
> alongside block number, and have a non-matching LSN invalidate the
> test.

Don't think we need that.

> How many clients are involved with your benchmark?

Just one, since it is demonstrating the reduced path lenth of doing that.

>> So as the size of the index increases, the benefits of the patch also tend
>> to increase. This is most likely because as the index becomes taller and
>> taller, the costs associated with index descent becomes higher.
>
> FWIW, I think that int4 indexes have to be extremely large before they
> exceed 4 levels (where the leaf level counts as a level). My
> conservative back-of-an-envelope estimate is 9 billion index tuples.

If they did, the gains would be even bigger.

But as you say, a unique index with many duplicates could be a
problem, and index fragmentation would make the situation worse.

--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services