Speeding up COUNT(*) - WHERE clause slowing query The following query takes 497 ms to run, if I remove the AND portion onwards it only takes 320 ms. Is there any way to speed this up? The only indexes I have on 'messages' table is a PK on 'messages_id'. The 'hidden' field is a bit field (not null) and 'message_type_id' is an int field (not null) and message_id is an int field (PK).

SELECT COUNT(*)
FROM messages
WHERE message_type_id = 1
AND (hidden = 0 OR message_id = @message_id)


Thanks in advance!
Another approach to remove the OR.
You could try this and have 2 indexes on the table to satisfy the WHERE clauses.

SELECT
    COUNT(*)
FROM
    (
    SELECT message_id
    FROM messages
    WHERE message_type_id = 1 AND hidden = 0
    UNION
    SELECT message_id
    FROM messages
    WHERE message_type_id = 1 AND message_id = @message_id
    ) X