Re: [WIP] [B-Tree] Keep indexes sorted by heap physical location

Claudio Freire <klaussfreire(at)gmail(dot)com> writes:
> On Thu, Aug 18, 2016 at 6:04 PM, Kevin Grittner <kgrittn(at)gmail(dot)com> wrote:
>> Speaking of performance side effects, does this avoid O(N^2)
>> performance on index tuple insertion with duplicate values, for all
>> insertion orderings? For example, does it descend directly to the
>> right leaf page for the insert rather than starting at the front of
>> the block of duplicate values and scanning to the right for a
>> block with space, with a random chance to split a full block on
>> each page it moves through?

> Yes, but only on non-unique indexes.

How's that work if the existing entries aren't in TID order (which they
will not be, in a pre-existing index)? Or are you assuming you can blow
off on-disk compatibility of indexes?

regards, tom lane