Fastest way to find string by substring in SQL?

Question

I have huge table with 2 columns: Id and Title. Id is bigint and I'm free to choose type of Title column: varchar, char, text, whatever. Column Title contains random text strings like "abcdefg", "q", "allyourbasebelongtous" with maximum of 255 chars.

My task is to get strings by given substring. Substrings also have random length and can be start, middle or end of strings. The most obvious way to perform it:

SELECT * FROM t LIKE '%abc%'

I don't care about INSERT, I need only to do fast selects. What can I do to perform search as fast as possible?

I use MS SQL Server 2008 R2, full text search will be useless, as far as I see.

Answer 1

Create index view there is new feature in sql create index on the column that you need to search and use that view after in your search that will give your more faster result.

Answer 2

If you want to use less space than Randy's answer and there is considerable repetition in your data, you can create an N-Ary tree data structure where each edge is the next character and hang each string and trailing substring in your data on it.

You number the nodes in depth first order. Then you can create a table with up to 255 rows for each of your records, with the Id of your record, and the node id in your tree that matches the string or trailing substring. Then when you do a search, you find the node id that represents the string you are searching for (and all trailing substrings) and do a range search.

Answer 3

You can add another calculated column on the table: titleLength as len(title) PERSISTED. This would store the length of the "title" column. Create an index on this.

Also, add another calculated column called: ReverseTitle as Reverse(title) PERSISTED.

Now when someone searches for a keyword, check if the length of keyword is same as titlelength. If so, do a "=" search. If length of keyword is less than the length of the titleLength, then do a LIKE. But first do a title LIKE 'abc%', then do a reverseTitle LIKE 'cba%'. Similar to Brad's approach - ie you do the next difficult query only if required.

Also, if the 80-20 rules applies to your keywords/ substrings (ie if most of the searches are on a minority of the keywords), then you can also consider doing some sort of caching. For eg: say you find that many users search for the keyword "abc" and this keyword search returns records with ids 20, 22, 24, 25 - you can store this in a separate table and have this indexed. And now when someone searches for a new keyword, first look in this "cache" table to see if the search was already performed by an earlier user. If so, no need to look again in main table. Simply return results from "cache" table.

You can also combine the above with SQL Server TextSearch. (assuming you have a valid reason not to use it). But you could nevertheless use Text search first to shortlist the result set. and then run a SQL query against your table to get exact results using the Ids returned by the TExt Search as a parameter along with your keyword.

All this is obviously assuming you have to use SQL. If not, you can explore something like Apache Solr.

Answer 4

Sounds like you've ruled out all good alternatives.

You already know that your query

SELECT * FROM t WHERE TITLE LIKE '%abc%'

won't use an index, it will do a full table scan every time.

If you were sure that the string was at the beginning of the field, you could do

SELECT * FROM t WHERE TITLE LIKE 'abc%'

which would use an index on Title.

Are you sure full text search wouldn't help you here?

Depending on your business requirements, I've sometimes used the following logic:

• Do a "begins with" query (LIKE 'abc%') first, which will use an index.
• Depending on if any rows are returned (or how many), conditionally move on to the "harder" search that will do the full scan (LIKE '%abc%')

Depends on what you need, of course, but I've used this in situations where I can show the easiest and most common results first, and only move on to the more difficult query when necessary.

Answer 5

1. Use ASCII charset with clustered indexing the char column. The charset influences the search performance because of the data size on both ram and disk. The bottleneck is often I/O.
2. Your column is 255 characters long so you can use normal index on your char field rather than full text, which is faster. Do not select unnecessary columns in your select statement.
3. Lastly, add more RAM to the server and Increase cache size.

Answer 6

if you dont care about storage, then you can create another table with partial Title entries, beginning with each substring (up to 255 entries per normal title ).

in this way, you can index these substrings, and match only to the beginning of the string, should greatly improve performance.