[PATCH] Implement Robin Hood distance-based early termination in simplehash

From: Aviral Asthana <aviral(dot)asthana0704(at)gmail(dot)com>
To: pgsql-hackers(at)postgresql(dot)org
Subject: [PATCH] Implement Robin Hood distance-based early termination in simplehash
Date: 2026-09-09 09:53:29
Message-ID: CAA7-H4u9-Sk5TqA5a2sR2Jaw+d5yGRJWN54Oxcz9+mOLxCfKgw@mail.gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hi,
I noticed two TODO comments in simplehash.h (lines 825 and 923) asking
whether
we could stop hash table searches based on distance-from-optimal. Since
simplehash uses Robin Hood hashing, which keeps elements implicitly sorted
by
distance, this optimization is straightforward to implement.

This patch adds early termination to SH_LOOKUP_HASH_INTERNAL and SH_DELETE.
When searching at distance D, if we encounter an element with distance < D,
we can immediately return NULL/false because Robin Hood insertion would have
placed our target before this element if it existed.

The optimization is only enabled when SH_STORE_HASH is defined, to avoid
recomputing hashes during search (as suggested in the original TODO
comment).

Implementation details:

1. Added searchdist counter tracking probe distance from optimal bucket
2. At each probe, compare current element's distance vs. search distance
3. Early return when current distance < search distance
4. Increment searchdist after each probe
5. Conditional compilation via #ifdef SH_STORE_HASH

Benefits:
- Faster unsuccessful lookups (common in hash operations)
- Better average-case performance, especially at high load factors
- Zero memory overhead
- No performance cost when SH_STORE_HASH is undefined
- Preserves correctness

Testing:
- Build tested successfully with --enable-cassert --enable-debug
- All regression tests pass (make check)
- Edge cases verified: empty tables, single elements, wraparound, long
collision chains

The optimization has the biggest impact on unsuccessful lookups in hash
tables with many collisions, which is a common scenario in query processing.

Patch attached.

Aviral Asthana
aviral(dot)asthana0704(at)gmail(dot)com

Attachment Content-Type Size
robin-hood-optimization-v1-TESTED.patch text/plain 4.3 KB

Browse pgsql-hackers by date

  From Date Subject
Next Message Nazir Bilal Yavuz 2026-09-09 10:00:46 Re: Speed up COPY FROM text/CSV parsing using SIMD
Previous Message wenhui qiu 2026-09-09 09:49:51 Do we reduce autovacuum_naptime max values