I'm working on adding support for unique indexes to the hash index code.
The majority of the code is finished, with the exception of the changes
to locking. My proposed changes are below -- if anyone sees a better way
to do things, let me know.

There's lots of info on the locking scheme used by hash indexes in
src/backend/access/hash/README, but I'll present a short summary here.
(I've omitted some unimportant details.) Insertions do the following:

        1. Lookup the bucket in which to store the index item, based on
        its hash (we acquire some locks to ensure the hash-key-to-bucket
        mapping doesn't change under our feet).
        
        2. Acquire a shared lmgr lock on the target bucket, to ensure
        that no one tries to split or compact it while we're looking at
        it.
        
        3. Acquire an exclusive lwlock on the primary bucket page. This
        prevents hash scans from seeing the partially written page.
        
        4. If the primary bucket page has enough free space to fit the
        new index item, insert it and release the lwlock; if not,
        release the lwlock, advance to the next overflow page, and
        repeat. If we're out of overflow pages but haven't found free
        space, create a new overflow page.
        
        5. Release the shared lmgr lock on the target bucket.

Scans use a similar algorithm, with the exception that they need only
acquire a shared lwlock on the bucket's pages.

The additional requirement for unique hash indexes is to be able to
prevent other backends from concurrently inserting a duplicate key into
the target bucket chain.

In order to do this, we could:

- Invent a new set of lmgr locks; call them "right of insertion" locks,
and have one for each bucket in the hash index. Only one backend will
hold the ROI lock for a given bucket at any given time.

- On insertion, grab the ROI lock in exclusive mode for the target
bucket, after we've already done #2. This serializes insertions into the
bucket.

- Index scans don't need to acquire the ROI lock, since they can't
possibly insert a duplicate, and they're already protected from seeing
partially written pages by the lwlocks acquired by the inserting
backend. Similarly, bulk deletions don't need to acquire the ROI lock,
since they already can't proceed in parallel with an insertion on any
given bucket (they acquire #2 in exclusive mode). Insertions on other
buckets in the index can proceed in parallel with one another, since by
definition they couldn't be inserting duplicate tuples.

- naturally, we don't bother with ROI locks if the hash index isn't a
unique index

Q: Is there a possibility of deadlock here? (If not, the ROI lock could
be an lwlock, perhaps.)

Any comments would be welcome.

-Neil

P.S. While we're on the subject on hash indexes and locking, ISTM that
we could get better concurrent performance in #4 by first acquiring the
lwlock on a particular bucket page in shared mode, checking if it has
free space, and only if it does, getting a write lock on it and doing
the insertion. Of course, we'd need to re-check the free space once we
got the write lock, to insure that someone else wasn't granted a write
lock on that page while we were waiting and then decreased the free
space.


Tue, 16 Sep 2003 22:30:22 -0400
Neil Conway <neilc@samurai.com>
locking for unique hash indexes
Neil Conway <neilc@samurai.com> writes:
> - Invent a new set of lmgr locks; call them "right of insertion" locks,
> and have one for each bucket in the hash index. Only one backend will
> hold the ROI lock for a given bucket at any given time.

Rather than trying to invent a new set of lock IDs (which would be
difficult to squeeze into the page mapping I think), you could encode
this as an appropriate lock mode on the existing set of bucket lock IDs.
It looks like this would work:

	HASH_SHARE		-> AccessShareLock
	unique-insertion lock	-> ShareUpdateExclusiveLock
	HASH_EXCLUSIVE		-> AccessExclusiveLock

> Q: Is there a possibility of deadlock here?

I think you would need to set it up so that insertion into a unique
index grabs ShareUpdateExclusiveLock *instead of* AccessShareLock, not
*in addition to*.  Otherwise I think there is indeed some risk.
However, it should be easy enough to do it that way, and there's no
real cost since it's still just one lock acquisition.


> P.S. While we're on the subject on hash indexes and locking, ISTM that
> we could get better concurrent performance in #4 by first acquiring the
> lwlock on a particular bucket page in shared mode, checking if it has
> free space, and only if it does, getting a write lock on it and doing
> the insertion.

The free-space check is cheap enough that I think this would just be a
waste of cycles.

			regards, tom lane

Fri, 19 Sep 2003 17:24:32 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: locking for unique hash indexes 