Webtest,

Do you have an index on your Oracle database for the field that you are querying on?

You should be able to get to those records in seconds not minutes.