Estou surpreso que qualquer um seja rápido. Sugiro substituí-los por
exists :SELECT COUNT(*)
FROM ips_usuario u
WHERE EXISTS (SELECT 1 FROM ips_fatura f WHERE u.id = f.ips_usuario_id) OR
EXISTS (SELECT 1 FROM ips_fatura f WHERE u.ips_usuario_id_titular = f.ips_usuario_id);
E para o segundo:
SELECT COUNT(*)
FROM ips_usuario u
WHERE EXISTS (SELECT 1 FROM ips_fatura f WHERE u.id = f.ips_usuario_id) OR
(u.ips_usuario_id_titular IS NOT NULL AND
EXISTS (SELECT 1 FROM ips_fatura f WHERE u.ips_usuario_id_titular = f.ips_usuario_id)
)
Para ambos, você quer dois índices:
ips_fatura(ips_usuario_id) e ips_fatura(ips_usuario_id_titular) . Você pode verificar a explicação para ter certeza de que EXISTS está usando o índice. Caso contrário, as versões mais recentes do MySQL usam índices para IN :SELECT COUNT(*)
FROM ips_usuario u
WHERE u.id IN (SELECT f.ips_usuario_id FROM ips_fatura f) OR
u.ips_usuario_id_titular IN (SELECT f.ips_usuario_id FROM ips_fatura f);
Em ambos os casos (
EXISTS ou IN ) o objetivo é fazer uma "semi-junção". Ou seja, para corrigir apenas a primeira linha com uma correspondência em vez de todas as correspondências. Essa é uma eficiência importante, pois permite que a consulta evite a remoção de duplicações. Eu especularia que o problema é a otimização do
or -- geralmente isso resulta em JOIN ineficiente algoritmos. No entanto, talvez o MySQL seja inteligente em seu primeiro caso. Mas a adição do IS NULL para a mesa externa joga fora. 
