Insertion algorithm in a nutshell:
1. Calculate hash value
2. Take 4 least-significant bits of the hash value. These tell you which
partition the value belongs to.
3. Lock that partition
4. Take the X (X > 4) least significant bits of the hash value. These
tell you which hash bucket the value belongs to.
5. Add value to that hash bucket. A bucket is implemented as a linked
list. Also called a "hash chain" in the README.
6. Unlock partition
Cui Shijun wrote:
> Ah... It seems that a item is calculated its hash value, get the bucket
> number from it and insert into that bucket "chain". The insertion has
> nothing to do with partition number(but Alvaro says "which hash is
> used depends on the partition number". I haven't really understood
> this: how can we get a hash value without deciding which hash to
> use? ). However, when we travel along a chain to get a item, we can
> infer its partition number from its hash value.
> My problem is, I'm not so sure about the process stated above,
> because in that way, items in ONE chain may belong to different
> partitions,and it is obviously conflicted with "so that different
> partitions use different hash chains" as README mentioned.
> 2007/4/28, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>:
>> It's not that hard: the bucket number is some number of low-order bits
>> of the hash value, and the partition number is some smaller (or at most
>> equal) number of low-order bits of the hash value.
>> regards, tom lane
In response to
pgsql-hackers by date
|Next:||From: Heikki Linnakangas||Date: 2007-04-28 08:08:34|
|Subject: Re: When the locially dropped column is also physically
|Previous:||From: Cui Shijun||Date: 2007-04-28 06:10:33|
|Subject: Re: Fwd: How does the partitioned lock manager works?|