Eu tentaria o seguinte:
Primeiro, verifique se há índices nas tabelas e colunas a seguir (cada conjunto de colunas entre parênteses deve ser um índice separado):
table1 : (subscribe, CDate)
(CU_id)
table2 : (O_cid)
(O_ref)
table3 : (I_oref)
(I_pid)
table4 : (P_id)
(P_cat)
table5 : (C_id, store)
Segundo, se adicionar os índices acima não melhorou as coisas tanto quanto você gostaria, tente reescrever a consulta como
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
Espero aqui que a primeira sub-seleção reduza significativamente o número de linhas a serem consideradas para junção, fazendo com que as junções subsequentes trabalhem menos. Idem o raciocínio por trás da segunda sub-seleção na tabela5.
De qualquer forma, mexa com isso. Quero dizer, em última análise, é apenas um SELECT - você não pode prejudicar nada com isso. Examine os planos que são gerados por cada permutação diferente e tente descobrir o que é bom ou ruim em cada uma.
Compartilhe e curta.