WHERE on SQL with JOIN on large tables

Question

We have a set of large tables (millions of records) on a MySQL DB, having schema like so (simplified):

T1: id, uid, rid, text1, text2, int1, int2, ...
T2: id, rid, tag_id, created_at
T3: id, owner_id, tag_name

Indices:

T1: Primary(id), unique(uid,rid), index(rid), index(uid,int1)
T2: Primary(id), unique(tag_id,rid), index(tag_id), index(created_at)
T3: Primary(id), unique(owner_id,tag_name)

And a requirement to do a select which returns 'rids' having tag_name = XX but not YY:

SELECT t1.rid 
FROM t1 
LEFT JOIN t2 ON t1.rid = t2.rid 
LEFT JOIN t3 ON t2.tag_id = t3.id 
WHERE t1.uid = 123
AND t1.int1 = 3
AND t3.tag_name eq 'XX'
AND t3.tag_name != 'YY'
LIMIT 100

This naturally does not work, since the WHERE does not eliminate an rid having more than one tag. How can we achieve this with performance in mind for the large tables?

More about data:

A user represented by uid will have about 100,000 records in T1, out of which about 10% have T2 records 10,000 (rids which are tagged), and less than 10 tags in T3. There are 1000s of users (uids) in T1.

A given rid can be one of:

1. ) Has a single tag --> a single T2 record
2. ) Has multiple tags --> Multiple t2 records
3. ) Has no tags --> 0 T2 records

We can also alter the table structure and indices for T2 and T3 to accommodate for that, as long as we maintain ability to filter 'tags' and 'T2' creation time.

Answer 1

You can use NOT EXISTSas:

SELECT t2.rid
FROM t2
WHERE NOT EXISTS (
    SELECT 1 
    FROM t3
    WHERE t2.tag_id = t3.id
      AND t3.tag_name <> 'YY'
)
AND EXISTS (
    SELECT 1 
    FROM t3
    WHERE t2.tag_id = t3.id
      AND t3.tag_name <> 'XX'
);

Your index T2:index(tag_id) is already covered by T2:unique(tag_id,rid) som you can get rid of that

I don't work much with MySQL, but I get the impression that JOINs are often preferred over EXISTS/NOT EXISTS. Translating the query (Note the DISTINCT):

SELECT DISTINCT t2.rid
FROM t2
JOIN t3 AS t31
    ON t2.tag_id = t31.id
   AND t31.tag_name = 'XX'
LEFT JOIN t3 AS t32
    ON t2.tag_id = t32.id
   AND t32.tag_name <> 'YY'
WHERE t32.id IS NULL;

Answer 2

for full and proper answer not all information presented:

• structure (including indexes), hope t1.int1 - have index at least
• cardinality (guess about it at least) for tags
• present query plan

So, just common advices:

1. LIKE %xx% - not use indexes always. It mean, search for T2 and T3 - in this case always will be fullscan. Possible solution - if it real tags - choose tags from list and make search by full name using = or LIKE "XXX%" - this construction start use indexes for T2 and T3 tables
2. if difference in size T1 and T2/T3 serious - You can change query for select from smallest table and join with biggest. It continue make fullscan on small table, but once and than for each from small use index for compare with big Some time MySQL do this auto, need profile query for check plan
3. about cardinality - LIMIT 100 of course reduce time for display data, but nothing do with data size from original query (especial if on final query You use any sort ORDER BY t1.int1). So if 10 millions records table has only 20 tags - it always will manage huge amount of records and memory could be a bottleneck.

Answer 3

We ended up trying something of the sort:

SELECT t1.rid FROM t1, GROUP_CONCAT(t3.tag_name SEPARATOR ',') AS tags
LEFT JOIN t2 ON t1.rid = t2.rid 
LEFT JOIN t3 ON t2.tag_id = t3.id 
WHERE t1.uid = 123 
AND t1.int1 = 3
HAVING tags NOT LIKE '%XX%' AND tags LIKE '%YY%'
GROUP BY t1.rid
LIMIT 100

Which works, but performs really poorly (9-10 seconds of query time) as expected.

As such, we completely removed the tags table (t3) and used the 'tag_names' as column names in t2, with values = 'tag_time' (effectively created_at values):

T2: id, rid, tag_id, tag1, tag2, tag3.....tag7

And queries now become simple, but having a problem when we search (tag_name is not empty: query becomes a big OR IS NOT NULL except for tag1 which is a special case).

Hopefully this will fix the slow performance, and appreciate if you have some suggestions here.