2

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' +'%'
4

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])
  • 1
    See also my SQLPerformance.com article Trigram Wildcard String Search in SQL Server – Paul White Oct 13 '17 at 8:28
  • Awesome article @PaulWhite. My current implementation has 11-30ms total execution time using the above solution. I have around 400k different models(varchar(75) column) in there resulting in 6 million rows in the product dictionary. Seeing how you've had 17m triangrams in your tests I think your method is faster ! – A_V Oct 13 '17 at 14:12
  • Also worth noting that I don't in any way support middle-of-string wildcard search the same way you do. I only search for "%string%" – A_V Oct 13 '17 at 14:14
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: enter image description here

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

enter image description here

Now using Full-Text Indexing:

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

enter image description here

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') 

enter image description here enter image description here

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

  • FTS depends on whole words, though, doesn't it? I don't think it will solve the case where the column holds I129LMH1HKC and the user searches for LMH1. – Aaron Bertrand Jul 24 '17 at 16:12
  • How does FTS handle parts? %hum% - 3 letters from the word human? – TomTom Jul 24 '17 at 16:12
  • I was actually referring to his example where he used word y-5151, assuming you would need to provide atlest word, to start autocomplete box. – S4V1N Jul 24 '17 at 16:20
  • For 3 letters, you could use where contains(*,'"*hum*"') and get expected results – S4V1N Jul 24 '17 at 16:27
-1

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.

  • It doesn't take 2.5 seconds for the most part, but SOMETIMES it does. Average run time is still over 1000ms for full wildcard search though. – A_V Jul 24 '17 at 13:59
  • 1
    @A_V thsoe SOMETIMES you should check to see what it's waiting on. It could be blocking or something else that is intermittent. – Aaron Bertrand Jul 24 '17 at 15:14

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.