Quando l'indice HNSW non serve a niente — DuckDB VSS in pratica

Stavo leggendo l'altro giorno questo post sui vettori HNSW, e da lì ho deciso di condividere qualche riflessione sulla mia esperienza nata durante la riprogettazione di questo sito, basato su un generatore di siti statici (questa volta scritto in Python).

Questo nuovo generatore di siti statici, tra le altre cose, calcola la similarità semantica tra i post del blog in modo che la fase di build possa eseguire automaticamente tre operazioni:

• mostrare i "post correlati" in fondo a ogni articolo,
• accoppiare le traduzioni inglesi e italiane per hreflang, e
• suggerire opportunità di internal link a livello di chunk.

Tutte e tre si basano sulla cosine similarity calcolata su embedding di sentence-transformers, memorizzati e interrogati dentro l'estensione VSS di DuckDB.

Quando ho messo in piedi questa parte la prima volta, ho aggiunto un indice HNSW. Sembrava la cosa ovvia da fare — i vettori meritano un indice vettoriale, e perfino la documentazione lo incoraggia. Se non che ho scoperto che l'indice non veniva mai utilizzato. Su nessuna delle tre query. Me ne sono accorto per caso: l'SQL che avevo scritto non corrispondeva al pattern di cui aveva bisogno l'optimiser di DuckDB per invocare HNSW.

Questo è un articolo post-mortem per ricordare quale tipo di errore sia facile commettere quando si cerca di utilizzare un "indice vettoriale", e il costo di sbagliare è invisibile perché il dataset è cosi piccolo che le operazioni di interogazzione finiscono comunque in millisecondi.

Cos'è HNSW?

HNSW sta per Hierarchical Navigable Small World. È un algoritmo basato su grafi per la ricerca approssimata di nearest-neighbour in spazi ad alta dimensionalità — la struttura dati cavallo di battaglia dentro Pinecone, Weaviate, Qdrant, FAISS e nelle estensioni VSS di Postgres (pgvector) e DuckDB.

Il modo in cui sono arrivato a visualizzarlo, dopo un paio di letture sofferte del paper originale: c'è un grafo a livelli che si stratifica sopra i vettori. Il livello più alto è sparso — solo una manciata di nodi — e ogni livello sottostante è progressivamente più denso, fino al livello più basso che contiene ogni vettore che ho indicizzato. Quando lancio una query mi calo nel livello più alto, cammino avidamente verso il vettore di query, scendo di un livello, raffino, e proseguo finché non tocco il fondo. Il costo per query collassa dallo scan O(N) che pagherei altrimenti a circa O(log N) — e la prima volta che mi è scattato in testa ricordo di aver pensato che fosse un'idea quasi troppo elegante per essere vera.

Questa è la magia, e funziona davvero. Su un milione di vettori HNSW finisce una query top-K in decine di microsecondi quando uno scan esaustivo impiegherebbe secondi. È per questo che ogni database vettoriale moderno vi fa affidamento.

L'inghippo — ed è la parte che mi era sfuggita — è che HNSW sa rispondere soltanto a un tipo di domanda: "dato questo singolo vettore di query, quali sono i suoi K nearest neighbour nell'indice?" Questa è l'unica operazione. Tutto il resto sta a te e al tuo query planner.

Perché ho aggiunto l'indice in primo luogo

Quando ho innestato VSS di DuckDB nella build pipeline, il codice somigliava a questo:

con.execute("INSTALL vss; LOAD vss;")
# … bulk-load article vectors …
con.execute("""
    CREATE INDEX hnsw_idx ON articles
    USING HNSW (embedding) WITH (metric = 'cosine')
""")

Ho aggiunto la riga CREATE INDEX con il pilota automatico. Il ragionamento era: ho una colonna FLOAT array a 384 dimensioni, la interrogherò per similarità, è quello che si fa. I log della build dicevano che l'indice era stato creato con successo e sono passato alla cosa successiva.

Quello che non ho fatto — e che avrebbe colto l'errore immediatamente — è stato eseguire EXPLAIN ANALYZE sull'SQL effettivo che l'applicazione stava lanciando.

Le tre query

La similarità vettoriale viene utilizzata in tre differenti parti del sito:

1. Post correlati, in fase di build. Per ogni articolo, trovare i top-3 fratelli nella stessa lingua.
2. Suggerimenti hreflang. Per ogni post inglese, trovare la controparte italiana più vicina sopra una soglia alta.
3. Generazione di Internal link (aggiunti dopo). Per ogni chunk di ogni corpo articolo, trovare i top-3 post con cosine ≥ 0,55, escludendo l'articolo sorgente.

Tutte e tre condividono la stessa struttura — un self-join sulla colonna embedding, la cosine calcolata come colonna, e una window function ROW_NUMBER() che seleziona i top-K per ogni sorgente. La query di internal link, la più pesante delle tre, ha questa forma:

WITH pairs AS (
    SELECT c.slug AS src, c.chunk_idx,
           a.slug AS dst,
           array_cosine_similarity(c.embedding, a.embedding) AS score
    FROM   chunks c, articles a
    WHERE  c.lang = a.lang AND c.slug != a.slug
),
ranked AS (
    SELECT src, chunk_idx, dst, score,
           ROW_NUMBER() OVER (PARTITION BY src, chunk_idx
                              ORDER BY score DESC) AS rn
    FROM   pairs WHERE score >= ?
)
SELECT src, chunk_idx, dst, score
FROM   ranked WHERE rn <= ?

È un CROSS JOIN che materializza ogni coppia (chunk, articolo), calcola la cosine sfruttando il motore colonnare vettorizzato di DuckDB, e infine partiziona e ordina. In nessuno di questi passaggi il planner riconosce l'unica forma che saprebbe risolvere come ricerca diretta sull'indice HNSW, che è grossomodo:

SELECT slug FROM articles
ORDER BY array_cosine_similarity(embedding, ?) DESC
LIMIT K

Un vettore passato come parametro, ORDER BY similarity, LIMIT K: questa è l'unica forma — per quanto ne sappia — in grado di attivare HNSW. Quando invece la cosine compare come colonna del risultato — come nel nostro CROSS JOIN, nel self-join della query dei post correlati e nella query delle coppie hreflang — DuckDB non sa usare HNSW e finisce per calcolare la similarità a mano, per ogni possibile coppia di righe. L'indice resta in memoria senza rispondere a una sola query.

Il benchmark

Una volta capito questo, volevo vedere come si comportavano le alternative. Ho scritto un piccolo benchmark che esegue tre approcci diversi sullo stesso dataset, confrontandone il tempo wall-clock e la corrispondenza dei risultati:

Ho eseguito ogni metodo tre volte sul sottoinsieme inglese del corpus — 118 post divisi in 2.111 chunk a livello di frase, ≈530.000 coppie (chunk, articolo) da valutare:

Tutti e tre i metodi hanno prodotto risultati byte-per-byte identici — recall 1,0000, zero mancanti, zero in eccesso. Non si tratta quindi di un compromesso sulla qualità: è una pura questione di prestazioni.

Perché ogni non-vincitore perde

Il metodo B è catastroficamente lento per un motivo che non ha nulla a che vedere con HNSW. Ogni iterazione del loop paga un round-trip Python-DuckDB di circa 60 ms solo per inviare il vettore e recuperare il risultato. Su 2.111 chunk si arriva a ≈127 secondi prima ancora che HNSW possa fare qualcosa di utile. Il risparmio O(log N) all'interno di DuckDB è reale ma minuscolo — forse un millisecondo per chiamata contro una scansione a forza bruta di 250 articoli — e il costo del round-trip lo supera di due ordini di grandezza.

Il metodo C è più interessante, perché sulla carta sembra perfetto. È un singolo statement SQL — niente loop Python, niente round-trip — e usa LATERAL, un costrutto che, per ogni riga della query esterna, ri-esegue la subquery interna con i valori di quella riga. E la subquery interna è scritta esattamente nella forma che HNSW sa riconoscere: un vettore in input, ORDER BY similarity, LIMIT K.

Solo che non funziona. Ho chiesto a DuckDB il piano di esecuzione reale con EXPLAIN ANALYZE e ho scoperto che, per ogni chunk di partenza, l'optimiser ignora HNSW e scorre l'intera tabella — esattamente come fa la forza bruta. L'indice resta in memoria a non far niente anche qui. In più, la query paga il costo aggiuntivo della macchineria LATERAL — preparare la subquery, eseguirla riga per riga, raccogliere i risultati — sopra a quella stessa scansione completa. Risultato netto: 1,9× più lenta del semplice CROSS JOIN a forza bruta del metodo A.

Quindi, a questa scala, tutti e tre i metodi restituiscono le stesse risposte: due sono più lenti dell'approccio più semplice, e l'unico che usa davvero HNSW è anche di gran lunga il peggiore.

Perché la forza bruta vince con database di piccole dimensioni

Due fattori si sommano a rendere la forza bruta la risposta giusta su N piccolo:

1. Il motore colonnare di DuckDB vettorizza il loop del prodotto scalare. Calcolare la cosine su una colonna FLOAT[384] per 800.000 coppie si completa in meno di un secondo su un laptop, perché il loop interno è SIMD-friendly e i dati risiedono contigui in memoria. Non c'è alcuna magia residua da estrarre con un'ottimizzazione.
2. Round-trip e overhead del planner non sono gratis. Con N piccolo ogni chiamata a DuckDB porta con sé centinaia di microsecondi — fino a qualche millisecondo — di costo fisso, e questa soglia minima basta da sola ad annullare il risparmio logaritmico di HNSW finché l'indice non diventa abbastanza grande.

Il punto di pareggio oltre il quale HNSW comincia davvero a vincere dipende dalla forma della query e dal linguaggio usato per emetterla, ma nel nostro caso si trova da qualche parte sopra i 10.000 elementi indicizzati — e solo a condizione che il planner di DuckDB acquisisca il supporto per almeno uno dei pattern con JOIN. Sotto quella soglia, la forza bruta è lo strumento giusto.

Cosa ho cambiato

Ho rimosso la riga CREATE INDEX hnsw_idx ON articles USING HNSW (embedding) dal servizio degli embeddings. La build è leggermente più veloce (nessun tempo speso a costruire un indice che nessuno interroga) e l'SQL resta invariato. Tutte e tre le query — post correlati, coppie hreflang, suggerimenti di internal link — continuano a funzionare esattamente come prima, perché eseguivano già un calcolo a forza bruta.

Quando il corpus crescerà abbastanza da meritarsi una revisione, la mossa giusta sarà un loop Python con ORDER BY similarity LIMIT K — il metodo B del benchmark — momento in cui l'overhead di round-trip diventa un costo fisso che vale la pena pagare per il guadagno O(log N) per chiamata.

La lezione

L'errore non è stato aggiungere un indice HNSW. L'errore è stato dare per scontato che l'indice venisse usato solo perché era stato creato. Due abitudini che sto cercando di interiorizzare:

• Un indice vettoriale non è una proprietà della colonna. È una proprietà delle query che il planner riscrive se necessario. "Index created successfully" non è sinonumo che le query utilizzeranno l'indice come si presuppone. L'unica risposta autoritativa è l'uso di EXPLAIN ANALYZE: leggendo il piano di esecuzione, se l'operatore sull'indice non esiste, allora neanche i benefici ad esso collefato esistono.
• Non ricorrere a un indice finché la query non è davvero troppo lenta per essere utilizzata in produzione. Con un numero di recordo N piuttosto piccolo, lo scan colonnare vettoriale di DuckDB è difficile da battere. Gli indici ripagano quando il loro costo ammortizzato (O(log N) per chiamata invece di O(N)) supera l'overhead per chiamata — che significa che servono sia un N abbastanza grande sia una query supportata dal planner. Se manca una delle due, l'indice è solo un peso morto.

La maggior parte del mio tempo di debugging negli ultimi anni è andata in cose che sembravano funzionare perché i log lo suggerivano. La soluzione è stata la cancellazione di una riga. La lezione è sempre la stessa: verifica sempre, non dare mai per scontato.