0

as shown in this sql-fiddle I have a bridge table events_tags representing a many-to-many between events and tags.

I need the fastest way to find all events not associated to a given tag t.

The first query in the fiddle shows the incorrect solution where a an event assigned to t and another tag is included in the result set.

The second query makes a anti-join (learned this from an answer by ypercubeᵀᴹ) and is correct, but very slow in my real schema, where it would return 18K rows from the bridge table in ~130ms on the hardware on which our application runs.

I need this functionality in an endpoint of a RESTful API, whose total response time must stay <300ms.

Is there a faster approach I can use or am I limited to the fact that the "real" query has to deal with a derived table of 18K rows?

EDIT I failed to mention that I will then combine this (as a subquery) with another query selecting only events matching some criteria. I am not selecting 18K events :)

P.S.: let me know if any other detail on the problem is required

Thanks

1
SELECT DISTINCT events.id, events.title
  FROM events 
  JOIN events_tags et1 
         on events.id = et1.event_id 
        and not exists ( select 1 
                           from events_tags et2 
                          where et2.event_id = et1.event_id
                            and et2.tag_id IN (1) );

And why a iden PK in events_tags? Drop that.
Just have a composite PK of tag_ID, event_id in that order.

This might be faster but I doubt it

SELECT DISTINCT events.id, events.title
  FROM events 
  JOIN events_tags et1 
         on et1.event_id = events.id  
        and et1.tag_id not IN (1)
        and not exists ( select 1 
                           from events_tags et2 
                          where et2.event_id = et1.event_id
                            and et2.tag_id IN (1)
                       );

I don't think MYSQL supports except

SELECT events.id, events.title
  FROM events 
  JOIN (   select event_id  
           from events_tags
           where tag_id not IN (1)
         except
           select event_id  
           from events_tags
           where tag_id     IN (1)
       ) tt
    on tt.event_id = events.id
  • Thank you for your suggestions! The first query is indeed faster and the second one has similar performance. As you say, MySQL does not support EXCEPT. I just got back to the office and I'm gonna do some tests to see the whole performance on staging. From what I understand, your query beats mine because it avoids one more subquery nesting, am I correct? – Cec Mar 26 '16 at 17:43
  • Filter early is always better than filter late. You did not give the optimizer much of a chance. – paparazzo Mar 26 '16 at 18:17
  • I have put this to work on staging and median response time dropped from 500ms to 150ms (of course with some randomisation to prevent caching from hiding bottlenecks). Thank you very much for your help, made my day and reminded me to not overcomplicate my queries – Cec Mar 26 '16 at 18:20
  • Indeed, I basically handcuffed the optimizer... I know it is out of scope, but do you have some resources on query plan analysis that you'd recommend ? – Cec Mar 26 '16 at 18:24
  • 1
    Not really. Think in terms of giving it a chance to filter early. When you see loop joins and later filters then think about how to serve it up better. Less joins is almost always better. – paparazzo Mar 26 '16 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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