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