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

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?

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company