Hast du einen Index auf die zu durchsuchende Spalte?

Und warum schreibst du "use CGI", machst dann das Parameterhandling aber selbst? Außerdem verwendest du keine DBI-Platzhalter, gefährlich!

Eine hohe Last könnte auf zu wenig Speicher hindeuten.

Mit mod_perl lässt sich gegenüber CGI viel gewinnen.