0

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.

1
  • Left joins make no sense when you then do any comparisons on those tables in WHERE. And then there is one trick . you can join the t3 twice, one inner join for XX and second time as LEFT JOIN t3 AS t4 ON t2.tag_id = t4.id AND AND t4.tag_name LIKE %YY% WHERE t4.id IS NULL - that way you wil exclude the rows for which the tag YY exists. The problem with LIKE %XX% from the answer stands too, fix it.
    – jkavalik
    Nov 15, 2015 at 9:20

3 Answers 3

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;
0

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.
2
  • Thanks for the Answer, You're corect about the "LINK", T2 is still a large a table. I've updated the question to hopefully better show the problem, so hopefully you can suggest something now that there is more info about the 'indices' and 'dataset', but generally indices are flexible, and I already know about limit but thanks Nov 15, 2015 at 19:47
  • we can test in SQL Fiddle, because, at least on my side, all as described) Has a single tag --> a single T2 record Has multiple tags --> Multiple t2 records Has no tags --> 0 T2 records
    – a_vlad
    Nov 16, 2015 at 10:01
0

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.

1
  • Is your example an typo? should it be: SELECT t1.rid, GROUP_CONCAT(t3.tag_name SEPARATOR ',') AS tags FROM t1 ...? Dec 20, 2019 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.