Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

This query takes about 2-6 seconds to run depending which tag id(s) is/are selected:

SELECT t2.id, t2.name, count(*) as kpl FROM
    (SELECT pt1.post_id
    FROM posts_tags pt1
    WHERE pt1.tag_id IN (88, 5)
    GROUP BY pt1.post_id
    HAVING COUNT(DISTINCT pt1.tag_id) = 2) Matchingposts
INNER JOIN posts_tags pt2 ON (Matchingposts.post_id = pt2.post_id)
INNER JOIN tags t2 ON (pt2.tag_id = t2.id)
WHERE pt2.tag_id NOT IN (88, 5)
GROUP BY pt2.tag_id
HAVING count(*) > 10;

This query gives list of tags available to filter posts further. There can be 1 to n tags selected but the problem is biggest when there are only 1 selected.

Here is EXPLAIN:

+----+-------------+------------+--------+-------------------------------------+------------+---------+--------------------------------+-------+---------------------------------+
| id | select_type | table      | type   | possible_keys                       | key        | key_len | ref                            | rows  | Extra                           |
+----+-------------+------------+--------+-------------------------------------+------------+---------+--------------------------------+-------+---------------------------------+
|  1 | PRIMARY     | <derived2> | ALL    | NULL                                | NULL       | NULL    | NULL                           | 13583 | Using temporary; Using filesort |
|  1 | PRIMARY     | pt2        | ref    | post_id,tag_id,post_id_2,tag_id_2   | post_id_2  | 5       | Matchingposts.post_id          |     9 | Using where; Using index        |
|  1 | PRIMARY     | t2         | eq_ref | PRIMARY                             | PRIMARY    | 4       | database.pt2.tag_id            |     1 |                                 |
|  2 | DERIVED     | pt1        | ref    | tag_id,tag_id_2                     | tag_id_2   | 5       |                                | 11586 | Using where; Using index        |
+----+-------------+------------+--------+-------------------------------------+------------+---------+--------------------------------+-------+---------------------------------+
4 rows in set (0.00 sec)

The question is: is there better way to structure this query? And if there isn't: How to config MySQL to keep the tmp table in memory?

In future I would like to use ORDER BY t2.name but I have left that out for now.

EDIT: Tried so far:

My original query: 0,9299 s resultset 379 rows

ypercupe's query: 1,1457 s resultset 379 rows

Walter Mitty's: 1,3014 s resultset 356 rows

EXPLAIN for both Walter Mitty's and ypercupe's query were exactly same:

+----+-------------+-------+--------+-------------------------------------+------------+---------+------------------------------------------+-------+-----------------------------------------------------------+
| id | select_type | table | type   | possible_keys                       | key        | key_len | ref                                      | rows  | Extra                                                     |
+----+-------------+-------+--------+-------------------------------------+------------+---------+------------------------------------------+-------+-----------------------------------------------------------+
|  1 | SIMPLE      | pt_88 | ref    | post_id,tag_id,post_id_2,tag_id_2   | tag_id_2   | 5       | const                                    | 19071 | Using where; Using index; Using temporary; Using filesort |
|  1 | SIMPLE      | pt_5  | ref    | post_id,tag_id,post_id_2,tag_id_2   | post_id_2  | 10      | database.pt_88.post_id,const             |     1 | Using where; Using index                                  |
|  1 | SIMPLE      | pt2   | ref    | post_id,tag_id,post_id_2,tag_id_2   | post_id_2  | 5       | database.pt_5.post_id                    |     9 | Using where; Using index                                  |
|  1 | SIMPLE      | t2    | eq_ref | PRIMARY                             | PRIMARY    | 4       | database.pt2.tag_id                      |     1 |                                                           |
+----+-------------+-------+--------+-------------------------------------+------------+---------+------------------------------------------+-------+-----------------------------------------------------------+
4 rows in set (0.00 sec)

You asked about indexes in posts_tags table. I have put all possible indexes there so MySQL can pick most suitable.

And yes. post_id tag_id combinations should be unique.

EDIT 2: SHOW CREATE TABLEs

 CREATE TABLE `posts_tags` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `post_id` int(11) DEFAULT NULL,
  `tag_id` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `post_id` (`post_id`),
  KEY `tag_id` (`tag_id`),
  KEY `post_id_2` (`post_id`,`tag_id`),
  KEY `tag_id_2` (`tag_id`,`post_id`)
) ENGINE=MyISAM AUTO_INCREMENT=4556133 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci

CREATE TABLE `tags` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(100) COLLATE utf8_unicode_ci DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `name` (`name`)
) ENGINE=MyISAM AUTO_INCREMENT=44433 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci

EDIT 3: Rolando's query:

I killed it after 60 s. State was "copying to tmp table".

Here is EXPLAIN:

+----+-------------+-------------+--------+-----------------+------------+---------+------------+---------+---------------------------------+
| id | select_type | table       | type   | possible_keys   | key        | key_len | ref        | rows    | Extra                           |
+----+-------------+-------------+--------+-----------------+------------+---------+------------+---------+---------------------------------+
|  1 | PRIMARY     | <derived2>  | ALL    | NULL            | NULL       | NULL    | NULL       |    6443 | Using temporary; Using filesort |
|  1 | PRIMARY     | <derived3>  | ALL    | NULL            | NULL       | NULL    | NULL       | 4466982 | Using where; Using join buffer  |
|  1 | PRIMARY     | t2          | eq_ref | PRIMARY         | PRIMARY    | 4       | pt2.tag_id |       1 |                                 |
|  3 | DERIVED     | posts_tags  | index  | tag_id,tag_id_2 | post_id_2  | 10      | NULL       | 4561828 | Using where; Using index        |
|  2 | DERIVED     | pt1         | index  | tag_id,tag_id_2 | post_id_2  | 10      | NULL       | 4561828 | Using index                     |
+----+-------------+-------------+--------+-----------------+------------+---------+------------+---------+---------------------------------+
5 rows in set (5.15 sec)

EDIT 4: Outputs as Rolando requested:

mysql> SELECT COUNT(DISTINCT post_id) postcount FROM posts_tags;
+-----------+
| postcount |
+-----------+
|    515935 |
+-----------+
1 row in set (10.57 sec)

mysql> SELECT COUNT(DISTINCT tag_id) tagcount FROM posts_tags;
+----------+
| tagcount |
+----------+
|    45078 |
+----------+
1 row in set (8.25 sec)

mysql> SELECT tag_id,COUNT(1) postcount FROM  posts_tags GROUP BY tag_id INTO OUTFILE '/tmp/output.txt';
Query OK, 45083 rows affected (1.84 sec)
http://pastebin.com/1VRW0UEr

mysql> SELECT post_id,COUNT(1) tagcount FROM posts_tags GROUP BY post_id INTO OUTFILE '/tmp/output2.txt';
Query OK, 516247 rows affected (2.29 sec)
http://koti.mbnet.fi/photos/output2.txt

Updated question:

The problem is biggest when only one of common used tag is selected. In such case we need to check what different tags 50000 posts have.

Can we agree that tmp table is inevitable in any case?

share|improve this question
    
What indexes do you have on the tables? Can you add the tables' definitions? –  ypercube Feb 28 '12 at 7:09
    
I added another refactored query for you to try !!! –  RolandoMySQLDBA Feb 28 '12 at 17:51
    
As a sidenote, you should run ALTER TABLE post_tags DROP INDEX post_id; and then ALTER TABLE post_tags DROP INDEX tag_id; to save space. They are redudndant indexes. –  RolandoMySQLDBA Feb 28 '12 at 20:58
add comment

3 Answers

Is it safe to assume that for every relevant post the tag 88 occurs exactly once and the tag 5 also occurs exactly once?

Is there an index on post_id in table post_tags?

If the answer is yes to both, something like this might work:

select
      t1.id,
      t1.name,
      count (*) - 2 as kpl
from
              post_tags pt1
   inner join post_tags pt2 on (pt2.post_id = pt1.post_id)
   inner join post_tags pt3 on (pt3.post_id = pt1.post_id)
   inner join tags t1 on (t1.id = pt3.tag_id)
where
         pt1.tag_id = 88
    and  pt2.tag_id = 5
group by
   t1.id,
   t1.name
having
   count (*) > 12;
share|improve this answer
    
Thanks for reply! Looks like I need 5 more hours to be able to test that. I am using NOT IN() because I don't want to view the tags that are already selected. But it is possible to delete them afterwards if it is faster to do that way. –  Henri Feb 27 '12 at 13:46
    
Question updated. –  Henri Feb 27 '12 at 21:52
add comment

My first suggestion would be to change the COUNT(DISTINCT pt1.tag_id) = 2 to COUNT(*) = 2. Assuming that the (post_id, tag_id) combination is unique in table posts_tags, the results will be the same (and faster).

Second is to restructure completely the query into:

SELECT t2.id, t2.name, count(*) as kpl 
FROM posts_tags pt_5
  INNER JOIN posts_tags pt_88
    ON  pt_88.post_id = pt_5.post_id
    AND pt_88.tag_id = 88
INNER JOIN posts_tags pt2 
    ON  pt_5.post_id = pt2.post_id
INNER JOIN tags t2 
    ON  pt2.tag_id = t2.id
WHERE pt_5.tag_id = 5
  AND pt2.tag_id NOT IN (88, 5)
GROUP BY pt2.tag_id
HAVING COUNT(*) > 10;

Another try:

SELECT t2.id, t2.name, kpl 
FROM
    ( SELCT pt.tag_id, COUNT(*) AS kpl
      FROM post_tags pt
        JOIN posts_tags pt_5
          ON  pt_5.post_id = pt.post_id
          AND pt_5.tag_id = 5
        JOIN posts_tags pt_88
          ON  pt_88.post_id = pt.post_id
          AND pt_88.tag_id = 88
      GROUP BY pt.tag_id
      HAVING COUNT(*) > 10
    ) pt2
  JOIN tags t2 
    ON  pt2.tag_id = t2.id
WHERE t2.id NOT IN (88, 5)
share|improve this answer
    
Thank you for a reply! I am able to test this in 8 hours. I also need to make sure that this query performs well with for example 10 tags. That is going to be a pretty long query. –  Henri Feb 27 '12 at 8:20
    
Changing COUNT(DISTINCT pt1.tag_id) = 2 to COUNT(*) = 2 doubles the resultset. So that didn't work. I update my question in a minute. –  Henri Feb 27 '12 at 21:34
add comment

Here is your original query

SELECT t2.id, t2.name, count(*) as kpl FROM 
    (SELECT pt1.post_id 
    FROM posts_tags pt1 
    WHERE pt1.tag_id IN (88, 5) 
    GROUP BY pt1.post_id 
    HAVING COUNT(DISTINCT pt1.tag_id) = 2) Matchingposts 
INNER JOIN posts_tags pt2 ON (Matchingposts.post_id = pt2.post_id) 
INNER JOIN tags t2 ON (pt2.tag_id = t2.id) 
WHERE pt2.tag_id NOT IN (88, 5) 
GROUP BY pt2.tag_id 
HAVING count(*) > 10; 

Here are some changes I see that can be made

CHANGE #1 Slide WHERE clause for pt2 into a subquery called pt2

SELECT t2.id, t2.name, count(*) as kpl FROM 
    (SELECT pt1.post_id 
    FROM posts_tags pt1 
    WHERE pt1.tag_id IN (88, 5) 
    GROUP BY pt1.post_id 
    HAVING COUNT(DISTINCT pt1.tag_id) = 2) Matchingposts 
INNER JOIN
(SELECT tag_id,post_id FROM posts_tags WHERE tag_id NOT IN (88, 5)) pt2
ON (Matchingposts.post_id = pt2.post_id) 
INNER JOIN tags t2 ON (pt2.tag_id = t2.id) 
GROUP BY pt2.tag_id 
HAVING count(*) > 10; 

CHANGE #2 Make sure there is a proper index for the posts_tags table

ALTER TABLE posts_tags ADD INDEX tag_id_post_id_ndx (tag_id,post_id);

This should make a significant difference

Give it a Try !!!

UPDATE 2012-02-28 12:51 EDT

I refactored the query a little deeper to try to get a hold of the posts with 88 and 5 tag_ids a little differently

SELECT B.id,B.name,A.kpl
FROM
(
    SELECT pt2.tag_id,COUNT(*) kpl
    FROM
    (
        SELECT pt88.post_id FROM
        (SELECT post_id FROM posts_tags WHERE tag_id = 88) pt88
        INNER JOIN
        (SELECT post_id FROM posts_tags WHERE tag_id =  5) pt05
        USING (post_id)
    ) Matchingposts
    INNER JOIN
    (
        SELECT pt.tag_id,pt.post_id FROM posts_tags pt
        LEFT JOIN
        (SELECT tag_id,post_id FROM posts_tags WHERE tag_id = 88) pt88
        USING (post_id)
        LEFT JOIN
        (SELECT tag_id,post_id FROM posts_tags WHERE tag_id =  5) pt05
        USING (post_id)
        WHERE pt88.tag_id IS NULL
        AND pt05.tag_id IS NULL
    ) pt2
    USING (post_id)
    GROUP BY pt2.tag_id
    HAVING count(*) > 10
) A
INNER JOIN tags B USING (tag_id)
; 

Give it a Try !!!

UPDATE 2012-02-28 16:08 EDT

I placed Matching Posts subquery inside pt2

SELECT B.id,B.name,A.kpl
FROM
(
    SELECT pt2.tag_id,COUNT(*) kpl
    FROM
    (
        SELECT pt88.post_id FROM
        (SELECT post_id FROM posts_tags WHERE tag_id = 88) pt88
        INNER JOIN
        (SELECT post_id FROM posts_tags WHERE tag_id =  5) pt05
        USING (post_id)
    ) Matchingposts
    INNER JOIN
    (
        SELECT pt.tag_id,pt.post_id FROM posts_tags pt
        LEFT JOIN
        (
            SELECT pt88.post_id FROM
            (SELECT post_id FROM posts_tags WHERE tag_id = 88) pt88
            INNER JOIN
            (SELECT post_id FROM posts_tags WHERE tag_id =  5) pt05
            USING (post_id)
        ) ptkeys
        USING (post_id)
        WHERE ptkeys.post_id IS NULL
    ) pt2
    USING (post_id)
    GROUP BY pt2.tag_id
    HAVING count(*) > 10
) A
INNER JOIN tags B USING (tag_id)
; 

UPDATE 2012-03-01 14:05 EDT

SELECT B.id,B.name,A.kpl
FROM
(
    SELECT pt2.tag_id,COUNT(*) kpl
    FROM
    (
        SELECT post_id,count(tag_id)
        tagcount FROM posts_tags
        WHERE tag_id IN (88,5)
        GROUP BY post_id
        HAVING COUNT(tag_id)=2
    ) Matchingposts
    INNER JOIN
    (
        SELECT pt.tag_id,pt.post_id FROM posts_tags pt
        LEFT JOIN
        (
            SELECT post_id,count(tag_id)
            tagcount FROM posts_tags
            WHERE tag_id IN (88,5)
            GROUP BY post_id
            HAVING COUNT(tag_id)=2
        ) ptkeys
        USING (post_id)
        WHERE ptkeys.post_id IS NULL
    ) pt2
    USING (post_id)
    GROUP BY pt2.tag_id
    HAVING count(*) > 10
) A
INNER JOIN tags B USING (tag_id)
; 

Give it a Try !!!

share|improve this answer
    
I don't know what went wrong but I killed this query after 60s. I updated EXPLAIN to my question. –  Henri Feb 28 '12 at 8:03
    
I really appreciate your efforts but no luck this time either. I killed the query and I also killed the EXPLAIN query both after 2 minutes. Both got state: "Sending data". –  Henri Feb 28 '12 at 19:26
    
Please add the output of each of these queries to the question : 1) SELECT COUNT(DISTINCT post_id) postcount FROM posts_tags;, 2) SELECT COUNT(DISTINCT tags_id) tagcount FROM posts_tags;, 3) SELECT tag_id,COUNT(1) postcount FROM posts_tags GROUP BY tag_id;, 4) SELECT post_id,COUNT(1) tagcount FROM posts_tags GROUP BY post_id; –  RolandoMySQLDBA Feb 28 '12 at 19:41
    
Outputs added ! –  Henri Feb 28 '12 at 20:41
    
Question : How fast does this query run? : SELECT pt88.post_id FROM (SELECT post_id FROM posts_tags WHERE tag_id = 88) pt88 INNER JOIN (SELECT post_id FROM posts_tags WHERE tag_id = 5) pt05 USING (post_id) –  RolandoMySQLDBA Feb 28 '12 at 21:01
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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