PostgreSQL 18: Indici BTree vs Hash — Un Benchmark

Ho eseguito benchmark su PostgreSQL 18.4 con 100K righe per tabella, confrontando indici BTree e Hash su tre tipi di colonna (char(1), varchar(10), varchar(1000)) e due distribuzioni di dati: 3 valori distinti (codici di stato) e valori casuali (26–100K distinti). Ogni tabella ha una colonna di padding char(100) per simulare una larghezza di riga realistica. Tutte le query sono con cache calda con 5 iterazioni di warmup + 30 iterazioni misurate; si riporta la mediana (p50).

Archiviazione

Dati	Tipo	Heap	BTree	Hash
Stato (3 distinti)	char(1)	14 MB	704 KB	6,592 KB
	varchar(10)	14 MB	696 KB	6,248 KB
	varchar(1000)	112 MB	712 KB	6,064 KB
Casuale (26–100K distinti)	char(1)	14 MB	704 KB	5,984 KB
	varchar(10)	14 MB	3,104 KB	4,680 KB
	varchar(1000)	112 MB	156 MB	4,112 KB

Con 3 valori distinti, la deduplicazione BTree archivia ogni chiave una sola volta con una posting list. Tutti gli indici BTree sono circa 700 KB indipendentemente dalla larghezza della chiave. Gli indici Hash non possono deduplicare — sono 8–9 volte più grandi a 6 MB perché ogni riga ottiene la propria voce nel bucket.

Con valori casuali la situazione si capovolge per chiavi larghe. Il BTree su varchar(1000) è 156 MB (più grande dell'heap), mentre l'indice Hash è solo 4 MB — una riduzione di 38 volte. Hash archivia solo un codice hash di 4 byte per riga indipendentemente dalla larghezza della chiave.

Prestazioni delle query: WHERE status = ?

Dati	Tipo	BTree (p50)	Hash (p50)	Scansione BTree	Scansione Hash
Stato (3 distinti)	char(1)	4.15 ms	7.93 ms	Index Only	Seq Scan
	varchar(10)	4.19 ms	6.41 ms	Index Only	Seq Scan
	varchar(1000)	10.90 ms	21.88 ms	Index Only	Seq Scan
Casuale (26–100K distinti)	char(1)	0.24 ms	1.30 ms	Index Only	Bitmap
	varchar(10)	0.06 ms	0.05 ms	Index Only	Index Scan
	varchar(1000)	0.06 ms	0.05 ms	Index Only	Index Scan

Per le colonne di stato a bassa cardinalità, il planner ignora completamente l'indice Hash e usa una Seq Scan — con ~33K righe corrispondenti per valore, gli accessi casuali all'heap tramite Hash sarebbero più lenti della lettura sequenziale della tabella da 14 MB. Il BTree deduplicato (~700 KB) abilita le Index Only Scan che non toccano mai l'heap.

Per le ricerche puntuali ad alta cardinalità (trovare 1 riga), BTree e Hash sono appaiati sotto il millisecondo. L'indice Hash su varchar(1000) è 38 volte più piccolo (4 MB contro 156 MB), ma poiché l'intero BTree resta in memoria, l'attraversamento è comunque veloce nei test a cache calda.

WHERE status IN (...) e GROUP BY

Query	Tipo	BTree (p50)	Hash (p50)
IN (2 valori)	char(1)	3.3 ms	10.89 ms
	varchar(10)	3.36 ms	10.09 ms
GROUP BY	char(1)	7.55 ms	14.09 ms
	varchar(10)	8.22 ms	14.72 ms

Le query IN e GROUP BY svantaggiano ulteriormente Hash sui dati a bassa cardinalità. Gli indici BTree restituiscono le righe in ordine e restano compatti con la deduplicazione. Gli indici Hash non forniscono ordinamento e, in queste distribuzioni, il planner ricade spesso su piani basati su Seq Scan.

Conclusioni

• Bassa cardinalità (codici di stato, enumerazioni): Usate sempre BTree. La deduplicazione rende l'indice ~700 KB indipendentemente dalla larghezza della chiave, abilita le Index Only Scan, e il planner non userà un indice Hash qui. char(1) risparmia spazio heap; la dimensione dell'indice è la stessa.
• Alta cardinalità con chiavi larghe (UUID, stringhe lunghe): Gli indici Hash sono molto più piccoli (4 MB vs 156 MB per varchar(1000)). Per ricerche di uguaglianza pure sono veloci quanto BTree. Ma non supportano ordinamento, range, unicità o Index Only Scan.
• Alta cardinalità con chiavi corte: BTree e Hash sono simili in dimensione e velocità. BTree vince per generalità — usatelo a meno che non abbiate una ragione specifica per Hash.
• Non usate mai Hash per colonne di stato: il planner lo ignora in favore di una Seq Scan, sprecando 6 MB di disco e memoria.

Metodologia

• PostgreSQL: 18.4 (Debian), Docker, shared_buffers=512MB, work_mem=64MB
• Righe: 100.000 per tabella, 3 valori distinti (stato) o 26/100K distinti (random)
• Timing: 5 iterazioni di warmup scartate, 30 registrate, p50 riportata
• Indici: BTree standard (deduplicazione abilitata) vs Hash, fillfactor predefinito
• Riproducibilità: bench.sh nel repository — completamente automatizzato