Now that you know that the database is sucking up a lot of time, profile DBI. See the docs for DBI::Profile or the chapter of profiling in Mastering Perl which also talks about DBI profiling.

Good luck! :)