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

On Thu, Aug 18, 2016 at 6:04 PM, Kevin Grittner <kgrittn(at)gmail(dot)com> wrote:
> On Thu, Aug 18, 2016 at 3:41 PM, Claudio Freire <klaussfreire(at)gmail(dot)com> wrote:
>
>> It also makes index scans of the form
>>
>> SELECT * FROM t WHERE some_col = some_const;
>>
>> Scan the heap in sequential order, even if some_col has low
>> cardinality (ie: the query returns lots of tuples), which is a nice
>> performance side effect.
>
> 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.

Unique indexes still need to scan all duplicates to check visibility
and will become O(N^2) there.

The code with the random chance to split is still there, but it should
never have a chance to run because the comparison against the heap
tuple pointer would stop it very quickly (before walking a single
offset I believe).

I thought about cleaning that up, but to make review easier I thought
I'd leave it there for now. Removing it would add a lot of diff noise.