date:20131109

The B-tree page deletion algorithm has a race condition. We don't allow 
a page to be deleted if it's the rightmost child of its parent, but that 
situation can change after we check for it.


Problem
---

We check that the page to be deleted is not the rightmost child of its 
parent, and then lock its left sibling, the page itself, its right 
sibling, and the parent, in that order. However, if the parent page is 
split after the check but before acquiring the locks, the target page 
might become the rightmost child, if the split happens at the right 
place. That leads to an error in vacuum (I reproduced this by setting a 
breakpoint in debugger):


ERROR:  failed to delete rightmost child 41 of block 3 in index foo_pkey

We currently re-check that the page is still the rightmost child, and 
throw the above error if it's not. We could easily just give up rather 
than throw an error, but that approach doesn't scale to half-dead pages. 
To recap, although we don't normally allow deleting the rightmost child, 
if the page is the *only* child of its parent, we delete the child page 
and mark the parent page as half-dead in one atomic operation. But 
before we do that, we check that the parent can later be deleted, by 
checking that it in turn is not the rightmost child of the grandparent 
(potentially recursing all the way up to the root). But the same 
situation can arise there - the grandparent can be split while we're not 
holding the locks. We end up with a half-dead page that we cannot delete.


To make things worse, the keyspace of the deleted page has already been 
transferred to its right sibling. As the README points out, the keyspace 
at the grandparent level is out-of-whack until the half-dead page is 
deleted, and if enough tuples with keys in the transferred keyspace are 
inserted, the page might get split and a downlink might be inserted into 
the grandparent that is out-of-order. That might not cause any serious 
problem if it's transient (as the README ponders), but is surely bad if 
it stays that way.


Solutions
-

1. The simplest solution I can see is to never delete internal pages, 
avoiding the whole concept of half-dead pages. That obviously leads to 
some bloat, though.


2. The second-simplest solution I see is to keep locked the whole chain 
of pages that will be deleted, and delete all of them as one atomic 
WAL-logged operation. Ie. the leaf page, and all the parent pages above 
it that will become half-dead, and the parent of the last half-dead page.


3. Another approach would be to get rid of the can't delete rightmost 
child limitation. We currently have that limitation because it ensures 
that we never need to change the high-key of a page. If we delete a page 
that is the rightmost child of its parent, we transfer the deleted 
keyspace from the parent page to its right sibling. To do that, we need 
to update the high key of the parent, as well as the downlink of the 
right sibling at the grandparent level. That's a bit complicated, 
because updating the high key might require splitting the page.


Still, I think it would be doable: When we delete a page that is the 
rightmost child of its parent, we mark the right sibling with an 
out-of-whack flag. It indicates that the keyspace of that page is not 
in sync in the parent level. Searches work fine, as there are no keys in 
the keyspace that is out-of-whack, but before allowing any insertions to 
the page, the situation needs to be fixed. That is the responsibility of 
the next insert to the page that comes along. To fix it, the parent's 
left sibling's high key needs to be updated, as well as the parent's 
downlink in the grandparent. We can do that in a few discrete steps; 
first update the high key, then update the downlink, and finally once 
the high key and parent's downlink are in sync with the reality at the 
bottom level, clear the out-of-whack flag.


On reflection, approach 2 seems best. It's fairly simple, although it 
potentially requires holding many pages locked simultaneously. In 
practice, B-trees are typically not very deep. We have a limit of 4 
full-page images in a single WAL record, but since all the pages are 
empty, we can just WAL-log all the information needed to reconstruct the 
pages in deleted state without using full-page images. This also might 
be back-patchable, although it requires changing the WAL record format, 
so it would break replication from higher minor version to lower.


- Heikki


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Race condition in b-tree page deletion

2013-11-09 Thread Tom Lane

Heikki Linnakangas hlinnakan...@vmware.com writes:
 2. The second-simplest solution I see is to keep locked the whole chain 
 of pages that will be deleted, and delete all of them as one atomic 
 WAL-logged operation. Ie. the leaf page, and all the parent pages above 
 it that will become half-dead, and the parent of the last half-dead page.

This would be more tenable if we could put a known limit on the number of
pages to be changed at once.  I'm not too awake at the moment, so maybe
this is not possible, but could we simply decide in advance that we won't
propagate page deletion up more than a-small-number of levels?  It'd
require allowing a page to remain half-dead until some other vacuum comes
along and fixes it, but that seems OK.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Race condition in b-tree page deletion

On 09.11.2013 18:24, Tom Lane wrote:

Heikki Linnakangas hlinnakan...@vmware.com writes:

2. The second-simplest solution I see is to keep locked the whole chain
of pages that will be deleted, and delete all of them as one atomic
WAL-logged operation. Ie. the leaf page, and all the parent pages above
it that will become half-dead, and the parent of the last half-dead page.

This would be more tenable if we could put a known limit on the number of
pages to be changed at once. I'm not too awake at the moment, so maybe
this is not possible, but could we simply decide in advance that we won't
propagate page deletion up more than a-small-number of levels? It'd
require allowing a page to remain half-dead until some other vacuum comes
along and fixes it, but that seems OK.

I don't feel comfortable leaving pages in half-dead state. Looking back
at the archives, your original design ten years ago did exactly that
(http://www.postgresql.org/message-id/8281.1045089...@sss.pgh.pa.us),
but that turned out to be a bad idea
(http://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=70ce5c908202ada7616f7afded8a91bbf2742471).
Mind you, even if we check that the half-dead page at some upper level
is eventually deletable because it's not the rightmost child, it might
become the rightmost child if we don't hold the lock so that the next
vacuum cannot delete it, and we're back to square one.

We could just punt if more than X pages would need to be changed. That
would mean that we never delete pages at the top (h - X) levels of the
tree. In practice that should be fine if X is high enough.
As a data point, GIN list page deletion holds 16 pages locked at once
(GIN_NDELETE_AT_ONCE). Normally, a 16-level deep B-tree is pretty huge.
As another data point, in the worst case the keys are so wide that only
2 keys fit on each B-tree page. With that assumption, the tree can be at
most 32 levels deep if you just insert into it with no deletions, since
MaxBlockNumber ~= 2^32 (I may be off by one in either direction, not
sure). Deletions make it more complicated, but I would be pretty
surprised if you can construct a B-tree tallers than, say 40 levels.

Things gets tricky if shared_buffers is very small; with
shared_buffers=16, you certainly can't hold more than 16 buffers pinned
at once. (in fact, I think ginfast.c already has a problem with that...)

- Heikki

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Race condition in b-tree page deletion


On 09.11.2013 18:49, Heikki Linnakangas wrote:

We could just punt if more than X pages would need to be changed. That
would mean that we never delete pages at the top (h - X) levels of the
tree. In practice that should be fine if X is high enough.
As a data point, GIN list page deletion holds 16 pages locked at once
(GIN_NDELETE_AT_ONCE). Normally, a 16-level deep B-tree is pretty huge.
As another data point, in the worst case the keys are so wide that only
2 keys fit on each B-tree page. With that assumption, the tree can be at
most 32 levels deep if you just insert into it with no deletions, since
MaxBlockNumber ~= 2^32 (I may be off by one in either direction, not
sure). Deletions make it more complicated, but I would be pretty
surprised if you can construct a B-tree tallers than, say 40 levels.


On further thought, it's worse than that. To delete a page, you need to 
lock the left and right siblings, so you need 3 pages locked per each 
level you delete...


- Heikki


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Race condition in b-tree page deletion


On 09.11.2013 19:18, Heikki Linnakangas wrote:

On 09.11.2013 18:49, Heikki Linnakangas wrote:

We could just punt if more than X pages would need to be changed. That
would mean that we never delete pages at the top (h - X) levels of the
tree. In practice that should be fine if X is high enough.
As a data point, GIN list page deletion holds 16 pages locked at once
(GIN_NDELETE_AT_ONCE). Normally, a 16-level deep B-tree is pretty huge.
As another data point, in the worst case the keys are so wide that only
2 keys fit on each B-tree page. With that assumption, the tree can be at
most 32 levels deep if you just insert into it with no deletions, since
MaxBlockNumber ~= 2^32 (I may be off by one in either direction, not
sure). Deletions make it more complicated, but I would be pretty
surprised if you can construct a B-tree tallers than, say 40 levels.


On further thought, it's worse than that. To delete a page, you need to
lock the left and right siblings, so you need 3 pages locked per each
level you delete...


On further further thought, we don't need to unlink the pages 
immediately. It's enough to mark them as half-dead and remove the 
downlink to the upmost half-dead page. Marking a page as half-dead is as 
good as deleting it outright as far as searches and insertions are 
concerned. Actually unlinking the pages from the left and right siblings 
can be done at any later time, and doesn't need to be done in any 
particular order.


So, my original musings about the number of concurrent locks needed 
still holds.


- Heikki


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Suggestion: Issue warning when calling SET TRANSACTION outside transaction block

On Fri, Nov 8, 2013 at 5:36 PM, Tom Lane t...@sss.pgh.pa.us wrote:
 [ I'm so far behind ... ]

 Bruce Momjian br...@momjian.us writes:
 Applied.  Thank you for all your suggestions.

 I thought the suggestion had been to issue a *warning*.  How did that
 become an error?  This patch seems likely to break applications that
 may have just been harmlessly sloppy about when they were issuing
 SETs and/or what flavor of SET they use.  We don't for example throw
 an error for START TRANSACTION with an open transaction or COMMIT or
 ROLLBACK without one --- how can it possibly be argued that these
 operations are more dangerous than those cases?

 I'd personally have voted for using NOTICE.

Well, LOCK TABLE throws an error, so it's not without precedent.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] UTF8 national character data type support WIP patch and list of open issues.

2013-11-09 Thread Albe Laurenz

MauMau wrote:
 Let me repeat myself: I think the biggest and immediate issue is that
 PostgreSQL does not support national character types at least officially.
 Officially means the description in the manual.  So I don't have strong
 objection against the current (hidden) implementation of nchar types in
 PostgreSQL which are just synonyms, as long as the official support is
 documented.  Serious users don't want to depend on hidden features.

I agree with you there.
Actually it is somewhat documented in
http://www.postgresql.org/docs/9.3/static/features-sql-standard.html
as F421, but that requires that you read the SQL standard.

 However, doesn't the current synonym approach have any problems?  Wouldn't
 it produce any trouble in the future?  If we treat nchar as char, we lose
 the fact that the user requested nchar.  Can we lose the fact so easily and
 produce irreversible result as below?

I don't think that it is a problem.
According to the SQL standard, the user requested a CHAR or VARCHAR with
an encoding of the choice of the DBMS.
PostgreSQL chooses the database encoding.

In a way, it is similar to using the data type serial.  The column will be
displayed as integer, and the information that it was a serial can
only be inferred from the DEFAULT value.
It seems that this is working fine and does not cause many problems,
so I don't see why things should be different here.

Again, for serial the behaviour is well documented, so that seconds
your request for more documentation.
Would you like to write a patch for that?

Yours,
Laurenz Albe

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] Fw: [COMMITTERS] pgsql: Fix blatantly broken record_image_cmp() logic for pass-by-value

Forwarding to -hackers.

- Forwarded Message -
 From: Kevin Grittner kgri...@ymail.com
 To: Tom Lane t...@sss.pgh.pa.us
 Cc: pgsql-committ...@postgresql.org pgsql-committ...@postgresql.org
 Sent: Friday, November 8, 2013 3:19 PM
 Subject: Re: [COMMITTERS] pgsql: Fix blatantly broken record_image_cmp() 
 logic for pass-by-value

 Tom Lane t...@sss.pgh.pa.us wrote:

  That is a serious compiler bug which you should file with your
  distro forthwith.

 I distilled it down to the simplest case I could find which failed
 to produce the warning; attached. Do you agree that it is a
 compiler bug that this generates no warning?

 Compile lines used:

 gcc -O2 -Wall -Wmissing-prototypes -Wpointer-arith
 -Wdeclaration-after-statement -Wendif-labels
 -Wmissing-format-attribute -Wformat-security -fno-strict-aliasing
 -fwrapv -fexcess-precision=standard -g -D_GNU_SOURCE -c -o
 warning_test.o warning_test.c -MMD -MP

 clang -O2 -Wall -Wmissing-prototypes -Wpointer-arith
 -Wdeclaration-after-statement -Wendif-labels
 -Wmissing-format-attribute -Wformat-security -fno-strict-aliasing
 -fwrapv -g -D_GNU_SOURCE -c -o warning_test.o warning_test.c -MMD
 -MP

 It is probably significant that if I simplify the while loop
 condition to just use one variable I do get the warning.

  It definitely does show up with what I'm using:
  gcc (GCC) 4.4.7 20120313 (Red Hat 4.4.7-3)

 The warning shows up, or the bug does?

  It might be worth trawling the buildfarm records to see which
  compilers did or didn't warn before.

 I'll get this filed first with the version I'm using, then look
 around to see if there is anything else to report.

 --
 Kevin Grittner
 EDB: http://www.enterprisedb.com
 The Enterprise PostgreSQL Company
 int test_warnings(int x, int y, int z);

int
test_warnings(int x, int y, int z)
{
	int i;

	switch (x)
	{
		case 1:
			if (y != z)
			{
i = (y  z) ? -1 : 1;
			}
			break;
		case 2:
			if (y != z)
			{
i = (y  z) ? -1 : 1;
			}
			break;
		default:
			return 0;
	}
	return i;
}
-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] Fw: [COMMITTERS] pgsql: Fix blatantly broken record_image_cmp() logic for pass-by-value

Forwarded to -hackers



- Forwarded Message -
 From: Kevin Grittner kgri...@ymail.com
 To: Kevin Grittner kgri...@ymail.com; Tom Lane t...@sss.pgh.pa.us
 Cc: pgsql-committ...@postgresql.org pgsql-committ...@postgresql.org
 Sent: Friday, November 8, 2013 4:33 PM
 Subject: Re: [COMMITTERS] pgsql: Fix blatantly broken record_image_cmp() 
 logic for pass-by-value
 
 Kevin Grittner kgri...@ymail.com wrote:
 
  I distilled it down to the simplest case I could find which
  failed to produce the warning; attached.
 
 For a compiler which seems to like to generate warnings for really
 esoteric cases, clang falls down rather badly on uninitialized
 variables -- at least on the package for Ubuntu 12.10.  It does not
 complain at all about this:
 
 
 int warning_test(int a);
 int warning_test(int a)
 {
     int result;
 
     if (a == 1)
     result = 1;
 
     return result;
 }
 
 
 I assume that everyone here agrees that merits a warning?
 
 Bug reports filed.
 
 
 --
 Kevin Grittner
 EDB: http://www.enterprisedb.com
 The Enterprise PostgreSQL Company



-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Fw: [COMMITTERS] pgsql: Fix blatantly broken record_image_cmp() logic for pass-by-value

Kevin Grittner kgri...@ymail.com wrote:

  int warning_test(int a);
  int warning_test(int a)
  {
  int result;

  if (a == 1)
  result = 1;

  return result;
  }

I had to file separate bug reports for gcc and clang.  I have
already gotten a response on the clang bug report using the above
test code.  It was closed with this response:

Fixed from clang 3.3
warning_test.c:8:6: warning: variable 'result' is used uninitialized whenever 
'if' condition is
  false [-Wsometimes-uninitialized]
    if (a == 1)
    ^~
warning_test.c:11:9: note: uninitialized use occurs here
    return result;
  ^~
warning_test.c:8:2: note: remove the 'if' if its condition is always true
    if (a == 1)
    ^~~
warning_test.c:6:14: note: initialize the variable 'result' to silence this 
warning
    int    result;
  ^
  = 0


** Changed in: clang (Ubuntu)
  Status: New = Fix Released


I take that to say that the bug will be fixed in clang version 3.3,
which is not available in any production release of Ubuntu.

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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] logical changeset generation v6.5

2013-11-09 Thread Steve Singer


On 11/05/2013 10:21 AM, Andres Freund wrote:

Hi,

Attached to this mail and in the xlog-decoding-rebasing-remapping branch
in my git[1] repository you can find the next version of the patchset that:
* Fixes full table rewrites of catalog tables using the method Robert
   prefers (which is to log rewrite mappings to disk)
* Extract the REPLICA IDENTITY as configured with ALTER TABLE for the
   old tuple for UPDATEs and DELETEs
* Much better support for synchronous replication
* Better resource cleanup (as in we need less local WAL available)
* Lots of smaller fixes
The change around REPLICA IDENTITY is *incompatible* to older output
plugins since we now log tuples using the table's TupleDesc, not the
indexes.


My updated plugin is getting rows with
change-tp.oldtuple as NULL on updates either with the default PRIMARY 
KEY identify or with a  FULL identity.


When I try the test_decoding plugin on UPDATE I get rows like:

table do_inventory: UPDATE: ii_id[int8]:251 ii_in_stock[int8]:1 
ii_reserved[int8]:144 ii_total_sold[int8]:911


which I think is only data from the new tuple.The lack of old-key 
in the output makes me think the test decoding plugin also isn't getting 
the old tuple.


(This is with your patch-set rebased ontop of 
ac4ab97ec05ea900db0f14d428cae2e79832e02d which includes the patches 
Robert committed the other day, I can't rule out that I didn't break 
something in the rebase).







Robert, I'd be very grateful if you could have a look at patch 0007
implementing what we've discussed. I kept it separate to make it easier
to look at it in isolation, but I think in the end it partially should
be merged into the wal_level=logical patch.
I still think the wide cmin/cmax solution is more elegant and has
wider applicability, but this works as well although it's about 5 times
the code.

Comments?

[1]: 
http://git.postgresql.org/gitweb/?p=users/andresfreund/postgres.git;a=summary
Greetings,

Andres Freund







--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] logical changeset generation v6.5

2013-11-09 Thread Andres Freund

On 2013-11-09 17:36:49 -0500, Steve Singer wrote:
 On 11/05/2013 10:21 AM, Andres Freund wrote:
 Hi,
 
 Attached to this mail and in the xlog-decoding-rebasing-remapping branch
 in my git[1] repository you can find the next version of the patchset that:
 * Fixes full table rewrites of catalog tables using the method Robert
prefers (which is to log rewrite mappings to disk)
 * Extract the REPLICA IDENTITY as configured with ALTER TABLE for the
old tuple for UPDATEs and DELETEs
 * Much better support for synchronous replication
 * Better resource cleanup (as in we need less local WAL available)
 * Lots of smaller fixes
 The change around REPLICA IDENTITY is *incompatible* to older output
 plugins since we now log tuples using the table's TupleDesc, not the
 indexes.
 
 My updated plugin is getting rows with
 change-tp.oldtuple as NULL on updates either with the default PRIMARY KEY
 identify or with a  FULL identity.
 
 When I try the test_decoding plugin on UPDATE I get rows like:
 
 table do_inventory: UPDATE: ii_id[int8]:251 ii_in_stock[int8]:1
 ii_reserved[int8]:144 ii_total_sold[int8]:911
 
 which I think is only data from the new tuple.The lack of old-key in
 the output makes me think the test decoding plugin also isn't getting the
 old tuple.
 
 (This is with your patch-set rebased ontop of
 ac4ab97ec05ea900db0f14d428cae2e79832e02d which includes the patches Robert
 committed the other day, I can't rule out that I didn't break something in
 the rebase).

I've pushed an updated tree to git, that contains that
http://git.postgresql.org/gitweb/?p=users/andresfreund/postgres.git;a=shortlog;h=refs/heads/xlog-decoding-rebasing-remapping
git://git.postgresql.org/git/users/andresfreund/postgres.git

and some more fixes. I'll send out an email with details sometime soon.

Greetings,

Andres Freund

-- 
 Andres Freund http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training  Services


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Fw: [COMMITTERS] pgsql: Fix blatantly broken record_image_cmp() logic for pass-by-value

Kevin Grittner kgri...@ymail.com wrote:

 I distilled it down to the simplest case I could find which
 failed to produce the warning; attached. Do you agree that it is
 a compiler bug that this generates no warning?

 gcc -O2 -Wall -Wmissing-prototypes -Wpointer-arith
 -Wdeclaration-after-statement -Wendif-labels
 -Wmissing-format-attribute -Wformat-security -fno-strict-aliasing
 -fwrapv -fexcess-precision=standard -g -D_GNU_SOURCE -c -o
 warning_test.o warning_test.c -MMD -MP

The actual test case I sent for gcc is what is attached here. 
Sorry for attaching the wrong file before.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Companyint warning_test(int a, int b, int c);
int warning_test(int a, int b, int c)
{
	int result = 0;
	int i1;
	int i2;

	i1 = i2 = 0;
	while (i1  2 || i2  2)
	{
		int cmpresult;

		switch (a)
		{
			case 1:
if (b != c)
	cmpresult = (b  c) ? -1 : 1;
break;
		}

		if (cmpresult  0)
		{
			result = -1;
			break;
		}

		i1++, i2++;
	}

	return result;
}

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Race condition in b-tree page deletion

On Sat, Nov 9, 2013 at 12:40 PM, Heikki Linnakangas
hlinnakan...@vmware.com wrote:
 On 09.11.2013 19:18, Heikki Linnakangas wrote:
 On 09.11.2013 18:49, Heikki Linnakangas wrote:
 We could just punt if more than X pages would need to be changed. That
 would mean that we never delete pages at the top (h - X) levels of the
 tree. In practice that should be fine if X is high enough.
 As a data point, GIN list page deletion holds 16 pages locked at once
 (GIN_NDELETE_AT_ONCE). Normally, a 16-level deep B-tree is pretty huge.
 As another data point, in the worst case the keys are so wide that only
 2 keys fit on each B-tree page. With that assumption, the tree can be at
 most 32 levels deep if you just insert into it with no deletions, since
 MaxBlockNumber ~= 2^32 (I may be off by one in either direction, not
 sure). Deletions make it more complicated, but I would be pretty
 surprised if you can construct a B-tree tallers than, say 40 levels.

 On further thought, it's worse than that. To delete a page, you need to
 lock the left and right siblings, so you need 3 pages locked per each
 level you delete...

 On further further thought, we don't need to unlink the pages immediately.
 It's enough to mark them as half-dead and remove the downlink to the upmost
 half-dead page. Marking a page as half-dead is as good as deleting it
 outright as far as searches and insertions are concerned. Actually unlinking
 the pages from the left and right siblings can be done at any later time,
 and doesn't need to be done in any particular order.

 So, my original musings about the number of concurrent locks needed still
 holds.

I think we've tried pretty hard to avoid algorithms where the maximum
number of lwlocks that must be held at one time is not a constant, and
I think we're in for a bad time of it if we start to deviate from that
principal.  I'm not sure what to do about this problem, but I think
locking N levels of the tree at once, where N can be as large as the
tree is deep, is probably a bad plan, whether the number of locks
required is N or 3N.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Comment - uniqueness of relfilenode

On Thu, Nov 7, 2013 at 10:56 AM, Antonin Houska
antonin.hou...@gmail.com wrote:
 catalog/catalog.c:GetNewRelFileNode() and its calls indicate that the
 following change makes sense:


 diff --git a/src/include/storage/relfilenode.h
 b/src/include/storage/relfilenode.h
 index 75f897f..7190974 100644
 --- a/src/include/storage/relfilenode.h
 +++ b/src/include/storage/relfilenode.h
 @@ -55,7 +55,7 @@ typedef enum ForkNumber
   * relNode identifies the specific relation.  relNode corresponds to
   * pg_class.relfilenode (NOT pg_class.oid, because we need to be able
   * to assign new physical files to relations in some situations).
 - * Notice that relNode is only unique within a particular database.
 + * Notice that relNode is only unique within a particular tablespace.
   *
   * Note: spcNode must be GLOBALTABLESPACE_OID if and only if dbNode is
   * zero.  We support shared relations only in the global tablespace.


 // Antonin Houska (Tony)

Technically speaking, I think it's only guaranteed to be unique with a
database-tablespace combination.  In other words, the same OID can be
reused as a relfilenode if *either* of those two values differs.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] Re: Fix pg_isolation_regress to work outside its build directory compiler warning