Re: Faster inserts with mostly-monotonically increasing values

Moin,

On Tue, January 2, 2018 7:51 am, Pavan Deolasee wrote:
> On Sun, Dec 31, 2017 at 4:36 PM, Peter Geoghegan <pg@bowt.ie> wrote:
>
>> On Sun, Dec 31, 2017 at 6:44 AM, Pavan Deolasee
>> <pavan.deolasee@gmail.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.
[snip]

>> > 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.
>>
>>
> Hmm Ok. I am not entirely sure whether it's the depth or just purely
> binary
> searching through 3-4 index pages and/or pinning/unpinning buffers result
> in much overhead. I will run some more tests and collect evidences.

Just a question trying to understand how btree indexes work:

If one inserts ever-increasing value, is the tree a balanced tree with a
minimum (or at least not-as-high) number of levels, or does it increase in
height every insert and creates a "tall stack"?

@Peter: Could you please share your back-of-the-envelope calculation, I'd
love to get some insights into the innards.

All the best,

Tels