Re: [HACKERS] Small patch for GiST: move childoffnum to child
On 14.07.2011 13:29, Alexander Korotkov wrote:
On Thu, Jul 14, 2011 at 12:56 PM, Heikki Linnakangas
heikki.linnakan...@enterprisedb.com wrote:
First, notice that we're setting ptr-parent = top. 'top' is the current
node we're processing, and ptr represents the node to the right of the
current node. The current node is *not* the parent of the node to the right.
I believe that line should be ptr-parent = top-parent.
I think same.
Second, we're adding the entry for the right sibling to the end of the list
of nodes to visit. But when we process entries from the list, we exit
immediately when we see a leaf page. That means that the right sibling can
get queued up behind leaf pages, and thus never visited.
I think possible solution is to save right sibling immediatly after current
page . Thus, this code fragment should looks like this:
if (top-parent XLByteLT(top-parent-lsn,
GistPageGetOpaque(page)-nsn)
GistPageGetOpaque(page)-**rightlink !=
InvalidBlockNumber /* sanity check */ )
{
/* page splited while we thinking of... */
ptr = (GISTInsertStack *) palloc0(sizeof(**
GISTInsertStack));
ptr-blkno = GistPageGetOpaque(page)-**rightlink;
ptr-childoffnum = InvalidOffsetNumber;
ptr-parent = top-parent;
ptr-next = top-next;
top-next = ptr;
if (tail == top);
tail = ptr;
}
Agreed, committed. Thanks for verifying my thinking.
--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com
--
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] Small patch for GiST: move childoffnum to child
On 13.07.2011 22:04, Heikki Linnakangas wrote: On 13.07.2011 21:56, Alexander Korotkov wrote: Thank you very much for detail explanation. But this line of modified patch seems strange for me: *newchildoffnum = blkno; I believe it should be: *newchildoffnum = i; Yes, you're right. It's scary that it worked during testing anyway. Maybe the resulting tree was indeed broken but it didn't affect the subsequent inserts so I didn't notice. Ok, committed this now. I decided to rename the childoffnum field to downlinkoffnum. I figured it'd be dangerous that the field means something subtly different in different versions, if we need to backpatch bug fixes that use that field. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- 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] Small patch for GiST: move childoffnum to child
On Fri, Jul 15, 2011 at 1:27 PM, Heikki Linnakangas heikki.linnakan...@enterprisedb.com wrote: Ok, committed this now. Thank you. I decided to rename the childoffnum field to downlinkoffnum. I figured it'd be dangerous that the field means something subtly different in different versions, if we need to backpatch bug fixes that use that field. Yes, it seems very reasonable. -- With best regards, Alexander Korotkov.
Re: [HACKERS] Small patch for GiST: move childoffnum to child
On Thu, Jul 14, 2011 at 12:56 PM, Heikki Linnakangas
heikki.linnakan...@enterprisedb.com wrote:
First, notice that we're setting ptr-parent = top. 'top' is the current
node we're processing, and ptr represents the node to the right of the
current node. The current node is *not* the parent of the node to the right.
I believe that line should be ptr-parent = top-parent.
I think same.
Second, we're adding the entry for the right sibling to the end of the list
of nodes to visit. But when we process entries from the list, we exit
immediately when we see a leaf page. That means that the right sibling can
get queued up behind leaf pages, and thus never visited.
I think possible solution is to save right sibling immediatly after current
page . Thus, this code fragment should looks like this:
if (top-parent XLByteLT(top-parent-lsn,
GistPageGetOpaque(page)-nsn)
GistPageGetOpaque(page)-**rightlink !=
InvalidBlockNumber /* sanity check */ )
{
/* page splited while we thinking of... */
ptr = (GISTInsertStack *) palloc0(sizeof(**
GISTInsertStack));
ptr-blkno = GistPageGetOpaque(page)-**rightlink;
ptr-childoffnum = InvalidOffsetNumber;
ptr-parent = top-parent;
ptr-next = top-next;
top-next = ptr;
if (tail == top);
tail = ptr;
}
--
With best regards,
Alexander Korotkov.
Re: [HACKERS] Small patch for GiST: move childoffnum to child
I think there's two bugs in the existing gistFindPath code:
if (top-parent XLByteLT(top-parent-lsn,
GistPageGetOpaque(page)-nsn)
GistPageGetOpaque(page)-rightlink !=
InvalidBlockNumber /* sanity check */ )
{
/* page splited while we thinking of... */
ptr = (GISTInsertStack *)
palloc0(sizeof(GISTInsertStack));
ptr-blkno = GistPageGetOpaque(page)-rightlink;
ptr-childoffnum = InvalidOffsetNumber;
ptr-parent = top;
ptr-next = NULL;
tail-next = ptr;
tail = ptr;
}
First, notice that we're setting ptr-parent = top. 'top' is the
current node we're processing, and ptr represents the node to the right
of the current node. The current node is *not* the parent of the node to
the right. I believe that line should be ptr-parent = top-parent.
Second, we're adding the entry for the right sibling to the end of the
list of nodes to visit. But when we process entries from the list, we
exit immediately when we see a leaf page. That means that the right
sibling can get queued up behind leaf pages, and thus never visited.
--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com
--
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] Small patch for GiST: move childoffnum to child
On 10.07.2011 21:43, Josh Berkus wrote: Teodor, Oleg, Heikki, My concern is that I am unable to prove to myself simply by reading the code that the 24 line chunk deleted from gistFindPath (near *** 919,947 ) are no longer needed. My familiarity with the gist code is low enough that it is not surprising that I cannot prove this to myself from first principles. I have no reason to believe it is not correct, it is just that I can't convince myself that it is correct. Can one of you weigh in on Jeff's concern here about this patch? As it happens, I'm just looking at it. I believe there's a small bug in the patch, I'm just testing it to verify. Stay tuned! -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- 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] Small patch for GiST: move childoffnum to child
On 30.06.2011 07:50, Jeff Janes wrote:
My concern is that I am unable to prove to myself simply by reading
the code that the 24 line chunk deleted from gistFindPath (near ***
919,947 ) are no longer needed. My familiarity with the gist code
is low enough that it is not surprising that I cannot prove this to
myself from first principles. I have no reason to believe it is not
correct, it is just that I can't convince myself that it is correct.
This is the piece of code we're talking about:
***
*** 919,947 gistFindPath(Relation r, BlockNumber child)
blkno = ItemPointerGetBlockNumber((idxtuple-t_tid));
if (blkno == child)
{
- OffsetNumber poff = InvalidOffsetNumber;
-
- /* make childs links */
- ptr = top;
- while (ptr-parent)
- {
- /* move childoffnum.. */
- if (ptr == top)
- {
- /* first iteration */
- poff = ptr-parent-childoffnum;
- ptr-parent-childoffnum =
ptr-childoffnum;
- }
- else
- {
- OffsetNumber tmp =
ptr-parent-childoffnum;
-
- ptr-parent-childoffnum = poff;
- poff = tmp;
- }
- ptr = ptr-parent;
- }
- top-childoffnum = i;
UnlockReleaseBuffer(buffer);
return top;
}
Now that I look closer at the patch, I think it's in fact incorrect. The
removed code used to store the offset of the downlink in the direct
parent of the child that was searched for, in top-childoffnum. That's
the last removed line: top-childoffnum = i. With the patch, that is
stored nowhere. gistFindPath() needs to return it somehow, so that it
gets updated in the stack returned by gistFindCorrectParent.
Attached is a modified patch that fixes that. I couldn't resist some
cosmetic changes along the way, sorry about that. I made gistFindPath
use a regular List instead of carrying the extra 'next' field in
GISTInsertStack. That seems much cleaner as that field is only needed
for local storage in the highly unlikely case that gistFindPath() is
called. I also made the error cases use elog() instead of assertions.
So I tried provoking situations where this surrounding code section
would get executed, both patched and unpatched. I have been unable to
do so--apparently this code is for an incredibly obscure situation
which I can't induce at will.
You'll need a concurrent split of the root page, while you're splitting
a page at some lower level. For example:
R
L1 L2
R is the root page, and L1 and L2 are leaf pages. Now, imagine that you
insert a tuple into L2, causing it to split into pages L2* and L3. Your
insertion stack looks like R-L2. Before you have a chance to insert the
downlink for L3 into R, someone else splits the root page:
R
I1 I2
L1 L3 L2* L3
The new parent of L2 is the new internal page I2, but
gistFindCorrectParent() will never visit that page. The insertion stack
is R-L2, so gistFindCorrectParent() will only search R, and won't find
the downlink for L2 there anymore.
The only practical way to test that is to use a debugger or add some
debugging statements to the code. Here's what I did:
1. Create a test table and gist index:
CREATE TABLE gisttest (p point);
CREATE INDEX i_gisttest ON gisttest USING gist (p)
2. Insert some test data. Use two different values so that you can
conveniently later insert into distinct branches of the gist tree.
INSERT INTO gisttest SELECT point(1,1) FROM generate_series(1,1000);
INSERT INTO gisttest SELECT point(10,10) FROM generate_series(1,1000);
3. Attach a debugger to the backend process, and create a couple of
breakpoints:
(gdb) break gistSplit
Breakpoint 1 at 0x46ace1: file gist.c, line 1295.
(gdb) break gistFindPath
Breakpoint 2 at 0x469740: file gist.c, line 884.
(gdb) cont
Continuing.
4. Insert some more tuples to the table using the debugged backend:
INSERT INTO gisttest SELECT point(1,1) FROM generate_series(1,1000);
This hits the breakpoint at gistSplit:
Breakpoint 1, gistSplit (r=0x7f84f4bad328, page=0x7f84f1b8b180 ,
itup=0x2032118, len=186, giststate=0x7fff8615e9e0) at gist.c:1295
1295SplitedPageLayout *res = NULL;
5. The
Re: [HACKERS] Small patch for GiST: move childoffnum to child
Thank you very much for detail explanation. But this line of modified patch seems strange for me: *newchildoffnum = blkno; I believe it should be: *newchildoffnum = i; -- With best regards, Alexander Korotkov.
Re: [HACKERS] Small patch for GiST: move childoffnum to child
On 13.07.2011 21:56, Alexander Korotkov wrote: Thank you very much for detail explanation. But this line of modified patch seems strange for me: *newchildoffnum = blkno; I believe it should be: *newchildoffnum = i; Yes, you're right. It's scary that it worked during testing anyway. Maybe the resulting tree was indeed broken but it didn't affect the subsequent inserts so I didn't notice. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- 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] Small patch for GiST: move childoffnum to child
Teodor, Oleg, Heikki, My concern is that I am unable to prove to myself simply by reading the code that the 24 line chunk deleted from gistFindPath (near *** 919,947 ) are no longer needed. My familiarity with the gist code is low enough that it is not surprising that I cannot prove this to myself from first principles. I have no reason to believe it is not correct, it is just that I can't convince myself that it is correct. Can one of you weigh in on Jeff's concern here about this patch? -- Josh Berkus PostgreSQL Experts Inc. http://pgexperts.com -- 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] Small patch for GiST: move childoffnum to child
Hi Jeff, Thank you for review. On Thu, Jun 30, 2011 at 8:50 AM, Jeff Janes jeff.ja...@gmail.com wrote: So I tried provoking situations where this surrounding code section would get executed, both patched and unpatched. I have been unable to do so--apparently this code is for an incredibly obscure situation which I can't induce at will. Yes, it also seems pretty hard to get this code section executed for me. I'm going to ask Teodor and Oleg about it. -- With best regards, Alexander Korotkov.
Re: [HACKERS] Small patch for GiST: move childoffnum to child
On Tue, Jun 28, 2011 at 10:21 AM, Alexander Korotkov aekorot...@gmail.com wrote: Actually, there is no more direct need of this patch because I've rewrote insert function for fast build. But there are still two points for having this changes: 1) As it was noted before, it simplifies code a bit. 2) It would be better if childoffnum have the same semantics in regular insert and fastbuild insert. Hi Alexander, I've looked at your patch and have done a partial review. It applies cleanly and makes without warnings, and passes make check plus some additional testing I've done (inserting lots of stuff into regression's test_tsvector table, in parallel, with the gist index in place) under --enable-cassert. I repeated that test without --enable-cassert, and saw no degradation in performance over unpatched code. No changes to documentation or make check code should be needed. The formatting looks OK. My concern is that I am unable to prove to myself simply by reading the code that the 24 line chunk deleted from gistFindPath (near *** 919,947 ) are no longer needed. My familiarity with the gist code is low enough that it is not surprising that I cannot prove this to myself from first principles. I have no reason to believe it is not correct, it is just that I can't convince myself that it is correct. So I tried provoking situations where this surrounding code section would get executed, both patched and unpatched. I have been unable to do so--apparently this code is for an incredibly obscure situation which I can't induce at will. I would love to use this as an opportunity to study the gist code until I can convince myself this patch is correct, but I'm afraid I won't be able to do that promptly, or for the remainder of this commit fest. Since Heikki has already looked at this patch, perhaps he can provide the assurance that I cannot, or another reviewer can. Sorry I couldn't do a more thorough review, Jeff -- 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] Small patch for GiST: move childoffnum to child
Actually, there is no more direct need of this patch because I've rewrote insert function for fast build. But there are still two points for having this changes: 1) As it was noted before, it simplifies code a bit. 2) It would be better if childoffnum have the same semantics in regular insert and fastbuild insert. -- With best regards, Alexander Korotkov.
Re: [HACKERS] Small patch for GiST: move childoffnum to child
On 24.05.2011 15:22, Alexander Korotkov wrote: During preparing patch of my GSoC project I found reasonable to move childoffnum (GISTInsertStack structure) from parent to child. This means that now child have childoffnum of parent's link to child. It allows to maintain entire parts of tree in that GISTInsertStack structures. Also it simplifies existing code a bit. Heikki advice me that since this change simplifies existing code it can be considered as a separate patch. Looks good to me. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
