Re: true serializability and predicate locking

From: "Albe Laurenz" <laurenz(dot)albe(at)wien(dot)gv(dot)at>
To: "Robert Haas *EXTERN*" <robertmhaas(at)gmail(dot)com>, "Jeff Davis" <pgsql(at)j-davis(dot)com>
Cc: "Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov>, <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: true serializability and predicate locking
Date: 2010-01-07 09:33:07
Message-ID: D960CB61B694CF459DCFB4B0128514C203938111@exadv11.host.magwien.gv.at
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Robert Haas wrote:
> Jeff Davis wrote:
> > I have a question regarding true serializability and predicate locking.
> > There's some context on the wiki page:
> >
> > 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.

I don't know if such a thing would be easy to implement in
PostgreSQL, but I had thought that the "standard" approach to
implement predicate locking is like this:

Whenever you touch (read) a data structure, you tag it with a lock
that prevents anybody else from modifying the data structure in a way
that would change your result if you perform the same operation again
(or with SIREAD locks, it will not prevent the modification, but
may lead to aborted transactions later).

So no matter how complex the index condition is, it will boil down
to accessing and hence locking certain parts of a table or index
(in the case of a B*-tree, you'll probably end up locking gaps in
the index).

I'd say that the index should know what exactly should be locked
if a certain operation must become repeatable.

Yours,
Laurenz Albe

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Fujii Masao 2010-01-07 09:34:48 Re: Hot standby documentation
Previous Message Nicolas Barbier 2010-01-07 09:28:33 Re: Serializable Isolation without blocking