まことさん、こてちゅさん、こんにちは。

検索に時間がかかるのは、レコード数が大量でネットワークの通信
時間が問題になる場合を除けば、ほとんどRDBMSの検索処理の問題で
す。
こてちゅさんのおっしゃる通り、SQL文やテーブル、インデックスの
設計で大きくパフォーマンスが変わってきます。
例えばWhere句に Like演算子を使っていたりすると、全データをベタ
ベタで検索しますし、インデックスを使っていない項目の検索にも同
じことが言えます。
またインデックスを使っているつもりでも、オプティマイザーが検索
パスを勝手にインデックス無しにしている場合もあり、RDBMSのパフォー
マンスチューニングはかなり複雑で難しい問題と言えます(ほとんどの
場合ケースバイケースですし･････)。

Oracleの場合、パフォーマンスチューニングに関する専門書もいくつ
か出版されていますので、そちらの方も参考にされてはどうでしょう
か？ 最近の日経オープンシステムでもパフォーマンスチューニングに
関する記事が載っていました。