problèmes d'index et de temps de requetes

Bonjour je débute,

Je dois faire des requêtes sur une table de 111000000 données et quand j'essaye de faire des order by (par exemple) et bien mysql n'y arrive pas ,
il s'arrête au bout de 600 secondes avec ce message d'erreur:
error code: 2013 .lost connection to my sql server during query.

J'ai pensé faire des index pour accélerer les requêtes par exemple :
CREATE INDEX circulation ON brehat.observation (b_num_circ);
Là aussi mysql ne va pas jusqu'au bout et s'arrête au bout de 600 secondes avec le même message d'erreur.

Par ailleurs en faisant :
show index from brehat.observation;
je peux voir qu'il y a déjà un index sur la clé primaire de la table mais je pense que ca suffit pas puisque mysql plante au bout de 600 seconde quand je fais certaines requêtes.

Que puis je faire pour que mysql aille au bout des requêtes?? et/ou construire de nouveaux index.
merci de m'aider

Si au bout de 10 minutes de suite le traitement de tes requêtes n'est pas terminé, tu perdras alors automatiquement ta connexion avec MySQL.

Quelques infos ici : http://bugs.mysql.com/bug.php?id=60103

111 millions de lignes, ça commence à faire beaucoup.
Perso, j'ai quand même déjà interrogé une table de 64 millions de lignes et avec des jointures, sur un PC assez banal et sans problème car la BDD était bien modélisée.

On peut voir la structure de la table et la requête qui n'aboutit pas ?