Message-ID: <4E7765B0.4000900@gmail.com>
Date: Mon, 19 Sep 2011 18:54:24 +0300
From: Vitalii Tymchyshyn <tivv00@gmail.com>
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US;
	rv:1.9.2.18) Gecko/20110617 Lightning/1.0b2 Thunderbird/3.1.11
MIME-Version: 1.0
To: Robert Klemme <shortcutter@googlemail.com>
CC: Merlin Moncure <mmoncure@gmail.com>, Stefan Keller <sfkeller@gmail.com>,
	Jeff Janes <jeff.janes@gmail.com>,
	Peter Geoghegan <peter@2ndquadrant.com>, pgsql-performance@postgresql.org
Subject: Re: Hash index use presently(?) discouraged since 2005:
	revive or bury it?
References: 
 <CAFcOn293Rzi7cZYWBT8tjxCtNX5pYdbknANXgf9mWfBizK8Frg@mail.gmail.com>
	<CAEYLb_Udue8_XSE9K0KMqKBE_62yurv1bY4Wc+qJoGykZ_rXtA@mail.gmail.com>
	<CAMkU=1x7EsbLh8oxYtXKWzDx5HUDxQ2Vb4sFDCVY0FE8rnttSg@mail.gmail.com>
	<CAHyXU0wPJkYhQLioswNRe6YmXcC_JKZmDxXsb1jcLHo8+BuJkw@mail.gmail.com>
	<CAFcOn2_NnrzquFQ+YPw2vh=ioC+KXcE1NdEJZWG4O7pmY1Eu3Q@mail.gmail.com>
	<CAHyXU0yExA3sBDy1o1vJ57g5pTV5MQ_Z7HXhBo9Pv0+Zg-moHg@mail.gmail.com>
	<CAM9pMnNUoOnLye5iPqGu15K43Nus=xtCL_rRW5LRt3UJ3vqDQQ@mail.gmail.com>
In-Reply-To: 
 <CAM9pMnNUoOnLye5iPqGu15K43Nus=xtCL_rRW5LRt3UJ3vqDQQ@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit

19.09.11 18:19, Robert Klemme написав(ла):
>
> I still haven't seen a solution to locking when a hash table needs
> resizing.  All hashing algorithms I can think of at the moment would
> require a lock on the whole beast during the resize which makes this
> type of index impractical for certain loads (heavy updating).
Sorry for the second reply, I should have not start writing until I've 
read all your post. Anyway.
Do you need read lock? I'd say readers could use "old" copy of hash 
table up until the moment new bigger copy is ready. This will simply 
look like the update is not started yet, which AFAIK is OK for MVCC.
Yep, all the writers will wait.

Another option could be to start background build of larger hash - for 
some time your performance will be degraded since you are writing to two 
indexes instead of one plus second one is rebuilding, but I'd say low 
latency solution is possible here.

One more: I don't see actually why can't you have a "rolling" expand of 
hash table. I will try to describe it correct me if I am wrong:
1) The algorithm I am talking about will take "n" bits from hash code to 
for hash table. So, during expansion it will double number of baskets.
2) Say, we are going from 2^n = n1 to 2^(n+1) = n2 = n1 * 2 baskets. 
Each new pair of baskets will take data from single source basket 
depending on the value of new hash bit used. E.g. if n were 2, we've had 
4 baskets and new table will have 8 baskets. Everything from old basket 
#1 will go into new baskets #2 and #3 depending on hash value.
3) So, we can have a counter on number of baskets processed. Any 
operation on any lower numbered basket will go to "new set". Any 
operation on any higher numbered basket will go to "old set". Any 
operation on currently converting basket will block until conversion is 
done.

P.S. Sorry for a lot of possibly dumb thoughts, I don't know why I've 
got such a though stream on this topic :)

Best regards, Vitalii Tymchyshyn.