Best way to index a SQL table to find best matching string <p>Let's say I have a SQL table with an <code>int</code> PK column and an <code>nvarchar(max)</code>. In the the <code>nvarchar(max)</code> column, I have a bunch of table entries that are all like this:</p> <pre><code>SOME_PEOPLE_LIKE_APPLES SOME_PEOPLE_LIKE_APPLES_ON_TUESDAY SOME_PEOPLE_LIKE_APPLES_ON_THE_MOON SOME_PEOPLE_LIKE_APPLES_ON_THE_MOON_CAFE SOME_PEOPLE_LIKE_APPLES_ON_THE_RIVER . . . SOME_ANTS_HATE_SYRUP SOME_ANTS_HATE_SYRUP_WITH_STRAWBERRIES </code></pre> <p>There's millions of these rows - Then let's say my goal is to find the row with the most overlap for an input <code>searchTerm</code> - So in this case, if I input <code>SOME PEOPLE_LIKE_APPLES_ON_THE_MOON_MOUNTAIN</code>, the returned entry would be the third entry from the table above, <code>SOME_PEOPLE_LIKE_APPLES_ON_THE_MOON</code></p> <p>I have a SPROC that does this very naively, it goes through the entire table as follows:</p> <pre><code>SELECT DISTINCT phrase, len(phrase) l, [id] FROM X WHERE searchTerm LIKE phrase + '%' -- phrase is the row entry being searched against -- searchTerm is the phrase we're searching for </code></pre> <p>I then <code>ORDER BY</code> length and pick the <code>TOP</code> only</p> <p>Would there be a way to speed this up, perhaps by doing some indexing?</p> <p>If this is confusing, think of it as <code>tableRowEntry + wildcard = searchTerm</code></p> <p>I'm on MSSQL 2008 if that makes any difference</p>