Re: New lock types

Hello hackers,

I'm looking at implementing the btree reorganizer described in "On-line
reorganization of sparsely-...", ACM SIGMOD proceedings 1996, by Zou and
Salzberg. It seems to me I'll have to add some amount of lock types
in the lock manager. Does that bother you?

--
Alvaro Herrera (<alvherre[a]atentus.com>)
"On the other flipper, one wrong move and we're Fatal Exceptions"
(T.U.X.: Term Unit X - http://www.thelinuxreview.com/TUX/)

Alvaro Herrera <alvherre(at)atentus(dot)com> writes:
> I'm looking at implementing the btree reorganizer described in "On-line
> reorganization of sparsely-...", ACM SIGMOD proceedings 1996, by Zou and
> Salzberg. It seems to me I'll have to add some amount of lock types
> in the lock manager. Does that bother you?

Such as?

regards, tom lane

En Fri, 04 Oct 2002 17:58:06 -0400
Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> escribió:

> Alvaro Herrera <alvherre(at)atentus(dot)com> writes:
> > I'm looking at implementing the btree reorganizer described in "On-line
> > reorganization of sparsely-...", ACM SIGMOD proceedings 1996, by Zou and
> > Salzberg.

The title is "On-line reorganization of sparsely-populated B+-trees".
My purpose is to implement the reorganizer so that B+-trees can be
compacted concurrently with other uses of the index.

> > It seems to me I'll have to add some amount of lock types
> > in the lock manager. Does that bother you?
>
> Such as?

There are three new lock modes: R, RX and RS (Reorganizer, Reorganizer
Exclusive and Reorganizer Shared). Actually, they are not new lock
types; rather, new objects on which locks should be obtained before
using the index pages.

But there's some work to do before that. I need to make the nbtree code
actually use its free page list. That is, new pages for splits should
be taken from the free page, or a new page should be created if there
are none; also, deleting the last element from a page should put it into the
free page list. I'm looking at that code now. Let me know if you think
there's something I should know about this.

--
Alvaro Herrera (<alvherre[a]atentus.com>)
"El sudor es la mejor cura para un pensamiento enfermo" (Bardia)

Alvaro Herrera <alvherre(at)atentus(dot)com> writes:
>>> It seems to me I'll have to add some amount of lock types
>>> in the lock manager. Does that bother you?
>>
>> Such as?

> There are three new lock modes: R, RX and RS (Reorganizer, Reorganizer
> Exclusive and Reorganizer Shared). Actually, they are not new lock
> types; rather, new objects on which locks should be obtained before
> using the index pages.

We've got a ton of lock modes already; perhaps these operations can be
mapped into acquiring some existing lock modes on index pages?

Note that there is currently a notion of using exclusive lock on page
zero of a relation (either index or heap) to interlock extension of the
relation. You can probably change that or work around it if you want to
assign other semantics to locking index pages; just be aware that it's
out there.

> But there's some work to do before that. I need to make the nbtree code
> actually use its free page list. That is, new pages for splits should
> be taken from the free page, or a new page should be created if there
> are none; also, deleting the last element from a page should put it into the
> free page list. I'm looking at that code now. Let me know if you think
> there's something I should know about this.

Yeah, you can't recycle pages without a freelist :-(. One thing that
bothered me about that was that adding/removing freelist pages appears
to require exclusive lock on the index metapage, which would
unnecessarily block many other index operations. You should try to
structure things to avoid that. Maybe the freelist head link can be
treated as a separately lockable object.

Don't forget to think about WAL logging of these operations.

regards, tom lane

On Sat, Oct 05, 2002 at 08:25:35PM -0400, Tom Lane wrote:
> Alvaro Herrera <alvherre(at)atentus(dot)com> writes:
> >>> It seems to me I'll have to add some amount of lock types
> >>> in the lock manager. Does that bother you?
> >>
> >> Such as?
>
> > There are three new lock modes: R, RX and RS (Reorganizer, Reorganizer
> > Exclusive and Reorganizer Shared). Actually, they are not new lock
> > types; rather, new objects on which locks should be obtained before
> > using the index pages.
>
> We've got a ton of lock modes already; perhaps these operations can be
> mapped into acquiring some existing lock modes on index pages?

I'll have a look. Can't say right now. Some of the locks have special
semantics on what to do when a conflicting request arrives.

> Yeah, you can't recycle pages without a freelist :-(.

In access/nbtree/README says that the metapage of the index "contains a
pointer to the list of free pages". However I don't see anything like
that in the BTMetaPageData. Should I suppose that it was ripped out
sometime ago? I'll add it if that's the case. Or maybe I'm looking at
the wrong place?

> Maybe the freelist head link can be treated as a separately lockable
> object.

I think creating a new LWLockId (BTFreeListLock?) can help here. The
operations on freelist are short lived and rather infrequent so it
doesn't seem to matter that it is global to all indexes. Another way
would be to create one LockId per index, but it seems a waste to me.

--
Alvaro Herrera (<alvherre[a]atentus.com>)
"No hay ausente sin culpa ni presente sin disculpa" (Prov. frances)

Alvaro Herrera <alvherre(at)atentus(dot)com> writes:
> I think creating a new LWLockId (BTFreeListLock?) can help here. The
> operations on freelist are short lived and rather infrequent so it
> doesn't seem to matter that it is global to all indexes.

Seems like a really bad idea to me ... what makes you think that this
would not be a bottleneck? You'd have to take such a lock during every
index-page split, which is not that uncommon.

> Another way
> would be to create one LockId per index, but it seems a waste to me.

No, you should be looking at a way to represent index locking in the
standard lock manager, not as an LWLock. We've already got a concept
of page-level lockable entities there.

regards, tom lane