How can I speed up MySQL query with multiple joins

Make sure your date columns and all the columns you are joining on are indexed.

Doing an unequivalence operator on your dates means it checks every row, which is inherently slower than an equivalence.

Also, using DISTINCT adds an extra comparison to the logic that your optimizer is running behind the scenes. Eliminate that if possible.

Well, first, make a subquery to decimate table1 down to just the records you actually want to go to all the trouble of joining...

SELECT DISTINCT t1.first_name, t1.last_name, t1.email  
FROM (  
SELECT first_name, last_name, email, CU_id FROM table1 WHERE  
table1.subscribe = 1  
AND table1.Cdate >= $startDate  
AND table1.Cdate <= $endDate  
) AS t1  
INNER JOIN table2 AS t2 ON t1.CU_id = t2.O_cid  
INNER JOIN table3 AS t3 ON t2.O_ref = t3.I_oref  
INNER JOIN table4 AS t4 ON t3.I_pid = t4.P_id  
INNER JOIN table5 AS t5 ON t4.P_cat = t5.C_id  
WHERE t5.store = 2

Then start looking at modifying the directionality of the joins.

Additionally, if t5.store is only very rarely 2, then flip this idea around: construct the t5 subquery, then join it back and back and back.

I'd try the following:

First, ensure there are indexes on the following tables and columns (each set of columns in parentheses should be a separate index):

table1 : (subscribe, CDate)
         (CU_id)
table2 : (O_cid)
         (O_ref)
table3 : (I_oref)
         (I_pid)
table4 : (P_id)
         (P_cat)
table5 : (C_id, store)

Second, if adding the above indexes didn't improve things as much as you'd like, try rewriting the query as

SELECT DISTINCT t1.first_name, t1.last_name, t1.email FROM
  (SELECT CU_id, t1.first_name, t1.last_name, t1.email
     FROM table1
     WHERE subscribe = 1 AND
           CDate >= $startDate AND
           CDate <= $endDate) AS t1
  INNER JOIN table2 AS t2
    ON t1.CU_id = t2.O_cid   
  INNER JOIN table3 AS t3
    ON t2.O_ref = t3.I_oref   
  INNER JOIN table4 AS t4
    ON t3.I_pid = t4.P_id   
  INNER JOIN (SELECT C_id FROM table5 WHERE store = 2) AS t5
    ON t4.P_cat = t5.C_id

I'm hoping here that the first sub-select would cut down significantly on the number of rows to be considered for joining, hopefully making the subsequent joins do less work. Ditto the reasoning behind the second sub-select on table5.

In any case, mess with it. I mean, ultimately it's just a SELECT - you can't really hurt anything with it. Examine the plans that are generated by each different permutation and try to figure out what's good or bad about each.

Share and enjoy.