Re: Reviewing new index types (was Re: [PATCHES] Updated bitmap indexpatch)

Tom Lane wrote:
> "Simon Riggs" <simon(at)2ndquadrant(dot)com> writes:
>> ... BMI is not useful at all
>> for PKs, whilst GIT is specifically designed to handle them.
>
> This seems a strange statement, because GIT doesn't look particularly
> efficient for unique indexes AFAICS. In the worst case you'd have to
> look individually at each tuple on a heap page to check for uniqueness
> conflict (no binary search, because you couldn't assume they are
> ordered).

It handles them in the sense that a clustered PK index is way smaller
than a normal PK index. Unlike the bitmap index, which is not suitable
for highly distinct columns.

Inserting and performing a uniqueness check is more expensive on a
clustered index, because as you said it needs to scan the heap page
looking for conflicts. It's alleviated by the heuristics Simon
mentioned; a page is "groupified" when only when it gets full, which
means there'll usually be a mixture of normal and groupified tuples on a
leaf page. In particular, if there's hot key values that are repeatedly
inserted, the index tuples corresponding those key values are likely to
stay as normal index tuples, and are therefore cheaper to check
uniqueness against.

Also IIRC, the patch tries to keep the last index tuple on a page as a
normal index tuple, which catches the important special case of
inserting monotonically increasing keys, like with a sequence-generated PK.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com