先ほど読んだように、ALTER TABLE ... ORDER BY ... クエリは、特定のシナリオでパフォーマンスを向上させるのに役立ちます。 PKインデックスがこれに役立たないことに驚いています。ただし、MySQLドキュメント
から 、InnoDBはしているようです インデックスを使用します。ただし、InnoDBはMyISAMよりも遅くなる傾向があります。そうは言っても、InnoDBを使用すると、テーブルを並べ替える必要はありませんが、MyISAMの驚異的な速度が失われます。それでも一撃の価値があるかもしれません。
問題を説明する方法では、メモリにロードされているデータが多すぎるようです（おそらくスワッピングが行われているのでしょうか？）。メモリ使用量を監視することで、それを簡単に確認できます。 MySQLをあまりよく知らないので、言うのは難しいです。
一方、問題は非常に異なる場所にあると思います。4Mioを超える行を含むテーブルを持つデータベースサーバーとして、RAMが512メガバイトしかないマシンを使用しています...そして、非常にメモリを大量に消費しています。そのマシンのテーブル全体に対する操作。 512Megでは十分ではないようです。
私がここで見ているはるかに根本的な問題：あなたは本番環境とは非常に異なる環境で開発を行っています（そしておそらくテストも行っています）。あなたが説明している種類の問題は予想されることです。開発マシンには、本番マシンの6倍のメモリがあります。プロセッサもはるかに高速であると私は安全に言うことができると思います。その場合は、本番サイトを模倣した仮想マシンを作成することをお勧めします。そうすれば、本番サイトを中断することなく、プロジェクトを簡単にテストできます。