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?

  • Step 1 would be get some good indexes on your database – Tom Squires Aug 17 '12 at 9:14
  • indexing etc is in place, were more concerned about the algorithm to find a all the possible outcomes of the string and its replacements – Samuel Cambridge Aug 17 '12 at 10:52
  • Could you please provide an example. – NoChance Aug 17 '12 at 12:03
  • ok, lets say the table A contained the strings YES,Y3S,Y55, NO, N0 and the user searched for "YES" in table B there is E = 3, S = 5, the code figure out all avaialable versions of the word yes, IE YES, Y3S, Y35 and find all 3 from table A doing a simple find would obviously only return YES, so i need to get an array of all possibles and do an IN() or something similar. This example does not show lowercase letters that also need to be handled. – Samuel Cambridge Aug 17 '12 at 13:12

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

It sounds like an RDBMS is not appropriate for this task.

As @Jim Arnold says, you should use either Lucene or Endeca for this task.


Here is what I see possible based on my understanding:

One way is to create a column (preferably on table A) and have a database trigger (or write code in your language) such that whenever a row is inserted or update, a new column (shown below as "SearchColumn") would get populated with ONLY ONE STANDARD FORMAT of the string value. In the example blow I have arbitrary chosen upper case.

The seach column need to have a non-unique index.

When the user performs a search for say,'yes', you do:

SELECT FROM myTable WHERE SearchColumn="YES" (see the last paragraph regarding the index cases sensitivity).

myTable would include the following columns (amongst others of course):

OriginalColumn, SearchColumn



Y55, YSS

yes, YES


N0, NO


By doing this, you don't need to perform non-indexed row searching. This method, since it uses an index will be very fast. The overhead of processing the extra column should not be significant, unless you have simultaneous thousands of concurrent inserts/updates.

In MySQL (and some other database), you can control whether an index uses case sensitivity or not via the column collating properties definition.

  • Y55 would be YSS not YES. But I think that you would need to map Y55 to Y5S, YS5, YSS, and Y55 for the purposes of the search. – Sign Aug 17 '12 at 14:09
  • @Sign, thank you for your comment. I am not sure why we need to map those strings if the user input is 'YES'. Mapping would be required if user input is 'Y55' and the user is expecting 'YES' to be returned. Maybe the PO could clarify this for us. – NoChance Aug 17 '12 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.