Storing multiple tags on analytics database

Question

I would like to store user purchase custom tags on each transaction, example if user bought shoes then tags are "SPORTS", "NIKE", SHOES, COLOUR_BLACK, SIZE_12,..

These tags are that seller interested in querying back to understand the sales.

My idea is when ever new tag comes in create new code(something like hashcode but sequential) for that tag, and code starts from "a-z" 26 letters then "aa, ab, ac...zz" goes on. Now keep all the tags given for in one transaction in the one column called tag (varchar) by separating with "|".

Let us assume mapping is (at application level)

"SPORTS" = a
"TENNIS" = b
"CRICKET" = c
...
...
"NIKE"  = z        //Brands company
"ADIDAS" = aa
"WOODLAND" = ab
...
...
SHOES   = ay
...
...
COLOUR_BLACK = bc
COLOUR_RED = bd
COLOUR_BLUE = be
...
SIZE_12 = cq
...

So storing the above purchase transaction, tag will be like tag="|a|z|ay|bc|cq|" And now allowing seller to search number of SHOES sold by adding WHERE condition tag LIKE %|ay|%. Now the problem is i cannot use index (sort key in redshift db) for "LIKE starts with %". So how to solve this issue, since i might have 100 millions of records? dont want full table scan..

any solution to fix this?

Update_1: I have not followed bridge table concept (cross-reference table) since I want to perform group by on the results after searching the specified tags. My solution will give only one row when two tags matched in a single transaction, but bridge table will give me two rows? then my sum() will be doubled.

I got suggestion like below

EXISTS (SELECT 1 FROM transaction_tag WHERE tag_id = 'zz' and trans_id = tr.trans_id) in the WHERE clause once for each tag (note: assumes tr is an alias to the transaction table in the surrounding query)

I have not followed this; since i have to perform AND and OR condition on the tags, example ("SPORTS" AND "ADIDAS") ---- "SHOE" AND ("NIKE" OR "ADIDAS")

Update_2: I have not followed bitfield, since dont know redshift has this support also I assuming if my system will be going to have minimum of 3500 tags, and allocating one bit for each; which results in 437 bytes for each transaction, though there will be only max of 5 tags can be given for a transaction. Any optimisation here?

Solution_1:

I have thought of adding min (SMALL_INT) and max value (SMALL_INT) along with tags column, and apply index on that.

so something like this

"SPORTS" = a = 1
"TENNIS" = b = 2
"CRICKET" = c = 3
...
...
"NIKE"  = z  = 26
"ADIDAS" = aa = 27

So my column values are

`tag="|a|z|ay|bc|cq|"` //sorted?
`minTag=1`
`maxTag=95` //for cq

And query for searching shoe(ay=51) is

maxTag <= 51 AND tag LIKE %|ay|%

And query for searching shoe(ay=51) AND SIZE_12 (cq=95) is

minTag >= 51 AND maxTag <= 95 AND tag LIKE %|ay|%|cq|%

Will this give any benefit? Kindly suggest any alternatives.

Answer 1

I'm still convinced that using a many-to-many lookup table (a bridge table) is still your best option here. Your concern about matching multiple rows can be fixed by proper query design. Let's say your tables are:

CREATE TABLE purchases(PurchaseID,CustomerID,PurchaseDate,...)
CREATE TABLE tags(TagID,TagType,TagName)
CREATE TABLE purchasetags(PurchaseID,TagID)

So each purchase can have multiple tags set (no limit), and just for fun, I added the ability to categorized the tags by TagType, maybe that contains things like "ProductType", "Brand", "Color", "Sport", so you have a way to tell that "shoes" is a "ProductType" tag, "Nike" is a brand tag, and "soccer" is a sport tag.

Then if you want to query (and return just single rows), just do:

SELECT *
FROM purchases 
WHERE PurchaseID IN (SELECT pt.PurchaseID 
                     FROM purchasetag pt
                     INNER JOIN tags t ON pt.TagID=t.TagID
                     WHERE t.TagName IN ('Adidas','Nike'))
GROUP BY whatever...

If you need to do fancier combo-searches (find purchases of Nike shoes or Adidas shoes, your query will have to also be fancier:

SELECT *
FROM purchases 
WHERE PurchaseID IN (SELECT pt.PurchaseID 
                     FROM purchasetag pt
                     INNER JOIN tags t ON pt.TagID=t.TagID
                     WHERE t.TagName = 'Shoes')
AND   PurchaseID IN (SELECT pt.PurchaseID 
                     FROM purchasetag pt
                     INNER JOIN tags t ON pt.TagID=t.TagID
                     WHERE t.TagName IN ('Adidas','Nike'))

Again, that's still returning a single row for each purchase that matches your desired tag combination.

Answer 2

The usual way to solve such a problem, is to use a bitfield.

So you would create a tags table, and link that via an n:m table to the sales figures or products. Then in the tags table, for each tag you would assign a unique bitvalue as a power of 2, e.g. 1, 2, 4, 8, ..., 1024, 2048, ... for sports, tennis, cricket, ... and so on.

Using bit_oryou can then condense these values into a single numeric value and store this alongside the product or sales figures. For example tags "sports" and "cricket" on one product become 5.

If the bitsize of the numeric type you have available is not enough to store all your tags, use multiple of these fields and store the number or column name of the field and the bitvalue with the tag.

Then for querying use clauses of the form:

flags & 1024 = 1024 or flags & 1024 <> 0 = 10th flag set

You can now do any Boolean expression on the flags. If you designate a single field for all colors you can also do other tricks, like querying for products, which have a Color tag: colorflags <> 0 and so on.

As you're in a column oriented database (redshift), & is only executed once per unique value in the column. Depending on implementation, the database will further reduce this, by analysing the &-clause and use constraints on size through sort order of column values (for free).

And if you need that last bit of performance, you can do tricks by collecting statistics on the flags and the queries and grouping them together intelligently. I expect in the use case that you're describing (perform sum ... group by after filtering), performance that you could gain through this, would be negligible compared to the cost of calculation.

Answer 3

Tables

brand 
ID
Name  

size 
ID
name  

color 
ID 
name  

customer 
ID 
Name  

purchase 
ID
customerID
date 

purchaseDetail 
purchaseID  
brandID 
sizeID 
colorID

You need purchaseDetail to associate all the tags with the item

select * 
from purchase 
join purchaseDetail 
  on purchase.ID = purchaseDetail.purchaseID 
join brand 
  on brand.ID    = purchaseDetail.brandID 
 and brand.Name in ('Nike', 'Adidas')
join size 
  on size.ID     = purchaseDetail.sizeID
join color 
  on color.ID    = purchaseDetail.colorID 
 and color.Name = 'black'