DEV Community: Thiago Silva

SetrixDB: a set engine in Go — exact set intersection over IDs (and where it loses)

Thiago Silva — Tue, 15 Sep 2026 21:40:11 +0000

“Given an ID, is it in this list?” and “which IDs are in both lists at the same time?” These look like
textbook exercises. But when those lists hold millions or billions of elements and must answer in
microseconds — in a faceted filter, a permission check, a pre-filter of candidates for an LLM — the
answer stops being trivial.

This article is about one specific primitive: an exact set engine over uint64 IDs, with measured,
reproducible numbers — and a dedicated section on where it loses to an established library. It is
not about replacing databases; it is about an operation that usually gets left open.

The problem: set algebra over IDs

A lot of modern software spends its time crossing lists of identifiers:

E-commerce / search: "products this color AND this size AND this brand AND in stock" — an intersection of four sets.
Permissions / RAG: "which documents can this user see AND match the query?" — intersect a permission list with a candidate list.
Anti-fraud / access: "is this ID on any blocklist?" — pure membership.
Text: every term or phrase becomes a key; combined queries are intersections.

In all of these, what matters is exact presence and exact intersection over IDs — not
payloads. Generic structures (map, joins, sorted scans) solve it — just not optimally: they carry
pointers, indirections and comparisons you don't need when the data is the number.

The core choice: always work with uint64 IDs. A set is a pile of uint64; an intersection is an
AND. Everything is arithmetic.

The mistake that made the project: 78% collisions

Before a set can exist, I need dense, collision-free identifiers. My first keygen was a positional
hash — a simple arithmetic formula. It collided badly: on 200k short alphanumeric tokens, 78%
collided, and "Oa" and "0b" landed on the same ID.

The fix was implementing a Minimal Perfect Hash Function (CHD v2, from scratch):

0 collisions on a base of 50 million keys;
4.03 bits/key (~24 MiB for 50M keys) — 3.4× less memory than v1 (13.68 bits/key);
lookup in ~118 ns, and membership stays exact.

If this article has one takeaway, it is this: measure the collision rate on the real corpus
is the step almost everyone skips — and it changes the whole architecture.

How it works (from term to result)

Keygen (MPHF): term → deterministic, collision-free uint64 ID.
Representation: ID i becomes bit i of a bitset; there is also a sparse set (sorted list) and a hybrid (hot ranges in a bitset + cold tail sparse).
Kernel: the bitset AND runs in AVX-512 (vpandq + vpopcntq) via cgo, with runtime dispatch (__builtin_cpu_supports) and a scalar fallback — the same binary runs anywhere.
Scale: the universe is split into shards (parallelizes compute); in the cluster, each node serves a shard, the coordinator broadcasts and sums, and a consistent hash ring decides ownership (adding/removing a node remaps only ~1/(N+1) of the IDs).

The real numbers

Environment (all measurements): reference server — 2 vCPU AMD EPYC (Zen4, AVX-512), 3.8 GB RAM,
Go 1.22 (+ gcc for cgo). Date: 09/2026.

Membership (n = 1M)

Structure	memory	speed	exact?
`map[uint64]` (Go)	22.3 B/key	133.3M ops/s	yes
SetrixDB (MPHF CHD v2)	0.5 B/key (structure)	~118 ns/lookup	yes
Bloom filter (1% false positive)	1.2 B/key	23.6M ops/s	no

Speed parity with map, at 2.2× less memory — and exact, unlike a probabilistic filter.

Intersection (A = B = 1M)

Strategy	dense IDs (`denso32`)	random 64-bit IDs (`aleat64`)
Sorted merge (SetrixDB)	9.2 ms	11.3 ms
Roaring (compressed bitmap)	148 µs	523 ms
Hash join (`map`)	91.6 ms	94.9 ms
Bitset `AND` (pure Go)	29 µs	—
Bitset `AND` (AVX-512)	6 µs	—

Where it loses (and why that matters)

Let me be explicit, because a comparison without context is misleading:

Sparse, huge universe: when the universe does not fit in RAM, the dense bitset is out (it always takes universe/8). That's where Roaring wins — that's what it's for. Measured: universe 2²⁶, Roaring64 used ~2 MB against 8.2 MB for my bitset (slower in time, cheaper in memory).
Random 64-bit IDs: in the aleat64 case, Roaring took 523 ms — but that's because it was designed for a different regime. The point is not "I always win"; it's which regime each one shines in.
Range queries, similarity, joins: SetrixDB doesn't do them. It's pure equality.
Frequent updates: an MPHF is built for a set; adding/removing new keys requires a rebuild. For mutable workloads, it is not the tool.

So where does it win? In the opposite regime: a dense universe that fits in RAM, large sets,
exact intersection on the hot path. That's exactly what a real-data test showed ↓

Real data (not just synthetic)

I ran three public datasets and checked every result externally (sort + comm).

Retail — Online Retail II (UCI)

1,067,371 real sale lines (UK, 2009–2011). Query "United Kingdom AND Q4/2011 AND price ≥
5" → 22,701 rows in 823 µs. Independent check: 22,701. Identical.

Text — Wikipedia titles (19.3 million terms)

enwiki-latest-all-titles-in-ns0: 19,264,252 titles. "multi-word AND starts with s" →
1,408,399 in 9.5 ms; "multi-word AND United" → 38,602 in 8.0 ms. Verified: identical.

Scale — MovieLens 25M (25 million interactions)

25,000,095 real ratings; derived facets (genre, decade, score). Sets with 10.9M and 12.4M
members. Three queries, all externally verified:

Query	Result
Drama AND 2000s AND rating ≥ 4	1,634,027
Drama AND rating ≥ 4	6,096,563
Comedy AND rating ≥ 4 AND 2000s	965,677

And here is the number I like most — because it is about picking the right representation. On the
same 25M-ID universe, with sets of tens of millions:

Path	memory/set	latency (A∩B)
Sorted list merge	87.7 MB	80.4 ms
Dense bitset (AVX-512)	2 MB	227 µs

Same exact result, ~350× faster and ~43× smaller. When the universe is dense and fits in memory,
the bitset isn't just the fastest — it's the most economical too.

What SetrixDB IS — and what it is NOT

It IS an embeddable set engine, in Go, that answers exact presence and exact intersection
over uint64 IDs, with a SIMD kernel, sharding and a cluster mode. It coexists with your current
database: your data stays where it is; SetrixDB sits beside it as an index/pre-filter.

It is NOT a relational, columnar, NoSQL or vector database. It doesn't do SQL, joins or
similarity. And — importantly — it stores sets of IDs, not payloads.

Honest limitations

Alpha (v0.1.0). Tested on loopback and between two machines; the 3-node cluster ran in the cloud, but not yet in multi-datacenter production.
Bitset memory is linear in the universe (universe/8); the hybrid mitigates it (2³⁶ IDs: 8.59 GB dense → 1.73 MB hybrid), but it's a trade-off with a cost.
NPU backend and compact UDP protocol: roadmap, not implemented.
Energy benchmarks (J/search): planned, not yet measured.
If any number here doesn't reproduce on your machine, that's a bug — and I want to know.

Hard questions (and answers)

"Why not just use CRoaring/Roaring?"
Because Roaring is excellent — and it is the right answer when the universe doesn't fit in RAM or is
very sparse. SetrixDB targets another point: native Go, embeddable, dense universe that fits in
RAM, with MPHF in the keygen and sharding/cluster built in. If your case is Roaring's case, use
Roaring.

"Why not a map/Bloom filter?"
A map stores pointers and is ~44× fatter per key (22.3 vs 0.5 B/key here). Bloom is smaller but it
errs (1% false positive) — in permissions, erring toward "can see" is unacceptable.

"Does MPHF handle insert/delete?"
No. It's built for a set. Mutable loads require a rebuild (or the sparse mode). It's a conscious
trade for O(1) lookup at ~4 bits/key.

"What about Go's GC on the hot path?"
The bitsets are contiguous []uint64, allocated once; the hot loop doesn't allocate. For DMA (NPU)
there's UnsafePtr + pinning — with the caveat of keeping the buffer alive.

"Isn't this just 'bitset with AVX-512'?"
Partly, yes — and that's fine: bitset + SIMD is a solid, well-known base. What the project adds is the
package: a collision-free keygen, adaptive representation (dense/sparse/hybrid), sharding/cluster,
and the "stored sets" mode (only the name travels over the network).

The invitation

SetrixDB is open source (Apache-2.0). If the next wave isn't about storing more, but about
deciding faster — and if set operations deserve a dedicated, exact, vectorized engine beside what
you already use — come test it.

Code, reproducible benchmarks and a quickstart: https://github.com/setrixdb/setrixdb

Run the benchmarks, open an issue, and tell me where the numbers don't add up.

SetrixDB — the arithmetic set engine.
Sets. In microseconds. On any chip. Beside your database.

SetrixDB: motor de conjuntos em Go — interseção exata sobre IDs (e onde ele perde)

Thiago Silva — Tue, 15 Sep 2026 21:40:00 +0000

“Dado um ID, ele está nesta lista?” e “quais IDs aparecem nas duas listas ao mesmo tempo?” Parecem
exercícios de livro-texto. Mas quando essas listas têm milhões ou bilhões de elementos e precisam
responder em microssegundos — num filtro facetado, numa checagem de permissão, num pré-filtro de
candidatos para um LLM — a resposta deixa de ser trivial.

Este artigo é sobre uma primitiva específica: um motor de conjuntos exato sobre IDs uint64, com
números medidos e reproduzíveis — e uma seção dedicada a onde ele perde para uma biblioteca
consagrada. Não é sobre substituir bancos de dados; é sobre uma operação que costuma ficar em aberto.

O problema: álgebra de conjuntos sobre IDs

Boa parte do software moderno passa o tempo cruzando listas de identificadores:

E-commerce / busca: “produtos desta cor E deste tamanho E desta marca E em estoque” — interseção de quatro conjuntos.
Permissões / RAG: “quais documentos este usuário pode ver E casam com a busca?” — interseção de uma lista de permissão com uma lista de candidatos.
Antifraude / acesso: “este ID está em alguma lista de bloqueio?” — pertencimento puro.
Texto: cada termo ou frase vira uma chave; consultas combinadas são interseções.

Em todos esses casos o que importa é presença e interseção exatas sobre IDs — não payloads.
Estruturas genéricas (map, joins, varredura ordenada) resolvem isso — só não de forma otimizada:
carregam ponteiros, indireções e comparações desnecessárias quando o dado é o número.

A escolha central: trabalhar sempre com IDs uint64. Um conjunto é um monte de uint64; a
interseção é um AND. Tudo é aritmética.

O erro que valeu o projeto: 78% de colisão

Antes de existir conjunto, preciso de identificadores densos e sem colisão. O primeiro keygen foi um
hash posicional — uma fórmula aritmética simples. Ele colidia feio: numa base de 200 mil tokens
alfanuméricos curtos, 78% colidiam, e "Oa" e "0b" caíam no mesmo ID.

A correção foi implementar um Minimal Perfect Hash Function (CHD v2, do zero):

0 colisões numa base de 50 milhões de chaves;
4,03 bits/chave (≈ 24 MiB para 50M de chaves) — 3,4× menos memória que a v1 (13,68 bits/chave);
lookup em ~118 ns, e o pertencimento continua exato.

Se este artigo tiver uma única lição, é esta: medir a taxa de colisão no corpus real é o passo
que quase todo mundo pula — e é o que muda a arquitetura inteira.

Como funciona (do termo ao resultado)

Keygen (MPHF): termo → ID uint64 determinístico e sem colisão.
Representação: o ID i vira o bit i de um bitset; há também conjunto esparso (lista ordenada) e um híbrido (faixas quentes em bitset + cauda fria esparsa).
Kernel: o AND dos bitsets roda em AVX-512 (vpandq + vpopcntq) via cgo, com dispatch em runtime (__builtin_cpu_supports) e fallback escalar — o mesmo binário funciona em qualquer máquina.
Escala: o universo é fatiado em shards (paraleliza o compute); no cluster, cada nó serve um shard, o coordenador faz broadcast e soma, e um consistent hash ring decide a posse (entrar/sair um nó remapeia só ~1/(N+1) dos IDs).

Os números reais

Ambiente (todas as medições): servidor de referência — 2 vCPU AMD EPYC (Zen4, AVX-512), 3,8 GB
RAM, Go 1.22 (+ gcc para o cgo). Data: 09/2026.

Pertencimento (n = 1M)

Estrutura	memória	velocidade	exato?
`map[uint64]` (Go)	22,3 B/chave	133,3M ops/s	sim
SetrixDB (MPHF CHD v2)	0,5 B/chave (estrutura)	~118 ns/lookup	sim
Bloom filter (1% falso-positivo)	1,2 B/chave	23,6M ops/s	não

Paridade de velocidade com o map, com 2,2× menos memória — e resultado exato, ao contrário
de um filtro probabilístico.

Interseção (A = B = 1M)

Estratégia	IDs densos (`denso32`)	IDs aleatórios 64-bit (`aleat64`)
Merge ordenado (SetrixDB)	9,2 ms	11,3 ms
Roaring (bitmap comprimido)	148 µs	523 ms
Hash join (`map`)	91,6 ms	94,9 ms
Bitset `AND` (Go puro)	29 µs	—
Bitset `AND` (AVX-512)	6 µs	—

Onde ele perde (e por que isso importa)

Vou ser explícito, porque comparação sem contexto engana:

Universo esparso e enorme: quando o universo não cabe na RAM, o bitset denso deixa de ser opção (ele ocupa universo/8, sempre). Aí o Roaring ganha — é para isso que ele existe. Medido: universo 2²⁶, o Roaring64 usou ~2 MB contra 8,2 MB do meu bitset (mais lento em tempo, mais econômico em memória).
IDs aleatórios de 64 bits: no caso aleat64, o Roaring levou 523 ms — mas porque ele foi projetado para outro regime. O ponto não é “eu ganho sempre”; é em qual regime cada um brilha.
Range queries, similaridade, joins: o SetrixDB não faz. É igualdade pura.
Atualizações frequentes: um MPHF é construído para um conjunto; inserir/remover chaves novas exige reconstrução. Para cargas mutáveis, ele não é a ferramenta.

Então onde ele ganha? No regime oposto: universo denso que cabe em RAM, conjuntos grandes,
interseção exata no caminho quente. Foi exatamente o que um teste com dados reais mostrou ↓

Dados reais (nada de só sintético)

Rodei três datasets públicos e conferi cada resultado por fora do SetrixDB (sort + comm).

Varejo — Online Retail II (UCI)

1.067.371 linhas reais de venda (UK, 2009–2011). Consulta “Reino Unido E 4º tri/2011 E
preço ≥ 5” → 22.701 linhas em 823 µs. Verificação independente: 22.701. Idêntico.

Texto — títulos da Wikipédia (19,3 milhões de termos)

enwiki-latest-all-titles-in-ns0: 19.264.252 títulos. “multi-palavra E começa com s” →
1.408.399 em 9,5 ms; “multi-palavra E United” → 38.602 em 8,0 ms. Verificado: idêntico.

Escala — MovieLens 25M (25 milhões de interações)

25.000.095 avaliações reais; facetas derivadas (gênero, década, nota). Conjuntos com 10,9M e
12,4M de membros. Três consultas, todas verificadas por fora:

Consulta	Resultado
Drama E anos 2000 E nota ≥ 4	1.634.027
Drama E nota ≥ 4	6.096.563
Comédia E nota ≥ 4 E anos 2000	965.677

O resultado mais revelador deste teste é sobre escolher a representação certa. No mesmo
universo de 25M de IDs, com conjuntos de dezenas de milhões:

Caminho	memória/conjunto	latência (A∩B)
Merge de listas ordenadas	87,7 MB	80,4 ms
Bitset denso (AVX-512)	2 MB	227 µs

Mesmo resultado exato, ~350× mais rápido e ~43× menor. Quando o universo é denso e cabe na
memória, o bitset não é só o mais rápido: é o mais econômico também.

O que o SetrixDB É — e o que NÃO É

É um motor de conjuntos embarcável, em Go, que responde presença e interseção exatas
sobre IDs uint64, com kernel SIMD, sharding e modo de cluster. Ele coexiste com o seu banco
atual: o dado continua onde está; o SetrixDB entra ao lado como índice/pré-filtro.

Não é banco relacional, colunar, NoSQL ou vetorial. Não faz SQL, joins nem similaridade. E —
importante — guarda conjuntos de IDs, não payloads.

Limitações honestas

Alpha (v0.1.0). Testado em loopback e entre duas máquinas; o cluster de 3 nós rodou em nuvem, mas ainda não em produção multi-datacenter.
Memória do bitset é linear no universo (universo/8); o híbrido mitiga (2³⁶ IDs: 8,59 GB densos → 1,73 MB híbridos), mas é uma escolha com custo.
Backend de NPU e protocolo UDP compacto: roadmap, não implementados.
Benchmarks de energia (J/busca): planejados, ainda não medidos.
Se algum número não se reproduzir na sua máquina, isso é um bug — e eu quero saber.

Perguntas difíceis (e respostas)

“Por que não usar CRoaring/Roaring direto?”
Porque o Roaring é excelente — e é a resposta certa quando o universo não cabe em RAM ou é muito
esparso. O SetrixDB mira outro ponto: Go nativo, embarcável, universo denso que cabe em RAM, com
MPHF no keygen e sharding/cluster integrados. Se o seu caso é o do Roaring, use o Roaring.

“Por que não um map/Bloom filter?”
map guarda ponteiros e é ~44× mais gordo por chave (22,3 vs 0,5 B/chave aqui). Bloom é menorzinho,
mas erra (1% de falso-positivo) — em permissão, errar para o lado “pode ver” é inaceitável.

“MPHF aguenta inserção/remoção?”
Não. Ele é construído para um conjunto. Cargas mutáveis exigem reconstrução (ou o modo esparso). É
uma troca consciente por lookup O(1) e ~4 bits/chave.

“E o GC do Go no caminho quente?”
Os bitsets são []uint64 contíguos, alocados uma vez; o laço quente não aloca. Para DMA (NPU) há
UnsafePtr + pinning — com o aviso de manter o buffer vivo.

“Isso não é só ‘bitset com AVX-512’?”
Em parte, sim — e é bom que seja: bitset + SIMD é uma base sólida e conhecida. O que o projeto
adiciona é o pacote: keygen sem colisão, representação adaptativa (denso/esparso/híbrido),
sharding/cluster e o modo “conjuntos armazenados” (só o nome trafega na rede).

O convite

O SetrixDB é open source (Apache-2.0). Se a próxima onda não é sobre guardar mais, mas sobre
decidir mais rápido — e se operações de conjunto merecem um motor dedicado, exato e vetorizado,
ao lado do que você já usa — venha testar.

Código, benchmarks reproduzíveis e quickstart: https://github.com/setrixdb/setrixdb

Rode os benchmarks, abra uma issue e me diga onde os números não fecham.

SetrixDB — the arithmetic set engine.
Conjuntos. Em microssegundos. Em qualquer chip. Ao lado do seu banco.