The obvious advice is "profile your program, find hotspots, optimize those". Devel::NYTProf is a great profiler, I can really recommend it.

My second advice is to try to let the database do as much work for you as possible.

If your program processes one database entry at a time, you could also try to parallelize it.

Update: There's also a document in the newest (not yet released) perl verions about performance, pod/perlperf.pod in perl.git.