Skip site navigation (1) Skip section navigation (2)

true serializability and predicate locking

From: Jeff Davis <pgsql(at)j-davis(dot)com>
To: Kevin Grittner <Kevin(dot)Grittner(at)wicourts(dot)gov>
Cc: pgsql-hackers(at)postgresql(dot)org
Subject: true serializability and predicate locking
Date: 2010-01-05 19:14:03
Message-ID: 1262718843.5908.183.camel@monkey-cat.sm.truviso.com (view raw or flat)
Thread:
Lists: pgsql-hackers
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.

Regards,
	Jeff Davis


Responses

pgsql-hackers by date

Next:From: Peter EisentrautDate: 2010-01-05 19:19:38
Subject: Re: Proposal: XML helper functions
Previous:From: Scott BaileyDate: 2010-01-05 19:07:28
Subject: Re: Proposal: XML helper functions

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group