Bloom Filters in Postgres

April 19, 2026

A common pattern for sign-up forms is to check whether a username is available while you’re still typing it. On every keystroke the backend sends a request to the database, which costs one index lookup and is usually cheap enough to ignore.

However, once the users table is sharded across nodes by user ID, a username could be on any shard, and every check becomes a scatter and gather across all of them. For example, with sixteen Postgres nodes, typing a twelve-character username costs almost two hundred queries.

Debouncing the username field cuts down how many checks go out, but each check still lands on every shard and needs to wait for the slowest one to answer. Every shard you add makes that a little worse.

A Bloom filter can tell you a name is free without asking any of them, and you can build one in Postgres from a table and a function.

Bloom filters

A Bloom filter, first described by Burton Bloom in 1970, is an array of bits that tests whether an item is in a set. It starts out as all zeros. To add an item, you hash it k different ways and set the bit at each of those positions. To check an item, you hash it the same way and look at the same bits. If any of them is 0, the item was never added. If they’re all 1, it probably was.

Those k hashes can all come from the same hash function. To see how, let’s take a 16-bit filter with k = 3 and add the username ada. Hashing ada always gives the same result, so a counter in front makes each input different: 0:ada, 1:ada and 2:ada.

Each hash comes back as a huge number. With md5 it’s 128 bits, up to 39 digits long, and the array only has 16 positions. Taking the hash modulo 16 turns it into a position between 0 and 15. A good hash spreads its outputs evenly, so the bits get used evenly too. Here are ada’s three:

input    md5 in hex                          % 16
0:ada    2d0adfba24320bd14abdb38aa02ff6fe    14
1:ada    e4d0f800ff16f1b94c8ce1de8bb8fefd    13
2:ada    cf0c119c0624d173d6d86cdbfda09965     5

Put together in Python, the whole filter looks like this:

from hashlib import md5

SIZE = 16
K = 3
bits = [0] * SIZE


def positions(item):
    for i in range(K):
        h = md5(f"{i}:{item}".encode()).hexdigest()
        yield int(h, 16) % SIZE


def add(item):
    for p in positions(item):
        bits[p] = 1


def check(item):
    return all(bits[p] for p in positions(item))

Here’s what it does after adding two names and checking three:

add ada        bits 5, 13, 14
add grace      bits 2, 3, 8

position       0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
bits           0  0  1  1  0  1  0  0  1  0  0  0  0  1  1  0

check ada      bits 5, 13, 14    all set, and ada was added
check alan     bits 2, 8, 10     bit 10 is 0, definitely not added
check bjarne   bits 3, 5, 8      all set, but bjarne was never added

alan gets a definite no. bjarne gets the same answer as ada even though it was never added, because ada and grace set all three of its bits between them. That’s a false positive, and the filter has no way to tell it apart from a real match.

A Bloom filter’s “no” is always right, while its “yes” is only probably right, and how often it’s wrong depends on how many bits the array has for each item in it. If $m$ is the number of bits and $n$ is the number of items, the best k is:

k = \frac{m}{n} \ln 2

At that k, about half the bits end up set. For a 1% false-positive rate, the smallest filter that works has about 9.6 bits per item, with a k of about 7.

For a username check, that definite “no” is exactly what you want. It means the name is free, and no shard had to be queried.

Storing it in Postgres

Since the filter is a single bit array covering every username, one Postgres table is all we need to hold it. For 100 million users, a 1% false-positive rate needs at least 960 million bits. Rounding up to the next power of two gives 2^30 bits (128 MiB), which lets every position come straight out of the hash’s bits, as the function below shows. That works out to 10.7 bits per name, so the best k is:

k = 10.74 \times \ln 2 \approx 7.44

k has to be a whole number, and 7 and 8 give almost the same false-positive rate, so 7 wins because it’s one fewer bit to set and check for every name.

The whole array can’t go in one row, though. Postgres doesn’t modify values in place, so flipping a single bit writes a new copy of the whole value. That would mean writing 128 MiB on every sign-up, with every write waiting on the same row lock.

Splitting it into chunks solves both problems. Here it’s 131,072 rows of 8,192 bits each:

create table username_filter (
  chunk int primary key,
  bits  bit(8192) not null
);

insert into username_filter
select n, 0::bit(8192) from generate_series(0, 131071) as n;

That’s about 150 MiB on disk once Postgres adds its row headers and the primary key.

In a regular Bloom filter, a name’s seven bits can land anywhere in the array, which here usually means seven different rows. Adding a name would update seven rows, and checking one would read seven. To avoid that, each name first picks a single chunk, and all seven of its bits go inside it. This is known as a blocked Bloom filter. Adding a name then updates one 1 KiB row, and checking it reads one.

Keeping each name in one chunk costs a little bit in accuracy because names don’t spread across chunks perfectly evenly. Some chunks end up fuller than others, and a fuller chunk gives more false positives. At 8,192 bits per chunk, the difference is negligible with a 0.585% false-positive rate, compared to 0.578% for a regular Bloom filter of the same size.

This function turns a name into two things: its chunk, and a mask. The mask is an 8,192-bit value, the same size as a row, with only the name’s seven bits set:

create function username_bits(name text, out chunk int, out mask bit(8192))
language plpgsql as $$
declare
  h bit(128) := ('x' || md5(lower(name)))::bit(128);
begin
  chunk := substring(h from 1 for 17)::int;
  mask := 0::bit(8192);
  for i in 0..6 loop
    mask := set_bit(mask, substring(h from 18 + i * 13 for 13)::int, 1);
  end loop;
end
$$;

Calling it on ada returns chunk 71962 and a mask with seven bits set. The mask is too long to print, so this steps through all 8,192 positions with generate_series and uses get_bit to keep the ones that are set:

select chunk,
       array(select i from generate_series(0, 8191) i where get_bit(mask, i) = 1) as set_bits
from username_bits('ada');

 chunk |              set_bits
-------+-------------------------------------
 71962 | {619,1835,3259,3422,5396,5977,6900}

The function only hashes the name once. md5 returns 32 hex characters, and putting an x in front lets Postgres read them as a string of 128 bits. The name is lowercased first, so Ada and ada use the same bits. Here’s where ada’s chunk and bits come from:

md5('ada')     8c8d357b5e872bbacd45197626bd5759

bits 1-17      10001100100011010    chunk 71962
bits 18-30     0110101011110        bit 3422
bits 31-43     1101011110100        bit 6900
bits 44-56     0011100101011        bit 1835
bits 57-69     1011101011001        bit 5977
bits 70-82     1010100010100        bit 5396
bits 83-95     0110010111011        bit 3259
bits 96-108    0001001101011        bit 619

The first 17 bits pick the chunk, giving a number from 0 to 131,071 that covers every chunk. Each of the next seven 13-bit slices is a number from 0 to 8,191, and picks one bit inside that chunk. That’s eight positions from a single hash, using 108 of its 128 bits.

Adding a name ORs its mask into its chunk:

update username_filter f
set bits = f.bits | b.mask
from username_bits('ada') b
where f.chunk = b.chunk;

OR gives a 1 wherever either side has one, so ada’s seven bits get turned on and the bits other names set stay as they were. Here it is with 8 bits instead of 8,192:

row           0 1 0 0 1 0 0 0
mask          0 0 1 0 1 0 0 1
row | mask    0 1 1 0 1 0 0 1

Checking a name ANDs its chunk with its mask and compares the result to the mask:

select bits & mask = mask as maybe_taken
from username_filter
join username_bits('ada') using (chunk);

AND keeps only the bits that are set on both sides, which drops everything outside the mask. If what’s left equals the mask, all seven bits were already set and the name might be taken. If even one is missing, the name is definitely free:

mask          0 0 1 0 1 0 0 1

row           0 1 1 0 1 0 0 1
row & mask    0 0 1 0 1 0 0 1    equals the mask, might be taken

row           0 1 0 0 1 0 0 1
row & mask    0 0 0 0 1 0 0 1    bit 2 is missing, definitely free

In both queries, username_bits('ada') acts like a one-row table holding the chunk and the mask, and joining on chunk finds the row through the primary key. When the table fits in memory, a check is faster than a millisecond.

Checking while typing

A check now goes to the filter first, and only reaches the shards when the filter can’t rule the name out:

  flowchart LR
    K["<strong>keystroke</strong><br/><span class='mermaid-detail'>is ada free?</span>"]
    F["<strong>username_filter</strong><br/><span class='mermaid-detail'>one row</span>"]
    A["<strong style='color:#16181a'>free</strong><br/><span class='mermaid-detail' style='color:#16181a'>no shards asked</span>"]
    S["<strong>16 shards</strong><br/><span class='mermaid-detail'>scatter and gather</span>"]
    K --> F
    F -->|"definitely not"| A
    F -.->|"maybe"| S
    classDef free fill:#5eff6c,stroke:#5eff6c,color:#16181a
    classDef fanout stroke:#5ea1ff,stroke-width:2px
    class A free
    class S fanout

A “definitely not” is final, and none of the shards hear about it. A “maybe” falls back to the scatter and gather for the exact answer. That still happens for names that really are taken, plus about 1 in 170 free ones (the false-positive rate at 100 million users), but nearly every free name now costs one row read instead of sixteen queries.

If you can live with a free name occasionally showing as taken, you can drop the fallback and treat every “maybe” as taken. Then the shards are only queried when the form is submitted.

Every taken name has to be in the filter, or its “no” can’t be trusted. So when an account is created, the username needs to be added to the filter before the user is inserted.

If the insert then fails, the bits stay set for a name nobody has. The only cost is a slightly higher false-positive rate, and every answer stays correct because a “maybe” still checks the shards.

However, reversing the order is worse: a crash between inserting the user and updating the filter would leave a taken name that the filter calls free. A transaction can’t prevent that, because the filter and the user’s shard are on different nodes, and begin and commit only cover one database. Writing the filter first is what keeps it correct without one.

Submitting the form still runs one scatter and gather before the account is created, because that answer has to be exact. The filter also doesn’t change how the system stops two people from claiming the same name at once.

Tradeoffs

This filter has two costs.

The first is deleted accounts. They stay in the filter, because their bits may also belong to other names, and clearing them could turn a taken name into a “definitely not”. Names from deleted accounts keep coming back as “maybe” and the fallback finds them free, so the answer is still right, but it costs a scatter and gather every time.

That’s only a cost if deleting an account frees up its name, though. Many services soft delete accounts or keep the name reserved so nobody else can take it over, and then the name is still taken and the “maybe” is right.

The second is that the filter’s size is fixed when the table is created, so its false-positive rate climbs as people sign up. With the same 128 MiB, 1 in 170 free names gets a “maybe” at 100 million users. At 150 million users it’s 1 in 27, and at 200 million it’s 1 in 9.

That makes the rate worth keeping an eye on, and it can be read directly from the table. A free name lands in one chunk, and each of its seven bits is already set with a chance equal to that chunk’s share of set bits. So the chance that all seven are set is that share raised to the seventh power, and averaging it across chunks gives the false-positive rate:

select avg(power(bit_count(bits) / 8192.0, 7)) as false_positive_rate
from username_filter;

I loaded 100 million generated names to try it out. The query returned 0.0059, and checking a million names that were never added turned up 5,924 false positives, close to the 5,900 it predicted.

When the rate gets too high, you can rebuild the filter with more chunks:

Export every username from the shards and build a new filter table from them, which bit_or can do for every chunk in a single group by.
Add the names that signed up during the export.
Swap in the new table and its matching username_bits in one transaction, since both live in the same database.

A rebuild also clears out deleted names and picks up any account created without going through sign-up.

A Bloom filter only gives one answer with certainty, and in a sign-up form it’s the answer people are hoping for. The shards still have the final say on who gets a name, but they’re no longer queried for every name someone tries along the way.