To build on what ovid said, you might want to look to see how much of the time taken was from mysql. Dump the SQL that perl is using for its query, and then run that in the mysql client. If that takes a significant time, you might take a look at EXPLAIN. It's also necessary to ANALYZE your tables when they change significantly, so that the database can determine if the indexes are going to be a benefit or not. (it can be faster to not use an index unless you're throwing away the majority of the records, as you require more table reads... for oracle, I've heard that number is between 5 to 20% of the records kept.. so if you're throwing away less than 4/5 of the records, a full table scan may be the way to go.
Memory sizing of the system can also be important -- out of the box, mysql uses very little memory (in my opinion). If you have a 2GB dedicated server, it does no good if mysql is told to only use 256MB. (it might be 384MB as the default...still rather small for some people).
Anyway, if you find that the perl process is taking 30 minutes, but it's only taking 5 minutes for mysql to do its work, then you'll want to look at the Perl side of things. If it's taking 25 minutes in MySQL, then you'll want to look at adjusting the SQL statement, or tuning the database. If it's somewhere in between, well, pick one, and if that doesn't get enough time out to be acceptable, tune the other side, and keep going back and forth 'till it meets your goal time.