MySQL: 2 separate queries run very fast, combined query with OR runs very slow EXPLAIN 
SELECT inet_ntoa(src) as source, inet_ntoa(dst) as dest,
    firewall.name as fw, proto.proto, service, action.action, 
    sum(count) as hits, max(date) as lastused, rule_uid.rule_uid 
FROM log, action, firewall, proto, rule_uid 
WHERE ( rule_uid.id = log.rule_uid ) 
    AND ( proto.id = log.proto ) 
    AND ( log.action = action.id AND action.action='accept' ) 
    AND ( log.orig = firewall.id) 
    AND ( ( src &gt;= inet_aton('0.0.0.0') 
            AND src &lt;= inet_aton('255.255.255.255') ) )
    AND ( ( xlatedst &gt;= inet_aton('173.82.122.94') 
            AND xlatedst &lt;= inet_aton('173.82.122.94') ) ) 
GROUP BY src, dst 
ORDER BY hits DESC, dst 
LIMIT 100;


uses temporary/filesort, 92 lines, and runs in 30ms.

Similarly fast if I modify the query to search for the same IP in the dst column.

But if I combine both queries to search for that IP in the xlatedst OR the dst columns:

SELECT inet_ntoa(src) as source, inet_ntoa(dst) as dest, 
    firewall.name as fw,  proto.proto, service, action.action, 
    sum(count) as hits, max(date) as lastused, rule_uid.rule_uid 
FROM log, action, firewall, proto, rule_uid 
WHERE( rule_uid.id = log.rule_uid ) 
    AND ( proto.id = log.proto ) 
    AND ( log.action = action.id AND action.action='accept' )
    AND ( log.orig = firewall.id) 
    AND ( ( src &gt;= inet_aton('0.0.0.0') 
            AND src &lt;= inet_aton('255.255.255.255') ) ) 
    AND *( ( xlatedst &gt;= inet_aton('173.82.122.94') 
             AND xlatedst &lt;= inet_aton('173.82.122.94') )
         OR ( dst &gt;= inet_aton('173.82.122.94') 
              AND dst &lt;= inet_aton('173.82.122.94') ) 
         )* 
GROUP BY src, dst 
ORDER BY hits DESC, dst
LIMIT 100;


then it examines 2121544 rows and runs for 3 minutes.

Now I could just run both queries and concat the results. But I wonder if there is a simpler way?

There is a seperate index on both "dst" and "xlatedst". Why isnt it used?
In my experience though, doing anything with an OR condition can have horrible implications when running queries, have you considered running this as two separate queries and then combining the results?

E.g.

SELECT * FROM (

    SELECT inet_ntoa(src) as source, inet_ntoa(dst) as dest,
        firewall.name as fw, proto.proto, service, action.action, 
        sum(count) as hits, max(date) as lastused, rule_uid.rule_uid 
    FROM log, action, firewall, proto, rule_uid 
    WHERE ( rule_uid.id = log.rule_uid ) 
            AND ( proto.id = log.proto ) 
        AND ( log.action = action.id AND action.action='accept' ) 
        AND ( log.orig = firewall.id) 
        AND ( ( src &gt;= inet_aton('0.0.0.0') 
                AND src &lt;= inet_aton('255.255.255.255') ) )
        AND ( ( xlatedst &gt;= inet_aton('173.82.122.94') 
                AND xlatedst &lt;= inet_aton('173.82.122.94') ) ) 
    GROUP BY src, dst 
    ORDER BY hits DESC, dst

    UNION ALL

    SELECT inet_ntoa(src) as source, inet_ntoa(dst) as dest,
        firewall.name as fw, proto.proto, service, action.action, 
        sum(count) as hits, max(date) as lastused, rule_uid.rule_uid 
    FROM log, action, firewall, proto, rule_uid 
    WHERE ( rule_uid.id = log.rule_uid ) 
        AND ( proto.id = log.proto ) 
        AND ( log.action = action.id AND action.action='accept' ) 
        AND ( log.orig = firewall.id) 
        AND ( ( src &gt;= inet_aton('0.0.0.0') 
                AND src &lt;= inet_aton('255.255.255.255') ) )
        AND ( ( dst &gt;= inet_aton('173.82.122.94') 
              AND dst &lt;= inet_aton('173.82.122.94') ) ) 
    GROUP BY src, dst 
    ORDER BY hits DESC, dst

) ORDER BY hits DESC, dst
LIMIT 100;


That may do the job, or something similar :)