動的に検索条件を指定するのは、特に問題があるとは思いません。
データの検索に対するパフォーマンスは、SQL文にあることが多いからです。
DBMSに何を使用しているのか分からないので、Oracleに限定させて頂きますが、
何万件、何十万件のデータからたった1件を検索する場合でもインデックスが
はっていないキーでWhere句を使用した場合と、インデックスを設定しその条件を
踏まえてWhere句を指定した場合では、かなりパフォーマンスに差が出てきます。
JOINなんかしてるともっと顕著にあらわれます。

SQL文の構文によっては、Selectする項目の順番なども重要になってくることがあります。
Like検索もパフォーマンスにかなりの影響を与えます。
その他にももろもろの条件によりデータ検索のパフォーマンスが変わってきます。

動的に検索条件を指定する場合、インデックスなどを指定するのは難しい作業だとは
思いますが、ある程度の定型的な条件をWhere句の最初に持ってきて、インデックスを
作成しておくとか・・・

一度使用したSQLをもう一度実行すると、Oracleの場合は、1回目の時より数段早く返って
きます。（詳しくはOracleを参照して下さい。）これを利用するなどの方法も考えられます。

PBだけのせいにせず、DBの作り込みやSQL文の書き方などにも注意してみては？