I have a database table holding 40 million records (table A).

Each record has a string a user can search for.

I also have a table with a list of character replacements (table B) i.e. i = Y, I = 1 etc.

I need to be able to take the string a user is searching for, iterate through each letter and create an array of every possible outcome (the users string, then each outcome with alternative letters used).

I need to check for alternatives on both lower and uppercase letters in the word

A search string can be no longer than 10 characters long.

I'm using PHP and a MySQL database.

Does anyone have any thoughts / articles / guidance on doing this in an efficient way?