>>490
http://dev.mysql.com/doc/mysql/ja/Miscellaneous_functions.html
の FOUND_ROWS() を見れ。(以下触り)

> 状況によっては、LIMIT を指定しなかった場合にいくつの
> レコードが返されるかを、ステートメントを再度実行する
> ことなく確認したいことがある。このレコード数を確認する
> には SELECT ステートメントに SQL_CALC_FOUND_ROWS
> オプションを指定し、その後 FOUND_ROWS() を呼び出す。
> LIMIT なしで再度クエリを実行するより時間がかからない。

しかし、1万件程度で時間が掛かるってのも、DBのチューニング
や作りがおかしくね？