Re: Fwd: How does the partitioned lock manager works?

[Heikki Linnakangas <heikki(at)enterprisedb(dot)com>]

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


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