T-SQL stored procedure to return google style "suggested" search results

Question

Ok, using SQL Server 2008. On my web page I have a textbox with jQuery-UI AutoComplete hooked up.

Now I need a stored procedure to search across all columns of a single table(or multiple joined tables I suppose) for a search string coming from the textbox/autocomplete AJAX call, and return "suggested" search strings. I am using the AdventureWorks db for testing(Products table)

So for example, the product table has columns for product name and product number(among others) and I want to return suggested search strings based on user input where they may enter a product name and/or a product number.

I have it working across a single column which was simple. Any ideas?

Answer 1

I'm going to suggest full text search (MS' or Lucene will work) The code below use MSSQL FTS as its what I use in my app at the moment.

Install FTS Search if you haven't already. If you have check the service is running. In management studio run this to setup a catalog and add the products table; and Color / Name / Product Number to the catalog.

USE [AdventureWorks]
GO
CREATE FULLTEXT CATALOG [ProductsTest]WITH ACCENT_SENSITIVITY = OFF
AUTHORIZATION [dbo]

GO

USE [AdventureWorks]
GO
CREATE FULLTEXT INDEX ON [Production].[Product] KEY INDEX [PK_Product_ProductID] ON ([ProductsTest]) WITH (CHANGE_TRACKING AUTO)
GO
USE [AdventureWorks]
GO
ALTER FULLTEXT INDEX ON [Production].[Product] ADD ([Color])
GO
USE [AdventureWorks]
GO
ALTER FULLTEXT INDEX ON [Production].[Product] ADD ([Name])
GO
USE [AdventureWorks]
GO
ALTER FULLTEXT INDEX ON [Production].[Product] ADD ([ProductNumber])
GO
USE [AdventureWorks]
GO
ALTER FULLTEXT INDEX ON [Production].[Product] ENABLE
GO

You can then run queries against all columns at once; e.g. Silver (Chosen as its in color and Name)

Select * from production.product where
contains(*, '"Silver*"')

The * on the query will find Silver* so you can use this to build up results as the user types in. One thing to consider is that google make this work in real time - if you are searching a lot of data you to be able to get the data back without interrupting the typing of the user. i think generally people use these searches by typing from the first letter they are looking for - i accept there will be spelling mistakes- you could implement a spell checker after every space they press perhaps to handle that. Or store the searches that are run and look at the mispellings and change the code to handle that based on a mapping (or in FTS using a custom thesaurus.)

Ranking is going to be a fun development issue to any business; are you finding the first result for Mountain Frame -or do you want to weight them by sales or price? If the user types in more than one text term you can use FTS to produce a ranking based on the search string.

select aa.rank, bb.* 
From containstable(production.product, *, '"Mountain" and "Silver*"') aa
inner join production.product bb
on aa.[key] = bb.productid
order by rank desc

This returns 30 rows; and weights based on the user inputted text to determine the first place record. In either case you will likely want to add a coded ranking to tweak the results to suit your business desires - ranking te highest priced widget 1 might not be the way. That is why you are going to store what people searched for / clicked on so you can analyse the results later.

There is a really nice language parser for .Net that translates a google style string query inputted into FTS'able language which gives familiarity for any boolean searches that use your site.

You may also want to add some wisdom of crowds features by auditing against what users have input and ultimately gone to visit and use success maps to alter the final suggestions to actually make them relevant to the user.

As a final suggestion if this is a commercial website you might want to look at Easyask which is a scary great natural language processor

Answer 2

Using the soundex function would be the simplest way to match for similar "items" in several columns. But a better matching algorithm that will be nearly as fast to implement is the Levenshtein Edit Distance. Here is the T-SQL implementation wrapped in a function. Use it to match for similar search terms.

EDIT Sample of Levenshtien in action (based on gbn's SQL)

Suppose you named your Levenshtein T-SQL function lvn (just fro brevity's sake) then you could do something like:

SELECT productname FROM foo WHERE productname 
    LIKE '%myinput%' OR lvn(myinput) < 3
UNION
SELECT productnumber FROM foo WHERE productnumber 
    LIKE '%myinput%' OR lvn(myinput) < 3
UNION
...

ORDER BY 1 -- one-based column index sort for UNION queries

Yep. that simple. Btw, i updated the T-SQL levenshtein link to something that makes more sense, and it's an accepted SO answer.