How can I improve this query I have the following table:

CREATE TABLE `twitter_relationships` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `user_id` int(11) NOT NULL,
  `source_twitter_id` bigint(20) NOT NULL,
  `target_twitter_id` bigint(20) NOT NULL,
  `relationship_status` tinyint(1) NOT NULL,
  `status_change_date` int(11) unsigned DEFAULT NULL,
  PRIMARY KEY (`id`,`user_id`),
  UNIQUE KEY `source_and_target` (`user_id`,`source_twitter_id`,`target_twitter_id`),
  KEY `target_status_and_change_date_index` (`user_id`,`target_twitter_id`,`relationship_status`,`status_change_date`),
  KEY `user_id_index` (`user_id`,`status_change_date`)
) ENGINE=InnoDB AUTO_INCREMENT=116597775 DEFAULT CHARSET=latin1
/*!50100 PARTITION BY HASH (user_id)
PARTITIONS 1000 */


This table is pretty big, ~150M records.

And I have the following query:

SELECT target_twitter_id 
 FROM `twitter_relationships` 
WHERE (`twitter_relationships`.`relationship_status` = ? 
   AND `twitter_relationships`.`user_id` = ? 
   AND `twitter_relationships`.`source_twitter_id` = ?) 
LIMIT ?, ?


Here is the explain for this query:

           id: 1
  select_type: SIMPLE
        table: twitter_relationships
         type: ref
possible_keys: source_and_target,target_status_and_change_date_index,user_id_index
          key: source_and_target
      key_len: 12
          ref: const,const
         rows: 8560582
        Extra: Using where


Any ideas what I can do in the query or even in the table structure to speed this query up?
First, since you already have a UNIQUE index that contains the user_id, you should be able to get rid of the id field, and use the UNIQUE index as the PRIMARY KEY:

CREATE TABLE `twitter_relationships` (
  `user_id` int(11) NOT NULL,
  `source_twitter_id` bigint(20) NOT NULL,
  `target_twitter_id` bigint(20) NOT NULL,
  `relationship_status` tinyint(1) NOT NULL,
  `status_change_date` int(11) unsigned DEFAULT NULL,
  PRIMARY KEY (`user_id`,`source_twitter_id`,`target_twitter_id`),
  KEY `target_status_and_change_date_index`
    (`user_id`,`target_twitter_id`,`relationship_status`,`status_change_date`),
  KEY `user_id_index` (`user_id`,`status_change_date`)
) ENGINE=InnoDB AUTO_INCREMENT=116597775 DEFAULT CHARSET=latin1
PARTITION BY HASH (user_id) PARTITIONS 1000;


Unfortunately, while this removes an index, it may increase storage requirements, due to the way that InnoDB indexes data. See "How Secondary Indexes Relate to the Clustered Index" in http://dev.mysql.com/doc/refman/5.6/en/innodb-table-and-index.html

Second, while the source_and_target index has two of the three fields in your WHERE clause, MySQL will have to do an additional read to find the relationship_status.

Therefore, to improve performance, create an index that includes all three fields in your WHERE clause:

CREATE INDEX user_source_status ON twitter_relationships
    (`user_id`,`source_twitter_id`,`relationship_status`);


Then, if MySQL doesn't use this index automatically, you can force using it, with:

SELECT target_twitter_id 
 FROM `twitter_relationships` FORCE INDEX (user_source_status)
WHERE (`twitter_relationships`.`user_id` = ? 
   AND `twitter_relationships`.`source_twitter_id` = ?
   AND `twitter_relationships`.`relationship_status` = ?) 
LIMIT ?, ?


Lastly, you're missing the UNSIGNED attribute on the id, user_id, source_twitter_id, and target_twitter_id fields. I'm guessing these fields will never store negative values, so it would make sense to make them UNSIGNED.