I just began optimizing my schemas with indexes (pretty late I guess).
I never dealt with huge dataset but I'll be soon coping with about 1 to 5 millions rows.

Here is the schema I'm using right now for testing:

CREATE TABLE `object`
(
  `otype` VARCHAR(255),
  `id` BIGINT UNSIGNED AUTO_INCREMENT PRIMARY KEY NOT NULL,
  `domain` VARCHAR(255),
  `created_at` INT,
  `updated_at` INT,
  `deleted_at` INT,
  `category` VARCHAR(31), /* genre, type, category */
  `status` VARCHAR(15)
)ENGINE=InnoDB;
ALTER TABLE `object` ADD UNIQUE KEY `object` ( `otype`, `id` );
CREATE INDEX `id` ON `object` ( `otype`, `id` );
CREATE INDEX `object_id` ON `object` ( `id` );
CREATE INDEX `object_domain` ON `object` ( `domain` );
CREATE INDEX `object_category` ON `object` ( `category` );
CREATE INDEX `object_status` ON `object` ( `status` );

CREATE TABLE `offer`
(
id BIGINT UNSIGNED,
`category` VARCHAR(31), /* genre, type, category */
amount DECIMAL(12,3)
)ENGINE=InnoDB;
ALTER TABLE `offer` ADD FOREIGN KEY ( `id` ) REFERENCES object( `id` ) ON UPDATE CASCADE ON DELETE CASCADE;
CREATE INDEX `offer_id` ON `offer` ( `id` );
CREATE INDEX `offer_category` ON `offer` ( `category` );

And this is the query I'm trying to optimize: I'm reporting it twice because I was experimenting if using indexes filtering just the first table was faster than filtering both the tables and I guess I was right: aren't I?

mysql> select SQL_NO_CACHE count(*) from object, offer where object.id = offer.id and object.category = "bid" and status = "pending" order by created_at;
+----------+
| count(*) |
+----------+
|   499510 |
+----------+
1 row in set (2.06 sec)

mysql> explain extended select SQL_NO_CACHE count(*) from object, offer where object.id = offer.id and object.category = "bid" and status = "pending" order by created_at;
+----+-------------+--------+------+-------------------------------------------------+-----------------+---------+------------------+--------+----------+------------------------------------+
| id | select_type | table  | type | possible_keys                                   | key             | key_len | ref              | rows   | filtered | Extra                              |
+----+-------------+--------+------+-------------------------------------------------+-----------------+---------+------------------+--------+----------+------------------------------------+
|  1 | SIMPLE      | object | ref  | PRIMARY,object_id,object_category,object_status | object_category | 96      | const            | 498729 |   100.00 | Using index condition; Using where |
|  1 | SIMPLE      | offer  | ref  | offer_id                                        | offer_id        | 9       | testme.object.id |      1 |   100.00 | Using index                        |
+----+-------------+--------+------+-------------------------------------------------+-----------------+---------+------------------+--------+----------+------------------------------------+
2 rows in set, 1 warning (0.01 sec)

mysql> select SQL_NO_CACHE count(*) from object, offer where object.id = offer.id and offer.category = "bid" and status = "pending" order by created_at;
+----------+
| count(*) |
+----------+
|   499510 |
+----------+
1 row in set (3.78 sec)

mysql> explain extended select SQL_NO_CACHE count(*) from object, offer where object.id = offer.id and offer.category = "bid" and status = "pending" order by created_at;
+----+-------------+--------+--------+---------------------------------+----------------+---------+-----------------+--------+----------+------------------------------------+
| id | select_type | table  | type   | possible_keys                   | key            | key_len | ref             | rows   | filtered | Extra                              |
+----+-------------+--------+--------+---------------------------------+----------------+---------+-----------------+--------+----------+------------------------------------+
|  1 | SIMPLE      | offer  | ref    | offer_id,offer_category         | offer_category | 96      | const           | 498792 |   100.00 | Using index condition; Using where |
|  1 | SIMPLE      | object | eq_ref | PRIMARY,object_id,object_status | PRIMARY        | 8       | testme.offer.id |      1 |   100.00 | Using where                        |
+----+-------------+--------+--------+---------------------------------+----------------+---------+-----------------+--------+----------+------------------------------------+
2 rows in set, 1 warning (0.00 sec)

I studied different articles and the mysql index page which states:

They are used only for equality comparisons that use the = or <=> operators (but are very fast) […] The optimizer cannot use a hash index to speed up ORDER BY operations

1. Since I'll probably move to mysql cluster, does it make sense to switch from InnoDB to NDB engine and use HASH indexes on "category" and "status" columns?

2. I read how btrees stores data. If most of my queries involve a "WHERE category = x AND status = y", should I add 3 different indexes: one on category, one on status, and one on the combination of both?

3. "show warnings" doesn't show anything useful about what mysql is trying to warn me about: what's wrong with my query?

   mysql> show warnings \G
   *********************** 1. row ***********************
   Level: Note
   Code: 1003
   Message: /* select#1 */ select sql_no_cache count(0) AS count(*) from testme.object join testme.offer where ((testme.object.id = testme.offer.id) and (testme.object.category = 'bid') and (testme.object.status = 'pending'))
   1 row in set (0.00 sec)

4 Can the following:

CREATE INDEX `object_category_status` ON `object` ( `category`, `status` );
CREATE INDEX `object_category` ON `object` ( `category` );
CREATE INDEX `object_status` ON `object` ( `status` );

be reduced with the following for the very same result?

CREATE INDEX `object_category_status` ON `object` ( `category`, `status` );
CREATE INDEX `object_status` ON `object` ( `status` );

Thanks for your time!