Re: Performance degradation in TPC-H Q18

On Wed, Mar 1, 2017 at 9:38 AM, Andres Freund <andres(at)anarazel(dot)de> wrote:
> Hi,
>
> On 2017-03-01 09:33:07 +0530, Kuntal Ghosh wrote:
>> On Wed, Mar 1, 2017 at 9:19 AM, Andres Freund <andres(at)anarazel(dot)de> wrote:
>> >> So, I was looking for other alternatives and I've found one called
>> >> RobinHood hashing.
>> >
>> > simplehash.h implements robin hood hashing.
>
>> But, it doesn't implement the swapping idea, right?
>
> It does, that's the if (insertdist > curdist) block in SH_INSERT.
> Unless I misunderstand what you're proposing?
>
I think the idea of the existing implementation is:

if (insertdist > curdist)
{
find an empty space at the end of the cluster.
shift all the followers by 1 position to make space for the element to
be inserted.
insert the element at the current place.
}

What I'm trying to say is:

if (insertdist > curdist)
{
swap the entry to be inserted with the current entry.
Try to insert the current entry in the same logic.
}

So, the second approach will not cause all the followers to be shifted by 1.

--
Thanks & Regards,
Kuntal Ghosh
EnterpriseDB: http://www.enterprisedb.com