title: Creating a "spell check" that checks against a database with a reasonable runtime
body: <p>I'm not asking about implementing the spell check algorithm itself. I have a database that contains hundreds of thousands of records. What I am looking to do is checking a user input against a certain column in a table for all these records and return any matches with a certain hamming distance (again, this question's not about determining hamming distance, etc.). The purpose, of course, is to create a "did you mean" feature, where a user searches a name, and if no direct matches are found in the database, a list of possible matches are returned.</p>
  
  <p>I'm trying to come up with a way to do all of these checks in the most reasonable runtime possible. How can I check a user's input against all of these records in the most efficient way possible?</p>
  
  <p>The feature is currently implemented, but the runtime is exceedingly slow. The way it works now is it loads all records from a user-specified table (or tables) into <em>memory</em> and then performs the check.</p>
  
  <p>For what it's worth, I'm using NHibernate for data access.</p>
  
  <p>I would appreciate any feedback on how I can do this or what my options are.</p>