Consulta retorna errado quando tem muitos registros

Pessoal, estou precisando muito da ajuda de vocês.

Seguinte:

Tenho um banco de dados, que contem uma tabela chamada 'item', porem nessa tabela item já existem cerca de 10 milhões de registros.

Quando eu tento consultar um registro da tabela item pela coluna chamada 'chave', mesmo eu sabendo que o registro está la, muita das vezes consulta me retorna 0.

Segue abaixo como estou consultando:

$resultado = mysql_query("SELECT * FROM item WHERE chave='$chave'",$db);

 

$count = mysql_num_rows($resultado);

 

if ($count == 0 || $count == NULL) {

echo 'Registro não encontrado!'

}

Alguem, POR FAVOR, pode me da uma solução, como posso fazer para que a consulta me retorne corretamente ?