WIP patch for serializable transactions with predicate locking

I heard that others were considering work on predicate locks for
9.1. Since Dan Ports of MIT and I have been working on that for the
serializable implementation for the last few weeks, I felt it would
be good to post a WIP patch to avoid duplicate effort. This
implementation compiles without warning, passes all regression
tests, and passes several hundred permutations of a dozen basic
tests which are intended to confirm correct predicate locking.
SIREAD locks are generally taken at the tuple level for the heap,
with granularity promotion to page and then relation level as needed
to prevent resource exhaustion. We've been using indexes to
implement predicate locking, and currently have page level locking
for btree indexes and only relation level locking otherwise, but Dan
is actively working on getting btree down to next-key locking, and
when I return from PGCon I will be working on the other index AMs.

We're currently using Markus Wanner's dtester for testing, but that
can be moved out of the patch if we don't want to have a dependency
on it.

-Kevin

On Wed, May 19, 2010 at 5:37 PM, Kevin Grittner
<Kevin(dot)Grittner(at)wicourts(dot)gov> wrote:
> I heard that others were considering work on predicate locks for
> 9.1. Since Dan Ports of MIT and I have been working on that for the
> serializable implementation for the last few weeks, I felt it would
> be good to post a WIP patch to avoid duplicate effort.

I added this to the next commitfest with the 'WIP' prominent.

I figured it was worth including for initial reviews, although of
course, detailed work will likely wait until July.

-selena

--
http://chesnok.com/daily - me

Attached is an updated patch to correct for bitrot and include the
latest work.

Whoever reviews this will probably want to review the Serializable
Wiki page:

http://wiki.postgresql.org/wiki/Serializable

Some areas on which I would particularly appreciate feedback in the
initial review:

CODE ORGANIZATION: I started with predicate.c based on the lock.c
code, and so fell into the src/backend/storage/lmgr directory. It
has morphed into something which probably doesn't belong in that
directory, but I'm not sure where it *does* belong. An argument
could be made that the SSI logic should be split from the predicate
locking, except that there is so little code that isn't part of
tracking the predicate locks and their conflicts, I'm not sure about
that either. In a similar vein, the structures in predicate.h are
used in exactly one place outside of predicate.c; it might make
sense to split that .h file so that most places only bring in the
function prototypes, which is all they need. Or perhaps the code
added to lockfuncs.c should be moved to the new predicate.c file,
and called from lockfuncs.c?

NAMING: The names in predicate.c are somewhat inconsistent, and a
few of them outright annoy me -- particularly MyXxx in a structure
field. I want to do a pass to make the names more consistent, but
would appreciate any feedback on what's good, bad, or ugly in the
current code before I do.

CORNER CASES: What did we forget to handle?

-Kevin