public inbox for [email protected]  

help / color / mirror / Atom feed

From: Ben Mejia <[email protected]>
To: Tomas Vondra <[email protected]>
To: PostgreSQL Hackers <[email protected]>
Subject: Re: hashjoins vs. Bloom filters (yet again)
Date: Tue, 23 Jun 2026 15:36:06 -0700
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>



On 5/29/26 5:55 PM, Tomas Vondra wrote:

> old patches
> -----------
> 
> Those old patches tried to do a fairly small thing during a hash join,
> and that's building a Bloom filter on the inner relation (the one that
> gets hashed), and then use that filter before probing the hash table.
> 
> The benefits come from Bloom filters being (fairly) cheap, and a
> negative answer (hash is not in the filter) may allows us to skip a much
> more expensive operation.
> 
> The old threads patches focused especially at two hash join cases:
> 
> (a) A very selective join, i.e. a significant fraction of outer tuples
> does not have a match in the hash table.
> 
> (b) A selective hash join forced to do batching because the hash table
> is too large, and thus forced to spill outer tuples to temporary files.
> 
> For (a), the benefit comes from Bloom filters being much cheaper to
> probe than a hash table. The exact cost depends on the implementation,
> sizes, etc. We're in the ballpark of 50 vs. 500 cycles, maybe. But if
> the filter discards 90% of tuples, it can be a big win.
> 
> For (b), the filter (for all the batches at once) allows us to discard
> some of the outer tuples without writing them to temporary files. Which
> is way more expensive than probing a hash table.
As it happens, I've been exploring the use of a bitmap filter for the
same two cases you mention. This has some relevance to the issues you 
mention in your post about sizing, false-positive rate, etc.

Instead of a Bloom filter, I chose to use a bitmap filter, with one bit 
per bucket on the build side. As the inner table is built, I set a bit 
in the bitmap filter for every occupied bucket. If a bucket is empty, 
there are no matching hashes and those hash values can be skipped where 
appropriate. The advantages of this bitmap over a Bloom filter are:

  - sizing is pre-determined by nbuckets
  - small bitmaps (4k for 32k buckets)
  - cheaper - nominal cost to set/check bits

A well-chosen Bloom filter will be more discriminating, but the bitmap 
has the same no-false-negatives guarantee and costs much less space and 
time to build.

I implemented both of your cases:

Drop-before-spill: (Case b)
Build per-batch bitmaps during inner partition pass and drop tuples that 
don't have a bit set. Saves I/O on tuples that will never match. This 
only works for inner and semi joins.


Single-Batch probe: (Case a)
Only pays off in high-miss-rate joins and a bucket array larger than 
L2/L3 cache. This case has a higher penalty for hash table lookup than 
the in-cache bitmap check. This case works in multi-batch, but the I/O 
cost dominates and there is no gain.


I put runtime guards on both of these; I sampled the drop rate over a 
window and disable the filter for the rest of the pass if the rate falls 
below a threshold. (~5% for case b; ~25% for case a)

The benchmarks are encouraging:

For case a, I was able to see a best-case improvement of ~15% for 
carefully chosen data (dependent on L2/L3 cache size).

For case b, I tested 3 cases with sparse, average and dense probe hits:

     sparse probe (~95% miss):           +18% to +36%
     avg probe    (~37% miss):            +9%  to +13%
     dense probe  (FK-like, ~0% miss):    flat, within noise

(This was on a 8-core x86-64, L1 32KB/core, L2 4MB/core, L3 32MB, 31 GB 
RAM. PostgreSQL 19devel, serial hash join, 
max_parallel_workers_per_gather = 0, across work_mem = 1-8MB)

Happy to share the patch and full benchmark data if useful.

-Ben Mejia

view thread (23+ messages)  latest in thread

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: [email protected]
  Cc: [email protected], [email protected], [email protected]
  Subject: Re: hashjoins vs. Bloom filters (yet again)
  In-Reply-To: <[email protected]>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox