Hai ragione, rileggendo bene la parte dell'articolo che valuta le performance l'autore dice:

Because of the functions being performed on the rows, this type of query cannot benefit from an index. This means that the entire table will have to be scanned to find matches to user 8. However, as this is a bitwise operation, it should be quite efficient in spite of the full table scan (I was able to perform this operation on a randomly generated table of 500,000 rows and have 250,000 rows returned in 1.89 seconds on my 1.6 Ghz PC).
In pratica l'operazione di ricerca su campi set non può beneficiare di indici, ma ciononostante è molto veloce (credo per la velocità delle operazioni bitmask di cui parlavi tu) tanto che su una tabella random di 500000 righe in meno di 2 secondi ha tirato fuori la metà di campi con una WHERE CLAUSE che valutava i valori SET.

Ok, userò questo data type!
Grazie!