Autocomplete too slow: possible optimizations?

Question

The autocomplete search functionality of my website searches a varchar field which contains the model number of sale items.

This field can contains strings varying from 1 to 75 characters and the table contains 400 000 rows. I have come up with a query that searchs only from the start of the string and that takes about 150-250ms to execute which is acceptable but now my manager wants the query to search for any substrings which makes the query 3-10 times slower (around 1000-2000ms).

I have built a JS fiddle to give you an example of what the data looks like and what the two query are like.

http://sqlfiddle.com/#!6/9efa3/2/0

There already are a few indexes on the table. What would be the best practice to speed-up this auto-complete search field ? (database version is SQLSERVER 2008R2)

Here is a brief example of the data I'm dealing with :

CREATE TABLE [Products](
    [productid] [int] IDENTITY(1,1) NOT FOR REPLICATION NOT NULL,
    [model] [nvarchar](75) NOT NULL 
 CONSTRAINT [PK_Products] PRIMARY KEY CLUSTERED 
(
    [productid] ASC
));

insert into products values ('UMPX1AA0011 danish e-315 woot');
insert into products values ('P27y719VC');
insert into products values ('VG2y439m-LED');
insert into products values ('UMUyX165AAB01');
insert into products values ('U28y79VF');
insert into products values ('U52417HJ');
insert into products values ('VA25746M-LED WITH FLYING CORNERS');
insert into products values ('S19F350HNN 1pc california storage');
insert into products values ('VA211917A');
insert into products values ('PM2500X2');
insert into products values ('E22470SWHE');
insert into products values ('V22465WLYDP');
insert into products values ('I129LMH1HKC');
insert into products values ('OM5EN X 35 the new version');
insert into products values ('DLS3060WDB');
insert into products values ('PVW');
insert into products values ('LI23721S');
insert into products values ('V173516LBM');
insert into products values ('VX2376-SMHD-A');
insert into products values ('GUM5FX1AA1001');
insert into products values ('GPM300X11');
insert into products values ('GUM-WH6AA002');
insert into products values ('2435V5LSB');
insert into products values ('P2418HZ');
insert into products values ('Stylish sectional one of a kind y-5151');

and these are the two queries I'm comparing

--runs acceptably fast, about 100-250ms
select * from products where model like 'y-5151'+'%';
--takes too long, around 1000-2500ms
select * from products where model like '%' + 'y-5151' +'%'

Answer 1

The solution I went with is to build a "half-triangram" table which contains a pre-processsed version of all the model # substrings as suggested by Aaron Bertrand in the two following blog posts of his :

https://sqlperformance.com/2017/02/sql-indexes/seek-leading-wildcard-sql-server

https://sqlperformance.com/2017/02/sql-performance/follow-up-1-leading-wildcard-seeks

The solution for me was to create a new table where I look for models starting with the search string. Each model is listed as such, let's say the product_ID was 51 and the model was 7500 Twin Bed

ID|Model
----------------
51|7500 Twin Bed
51|500 Twin Bed
51|00 Twin Bed
51|0 Twin Bed
51| Twin Bed
51|Twin Bed
51|win Bed
51|in Bed
51|n Bed
51| Bed
51|Bed
51|ed
51|d

This way you never need to do a full wildcard search, a simple select distinct id_product from products_dictionary where model like 'Twin%' will return the required results. The query now takes less than 100ms.

Here is the code I used to create the table and populate it. Again, this is all described properly on Aaron's blog post:

CREATE TABLE [dbo].[products_dictionary](
    [Id_product] [int],
    [model] [nvarchar](75) NOT NULL
)
insert into [products_dictionary] 
select p.id_product,f.fragment from products p 
cross apply dbo.CreateStringFragments(p.model) AS f;

create clustered index index_idprod_substrmodel on [Products_dictionary]([model],[Id_product])

Answer 2

Fulltext index is usually "go to" option when you need to do complex and intensive string searches, as its based on a dictionary created from string values,rather than scanning a whole table each time(which is the case when you are using '% some text %' type of searching),it will use index seek instead if query optimizer consulting with dictionary determines that.

I created a table and populated it with 100,000 records.

Just using regular search pattern like :

select * from products where model like '%' + 'kind' +'%'

I`ve got this result:

Note there were 1102 records returned, using same query with other word returning one row select * from products where model like '%' + 'human' +'%':

Now using Full-Text Indexing:

Using a query: select * from products where freetext(model,'kind')

It really works the best when few rows are returned because it uses index seek,instead of scan

select  * from products where freetext(model,'Human') 

Another thing to note:

Your queries might get slower than expected 'sometimes' in case when there is some kind of blocking going on. It can happen when some one is trying to update or insert the record and is holding (X) lock on a page containing that row/rows. Which is the same page you will be requesting when searching a query using '% some text %' format, due to full table scan.

Using full-text indexing could avoid these situations using index seek,unless you are searching for exact same record, that has been updated at that moment.

There are also many searching variations,fuzzy matching, "spell checking" variations which could be of a great use.

There is a book Pro Full-Text Search in SQL Server 2008 which could help you building a proper search query

Answer 3

There is no real way to speed this up. "In the middle" means no index will be used, period. (as in: this is the way sql server is built).

What you could do is load those strings onto a separate table and then optimize your sql to not issue any locking statements (with reacommitted). An in memory table may be the next step.

There is no way a search on 400.000 strings of max 80 characters takes 2.5 seconds - there is locking congestion or other things going on. Make sure you set proper locking hints.