If you only care about the first match, try exiting the loop as soon as you find the match, that should save time. Also, if you know which keys will be found most often, you might want to try to match them first instead of relying on the return order of the 'keys' function.

while($cur_line=<fh_log>) 
{ 
   foreach $key (keys %hash) 
   { 
      $table = $hash{$key}[0]; 

      #If this query contains reference to this table 
      if($cur_line=~ m/$table/i) 
      {     
          #count up how many times this table is referenced. 
      $table_stats{$table}++; 
      $table_refs++;     #total table references (for % calc) 
      last; #added to exit inner loop upon match
      } 
   }
}