non esiste un metodo semplice, e veloce.

un modo veloce, ma non così semplice, è quello di simulare una ricerca full-text all'interno della stringa, appoggiandoti ad un motore esterno tipo sphinx.

se usi mariadb, in realtà, è praticamente "interno" (lato php), altrimenti devi usare funzioni specifiche per la ricerca (niente di che, ma non è immediato).
---
Puoi ottenere tempi dell'ordine di poche decine di millisecondi su tabelle con milioni di righe, SENZA tra l'altro caricare il server sql più di tanto (ritorna per default un massimo di 1000 righe, ma nel tuo caso immagino siano molte meno)