OK so it’s live – and achieved using no more than some C#/Java and SQL database skills! It helps me answer the question: Can I get to a particular product faster than via our standard web offering (of departments, aisles and shelves, or text searching)? Does it for you?
Go play at http://www.techfortesco.com/tescoinstant !!
The rest of this article is about the technical design and implementation, of interest to anyone wishing to look at similar solutions.
Step 1 – Design!
I created a database with the following tables and developed code that used the API to extract the products for a particular store (Greenford Dotcom Store which serves all homes in north London) and perform ‘lexicon analysis’ to make the data available efficiently.
My theory was that, if I broke all products down into their constituent words (called the ‘Lexicon’), and indexed those words efficiently using all possible key combinations up to 5 characters, then I could make product searching really fast!
Pencil, paper and SQL Enterprise Manager brought me to this design (note that there are extra clustered indices applied to the final design that are not shown in this diagram):
Step 2 – Get The Data
Using the Tesco grocery API I parsed through all the departments, aisles and shelves and copied some essential product data – just ProductID, BaseProductID (known as TPNB for future use when I hook up the application to the Tesco API for ‘add to basket’) and the product’s description name into a table called ProductsTable – totalling 21,638 rows.
Step 3 – Extract and store individual words to create the Lexicon. I took each product description and extracted individual words thanks to C#’s String.Split(‘ ‘) method using space ‘ ‘ as a delimiter. Each word was inserted into the LexiconTable (unless it was already there, in which case I just incremented the ProductCount value at the rate of one per product – a value which would be useful later).
Since I was creating a many-to-many relationship between ProductTable and LexiconTable (that is, products have more than word and each word can be used by more than one product), I also created a lookup table – LexiconProductTable. That way I could get to list the products quickly using any particular word much because it would be indexed (the alternative would have been to search for all products containing a particular word using the ‘LIKE’ keyword in SQL, which is highly inefficient and slow).
LexiconTable ended up with 11,237 unique words that described all the Tesco products, and LexiconProductTable had inserted 124,413 lookup rows.
If I sort by descending product count, I can uncover the top words used in most Tesco products! Intrigued? Here is the top 20:
10
Tesco
6288
4
And
2337
14
Pack
1320
136
Chicken
873
238
75Cl
732
311
500G
714
275
Sauce
665
150
Finest
661
49
400G
660
29
In
638
199
200G
627
60
Chocolate
623
47
250Ml
568
21
Value
532
24
1
517
465
2
517
266
250G
508
37
4
498
120
Organic
486
25
Litre
475
The left column is the LexiconID unique identifier, and the right column is the count of the number of products in which the word is used.
Step 4 – Build Indexed Searching based in anticipated input Now to get this application fast-acting when anyone typed in a search character. I needed a table that had a unique match for up to the first 5 letters typed in. That’s ANY 1, 2, 3, 4, or 5 characters from ‘aaaaa’ to ‘zzzzz’ as long as there at is at least one lexicon word that satisfies the particular combination. Index this match and the system should react like lightning!
To do this I wrote some code to look at each word in the LexiconTable that had an ‘a’ in it and, if so, inserted an entry into a new table, LexiconSearchCharTable. I then searched ‘b’, ‘c” and so on. Indeed I had a 5-nested search loop that efficiently checked for up to 5-letter combinations from ‘aaaaa’ to ‘zzzzz’ like this:
Does the current Lexicon word I am studying have an ‘a’? If yes, does it have an ‘aa’? If yes, does it have an ‘aaa’?
If yes, does it have an ‘aaaa’?
If yes, does it have an ‘aaaaa’?
In other words, I iterated through the alphabet from a-z, and if I got a ‘hit’ I then iterated again through the alphabet for a second character ‘aa-az’. Any hit I got I iterated through the alphabet using a third character ‘aaa’-‘azz’, then a fourth ‘aaaa’-‘azzz’ and finally a fifth character ‘aaaaa-azzzz’. This worked really well without going through every combination of ‘aaaaa’-‘zzzzz’ since of course words that have no characters ‘ab’ could not possibly have characters ‘aba’ through ‘abz’ either!
LexiconSearchCharTable ended up with 211,561 rows. Here is what the first 20 rows look like:
1
E
8973
2
H
8973
3
HE
8973
4
T
8973
5
TH
8973
6
THE
8973
7
B
7136
8
BE
7136
9
BER
7136
10
BERR
7136
11
BERRY
7136
12
C
7136
13
E
7136
14
ER
7136
15
ERR
7136
16
ERRY
7136
17
R
7136
18
RR
7136
19
RRY
7136
20
RY
7136
The left column is the table’s unique identifier for each row, the middle row contains the successfully tested characters, and the third column is the LexiconTable unique identifier for a word that matched. You can probably deduce that Lexicon ID 8973 is “THE” and 7136 has “BERRY” and a mysterious “C” – the word actually stored is “C/BERRY” (cranberry).
A user typing in ‘B’ will have row 7 returned. There will be other rows with just ‘B’ in them but they will be returned instantly since that column is indexed. Only rows with just ‘B’ in this column will be returned. Type in ‘BE’ and now row 8 is returned instead, really fast along with the other ‘BE’-only rows,
Step 5 – Extract appropriate data on demand QUICKLY via a stored procedure So now I have my data in a good place. I just needed a stored procedure to act swiftly on the tables to bring back the list of products quickly. Here we go:
CREATE PROCEDURE [dbo].[TescoGroceryInstantSearch] ( @SearchCharacters varchar(5) ) as SELECT TOP 20 pt.ProductID, pt.Description FROM ProductsTable pt INNER JOIN LexiconProductTable lpt ON pt.ProductID = lpt.ProductID INNER JOIN LexiconTable lt ON lt.LexiconID = lpt.LexiconID INNER JOIN LexiconSearchCharTable lsct on lsct.LexiconID = lt.LexiconID WHERE SearchCharacters = @SearchCharacters ORDER BY lt.ProductCount DESC
Nice – an easy to read and a quick way to grab the data! As you type each characters into the search box on the web page, the list of products results quickly from this stored procedure. This is confirmed by the SQL Execution Plan revealed by my SQL Server – all the heavy percentage CPU costs are borne by clustered index seeking.
I may as well make the maximum use of the data so I have a second stored procedure that will run in parallel with the first one in my web application, revealing word suggestions to help the user get to the product even quicker. Here it is:
CREATE PROCEDURE [dbo].[TescoGroceryInstantSearchSuggestions] ( @SearchCharacters varchar(5) ) as SELECT TOP 15 lt.LexiconID, lt.LexiconWord FROM LexiconTable lt INNER JOIN LexiconSearchCharTable lsct on lsct.LexiconID = lt.LexiconID WHERE lsct.SearchCharacters = @SearchCharacters ORDER BY lt.ProductCount DESC
Again its clustered index seeking all the way. Nice! No need for third party software – just some intelligent thinking around data storage, formatting and extraction. I always like to try stuff out myself before I recommend buying anything, as I prefer to use the tools I already have.
Step 6 – Build a simple web application to make it all happen!
Now back to the whole reason for doing this. Can you get to a chosen product quicker? Go play at http://www.techfortesco.com/tescoinstant and let me know.