Re: Performance degradation in TPC-H Q18

From: Andres Freund <andres(at)anarazel(dot)de>
To: Kuntal Ghosh <kuntalghosh(dot)2007(at)gmail(dot)com>
Cc: Robert Haas <robertmhaas(at)gmail(dot)com>, PostgreSQL-development <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Performance degradation in TPC-H Q18
Date: 2017-03-02 19:56:22
Message-ID: 20170302195622.al7zfc5mdqht327s@alap3.anarazel.de
Views: Raw Message | Whole Thread | Download mbox
Thread:
Lists: pgsql-hackers

On 2017-03-01 11:05:33 +0530, Kuntal Ghosh wrote:
> On Wed, Mar 1, 2017 at 10:53 AM, Andres Freund <andres(at)anarazel(dot)de> wrote:
> > On 2017-03-01 10:47:45 +0530, Kuntal Ghosh wrote:
> >> 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.
> >
> > How not? You'll have to do that game until you found a free slot.
> You can skip increasing the curdist of some elements for which it is
> already pretty high. Suppose, we've the following hash table and an
> element e,
> _,_,_,i,_,_,j,j+1,j+2,_,_
> We want to insert e at i but there is a collision and we start doing
> probing. At j, the condition if (insertdist > curdist) satisfies and
> we'll swap e with the element at j. Now, we try to insert e( = element
> at j) and so on. In this process, if the element at j+1,j+2 has
> already high distance from their optimal location, you can skip those
> element and go ahead. But, in the existing approach, we increase their
> distance further. Thoughts?

All the following elements already are at their "optimal" position given
the previous occupation of the hash-table. As we only start to move
once the insert-distance of the existing element is lower than the one
of the to-be-inserted one, the following elements will all be moved.
Doing the swap on a element-by-element basis would be possible, but just
achieves the same result at a higher cost.

Regards,

Andres

In response to

Browse pgsql-hackers by date

  From Date Subject
Next Message Alvaro Herrera 2017-03-02 21:35:44 Re: patch: function xmltable
Previous Message Andres Freund 2017-03-02 19:52:48 Re: Performance degradation in TPC-H Q18