This isn't a Perl question so far as it's a relational database design question. So, I'll treat it as such.

You have two different tables:

• respondent, where you have info about the respondent - name, address, etc
• responses, where you list the responses each respondent took

So, given the info you have, I would design tables as such:

CREATE TABLE respondent (
    id unsigned int not null auto_increment primary key
   ,name varchar(20)
#  , etc ...
);

CREATE TABLE response (
    id unsigned int not null auto_increment primary key
   ,name varchar(20)
);

CREATE TABLE responses (
    respondent unsigned int
   ,response   unsigned int
   ,PRIMARY KEY (respondent, response)
);
[download]

Then, I would create the query as such:

SELECT A.respondent AS respondent
  FROM responses A JOIN responses B on (A.respondent = B.respondent)
 WHERE A.response = ?
   AND B.response = ?
[download]

I would call it as such:

my $sth = $dbh->prepare_cached( $sql );
$sth->execute( $response_x, $response_y );

$sth->bind_columns( \my ($respondent) );

my @respondents;
while ($sth->fetch)
{
    push @respondents, $responses;
}

$sth->finish;
[download]

Depending on the power of your database server, this should run in under 3-5 seconds, given the numbers you mentioned. I should warn you that my experience is primarily with MySQL 4.1.x, so I don't have a lot of knowledge of the 3.x series.

I would also turn on query_caching, which will help a bunch with the reporting. I personally have found a 90% improvement with certain kinds of reporting when I turned it on.