Well, I've tried the 3,000 column by 20,000 row thing.

respondent_id, response_1, response_2, .....

Searches of the form

select count(*) from theTable where (response_1=1 and response_n=1);

performs abysmally. Averages ~ 0.24 seconds per select execution. I'm looking for under 0.1 sec because I'm producing reports in real time that require a few hundred selects to do to produce a single report.

I can use respondent _id as primary key, but each of the 3,000 columns is equally likely to be searched on and I can't index them all. I don't believe mysql will allow 3,000 indexes on a single table.

So .... I got hinking about an inverted index so I could quickly retrieve the list of respondents who gave response x, the list of respondents who gave response y, and then compute their intersection.

My first version of this was to have a separate table for each possible reponse and populate it with respondent id's. That improved performance to ~0.16 sec average. Of course, each table has its own index. If, instead, I had one large inverted index,

response_id, respondent_1, respondent_2, ...

I would only need to use the one response_id column as primary key, reducing total size and complexity of the database. In that case I have two options:

• put respondent id's in the columns and my selects become
  select * from theTable where response_id = x
• use the response id's as column names and fill with 1s and 0s, but then I need a way to associate matches with their column names.....
Soooo, I was thinking of trying the search engine trick and building a reverse index like Search::InvertedIndex.

I'm very interested in ideas.

Thanks.

I'm not sure I understand your database schema. From how I understood it, I created the following SQL schema (in SQLite syntax), which is not denormalized, so it might be suboptimal, but it is as clean as I can imagine it. By "fk" I mean "foreign key", so offered_choice.correct should be a value that can be found in the response.id column.

create table response (
  -- models a possible response
  id    integer primary key,
  text    varchar
);

create table question (
  -- models a possible question
  id    integer primary key,
  text    varchar
);

create table offered_choice (
  -- models the offered choices to a question
  id        integer primary key,
  question    integer,
  choice        integer -- fk into response
);


create table questionnaire (
  id        integer primary key,
  position    integer,
  choice_set    integer, -- fk into offered_choice
  correct    integer -- fk into response
);

create table answer (
  -- models a given answer
  id        integer primary key,
  subject    integer,
  questionlet    integer,
  response    integer
);

create table subject (
  -- models a person taking a test
  id        integer primary key,
  name        varchar()
);
[download]

With these tables filled, and indices at least on every primary key column, your queries become joins over multiple tables, but they should also not be too slow.

Your dataset doesn't seem too large though, so I wonder what you did to actually optimize MySQL performance - MySQL can hold a (read-only) table completely in memory, so you should tell MySQL to do just that - this should speed up your queries by quite a lot too. On the other hand, I still wonder about your current database schema, because blindly throwing around 3000 tables, or 3000 indices doesn't make much sense to me. I'm also not sure if every subject got asked every question and got offered every possible response - my schema allows for mixing the responses offered to every question, but also allows for only one "correct" response to every questionlet.

I don't want to sound too harsh, but you really need to do some reading on relational database schema design. There is no problem I can think of that would require 3000 columns to represent it. Something more like Corion's design is what I would have done. With proper indexes, this should handle the relatively small dataset you have very efficiently.

So I built a new database with the new keys:

CREATE TABLE `responses` ( `respondent` smallint(5) unsigned NOT NULL 
+default '0', `response` smallint(5) unsigned NOT NULL default '0', PR
+IMARY KEY (`respondent`,`response`), KEY `respondent` (`respondent`),
+ KEY `response` (`response`) ) TYPE=MyISAM
[download]

SELECT COUNT(*) FROM theTable A JOIN theTable B ON (A.respondent = B.r
+espondent) WHERE A.response = ? AND B.response = ?
[download]

Anyway, EXPLAIN on this query in this new database says

+-------+--------+-----------------------------+----------+---------+--------------------+------+--------------------------+
| table | type   | possible_keys               | key      | key_len | ref                | rows | Extra                    |
+-------+--------+-----------------------------+----------+---------+--------------------+------+--------------------------+
| A     | ref    | PRIMARY,respondent,response | response |       2 | const              | 3372 | Using where              |
| B     | eq_ref | PRIMARY,respondent,response | PRIMARY  |       4 | A.respondent,const |    1 | Using where; Using index |
+-------+--------+-----------------------------+----------+---------+--------------------+------+--------------------------+

Bit arrays and bit masks sound interesting, but Googling "bit array" & "bit mask" doesn't give me much. Any good reads on this somewhere?

Found the PDL pages....interesting...