How can I get mysql to use indexes with a simple AND + OR query?
===

This is using MySQL 5.5.
I cannot seem to convince MySQL to use indexes for these queries and they are taking anywhere from 2-10 seconds to run on a table with 1.1 million rows.

Table:

    CREATE TABLE `notifiable_events` (
    `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
    `key` varchar(255) NOT NULL,
    `trigger_profile_id` int(10) unsigned DEFAULT NULL,
    `model1` varchar(25) NOT NULL,
    `model1_id` varchar(36) NOT NULL,
    `model2` varchar(25) NOT NULL DEFAULT '',
    `model2_id` varchar(36) NOT NULL DEFAULT '',
    `event_data` text,
    `created` datetime DEFAULT NULL,
    `modified` datetime DEFAULT NULL,
    `deleted` tinyint(1) NOT NULL DEFAULT '0',
    PRIMARY KEY (`id`),
    KEY `key` (`key`),
    KEY `notifiable_events__trigger_profile` (`trigger_profile_id`),
    KEY `deleted` (`deleted`),
    KEY `noti_evnts__m2` (`model2`),
    KEY `noti_evnts__m1` (`model1`),
    CONSTRAINT `notifiable_events__trigger_profile` FOREIGN KEY (`trigger_profile_id`) REFERENCES `profiles` (`id`)
    ) ENGINE=InnoDB AUTO_INCREMENT=1177918 DEFAULT CHARSET=utf8

QUERY:

    SELECT * FROM notifiable_events WHERE (`model1` = 'page' AND `model1_id` = '54321') OR (`model2` = 'page' AND `model2_id` = '12345');

EXPLAIN(S):
<pre>
mysql> EXPLAIN EXTENDED SELECT * FROM notifiable_events WHERE (`model1` = 'page' AND `model1_id` = '922645') OR (`model2` = 'page' AND `model2_id` = '922645')\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: notifiable_events
         type: ALL
possible_keys: noti_evnts__m2,noti_evnts__m1,noti_evnts__m1_m2
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 1033088
     filtered: 100.00
        Extra: Using where
1 row in set, 1 warning (0.00 sec)

mysql> EXPLAIN EXTENDED SELECT * FROM notifiable_events WHERE (`model1` = 'page' AND `model1_id` = '922645') OR (`model1` = 'page' AND `model1_id` = '922645')\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: notifiable_events
         type: ref
possible_keys: noti_evnts__m1,noti_evnts__m1_m2
          key: noti_evnts__m1
      key_len: 77
          ref: const
         rows: 1
     filtered: 100.00
        Extra: Using where
1 row in set, 1 warning (0.00 sec)

mysql> EXPLAIN EXTENDED SELECT * FROM notifiable_events WHERE (`model2` = 'page' AND `model2_id` = '922645') OR (`model2` = 'page' AND `model2_id` = '922645')\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: notifiable_events
         type: ref
possible_keys: noti_evnts__m2
          key: noti_evnts__m2
      key_len: 77
          ref: const
         rows: 428920
     filtered: 100.00
        Extra: Using where
1 row in set, 1 warning (0.00 sec)
</pre>

You can see that if I only use model1 or only use model2 then it will use the index, however, as soon as I try to use both of them together it gives up on the index entirely and does a full table scan.
I have already tried FORCE INDEX and I have tried a combination of multi-key indexes (and I left one in place for this table as an example). I have also tried rearranging the order of elements in the query but that doesn't seem to have any effect either.

It seems like it should be really easy to use an index to limit the rows being checked here so I hope I am just missing something.