On Thu, Aug 18, 2016 at 6:04 PM, Kevin Grittner <kgri...@gmail.com> wrote: > On Thu, Aug 18, 2016 at 3:41 PM, Claudio Freire <klaussfre...@gmail.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. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
