This is not a Perl question, but a DB-optimization question (unless you want to write Perl code to intelligently combine queries and extract the data back out -- but that would probably *still* be slow).

Make sure you have normalized your DB for the type of queries you wish to perform, and index the columns you are searching through. For example, if you have a table with columns:

ID
Name
Age
Details
SSN
Record_file

and you commonly search for records by Name and SSN, create indexes on those columns. Intelligent use of indexes, along with proper normalization, nets in huge speed gains in many circumstances.