Opensource internals

PostgreSQL Hashes Lookups

54 min read Jay Hubbert

PostgreSQL has two hash tables: dynahash, a chained table in shared memory that grows one bucket at a time, and simplehash, a templated open-addressing table that resizes without rehashing a single key.

Every hash table in PostgreSQL is one of two things, and the difference between them explains a surprising amount of PostgreSQL’s behaviour. One is dynahash: a chained hash table that lives in shared memory, that never moves an entry once it is placed, and that grows by adding exactly one bucket at a time. The other is simplehash: a table generated from a C template, using open addressing with robin-hood insertion, that resizes its entire array in one memcpy-flavoured operation and never has to rehash a single key.

They are not interchangeable, and they are not supposed to be. The header of dynahash says so, in the source, in the first fifty lines (src/backend/utils/hash/dynahash.c):

c 
 * Compared to simplehash, dynahash has the following benefits:
 *
 * - It supports partitioning, which is useful for shared memory access using
 *   locks.
 * - Shared memory hashes are allocated in a fixed size area at startup and
 *   are discoverable by name from other processes.
 * - Because entries don't need to be moved in the case of hash conflicts,
 *   dynahash has better performance for large entries.
 * - Guarantees stable pointers to entries.

Four benefits, and every one of them is a constraint that a general-purpose open-addressing table cannot satisfy. Partitioning. Fixed address. Stable pointers. Large entries. That is the trade: dynahash is slower per lookup and much more awkward to use, but it can be shared between processes at a fixed address, locked a partition at a time, and hold pointers to entries that remain valid for the lifetime of the table.

This is a walk through how both of them work, based on reading the PostgreSQL source (version 20devel, commit e75fcc9867f).

The shape of a dynahash table

A dynahash table has two halves. The header (HASHHDR) holds everything that can change at runtime; the control block (HTAB) holds the function pointers and the local, per-backend copy of a few fields.

c 
struct HASHHDR
{
	/*
	 * The freelist can become a point of contention in high-concurrency hash
	 * tables, so we use an array of freelists, each with its own mutex and
	 * nentries count, instead of just a single one.  Although the freelists
	 * normally operate independently, we will scavenge entries from freelists
	 * other than a hashcode's default freelist when necessary.
	 *
	 * If the hash table is not partitioned, only freeList[0] is used and its
	 * spinlock is not used at all; callers' locking is assumed sufficient.
	 */
	FreeListData freeList[NUM_FREELISTS];

	/* These fields can change, but not in a partitioned table */
	/* Also, dsize can't change in a shared table, even if unpartitioned */
	int64		dsize;			/* directory size */
	int64		nsegs;			/* number of allocated segments (<= dsize) */
	uint32		max_bucket;		/* ID of maximum bucket in use */
	uint32		high_mask;		/* mask to modulo into entire table */
	uint32		low_mask;		/* mask to modulo into lower half of table */

	/* These fields are fixed at hashtable creation */
	Size		keysize;		/* hash key length in bytes */
	Size		entrysize;		/* total user element size in bytes */
	int64		num_partitions; /* # partitions (must be power of 2), or 0 */
	int64		max_dsize;		/* 'dsize' limit if directory is fixed size */
	int			nelem_alloc;	/* number of entries to allocate at once */
	bool		isfixed;		/* if true, don't enlarge */

	/* Current directory.  In shared tables, this doesn't change */
	HASHSEGMENT *dir;

#ifdef HASH_STATISTICS

	/*
	 * Count statistics here.  NB: stats code doesn't bother with mutex, so
	 * counts could be corrupted a bit in a partitioned table.
	 */
	uint64		accesses;
	uint64		collisions;
	uint64		expansions;
#endif
};

Two masks, one directory, and a max_bucket. That is the whole geometry.

The constants that define it are few and small:

c 
#define HASH_SEGSIZE			   256
#define HASH_SEGSIZE_SHIFT	   8	/* must be log2(HASH_SEGSIZE) */
#define DEF_DIRSIZE			   256

/* Number of freelists to be used for a partitioned hash table. */
#define NUM_FREELISTS			32
ConstantValueMeaning
HASH_SEGSIZE256bucket headers per segment
HASH_SEGSIZE_SHIFT8log2(HASH_SEGSIZE), used to split a bucket number into segment index and slot
DEF_DIRSIZE256minimum number of directory entries
NUM_FREELISTS32freelists in a partitioned table

The directory of segments

The buckets are not one flat array. They are arranged in a two-level structure: a directory of pointers to segments, each segment being an array of 256 bucket headers. The header comment says why:

c 
/*
 * A hash table has a top-level "directory", each of whose entries points to a
 * "segment" of HASH_SEGSIZE bucket headers.  The maximum number of hash
 * buckets is thus dsize * HASH_SEGSIZE (but dsize may be expansible).  Of
 * course, the number of records in the table can be larger, but we don't want
 * a whole lot of records per bucket or performance goes down.
 *
 * In a hash table allocated in shared memory, the directory cannot be
 * expanded because it must stay at a fixed address.  The directory size is
 * chosen at creation based on the initial number of elements, so even though
 * we support allocating more elements later, performance will suffer if the
 * table grows much beyond the initial size.  (Currently, shared memory hash
 * tables are only created by ShmemRequestHash()/ShmemInitHash() though, which
 * doesn't support growing at all.)
 */

The indirection through a directory exists so that a table can grow without moving the bucket headers themselves. A segment is allocated once and never moved; adding capacity means adding a pointer to the directory. And since the directory of a shared-memory table has to stay at a fixed address, dsize there is frozen:

c 
	/* SHM hash tables have a fixed directory. */
	if (hashp->isshared)
		hctl->max_dsize = hctl->dsize;

Turning a bucket number into a bucket header is two shifts and a mask, done in hash_initial_lookup():

c 
static inline uint32
hash_initial_lookup(HTAB *hashp, uint32 hashvalue, HASHBUCKET **bucketptr)
{
	HASHHDR    *hctl = hashp->hctl;
	HASHSEGMENT segp;
	int64		segment_num;
	int64		segment_ndx;
	uint32		bucket;

	bucket = calc_bucket(hctl, hashvalue);

	segment_num = bucket >> HASH_SEGSIZE_SHIFT;
	segment_ndx = MOD(bucket, HASH_SEGSIZE);

	segp = hashp->dir[segment_num];

	if (segp == NULL)
		hash_corrupted(hashp);

	*bucketptr = &segp[segment_ndx];
	return bucket;
}

And MOD is the fast path:

c 
/*
 * Fast MOD arithmetic, assuming that y is a power of 2 !
 */
#define MOD(x,y)			   ((x) & ((y)-1))

Two masks and a power of two

The bucket count is always a power of two, which is what lets the whole thing use masks instead of divisions. init_htab() sets it up:

c 
	/*
	 * Allocate space for the next greater power of two number of buckets,
	 * assuming a desired maximum load factor of 1.
	 */
	nbuckets = next_pow2_int(nelem);

	/*
	 * In a partitioned table, nbuckets must be at least equal to
	 * num_partitions; were it less, keys with apparently different partition
	 * numbers would map to the same bucket, breaking partition independence.
	 * (Normally nbuckets will be much bigger; this is just a safety check.)
	 */
	while (nbuckets < hctl->num_partitions)
		nbuckets <<= 1;

	hctl->max_bucket = hctl->low_mask = nbuckets - 1;
	hctl->high_mask = (nbuckets << 1) - 1;

Two masks, not one. low_mask covers the lower half of the current table size and high_mask covers twice that. The bucket function is a two-step reduction:

c 
/* Convert a hash value to a bucket number */
static inline uint32
calc_bucket(HASHHDR *hctl, uint32 hash_val)
{
	uint32		bucket;

	bucket = hash_val & hctl->high_mask;
	if (bucket > hctl->max_bucket)
		bucket = bucket & hctl->low_mask;

	return bucket;
}

Read it as: mask down to the current hash space; if the result is beyond the buckets that actually exist, fold it back into the lower half. So:

nbuckets (initial)low_maskhigh_maskbuckets in use initially
87150–7
1615310–15
3231630–31
64631270–63
1281272550–127

The two-mask scheme is what makes incremental growth possible. A table of 8 buckets has a hash space of 16 (high_mask = 15). Growing it means creating bucket 8, then 9, then 10, and so on, up to bucket 15 — and only when the table reaches 16 buckets in use do the masks double, at which point the hash space becomes 32.

The important consequence, and the reason for the whole exercise, is that growing the table never requires rehashing every key. In a conventional open-addressing table, doubling the array means recomputing every key’s bucket index, because the modulus changed. Here the mask changes, but the entries are not redistributed by rehashing — only one old bucket is split, and only the entries that land in the new bucket move.

The partition trick

Note the shape of calc_bucket(): it uses the low-order bits of the hash value to select the bucket. That is deliberate, and the file header spells out the consequence:

c 
 * This lets any subset of the hash buckets be treated as a separately
 * lockable partition.  We expect callers to use the low-order bits of a
 * lookup key's hash value as a partition number --- this will work because
 * of the way calc_bucket() maps hash values to bucket numbers.

Because the bucket is a function of the low bits of the hash, so is the partition. If partition p is defined as hashcode % p, then every key in partition p lands in a bucket that only ever holds keys from partition p. The buckets belonging to one partition are therefore an independent subtable, and can be locked on their own.

The entry layout

An entry in a dynahash table is a small header followed by the caller’s data, with the key at the start of the caller’s data. The header (src/include/utils/hsearch.h):

c 
/*
 * HASHELEMENT is the private part of a hashtable entry.  The caller's data
 * follows the HASHELEMENT structure (on a MAXALIGN'd boundary).  The hash key
 * is expected to be at the start of the caller's hash entry data structure.
 */
typedef struct HASHELEMENT
{
	struct HASHELEMENT *link;	/* link to next entry in same bucket */
	uint32		hashvalue;		/* hash function result for this entry */
} HASHELEMENT;

Two fields: a pointer to the next entry in the same bucket, and the hash value. The key follows, at a MAXALIGN’d boundary:

c 
/*
 * Key (also entry) part of a HASHELEMENT
 */
#define ELEMENTKEY(helem)  (((char *)(helem)) + MAXALIGN(sizeof(HASHELEMENT)))

/*
 * Obtain element pointer given pointer to key
 */
#define ELEMENT_FROM_KEY(key)  \
	((HASHELEMENT *) (((char *) (key)) - MAXALIGN(sizeof(HASHELEMENT))))

Note that HASHELEMENT carries the hash value with the entry. That is not decoration: it lets the chain walk reject a non-matching entry with a single 32-bit comparison instead of a memcmp of the whole key. Here is the entire chain-walking loop from hash_search_with_hash_value():

c 
	/*
	 * Follow collision chain looking for matching key
	 */
	match = hashp->match;		/* save one fetch in inner loop */
	keysize = hashp->keysize;	/* ditto */

	while (currBucket != NULL)
	{
		if (currBucket->hashvalue == hashvalue &&
			match(ELEMENTKEY(currBucket), keyPtr, keysize) == 0)
			break;
		prevBucketPtr = &(currBucket->link);
		currBucket = *prevBucketPtr;
#ifdef HASH_STATISTICS
		hctl->collisions++;
#endif
	}

The hash value is compared first, and only on a match is the full key comparison performed. On a 32-bit hash, a false positive requires the colliding pair to have identical hash values, which is 1 in 2^32 — so the memcmp is almost never executed for a non-matching entry.

Growth, one bucket at a time

Now the interesting part. Here is expand_table() in full (src/backend/utils/hash/dynahash.c):

c 
/*
 * Expand the table by adding one more hash bucket.
 */
static bool
expand_table(HTAB *hashp)
{
	HASHHDR    *hctl = hashp->hctl;
	HASHSEGMENT old_seg,
				new_seg;
	int64		old_bucket,
				new_bucket;
	int64		new_segnum,
				new_segndx;
	int64		old_segnum,
				old_segndx;
	HASHBUCKET *oldlink,
			   *newlink;
	HASHBUCKET	currElement,
				nextElement;

	Assert(!hctl->isfixed);
	Assert(!IS_PARTITIONED(hctl));

#ifdef HASH_STATISTICS
	hctl->expansions++;
#endif

	new_bucket = hctl->max_bucket + 1;
	new_segnum = new_bucket >> HASH_SEGSIZE_SHIFT;
	new_segndx = MOD(new_bucket, HASH_SEGSIZE);

	if (new_segnum >= hctl->nsegs)
	{
		/* Allocate new segment if necessary -- could fail if dir full */
		if (new_segnum >= hctl->dsize)
			if (!dir_realloc(hashp))
				return false;
		if (!(hashp->dir[new_segnum] = seg_alloc(hashp)))
			return false;
		hctl->nsegs++;
	}

	/* OK, we created a new bucket */
	hctl->max_bucket++;

	/*
	 * *Before* changing masks, find old bucket corresponding to same hash
	 * values; values in that bucket may need to be relocated to new bucket.
	 * Note that new_bucket is certainly larger than low_mask at this point,
	 * so we can skip the first step of the regular hash mask calc.
	 */
	old_bucket = (new_bucket & hctl->low_mask);

	/*
	 * If we crossed a power of 2, readjust masks.
	 */
	if ((uint32) new_bucket > hctl->high_mask)
	{
		hctl->low_mask = hctl->high_mask;
		hctl->high_mask = (uint32) new_bucket | hctl->low_mask;
	}

	/*
	 * Relocate records to the new bucket.  NOTE: because of the way the hash
	 * masking is done in calc_bucket, only one old bucket can need to be
	 * split at this point.  With a different way of reducing the hash value,
	 * that might not be true!
	 */
	old_segnum = old_bucket >> HASH_SEGSIZE_SHIFT;
	old_segndx = MOD(old_bucket, HASH_SEGSIZE);

	old_seg = hashp->dir[old_segnum];
	new_seg = hashp->dir[new_segnum];

	oldlink = &old_seg[old_segndx];
	newlink = &new_seg[new_segndx];

	for (currElement = *oldlink;
		 currElement != NULL;
		 currElement = nextElement)
	{
		nextElement = currElement->link;
		if ((int64) calc_bucket(hctl, currElement->hashvalue) == old_bucket)
		{
			*oldlink = currElement;
			oldlink = &currElement->link;
		}
		else
		{
			*newlink = currElement;
			newlink = &currElement->link;
		}
	}
	/* don't forget to terminate the rebuilt hash chains... */
	*oldlink = NULL;
	*newlink = NULL;

	return true;
}

Step by step:

  1. new_bucket = hctl->max_bucket + 1. One bucket. Not two, not a doubling.
  2. If the new bucket falls in a segment that doesn’t exist yet, allocate a new 256-entry segment and add a pointer to it in the directory. If the directory itself is full, double the directory (non-shared tables only).
  3. hctl->max_bucket++. Now calc_bucket() can produce new_bucket as a result.
  4. Compute the one old bucket that will be split: old_bucket = new_bucket & low_mask.
  5. If we have just crossed a power of two, adjust the masks: low_mask = high_mask, high_mask = new_bucket | low_mask.
  6. Walk the chain of old_bucket once. Each entry is re-tested with calc_bucket() under the new masks; entries that still hash to old_bucket stay, the rest are pushed onto the new bucket’s chain.

No entry is ever moved in memory. The HASHELEMENT structs stay exactly where they were allocated; only the link pointers are rewritten. That is the “Guarantees stable pointers to entries” promise in the file header, and it is why dynahash can be used for things where a caller holds a pointer to an entry for weeks.

Why can only one bucket be split? Because of how calc_bucket() reduces the hash. When max_bucket is one below a power of two, the hash space is 2 * nbuckets and buckets 0..nbuckets-1 are “full” in the sense that every hash value in the lower half and the upper half maps into them. When you add the first bucket of the new half of the hash space, only the entries whose upper-half hash bits happen to land on it need to move — and all of those live in exactly one old bucket, because the old bucket for a given upper-half value is value & low_mask.

Note the comment on the split itself:

NOTE: because of the way the hash masking is done in calc_bucket, only one old bucket can need to be split at this point. With a different way of reducing the hash value, that might not be true!

That is a load-bearing comment. The whole “grow by one bucket” scheme depends on the low-bit reduction. Change the reduction and you get an O(n) rehash.

When expansion happens

Expansion is triggered from hash_search_with_hash_value(), before the lookup, and only on an insert:

c 
	/*
	 * If inserting, check if it is time to split a bucket.
	 *
	 * NOTE: failure to expand table is not a fatal error, it just means we
	 * have to run at higher fill factor than we wanted.  However, if we're
	 * using the palloc allocator then it will throw error anyway on
	 * out-of-memory, so we must do this before modifying the table.
	 */
	if (action == HASH_ENTER || action == HASH_ENTER_NULL)
	{
		/*
		 * Can't split if running in partitioned mode, nor if frozen, nor if
		 * table is the subject of any active hash_seq_search scans.
		 */
		if (hctl->freeList[0].nentries > (int64) hctl->max_bucket &&
			!hctl->isfixed && !IS_PARTITIONED(hctl) && !hashp->frozen &&
			!has_seq_scans(hashp))
			(void) expand_table(hashp);
	}

Four separate conditions block the split, and each of them is a design decision worth understanding:

  • hctl->isfixed — the table has a hard size limit (HASH_FIXED_SIZE).
  • IS_PARTITIONED(hctl) — see below.
  • hashp->frozen — the table has been frozen with hash_freeze().
  • has_seq_scans(hashp) — see below.

And the trigger condition itself is a load factor of 1: grow when nentries > max_bucket, i.e. when the number of live entries exceeds the number of buckets. At that point the chain lengths start to become interesting.

The failure mode is graceful: expand_table() can fail (out of memory, directory full) and the table simply runs at a higher fill factor.

Allocating entries in chunks

Entries are not allocated one at a time. They are allocated in blocks, and the block size is chosen by choose_nelem_alloc():

c 
/*
 * Given the user-specified entry size, choose nelem_alloc, ie, how many
 * elements to add to the hash table when we need more.
 */
static int
choose_nelem_alloc(Size entrysize)
{
	int			nelem_alloc;
	Size		elementSize;
	Size		allocSize;

	/* Each element has a HASHELEMENT header plus user data. */
	/* NB: this had better match element_alloc() */
	elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(entrysize);

	/*
	 * The idea here is to choose nelem_alloc at least 32, but round up so
	 * that the allocation request will be a power of 2 or just less. This
	 * makes little difference for hash tables in shared memory, but for hash
	 * tables managed by palloc, the allocation request will be rounded up to
	 * a power of 2 anyway.  If we fail to take this into account, we'll waste
	 * as much as half the allocated space.
	 */
	allocSize = 32 * 4;			/* assume elementSize at least 8 */
	do
	{
		allocSize <<= 1;
		nelem_alloc = allocSize / elementSize;
	} while (nelem_alloc < 32);

	return nelem_alloc;
}

At least 32 elements per allocation, rounded so that the request size is close to a power of two. The reasoning is about palloc’s allocator: if you ask for 100 bytes, palloc gives you a 128-byte chunk, and you have wasted 28 bytes per block. Asking for a size that is itself near a power of two wastes at most half.

element_alloc() carves a block into a chain of elements and threads it onto the freelist:

c 
/*
 * allocate some new elements and link them into the indicated free list
 */
static bool
element_alloc(HTAB *hashp, int nelem, int freelist_idx)
{
	HASHHDR    *hctl = hashp->hctl;
	Size		elementSize;
	Size		requestSize;
	char	   *allocedBlock;
	HASHELEMENT *firstElement;
	HASHELEMENT *tmpElement;
	HASHELEMENT *prevElement;
	int			i;

	if (hctl->isfixed)
		return false;

	/* Each element has a HASHELEMENT header plus user data. */
	elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(hctl->entrysize);

	requestSize = nelem * elementSize;
	...
	/* prepare to link all the new entries into the freelist */
	prevElement = NULL;
	tmpElement = firstElement;
	for (i = 0; i < nelem; i++)
	{
		tmpElement->link = prevElement;
		prevElement = tmpElement;
		tmpElement = (HASHELEMENT *) (((char *) tmpElement) + elementSize);
	}

	/* if partitioned, must lock to touch freeList */
	if (IS_PARTITIONED(hctl))
		SpinLockAcquire(&hctl->freeList[freelist_idx].mutex);

	/* freelist could be nonempty if two backends did this concurrently */
	firstElement->link = hctl->freeList[freelist_idx].freeList;
	hctl->freeList[freelist_idx].freeList = prevElement;

	if (IS_PARTITIONED(hctl))
		SpinLockRelease(&hctl->freeList[freelist_idx].mutex);

	return true;
}

The elements in a block are contiguous, elementSize apart. The freelist threads them together by reusing the link field of each HASHELEMENT — a free entry’s link points at the next free entry rather than at the next entry in its bucket. One pointer, two uses, exactly like an arena allocator’s free list.

The 32 freelists

The FreeListData struct is small and, crucially, laid out so that the three things a partitioned table must protect do not share a cache line with another freelist’s:

c 
/*
 * Per-freelist data.
 *
 * In a partitioned hash table, each freelist is associated with a specific
 * set of hashcodes, as determined by the FREELIST_IDX() macro below.
 * nentries tracks the number of live hashtable entries having those hashcodes
 * (NOT the number of entries in the freelist, as you might expect).
 *
 * The coverage of a freelist might be more or less than one partition, so it
 * needs its own lock rather than relying on caller locking.  Relying on that
 * wouldn't work even if the coverage was the same, because of the occasional
 * need to "borrow" entries from another freelist; see get_hash_entry().
 *
 * Using an array of FreeListData instead of separate arrays of mutexes,
 * nentries and freeLists helps to reduce sharing of cache lines between
 * different mutexes.
 */
typedef struct
{
	slock_t		mutex;			/* spinlock for this freelist */
	int64		nentries;		/* number of entries in associated buckets */
	HASHELEMENT *freeList;		/* chain of free elements */
} FreeListData;

Three fields: a spinlock, a live-entry count, and the free chain. The comment about “separate arrays of mutexes, nentries and freeLists” is the whole point: if you had mutexes[32], nentries[32] and freeLists[32] as three parallel arrays, then mutexes[i] and mutexes[i+1] might share a cache line, and every spinlock acquisition on freelist i would invalidate the line holding freelist i+1’s lock. One struct per freelist means each freelist’s hot data is contiguous, and adjacent freelists are unlikely to land in the same line.

Which freelist an entry belongs to is a function of its hash code:

c 
#define IS_PARTITIONED(hctl)  ((hctl)->num_partitions != 0)

#define FREELIST_IDX(hctl, hashcode) \
	(IS_PARTITIONED(hctl) ? (hashcode) % NUM_FREELISTS : 0)

hashcode % 32 — the low five bits, as you would expect. And note the asymmetry: nentries counts live entries with those hash codes, not free entries. That is what makes the load-factor check in hash_search() work: hctl->freeList[0].nentries is the total number of entries in the table (for an unpartitioned table, where freelist 0 is the only one used).

Borrowing from another freelist

Here is the interesting part of get_hash_entry() — what happens when your own freelist is empty:

c 
		/*
		 * No free elements in this freelist.  In a partitioned table, there
		 * might be entries in other freelists, but to reduce contention we
		 * prefer to first try to get another chunk of buckets from the main
		 * shmem allocator.  If that fails, though, we *MUST* root through all
		 * the other freelists before giving up.  There are multiple callers
		 * that assume that they can allocate every element in the initially
		 * requested table size, or that deleting an element guarantees they
		 * can insert a new element, even if shared memory is entirely full.
		 * Failing because the needed element is in a different freelist is
		 * not acceptable.
		 */
		if (!element_alloc(hashp, hctl->nelem_alloc, freelist_idx))
		{
			int			borrow_from_idx;

			if (!IS_PARTITIONED(hctl))
				return NULL;	/* out of memory */

			/* try to borrow element from another freelist */
			borrow_from_idx = freelist_idx;
			for (;;)
			{
				borrow_from_idx = (borrow_from_idx + 1) % NUM_FREELISTS;
				if (borrow_from_idx == freelist_idx)
					break;		/* examined all freelists, fail */

				SpinLockAcquire(&(hctl->freeList[borrow_from_idx].mutex));
				newElement = hctl->freeList[borrow_from_idx].freeList;

				if (newElement != NULL)
				{
					hctl->freeList[borrow_from_idx].freeList = newElement->link;
					SpinLockRelease(&(hctl->freeList[borrow_from_idx].mutex));

					/* careful: count the new element in its proper freelist */
					SpinLockAcquire(&hctl->freeList[freelist_idx].mutex);
					hctl->freeList[freelist_idx].nentries++;
					SpinLockRelease(&hctl->freeList[freelist_idx].mutex);

					return newElement;
				}

				SpinLockRelease(&(hctl->freeList[borrow_from_idx].mutex));
			}

			/* no elements available to borrow either, so out of memory */
			return NULL;
		}

Three levels of fallback:

  1. Take an element from your freelist.
  2. Allocate a fresh chunk of elements.
  3. Borrow an element from another freelist, walking all 32 of them.

The borrowing is not an optimisation, it is a correctness requirement. The comment says why: callers assume that “deleting an element guarantees they can insert a new element, even if shared memory is entirely full”. If freelist 5 held the only free element in the table and a backend keyed into freelist 7 refused to take it, the insert would fail with “out of shared memory” even though memory was available. So the borrow is mandatory.

The one subtlety is the nentries bookkeeping. The borrowed element is counted in the borrowing freelist’s nentries, even though it physically came from the other one — because nentries counts live entries by hash code, and the new entry’s hash code belongs to the borrowing freelist. The comment flags it: /* careful: count the new element in its proper freelist */.

Partitioned tables

A partitioned table is one created with the HASH_PARTITION flag:

c 
#define HASH_PARTITION	0x0001	/* Hashtable is used w/partitioned locking */

From the file header:

To use a hash table in partitioned mode, the HASH_PARTITION flag must be given to hash_create. This prevents any attempt to split buckets on-the-fly. Therefore, each hash bucket chain operates independently, and no fields of the hash header change after init except nentries and freeList. (A partitioned table uses multiple copies of those fields, guarded by spinlocks, for additional concurrency.)

A partitioned table never splits buckets. And the rule is enforced at three levels:

  • The HASH_PARTITION flag is checked at creation, and the number of partitions must be a power of two:
c 
	if (flags & HASH_PARTITION)
	{
		/* Doesn't make sense to partition a local hash table */
		Assert(flags & HASH_SHARED_MEM);

		/*
		 * The number of partitions had better be a power of 2. Also, it must
		 * be less than INT_MAX (see init_htab()), so call the int version of
		 * next_pow2.
		 */
		Assert(info->num_partitions == next_pow2_int(info->num_partitions));

		hctl->num_partitions = info->num_partitions;
	}
  • The split itself is refused:
c 
	Assert(!hctl->isfixed);
	Assert(!IS_PARTITIONED(hctl));
  • And the trigger is skipped:
c 
		if (hctl->freeList[0].nentries > (int64) hctl->max_bucket &&
			!hctl->isfixed && !IS_PARTITIONED(hctl) && !hashp->frozen &&
			!has_seq_scans(hashp))
			(void) expand_table(hashp);

Why? Because a bucket split would move entries between buckets, and if two buckets belong to different partitions, the split would move an entry from one partition into another — while holding the lock on only one of them. That would be a data race on the chain pointer. The only safe thing to do for a partitioned table is to make the table big enough up front that the chains stay short.

The upshot: a partitioned table cannot grow. Its bucket count is fixed at creation, determined by nelem. If you underestimate nelem, the table keeps working but its chains get longer and longer, and lookups get slower and slower, with no error and no warning. This is why the shared-memory hash API insists on a good estimate:

c 
 * Note: for a shared-memory hashtable, nelem needs to be a pretty good
 * estimate, since we can't expand the table on the fly.  But an unshared
 * hashtable can be expanded on-the-fly, so it's better for nelem to be
 * on the small side and let the table grow if it's exceeded.  An overly
 * large nelem will penalize hash_seq_search speed without buying much.

Sequential scans and the split hazard

There is one more reason a table might refuse to split: an active hash_seq_search() scan. The mechanism is documented at length:

c 
/*
 * We track active hash_seq_search scans here.  The need for this mechanism
 * comes from the fact that a scan will get confused if a bucket split occurs
 * while it's in progress: it might visit entries twice, or even miss some
 * entirely (if it's partway through the same bucket that splits).  Hence
 * we want to inhibit bucket splits if there are any active scans on the
 * table being inserted into.  This is a fairly rare case in current usage,
 * so just postponing the split until the next insertion seems sufficient.
 *
 * Given present usages of the function, only a few scans are likely to be
 * open concurrently; so a finite-size stack of open scans seems sufficient,
 * and we don't worry that linear search is too slow.  Note that we do
 * allow multiple scans of the same hashtable to be open concurrently.
 *
 * This mechanism can support concurrent scan and insertion in a shared
 * hashtable if it's the same backend doing both.  It would fail otherwise,
 * but locking reasons seem to preclude any such scenario anyway, so we don't
 * worry.
 *
 * This arrangement is reasonably robust if a transient hashtable is deleted
 * without notifying us.  The absolute worst case is we might inhibit splits
 * in another table created later at exactly the same address.  We will give
 * a warning at transaction end for reference leaks, so any bugs leading to
 * lack of notification should be easy to catch.
 */

#define MAX_SEQ_SCANS 100

static HTAB *seq_scan_tables[MAX_SEQ_SCANS];	/* tables being scanned */
static int	seq_scan_level[MAX_SEQ_SCANS];	/* subtransaction nest level */
static int	num_seq_scans = 0;

A scan holds a cursor into one bucket’s chain. If that bucket is split underneath it, the cursor now points into a chain whose tail has been rewired — the scan could visit entries twice or skip them entirely. So the split is postponed until the next insertion, by which time the scan is probably finished.

The registry is a fixed-size stack of 100 entries. Exceed it and you get an error:

c 
	if (num_seq_scans >= MAX_SEQ_SCANS)
		elog(ERROR, "too many active hash_seq_search scans, cannot start one on \"%s\"",
			 hashp->tabname);

And leaked scans are reported at transaction end:

c 
	if (isCommit)
	{
		int			i;

		for (i = 0; i < num_seq_scans; i++)
		{
			elog(WARNING, "leaked hash_seq_search scan for hash table %p",
				 seq_scan_tables[i]);
		}
	}

There is a related escape hatch: hash_freeze() prevents all further insertions, which means no more splits, which means no more need to register scans:

c 
/*
 * hash_freeze
 *			Freeze a hashtable against future insertions (deletions are
 *			still allowed)
 *
 * The reason for doing this is that by preventing any more bucket splits,
 * we no longer need to worry about registering hash_seq_search scans,
 * and thus caller need not be careful about ensuring hash_seq_term gets
 * called at the right times.
 */

HASH_REMOVE returns a dangling pointer

One API wart deserves its own section, because it is a genuine footgun. The documentation of hash_search() says:

c 
 * Return value is a pointer to the element found/entered/removed if any,
 * or NULL if no match was found.  (NB: in the case of the REMOVE action,
 * the result is a dangling pointer that shouldn't be dereferenced!)

And the implementation says the same thing in more detail:

c 
				/*
				 * better hope the caller is synchronizing access to this
				 * element, because someone else is going to reuse it the next
				 * time something is added to the table
				 */
				return ELEMENTKEY(currBucket);

What actually happens on a remove is:

c 
				/* remove record from hash bucket's chain. */
				*prevBucketPtr = currBucket->link;

				/* add the record to the appropriate freelist. */
				currBucket->link = hctl->freeList[freelist_idx].freeList;
				hctl->freeList[freelist_idx].freeList = currBucket;

The entry is unlinked from its bucket and pushed onto the freelist, all under the same link pointer. From that instant the memory belongs to the freelist, and the next insert will take it and overwrite it. The returned pointer is useful for exactly one thing: identifying which entry was removed, if the caller needs to clean up a side table keyed by entry address. Dereferencing it is undefined behaviour, and in a partitioned table another backend may have already reused it.

Choosing the hash function

hash_create() selects the hash function, the comparison function, the key-copying function and the allocator, based on flags. The default selection:

c 
	/*
	 * Select the appropriate hash function (see comments at head of file).
	 */
	if (flags & HASH_FUNCTION)
	{
		Assert(!(flags & (HASH_BLOBS | HASH_STRINGS)));
		hashp->hash = info->hash;
	}
	else if (flags & HASH_BLOBS)
	{
		Assert(!(flags & HASH_STRINGS));
		/* We can optimize hashing for common key sizes */
		if (info->keysize == sizeof(uint32))
			hashp->hash = uint32_hash;
		else
			hashp->hash = tag_hash;
	}
	else
	{
		/*
		 * string_hash used to be considered the default hash method, and in a
		 * non-assert build it effectively still is.  But we now consider it
		 * an assertion error to not say HASH_STRINGS explicitly.  To help
		 * catch mistaken usage of HASH_STRINGS, we also insist on a
		 * reasonably long string length: if the keysize is only 4 or 8 bytes,
		 * it's almost certainly an integer or pointer not a string.
		 */
		Assert(flags & HASH_STRINGS);
		Assert(info->keysize > 8);

		hashp->hash = string_hash;
	}

The comparison function follows from the hash function:

c 
	/*
	 * If you don't specify a match function, it defaults to string_compare if
	 * you used string_hash, and to memcmp otherwise.
	 *
	 * Note: explicitly specifying string_hash is deprecated, because this
	 * might not work for callers in loadable modules on some platforms due to
	 * referencing a trampoline instead of the string_hash function proper.
	 * Specify HASH_STRINGS instead.
	 */
	if (flags & HASH_COMPARE)
		hashp->match = info->match;
	else if (hashp->hash == string_hash)
		hashp->match = (HashCompareFunc) string_compare;
	else
		hashp->match = memcmp;

So the choice is essentially:

FlagsHashCompareCopy
HASH_STRINGSstring_hashstring_comparestrlcpy
HASH_BLOBS, keysize == 4uint32_hashmemcmpmemcpy
HASH_BLOBS, other keysizetag_hashmemcmpmemcpy
HASH_FUNCTIONyoursmemcmpmemcpy

The hash functions themselves

The default hash for binary keys is Bob Jenkins’ 2006 hash, adapted for PostgreSQL. The file header explains the design decisions:

c 
/*
 * This hash function was written by Bob Jenkins
 * ([email protected]), and superficially adapted
 * for PostgreSQL by Neil Conway. For more information on this
 * hash function, see http://burtleburtle.net/bob/hash/doobs.html,
 * or Bob's article in Dr. Dobb's Journal, Sept. 1997.
 *
 * In the current code, we have adopted Bob's 2006 update of his hash
 * function to fetch the data a word at a time when it is suitably aligned.
 * This makes for a useful speedup, at the cost of having to maintain
 * four code paths (aligned vs unaligned, and little-endian vs big-endian).
 * It also uses two separate mixing functions mix() and final(), instead
 * of a slower multi-purpose function.
 */

mix() and final()

c 
/*----------
 * mix -- mix 3 32-bit values reversibly.
 *
 * This is reversible, so any information in (a,b,c) before mix() is
 * still in (a,b,c) after mix().
 ...
 * This does not achieve avalanche.  There are input bits of (a,b,c)
 * that fail to affect some output bits of (a,b,c), especially of a.  The
 * most thoroughly mixed value is c, but it doesn't really even achieve
 * avalanche in c.
 *----------
 */
#define mix(a,b,c) \
{ \
  a -= c;  a ^= rot(c, 4);	c += b; \
  b -= a;  b ^= rot(a, 6);	a += c; \
  c -= b;  c ^= rot(b, 8);	b += a; \
  a -= c;  a ^= rot(c,16);	c += b; \
  b -= a;  b ^= rot(a,19);	a += c; \
  c -= b;  c ^= rot(b, 4);	b += a; \
}
c 
/*----------
 * final -- final mixing of 3 32-bit values (a,b,c) into c
 ...
 * The use of separate functions for mix() and final() allow for a
 * substantial performance increase since final() does not need to
 * do well in reverse, but is does need to affect all output bits.
 * mix(), on the other hand, does not need to affect all output
 * bits (affecting 32 bits is enough).  The original hash function had
 * a single mixing operation that had to satisfy both sets of requirements
 * and was slower as a result.
 *----------
 */
#define final(a,b,c) \
{ \
  c ^= b; c -= rot(b,14); \
  a ^= c; a -= rot(c,11); \
  b ^= a; b -= rot(a,25); \
  c ^= b; c -= rot(b,16); \
  a ^= c; a -= rot(c, 4); \
  b ^= a; b -= rot(a,14); \
  c ^= b; c -= rot(b,24); \
}

The split exists because the two functions have different requirements. mix() is applied once per 12-byte chunk during the main loop, and it only needs to be reversible and to affect 32 bits of output; reversibility is what lets the same function be used for both directions, and it does not need full avalanche. final() is applied exactly once, at the end, and needs to affect all output bits but does not need to be reversible. Doing both jobs in one function means doing both jobs’ work every time, on every chunk.

Note that final() produces the answer in c; b is “a little less well mixed”, which is why hash_bytes_extended() combines them:

c 
	/* report the result */
	return ((uint64) b << 32) | c;

The aligned fast path

hash_bytes() is the workhorse:

c 
/*
 * hash_bytes() -- hash a variable-length key into a 32-bit value
 *		k		: the key (the unaligned variable-length array of bytes)
 *		len		: the length of the key, counting by bytes
 *
 * Returns a uint32 value.  Every bit of the key affects every bit of
 * the return value.  Every 1-bit and 2-bit delta achieves avalanche.
 * About 6*len+35 instructions. The best hash table sizes are powers
 * of 2.  There is no need to do mod a prime (mod is sooo slow!).
 * If you need less than 32 bits, use a bitmask.
 *
 * This procedure must never throw elog(ERROR); the ResourceOwner code
 * relies on this not to fail.
 *
 * Note: we could easily change this function to return a 64-bit hash value
 * by using the final values of both b and c.  b is perhaps a little less
 * well mixed than c, however.
 */
uint32
hash_bytes(const unsigned char *k, int keylen)

The body has two nearly-identical halves, selected by alignment:

c 
	/* If the source pointer is word-aligned, we use word-wide fetches */
	if (((uintptr_t) k & UINT32_ALIGN_MASK) == 0)
	{
		/* Code path for aligned source data */
		const uint32 *ka = (const uint32 *) k;

		/* handle most of the key */
		while (len >= 12)
		{
			a += ka[0];
			b += ka[1];
			c += ka[2];
			mix(a, b, c);
			ka += 3;
			len -= 12;
		}

versus the unaligned path, which reassembles the words byte by byte:

c 
		/* handle most of the key */
		while (len >= 12)
		{
#ifdef WORDS_BIGENDIAN
			a += (k[3] + ((uint32) k[2] << 8) + ((uint32) k[1] << 16) + ((uint32) k[0] << 24));
			b += (k[7] + ((uint32) k[6] << 8) + ((uint32) k[5] << 16) + ((uint32) k[4] << 24));
			c += (k[11] + ((uint32) k[10] << 8) + ((uint32) k[9] << 16) + ((uint32) k[8] << 24));
#else							/* !WORDS_BIGENDIAN */
			a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));
			b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));
			c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));
#endif							/* WORDS_BIGENDIAN */
			mix(a, b, c);
			k += 12;
			len -= 12;
		}

Four code paths total: aligned/unaligned times little/big endian. That is the price the file header mentions, and the payoff is word-wide loads instead of byte-at-a-time assembly.

The tail — the last 0 to 11 bytes — is handled by a switch fallthrough that assembles the remainder, with the comment that appears in all four variants:

c 
			case 8:
				/* the lowest byte of c is reserved for the length */
				b += ka[1];
				a += ka[0];
				break;

The initial state mixes the length into the seed so that keys of different lengths hash differently:

c 
	/* Set up the internal state */
	len = keylen;
	a = b = c = 0x9e3779b9 + len + 3923095;

0x9e3779b9 is the golden-ratio constant from TEA, used all over the place as a “nothing up my sleeve” seed.

The 32-bit specialisation

c 
/*
 * hash_bytes_uint32() -- hash a 32-bit value to a 32-bit value
 *
 * This has the same result as
 *		hash_bytes(&k, sizeof(uint32))
 * but is faster and doesn't force the caller to store k into memory.
 */
uint32
hash_bytes_uint32(uint32 k)
{
	uint32		a,
				b,
				c;

	a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
	a += k;

	final(a, b, c);

	/* report the result */
	return c;
}

No mix() at all — the whole key fits in one chunk, so the main loop never runs. It produces the same value as hash_bytes() would, which matters, because it lets dynahash switch between the two implementations based on key size without changing the hash of anything.

The three dynahash wrappers

c 
/*
 * string_hash: hash function for keys that are NUL-terminated strings.
 *
 * NOTE: this is the default hash function if none is specified.
 */
uint32
string_hash(const void *key, Size keysize)
{
	/*
	 * If the string exceeds keysize-1 bytes, we want to hash only that many,
	 * because when it is copied into the hash table it will be truncated at
	 * that length.
	 */
	Size		s_len = strlen((const char *) key);

	s_len = Min(s_len, keysize - 1);
	return hash_bytes((const unsigned char *) key, (int) s_len);
}

/*
 * tag_hash: hash function for fixed-size tag values
 */
uint32
tag_hash(const void *key, Size keysize)
{
	return hash_bytes((const unsigned char *) key, (int) keysize);
}

/*
 * uint32_hash: hash function for keys that are uint32 or int32
 *
 * (tag_hash works for this case too, but is slower)
 */
uint32
uint32_hash(const void *key, Size keysize)
{
	Assert(keysize == sizeof(uint32));
	return hash_bytes_uint32(*((const uint32 *) key));
}

string_hash is the only one that does anything clever: it truncates to keysize - 1 bytes because that is all that will survive the strlcpy that copies the key into the table. Two strings that agree on the first keysize - 1 bytes hash the same — and compare equal — because the stored copy is truncated.

simplehash: the templated open-addressing table

Now the other table. simplehash is not a runtime-configurable hash table; it is a code generator. You #define a handful of macros and #include the header, and it emits a complete, type-specialised hash table with your prefix on every symbol.

The header states the case for it:

c 
/*
 * simplehash.h
 *
 *	  When included this file generates a "templated" (by way of macros)
 *	  open-addressing hash table implementation specialized to user-defined
 *	  types.
 *
 *	  It's probably not worthwhile to generate such a specialized implementation
 *	  for hash tables that aren't performance or space sensitive.
 *
 *	  Compared to dynahash, simplehash has the following benefits:
 *
 *	  - Due to the "templated" code generation has known structure sizes and no
 *	    indirect function calls (which show up substantially in dynahash
 *	    profiles). These features considerably increase speed for small
 *	    entries.
 *	  - Open addressing has better CPU cache behavior than dynahash's chained
 *	    hashtables.
 *	  - The generated interface is type-safe and easier to use than dynahash,
 *	    though at the cost of more complex setup.
 *	  - Allocates memory in a MemoryContext or another allocator with a
 *	    malloc/free style interface (which isn't easily usable in a shared
 *	    memory context)
 *	  - Does not require the overhead of a separate memory context.
 */

“no indirect function calls (which show up substantially in dynahash profiles)” — that is the headline. In dynahash, every comparison goes through a function pointer (hashp->match), and every hash through hashp->hash. In simplehash, SH_EQUAL and SH_HASH_KEY are macros expanded into the generated code, so the compiler inlines them and knows the exact sizes of everything.

The generated type is tiny:

c 
typedef struct SH_TYPE
{
	/*
	 * Size of data / bucket array, 64 bits to handle UINT32_MAX sized hash
	 * tables.  Note that the maximum number of elements is lower
	 * (SH_MAX_FILLFACTOR)
	 */
	uint64		size;

	/* how many elements have valid contents */
	uint32		members;

	/* mask for bucket and size calculations, based on size */
	uint32		sizemask;

	/* boundary after which to grow hashtable */
	uint32		grow_threshold;

	/* hash buckets */
	SH_ELEMENT_TYPE *data;

#ifndef SH_RAW_ALLOCATOR
	/* memory context to use for allocations */
	MemoryContext ctx;
#endif

	/* user defined data, useful for callbacks */
	void	   *private_data;
}			SH_TYPE;

One array of elements. The “buckets” are the array itself, and an entry is either in use or empty:

c 
typedef enum SH_STATUS
{
	SH_STATUS_EMPTY = 0x00,
	SH_STATUS_IN_USE = 0x01
} SH_STATUS;

The element type must have a status member of that type. That is the only requirement on the caller’s struct.

Sizing: power of two and a fill factor

c 
/* normal fillfactor, unless already close to maximum */
#ifndef SH_FILLFACTOR
#define SH_FILLFACTOR (0.9)
#endif
/* increase fillfactor if we otherwise would error out */
#define SH_MAX_FILLFACTOR (0.98)

A 0.9 fill factor. Open addressing degrades badly near 1.0, so the table grows at 90% full. The table size is always a power of two:

c 
static inline uint64
SH_COMPUTE_SIZE(uint64 newsize)
{
	uint64		size;

	/* supporting zero sized hashes would complicate matters */
	size = Max(newsize, 2);

	/* round up size to the next power of 2, that's how bucketing works */
	size = pg_nextpower2_64(size);
	Assert(size <= SH_MAX_SIZE);
	...
	return size;
}

And the mask:

c 
static inline void
SH_UPDATE_PARAMETERS(SH_TYPE * tb, uint64 newsize)
{
	uint64		size = SH_COMPUTE_SIZE(newsize);

	/* now set size */
	tb->size = size;
	tb->sizemask = (uint32) (size - 1);

	/*
	 * Compute the next threshold at which we need to grow the hash table
	 * again.
	 */
	if (tb->size == SH_MAX_SIZE)
		tb->grow_threshold = ((double) tb->size) * SH_MAX_FILLFACTOR;
	else
		tb->grow_threshold = ((double) tb->size) * SH_FILLFACTOR;
}

The bucket for a hash is hash & sizemask:

c 
/* return the optimal bucket for the hash */
static inline uint32
SH_INITIAL_BUCKET(SH_TYPE * tb, uint32 hash)
{
	return hash & tb->sizemask;
}

Probing is linear, with wraparound:

c 
/* return next bucket after the current, handling wraparound */
static inline uint32
SH_NEXT(SH_TYPE * tb, uint32 curelem, uint32 startelem)
{
	curelem = (curelem + 1) & tb->sizemask;

	Assert(curelem != startelem);

	return curelem;
}

/* return bucket before the current, handling wraparound */
static inline uint32
SH_PREV(SH_TYPE * tb, uint32 curelem, uint32 startelem)
{
	curelem = (curelem - 1) & tb->sizemask;

	Assert(curelem != startelem);

	return curelem;
}

And the distance from the optimal position, which is the quantity the robin-hood algorithm compares:

c 
/* return distance between bucket and its optimal position */
static inline uint32
SH_DISTANCE_FROM_OPTIMAL(SH_TYPE * tb, uint32 optimal, uint32 bucket)
{
	if (optimal <= bucket)
		return bucket - optimal;
	else
		return (tb->size + bucket) - optimal;
}

Robin hood insertion

The design comment describes the algorithm:

c 
 * Hash table design:
 *
 *	  The hash table design chosen is a variant of linear open-addressing. The
 *	  reason for doing so is that linear addressing is CPU cache & pipeline
 *	  friendly. The biggest disadvantage of simple linear addressing schemes
 *	  are highly variable lookup times due to clustering, and deletions
 *	  leaving a lot of tombstones around.  To address these issues a variant
 *	  of "robin hood" hashing is employed.  Robin hood hashing optimizes
 *	  chaining lengths by moving elements close to their optimal bucket
 *	  ("rich" elements), out of the way if a to-be-inserted element is further
 *	  away from its optimal position (i.e. it's "poor").  While that can make
 *	  insertions slower, the average lookup performance is a lot better, and
 *	  higher fill factors can be used in a still performant manner.  To avoid
 *	  tombstones - which normally solve the issue that a deleted node's
 *	  presence is relevant to determine whether a lookup needs to continue
 *	  looking or is done - buckets following a deleted element are shifted
 *	  backwards, unless they're empty or already at their optimal position.

The insertion loop. This is the heart of it:

c 
	/* perform insert, start bucket search at optimal location */
	data = tb->data;
	startelem = SH_INITIAL_BUCKET(tb, hash);
	curelem = startelem;
	while (true)
	{
		uint32		curdist;
		uint32		curhash;
		uint32		curoptimal;
		SH_ELEMENT_TYPE *entry = &data[curelem];

		/* any empty bucket can directly be used */
		if (entry->status == SH_STATUS_EMPTY)
		{
			tb->members++;
			entry->SH_KEY = key;
#ifdef SH_STORE_HASH
			SH_GET_HASH(tb, entry) = hash;
#endif
			entry->status = SH_STATUS_IN_USE;
			*found = false;
			return entry;
		}

		/*
		 * If the bucket is not empty, we either found a match (in which case
		 * we're done), or we have to decide whether to skip over or move the
		 * colliding entry. When the colliding element's distance to its
		 * optimal position is smaller than the to-be-inserted entry's, we
		 * shift the colliding entry (and its followers) forward by one.
		 */

		if (SH_COMPARE_KEYS(tb, hash, key, entry))
		{
			Assert(entry->status == SH_STATUS_IN_USE);
			*found = true;
			return entry;
		}

		curhash = SH_ENTRY_HASH(tb, entry);
		curoptimal = SH_INITIAL_BUCKET(tb, curhash);
		curdist = SH_DISTANCE_FROM_OPTIMAL(tb, curoptimal, curelem);

		if (insertdist > curdist)
		{
			SH_ELEMENT_TYPE *lastentry = entry;
			uint32		emptyelem = curelem;
			uint32		moveelem;
			int32		emptydist = 0;

			/* find next empty bucket */
			while (true)
			{
				SH_ELEMENT_TYPE *emptyentry;

				emptyelem = SH_NEXT(tb, emptyelem, startelem);
				emptyentry = &data[emptyelem];

				if (emptyentry->status == SH_STATUS_EMPTY)
				{
					lastentry = emptyentry;
					break;
				}
				...
			}

			/* shift forward, starting at last occupied element */

			/*
			 * TODO: This could be optimized to be one memcpy in many cases,
			 * excepting wrapping around at the end of ->data. Hasn't shown up
			 * in profiles so far though.
			 */
			moveelem = emptyelem;
			while (moveelem != curelem)
			{
				SH_ELEMENT_TYPE *moveentry;

				moveelem = SH_PREV(tb, moveelem, startelem);
				moveentry = &data[moveelem];

				memcpy(lastentry, moveentry, sizeof(SH_ELEMENT_TYPE));
				lastentry = moveentry;
			}

			/* and fill the now empty spot */
			tb->members++;

			entry->SH_KEY = key;
#ifdef SH_STORE_HASH
			SH_GET_HASH(tb, entry) = hash;
#endif
			entry->status = SH_STATUS_IN_USE;
			*found = false;
			return entry;
		}

		curelem = SH_NEXT(tb, curelem, startelem);
		insertdist++;
		...
	}

The rule, in one line: if the entry already sitting in this bucket is closer to its own optimal position than we are, we steal its bucket and push it forward. The displaced entry is “rich” (it got lucky, it is close to home) and we are “poor” (we have been pushed far from home). The rich entry takes our place; we continue looking. This keeps the displacement distribution tight: the invariant is roughly that displacement is non-increasing as you probe forward, so lookups have predictable, bounded lengths.

The shift itself walks backwards from the empty slot, copying each element one slot forward, until it reaches the bucket we are stealing.

The compare is a macro, and if SH_STORE_HASH is defined, the hash is compared first:

c 
#ifdef SH_STORE_HASH
#define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey))
#else
#define SH_COMPARE_KEYS(tb, ahash, akey, b) (SH_EQUAL(tb, b->SH_KEY, akey))
#endif

Same trick as dynahash: compare the stored hash before calling the user’s equality function.

Two extra growth heuristics keep a badly-behaved table from degenerating. If a probe run gets too long, the table grows even if it is below its threshold:

c 
		if (unlikely(insertdist > SH_GROW_MAX_DIB) &&
			((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR)
		{
			tb->grow_threshold = 0;
			goto restart;
		}
c 
#ifndef SH_GROW_MAX_DIB
#define SH_GROW_MAX_DIB 25
#endif
/* grow if more than elements to move when inserting */
#ifndef SH_GROW_MAX_MOVE
#define SH_GROW_MAX_MOVE 150
#endif
#ifndef SH_GROW_MIN_FILLFACTOR
/* but do not grow due to SH_GROW_MAX_* if below */
#define SH_GROW_MIN_FILLFACTOR 0.1
#endif

The comment explains the scenario the move-count heuristic guards against:

c 
				/*
				 * To avoid negative consequences from overly imbalanced
				 * hashtables, grow the hashtable if collisions would require
				 * us to move a lot of entries.  The most likely cause of such
				 * imbalance is filling a (currently) small table, from a
				 * currently big one, in hash-table order.  Don't grow if the
				 * hashtable would be too empty, to prevent quick space
				 * explosion for some weird edge cases.
				 */

SH_GROW_MIN_FILLFACTOR (0.1) is the “don’t grow if the table would be too empty” guard — otherwise a table with three elements in it could decide to double, repeatedly, for no reason.

Backward-shift deletion, and no tombstones

Open-addressing tables usually need tombstones: a deleted slot has to be marked as “something was here” so that a lookup probe does not stop early at an empty slot that used to be full. Tombstones accumulate, and degrade probe lengths until the table is rebuilt.

simplehash avoids them by shifting the following entries backwards:

c 
		if (entry->status == SH_STATUS_IN_USE &&
			SH_COMPARE_KEYS(tb, hash, key, entry))
		{
			SH_ELEMENT_TYPE *lastentry = entry;

			tb->members--;

			/*
			 * Backward shift following elements till either an empty element
			 * or an element at its optimal position is encountered.
			 *
			 * While that sounds expensive, the average chain length is short,
			 * and deletions would otherwise require tombstones.
			 */
			while (true)
			{
				SH_ELEMENT_TYPE *curentry;
				uint32		curhash;
				uint32		curoptimal;

				curelem = SH_NEXT(tb, curelem, startelem);
				curentry = &tb->data[curelem];

				if (curentry->status != SH_STATUS_IN_USE)
				{
					lastentry->status = SH_STATUS_EMPTY;
					break;
				}

				curhash = SH_ENTRY_HASH(tb, curentry);
				curoptimal = SH_INITIAL_BUCKET(tb, curhash);

				/* current is at optimal position, done */
				if (curoptimal == curelem)
				{
					lastentry->status = SH_STATUS_EMPTY;
					break;
				}

				/* shift */
				memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE));

				lastentry = curentry;
			}

			return true;
		}

The rule: after deleting an entry, pull the following entries backwards until you hit either an empty slot (mark the vacated slot empty) or an entry that is already at its optimal position (it cannot be pulled back any further without making its own displacement worse, so leave it and mark the vacated slot empty instead).

The SH_DELETE_ITEM() variant does the same thing but starting from a pointer to the entry:

c 
SH_SCOPE void
SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
{
	SH_ELEMENT_TYPE *lastentry = entry;
	uint32		hash = SH_ENTRY_HASH(tb, entry);
	uint32		startelem = SH_INITIAL_BUCKET(tb, hash);
	uint32		curelem;

	/* Calculate the index of 'entry' */
	curelem = entry - &tb->data[0];

	tb->members--;
	...
}

Note the pointer arithmetic: curelem = entry - &tb->data[0] recovers the bucket index from the pointer, which works because the entries are the buckets.

The resize trick

This is the best trick in the file. When the table grows, every entry has to move to a new bucket index, because the mask changed. The naive way is to rehash every key and reinsert it. simplehash does not rehash a single key, and the comment explains how:

c 
	/*
	 * Copy entries from the old data to newdata. We theoretically could use
	 * SH_INSERT here, to avoid code duplication, but that's more general than
	 * we need. We neither want tb->members increased, nor do we need to do
	 * deal with deleted elements, nor do we need to compare keys. So a
	 * special-cased implementation is lot faster. As resizing can be time
	 * consuming and frequent, that's worthwhile to optimize.
	 *
	 * To be able to simply move entries over, we have to start not at the
	 * first bucket (i.e olddata[0]), but find the first bucket that's either
	 * empty, or is occupied by an entry at its optimal position. Such a
	 * bucket has to exist in any table with a load factor under 1, as not all
	 * buckets are occupied, i.e. there always has to be an empty bucket.  By
	 * starting at such a bucket we can move the entries to the larger table,
	 * without having to deal with conflicts.
	 */

	/* search for the first element in the hash that's not wrapped around */
	for (i = 0; i < oldsize; i++)
	{
		SH_ELEMENT_TYPE *oldentry = &olddata[i];
		uint32		hash;
		uint32		optimal;

		if (oldentry->status != SH_STATUS_IN_USE)
		{
			startelem = i;
			break;
		}

		hash = SH_ENTRY_HASH(tb, oldentry);
		optimal = SH_INITIAL_BUCKET(tb, hash);

		if (optimal == i)
		{
			startelem = i;
			break;
		}
	}

The argument: if you start copying at a bucket that is empty or holds an entry at its optimal position, then every entry from there onward can be placed in the new table by direct computation — the new bucket index is hash & new_mask, and since the new mask is larger, an entry that was at its optimal position in the old table is still at its optimal position in the new one, and no entry from that point onward can wrap around into the already-copied region.

And then the copy loop, which computes the destination directly:

c 
	/* and copy all elements in the old table */
	copyelem = startelem;
	for (i = 0; i < oldsize; i++)
	{
		SH_ELEMENT_TYPE *oldentry = &olddata[copyelem];

		if (oldentry->status == SH_STATUS_IN_USE)
		{
			uint32		hash;
			uint32		startelem2;
			uint32		curelem;
			SH_ELEMENT_TYPE *newentry;

			hash = SH_ENTRY_HASH(tb, oldentry);
			startelem2 = SH_INITIAL_BUCKET(tb, hash);
			curelem = startelem2;

			/* find empty element to put data into */
			while (true)
			{
				newentry = &newdata[curelem];

				if (newentry->status == SH_STATUS_EMPTY)
				{
					break;
				}

				curelem = SH_NEXT(tb, curelem, startelem2);
			}

			/* copy entry to new slot */
			memcpy(newentry, oldentry, sizeof(SH_ELEMENT_TYPE));
		}

		/* can't use SH_NEXT here, would use new size */
		copyelem++;
		if (copyelem >= oldsize)
		{
			copyelem = 0;
		}
	}

Note the subtlety: SH_INITIAL_BUCKET(tb, hash) is called with the already-updated tb->sizemask, so it computes the new bucket index. And the SH_NEXT in the inner loop is a belt-and-braces fallback — in the normal case, the first slot examined is already empty.

And there is no rehashing: SH_ENTRY_HASH reads the stored hash if SH_STORE_HASH is defined:

c 
static inline uint32
SH_ENTRY_HASH(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
{
#ifdef SH_STORE_HASH
	return SH_GET_HASH(tb, entry);
#else
	return SH_HASH_KEY(tb, entry->SH_KEY);
#endif
}

So with SH_STORE_HASH — which is strongly recommended — the resize is “copy the entry to hash & new_mask” and nothing else. With it undefined, the hash is recomputed per entry, which is still not a rehash in the “recompute bucket from scratch and reinsert with collision resolution” sense, but it is more work.

Iterating backwards

The iterator goes backwards, and the reason is the backward-shift deletion:

c 
/*
 * Initialize iterator.
 */
SH_SCOPE void
SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
{
	uint64		startelem = PG_UINT64_MAX;

	/*
	 * Search for the first empty element. As deletions during iterations are
	 * supported, we want to start/end at an element that cannot be affected
	 * by elements being shifted.
	 */
	for (uint32 i = 0; i < tb->size; i++)
	{
		SH_ELEMENT_TYPE *entry = &tb->data[i];

		if (entry->status != SH_STATUS_IN_USE)
		{
			startelem = i;
			break;
		}
	}

	/* we should have found an empty element */
	Assert(startelem < SH_MAX_SIZE);

	/*
	 * Iterate backwards, that allows the current element to be deleted, even
	 * if there are backward shifts
	 */
	iter->cur = startelem;
	iter->end = iter->cur;
	iter->done = false;
}
c 
SH_SCOPE	SH_ELEMENT_TYPE *
SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
{
	/* validate sanity of the given iterator */
	Assert(iter->cur < tb->size);
	Assert(iter->end < tb->size);

	while (!iter->done)
	{
		SH_ELEMENT_TYPE *elem;

		elem = &tb->data[iter->cur];

		/* next element in backward direction */
		iter->cur = (iter->cur - 1) & tb->sizemask;

		if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask))
			iter->done = true;
		if (elem->status == SH_STATUS_IN_USE)
		{
			return elem;
		}
	}

	return NULL;
}

The logic: if you iterate forwards and delete the current entry, the backward shift moves the next entries into the slot you just vacated, and your forward cursor will re-visit them. If you iterate backwards, the backward shift moves entries away from the cursor, and the element you just returned has already been handled. Starting at an empty slot and finishing at that same slot means the iteration never wraps over itself.

The SH_START_ITERATE_AT() variant lets a caller resume from an arbitrary bucket, for partial iteration:

c 
/*
 * Initialize iterator to a specific bucket. That's really only useful for
 * cases where callers are partially iterating over the hashspace, and that
 * iteration deletes and inserts elements based on visited entries. Doing that
 * repeatedly could lead to an unbalanced keyspace when always starting at the
 * same position.
 */

A real user: the shared buffer table

The shared buffer lookup table is the most performance-critical hash table in PostgreSQL: every buffer read and every buffer pin goes through it. Here is how it is set up (src/backend/storage/buffer/buf_table.c):

c 
/* entry for buffer lookup hashtable */
typedef struct
{
	BufferTag	key;			/* Tag of a disk page */
	int			id;				/* Associated buffer ID */
} BufferLookupEnt;
c 
void
BufTableShmemRequest(void *arg)
{
	int			size;

	/*
	 * Request the shared buffer lookup hashtable.
	 *
	 * Since we can't tolerate running out of lookup table entries, we must be
	 * sure to specify an adequate table size here.  The maximum steady-state
	 * usage is of course NBuffers entries, but BufferAlloc() tries to insert
	 * a new entry before deleting the old.  In principle this could be
	 * happening in each partition concurrently, so we could need as many as
	 * NBuffers + NUM_BUFFER_PARTITIONS entries.
	 */
	size = NBuffers + NUM_BUFFER_PARTITIONS;

	ShmemRequestHash(.name = "Shared Buffer Lookup Table",
					 .nelems = size,
					 .ptr = &SharedBufHash,
					 .hash_info.keysize = sizeof(BufferTag),
					 .hash_info.entrysize = sizeof(BufferLookupEnt),
					 .hash_info.num_partitions = NUM_BUFFER_PARTITIONS,
					 .hash_flags = HASH_ELEM | HASH_BLOBS | HASH_PARTITION | HASH_FIXED_SIZE,
		);
}

Look at the flags: HASH_PARTITION | HASH_FIXED_SIZE. Partitioned, so never splits. Fixed size, so it cannot grow. The nelem estimate is therefore a hard commitment, and the comment explains the fudge factor.

HASH_BLOBS with a keysize that is not 4 means tag_hash — the generic byte hash — is used.

Computing the hash once

The one piece of genuine cleverness in this file:

c 
/*
 * BufTableHashCode
 *		Compute the hash code associated with a BufferTag
 *
 * This must be passed to the lookup/insert/delete routines along with the
 * tag.  We do it like this because the callers need to know the hash code
 * in order to determine which buffer partition to lock, and we don't want
 * to do the hash computation twice (hash_any is a bit slow).
 */
uint32
BufTableHashCode(BufferTag *tagPtr)
{
	return get_hash_value(SharedBufHash, tagPtr);
}

The caller needs the hash code before it can take the right lock — the partition is selected by the hash code — and then it needs the same hash code to do the lookup. Computing it twice would be wasteful, so the hash is computed once by the caller and passed down to hash_search_with_hash_value():

c 
int
BufTableLookup(BufferTag *tagPtr, uint32 hashcode)
{
	BufferLookupEnt *result;

	result = (BufferLookupEnt *)
		hash_search_with_hash_value(SharedBufHash,
									tagPtr,
									hashcode,
									HASH_FIND,
									NULL);

	if (!result)
		return -1;

	return result->id;
}

And the partition selection uses the low bits, as dynahash’s design promised (src/include/storage/buf_internals.h):

c 
/*
 * The shared buffer mapping table is partitioned to reduce contention.
 * To determine which partition lock a given tag requires, compute the tag's
 * hash code with BufTableHashCode(), then apply BufMappingPartitionLock().
 * NB: NUM_BUFFER_PARTITIONS must be a power of 2!
 */
static inline uint32
BufTableHashPartition(uint32 hashcode)
{
	return hashcode % NUM_BUFFER_PARTITIONS;
}

static inline LWLock *
BufMappingPartitionLock(uint32 hashcode)
{
	return &MainLWLockArray[BUFFER_MAPPING_LWLOCK_OFFSET +
							BufTableHashPartition(hashcode)].lock;
}

With NUM_BUFFER_PARTITIONS defined in src/include/storage/lwlock.h:

c 
#define NUM_BUFFER_PARTITIONS  128

So: 128 LWLocks, one per partition, and the partition is chosen by the low 7 bits of the hash code. And because calc_bucket() uses the low bits of the hash to pick the bucket, all the keys in one partition land in a disjoint set of buckets from all the other partitions. The buckets of partition 3 are exclusively locked by partition lock 3. That is the entire trick, and it is why the buffer mapping table scales to hundreds of concurrent backends.

Caveats

A few things to keep in mind.

The hash value is 32 bits. Every hash in dynahash is a uint32. The stored hash is compared before the key, so a false positive means the full key comparison runs — but a false negative is impossible, because the stored hash is computed from the same key. So the only cost of a 32-bit hash is a slightly higher rate of full-key comparisons on collision. With 2^32 keys, expect a birthday-paradox collision somewhere around 77 000 distinct keys hashing to the same bucket. That is fine for a chain of a few entries; it is not fine if the hash is systematically bad.

A bad hash function is catastrophic and silent. hash_bytes() promises that “Every bit of the key affects every bit of the return value”. If you supply your own hash function via HASH_FUNCTION and it does not have that property, the table will degrade into a linked list and nothing will say so.

HASH_REMOVE returns a dangling pointer. Covered above. Do not dereference it.

Partitioned tables cannot grow. Their bucket count is fixed at creation. If you under-estimate nelem, you get long chains and no warning.

Shared hash tables cannot grow at all, directory or buckets:

c 
	/*
	 * Hash tables allocated in shared memory have a fixed directory and have
	 * all elements allocated upfront.  We don't support growing because we'd
	 * need to grow the underlying shmem region with it.
	 *
	 * The shared memory allocator must be specified too.
	 */
	infoP->alloc = ShmemHashAlloc;
	infoP->alloc_arg = NULL;
	hash_flags |= HASH_SHARED_MEM | HASH_ALLOC | HASH_FIXED_SIZE;

The two tables have different pointer guarantees. dynahash guarantees that an entry’s address never changes. simplehash does not: SH_GROW() reallocates the whole array, and SH_DELETE() moves entries backwards. Anything holding a SH_ELEMENT_TYPE * across an insert or a delete is holding a pointer that may have just been invalidated.

simplehash’s SH_START_ITERATE is not a snapshot. The documentation is blunt:

c 
 * During iteration the current entry in the hash table may be deleted,
 * without leading to elements being skipped or returned twice.  Additionally
 * the rest of the table may be modified (i.e. there can be insertions or
 * deletions), but if so, there's neither a guarantee that all nodes are
 * visited at least once, nor a guarantee that a node is visited at most once.

hash_seq_search on dynahash has the same caveat, in stronger form: “deleting any other element while the scan is in progress is UNDEFINED (it might be the one that curIndex is pointing at!)”.

What it all means in practice

If you are writing an extension, pick the right table. If the table lives in shared memory, needs partitioned locking, needs stable pointers to entries, or holds large entries, use dynahash — there is nothing else that does those things. If the table is local, small, and lookup-bound, use simplehash: the templating removes the indirect calls that dominate dynahash profiles for small entries.

Sizing a dynahash table is a commitment, not a hint. The nelem you pass determines the bucket count forever (for shared and partitioned tables). Under-estimate and you get silently degrading chains. Over-estimate and you waste shared memory and make hash_seq_search slower, because the scanner walks every bucket.

The growth algorithm is why dynahash never needs to rehash. This is not a detail — it is the reason the whole “grow one bucket at a time” scheme exists. The two-mask reduction in calc_bucket() is what makes a single old bucket splittable, and the low-bit reduction is what makes partitions independent. Both properties fall out of the same 32-bit masking trick.

Hash collisions cost you a memcmp, not a lookup. Because the hash value is stored alongside the entry and compared first, a colliding key costs one extra 32-bit comparison plus one full key comparison. It does not cost a rescan of the chain.

The shared buffer table is the template for anything you build in shared memory. Compute the hash once, use the low bits to pick the partition lock, use the same hash value for the lookup, and size the table for the worst case rather than the average case.

Deletion is where the two designs diverge most. dynahash puts freed entries on a freelist and never touches them again (which is why the pointer dangles). simplehash shifts entries backwards so that no tombstones are needed (which is why pointers move). If your workload is insert-heavy, simplehash wins. If it is delete-heavy and you need stable pointers, dynahash wins.

Further reading

  • src/backend/utils/hash/dynahash.c – the chained hash table; expand_table(), get_hash_entry(), calc_bucket().
  • src/include/utils/hsearch.h – HASHELEMENT, HASHCTL, the HASH_* flags.
  • src/include/lib/simplehash.h – the templated open-addressing table; SH_GROW(), SH_INSERT_HASH_INTERNAL(), SH_DELETE().
  • src/common/hashfn.c – hash_bytes(), mix(), final(), hash_bytes_uint32().
  • src/include/common/hashfn.h – hash_any(), hash_uint32(), hash_combine().
  • src/backend/storage/buffer/buf_table.c – the shared buffer lookup table.
  • src/include/storage/buf_internals.h – BufTableHashPartition(), BufMappingPartitionLock().
  • src/backend/storage/ipc/shmem_hash.c – ShmemRequestHash() and the fixed-size shared memory allocator.

PostgresPerformanceInternalsStorage