Bem, um índice na coluna timestamp e userid seria útil. Você precisa ser capaz de ler a saída de uma instrução EXPLAIN.
Vá para o MySQL e faça o seguinte:
EXPLAIN SELECT timestamp, username, [a few more] FROM log
WHERE timestamp BETWEEN '2012-03-30 08:00:00' AND '2012-03-30 16:00:00'
AND username='XX'
Isso mostra o plano que o MySQL usa para executar a consulta. Haverá uma coluna chamada chave. Isso indica qual índice o MySQL está usando na consulta. Eu suspeito que você verá ALL lá, o que significa que o MySQL está varrendo a tabela de cima para baixo, correspondendo a cada linha com sua cláusula where. Agora crie um índice nas colunas timestamp e userid. Execute a instrução EXPLAIN novamente. Você deve ver o índice que criou na coluna de chave.
Se o MySQL usa o índice, sua consulta deve ser consideravelmente mais rápida. Apenas lembre-se de não indexar demais. Os índices tornam as inserções, atualizações e exclusões mais lentas. Quando você insere uma nova linha em uma tabela e há três índices na tabela, a nova linha deve gravar 3 valores nos três índices diferentes. Portanto, é uma faca de dois gumes.
