Re: Bug in new buffering GiST build code

On 22.05.2012 01:09, Alexander Korotkov wrote:
> Hi!
>
> On Tue, May 22, 2012 at 12:56 AM, Heikki Linnakangas<
> heikki.linnakangas@enterprisedb.com>  wrote:
>
>> The management of the path stacks is a bit complicated, anyway. I'll think
>> about this some more tomorrow, maybe we can make it simpler, knowing that
>> we have to do those extra lookups.
>
> WOW! You did enormous work on exploring that!
> I just arrived from PGCon and start looking at it when find you've already
> done comprehensive research of this problem.
> On the step 5 if we've NSN in GISTBufferingInsertStack structure, we could
> detect situation of changing parent of splitted page. Using this we could
> save copy of GISTBufferingInsertStack for B2 with original parent A,
> because we know split of B to occur after creating GISTBufferingInsertStack
> but before split of A. The question is how to find this copy from C, hash?

I tested a patch that adds the extra getNodeBuffer() call after
refinding the parent, as discussed. However, I'm still getting a "failed
to-refind parent" error later in the build, so I think we're still
missing some corner case.

I think we should rewrite the way we track the parents completely.
Rather than keep a path stack attached to every node buffer, let's just
maintain a second hash table that contains the parent of every internal
node. Whenever a downlink is moved to another page, update the hash
table with the new information. That way we always have up-to-date
information about the parent of every internal node.

That's much easier to understand than the path stack structures we have
now. I think the overall memory consumption will be about the same too.
Although we need the extra hash table with one entry for every internal
node, we get rid of the path stack structs, which are also one per every
internal node at the moment.

I believe it is faster too. I added some instrumentation to the existing
gist code (with the additional getNodeBuffer() call added to fix this
bug), to measure the time spent moving right, when refinding the parent
of a page. I added gettimeofday() calls before and after moving right,
and summed the total. In my test case, the final index size was about
19GB, and the index build took 3545 seconds (59 minutes). Of that time,
580 seconds (~ 10 minutes) was spent moving right to refind parents.
That's a lot. I also printed a line whenever a refind operation had to
move right 20 pages or more. That happened 2482 times during the build,
in the worst case we moved right over 40000 pages.

Attached is a patch to replace the path stacks with a hash table. With
this patch, the index build time in my test case dropped from 59 minutes
to about 55 minutes. I don'ẗ know how representative or repeatable this
test case is, but this definitely seems very worthwhile, not only
because it fixes the bug and makes the code simpler, but also on
performance grounds.

Alexander, do you still have the test environments and data lying around
that you used for GiST buffering testing last summer? Could you rerun
some of those tests with this patch?

--
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com