one method to increase speed is to avoid hashing. This doesn't mean to create unfelxible datastructures, but in special cases hashing can be skipped for speed.

Second is: precompile regular expressions via qr//.

Third: Why pass $_ as argument? $_ is global. As long as scan() isn't used in different places...

my $scan = [0,qr/a/,2,qr/C/];
my @filtered = grep scan $scan,
             @$table
sub scan {
    my $aref = shift;
    my $i    = 0;
    while( ++$i < @$aref ){
        return unless $_->[$i-1] =~
                $aref->[$i++]
    }
    1
}
[download]

This code is untested.

--
http://fruiture.de