Q:

Indexing for tags

In my app, certain items will have tags -- very similar to tags for questions here on SO.
I'm using Azure SQL Database to store my tags in a master "Tags" table. I'm thinking the tags table will have only three columns i.e. Id, Tag, IsApproved.
How should I index my tags so that I can run queries against them? I'm sure at some point, I may have to cache them but in the meantime, what should I use for indexing? The main concern I have is that the user may type something that's in the middle. For example, I may have the following tags:

Writing
Creative Writing
Technical Writing
Script Writer

When the user starts typing the letters 

writ

I'd like to suggest all four above. I can't use LIKE in my select query which would scan the whole table. How do I handle this?

A:

You have quite a few different approaches you can take in this situation. I have explained this in detail below. You could try all and see which one better suits your situation.
Before going into more involved approaches explained here, you could always use a simple approach by using the query below; this should be preferred if your Tags table will not contain too many rows, since then even a table scan would be fast enough.
SELECT DISTINCT t.Tag FROM Tags t where t.Tag LIKE '%writ%'

If your Tags table could contain many rows like millions of tags that one of the three approaches below could be used.
Approach 1
Create a full-text index on the Tags table based on Tag column. 
This can be easily done in SSMS by right clicking on the Tags table and selecting Full-Text index with further options. You will get a a wizard that will guide you through creating the full text index.
With this approach you would use a query like below. Note that you can only use a wild card character * at end of your search substring, which means it will return only those Tags  starting with writ but not those Tags that have the second or third word starting with writ. This could be a disadvantage with this approach if your requirement is to search all words in a Tag starting with the search substring.
SELECT DISTINCT t.Tag FROM Tags t WHERE FREETEXT( t.Tag, 'writ*')

Approach 2
Since, your Tag column is limited to only 50 characters or so, you are going to have a limited number of words and not something like 100 or 200 per tag.

Create a new table called TagFragments whose columns are as below            (ID int, TagID int, TagFragment varchar(50)). You can use the query below to create this table.
CREATE TABLE dbo.TagFragments(
ID int IDENTITY(1,1) NOT NULL PRIMARY KEY,
TagId int,
TagFragment VARCHAR(50)

) 
This table will contain all words in a tag in normalized manner. You can easily populate it at the same time you populate the Tags table.
So, if your tag having an ID of 4 was Creative writing then this
table will contain 2 rows for this single tag record. These fragment records
will be as below assuming that 1  and 2 are the auto-generated IDs in TagFragments table.
(1, 4, 'Creative')
( 2, 4, 'writing')
Create an index on TagFragment column for TagFragments table. This should be a non-unique table. This index will now be used for your tag search query. You should create an inclusive index to further optimize your search query by including the column TagID but not including it in the index.

This approach has the advantage over approach 1 in that it searches all words in a Tag starting with a search substring. 
Use the query below to get matching tags as user types into the textbox. The key here is to always search with wild card at end like writ% which will use an index. If you instead use %writ or %writ% with LIKE then you will not be using any index and a table scan will be done.
Tag Search Query
SELECT DISTINCT t.Tag
FROM Tags t
INNER JOIN TagFragments tf ON t.ID = tf.TagID
WHERE tf.TagFragment LIKE 'writ%';

Create Inclusive Index query
CREATE NONCLUSTERED INDEX TagFragmentsSearchIndex ON dbo.TagFragments
(
    TagFragment ASC
)
INCLUDE (TagID)

NOTE: The advantage of an inclusive index is that you save an extra step of table lookup by primary key ID to find TagID value from TagFragments table, when using the above query.
Hybrid Approach
This is another approach you could use that uses the TableFragments table of Approach 2  with a full-text index on TableFragment column. You would not need  to create an index mentioned in approach 2, but do create a non-unique index on TagID column in TagFragments table.
The search query for this would be as below.
SELECT distinct t.Tag  FROM Tags t INNER JOIN TagFragments tf
  ON t.ID =  tf.TagID WHERE FREETEXT( tf.TagFragment, 'writ*');

The advantage of this hybrid approach is that it searches all words in a Tag starting with search substring and it will be fast when you have many Tags.

