One possibility is to use a HoA'a instead of your AoA's for your table. That would make the lookup process much quicker than a linear search.

#! perl -slw
use strict;
use Data::Dumper;

my $table=[[1,2,2,3,2,1],[qw(a b c d e a)],[qw(A D D C B A)]];

#! Convert your AoA's to a HoA's.
#! Use the values from the arrays as the key and store the indices in 
+the array
#! You could just store the index as the value if the keys are unique.
#! Better to build it this way in the first place though.
my %table;
push @{$table{"0:$table->[0][$_] 1:$table->[1][$_] 2:$table->[2][$_]"}
+}, $_ for 0..$#{$table->[0]};

print Dumper(\%table);

#! To find all entries which match on all three elements
my @elements = qw(0:1 1:a 2:A);
my @matches = @{$table{"@elements"}} if exists $table{"@elements"};

print "Element ids: @matches contained elements: @elements";

#! To find elements that match on a subset
@matches = ();
/0:2/ and /2:D/ and push @matches, @{$table{$_}}  for keys %table;

print "Element ids @matches contain elements: 0:2 2:D";
[download]

Gives

c:\test>218070
$VAR1 = {
          '0:2 1:e 2:B' => [
                             4
                           ],
          '0:2 1:c 2:D' => [
                             2
                           ],
          '0:1 1:a 2:A' => [
                             0,
                             5
                           ],
          '0:2 1:b 2:D' => [
                             1
                           ],
          '0:3 1:d 2:C' => [
                             3
                           ]
        };

0:1 1:a 2:A
Element ids: 0 5 contained elements: 0:1 1:a 2:A
Element ids 2 1 contain elements: 0:2 2:D

c:\test>
[download]

The caveat is that if your table elements contain 'n:...' sequences, then you might need to use a different fields specifier, but that wouldn't be too hard. Wrapping the lookup into a function that build the search keys from a list supplied would neaten the whole thing up a bit.