Re: Stating the significance of Lehman & Yao in the nbtree README

Peter Geoghegan <pg@heroku.com> wrote:

> The introductory paragraph of L&Y says the following:
>
> "Our solution compares favorably with earlier solutions in that the
> locking scheme is simpler (no read-locks are used) and only a (small)
> constant number of nodes are locked by any update process at any given
> time."
>
> They clearly and prominently state that not needing read locks is a
> major advantage of their algorithm, which doesn't quite ring true.

It's been a while since I read that paper, but my recollection is
that they assumed that each process or thread looking at a buffer
would have its own private copy of that buffer, which it could be
sure nobody was changing (even if the "master" copy somewhere else
was changing).  Locking was only needed to prevent conflicting
writes.  Now, whether it is safe to assume that creating a
process-local buffer and copying to it is cheaper than getting a
lock seems dicey, but that seemed to be the implicit assumption.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company