Re: true serializability and predicate locking

On Tue, Jan 5, 2010 at 2:14 PM, Jeff Davis <pgsql(at)j-davis(dot)com> wrote:
> I have a question regarding true serializability and predicate locking.
> There's some context on the wiki page:
>
> http://wiki.postgresql.org/wiki/Serializable
>
> under the heading "Predicate Locking".
>
> If you have the following DDL:
>
>  create table mytable(mycircle circle);
>  create index mytable_mycircle_idx on mytable
>    using gist (mycircle);
>
> and two transactions:
>
> T1:
>  BEGIN;
>  SELECT * FROM mytable WHERE mycircle && '<(0, 0), 10>';
>  -- if any rows are returned, ROLLBACK
>  INSERT INTO mytable(mycircle) VALUES('<(0, 0), 10>');
>  COMMIT;
>
> T2:
>  BEGIN;
>  SELECT * FROM mytable WHERE mycircle && '<(5, 5), 5>';
>  -- if any rows are returned, ROLLBACK
>  INSERT INTO mytable(mycircle) VALUES('<(5, 5), 5>');
>  COMMIT;
>
> Clearly one of those transactions should abort, because that will happen
> in either serialized order. But I don't see where any lock is stored,
> nor how the conflict is detected.
>
> There has been a lot of theoretical discussion on this matter, but I'd
> like to know how it will work in this specific case. You can't merely
> lock a few index pages, because the INSERT might put the tuple in
> another page.
>
> I'm still trying to catch up on this discussion as well as relevant
> papers, but this question has been on my mind.
>
> One approach that might work for GiST is to get some kind of lock
> (SIREAD?) on the predicates for the pages that the search does not
> match. That way, the conflict can be detected if an INSERT tries to
> update the predicate of a page to something that the search may have
> matched.
>
> If the index was GIN instead of GiST, I think the fastupdate feature
> would cause a problem, though (as Greg brought up). Fastupdate may need
> to be disabled when using truly serializable transactions.

It seems to me that we shouldn't pre-judge too much about how
predicate locking will ultimately be implemented. Suppose the first
query in your example were:

SELECT * FROM mytable WHERE [some incredibly complex condition
involving all sorts of strange magic]

It seems to me that in a case like this our only realistic option is
to lock the entire table until T1 commits.

Now, in certain cases, we can optimize this, if we want. For example,
if the first query were:

SELECT * FROM mytable WHERE id = 42;

...and if further we know that there is a unique B-tree index on the
id column, and if there is an existing record with id = 42, then we
can lock just that record. If no such record exists, we can either
fall back to locking the whole table, or we can take some sort of
key-range lock that will block any future attempts to read or update a
row with id = 42.

With GIST and GIN and so on, the situation is similar. If the index
AM can be modified to provide certain kinds of key-range locking then
we can take weaker locks for queries that involve those types of
conditions. If not, we have to fall back to a full-table lock.

...Robert