Re: Hash Indexes

On Thu, Sep 8, 2016 at 12:32 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:
> Hmm.  I think page or block is a concept of database systems and
> buckets is a general concept used in hashing technology.  I think the
> difference is that there are primary buckets and overflow buckets. I
> have checked how they are referred in one of the wiki pages [1],
> search for overflow on that wiki page. Now, I think we shouldn't be
> inconsistent in using them. I will change to make it same if I find
> any inconsistency based on what you or other people think is the
> better way to refer overflow space.

In the existing source code, the terminology 'overflow page' is
clearly preferred to 'overflow bucket'.

[rhaas pgsql]$ git grep 'overflow page' | wc -l     75
[rhaas pgsql]$ git grep 'overflow bucket' | wc -l      1

In our off-list conversations, I too have found it very confusing when
you've made reference to an overflow bucket.  A hash table has a fixed
number of buckets, and depending on the type of hash table the storage
for each bucket may be linked together into some kind of a chain;
here, a chain of pages.  The 'bucket' logically refers to all of the
entries that have hash codes such that (hc % nbuckets) == bucketno,
regardless of which pages contain them.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company