Dit lijkt vanaf het begin een probleem. Elke vorm van zoeken die u doet, vereist een tabelscan en we weten allemaal dat dat slecht is.
Hoe zit het met het toevoegen van een kolom met een hash van de huidige telefoonnummers nadat alle opmaaktekens zijn verwijderd. Dan kun je in ieder geval de hash-waarden indexeren en een volledige tabelscan vermijden.
Of is de hoeveelheid data klein en wordt er niet veel verwacht? Dan misschien gewoon alle cijfers in de client zuigen en daar een zoekopdracht uitvoeren.