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

From: Kevin Grittner <kgrittn(at)ymail(dot)com>
To: Peter Geoghegan <pg(at)heroku(dot)com>, Robert Haas <robertmhaas(at)gmail(dot)com>
Cc: Heikki Linnakangas <hlinnakangas(at)vmware(dot)com>, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com>, Pg Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Stating the significance of Lehman & Yao in the nbtree README
Date: 2014-09-12 19:39:52
Message-ID: 1410550792.8163.YahooMailNeo@web122304.mail.ne1.yahoo.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Peter Geoghegan <pg(at)heroku(dot)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

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Heikki Linnakangas 2014-09-12 19:45:57 Re: pgbench throttling latency limit
Previous Message Tomas Vondra 2014-09-12 19:39:04 Re: bad estimation together with large work_mem generates terrible slow hash joins