Comment 3 for bug 1362212

I don't yet know how to best share example data as I cannot share the real data publicly. For completeness, here's some more data from our system:

mysql> show global variables like '%version%';
+-------------------------+--------------------------------------------------+
| Variable_name | Value |
+-------------------------+--------------------------------------------------+
| innodb_version | 5.6.19-67.0 |
| protocol_version | 10 |
| slave_type_conversions | |
| version | 5.6.19-67.0-log |
| version_comment | Percona Server (GPL), Release 67.0, Revision 618 |
| version_compile_machine | x86_64 |
| version_compile_os | debian-linux-gnu |
+-------------------------+--------------------------------------------------+

mysql> show table status like 'suggestion'\G
*************************** 1. row ***************************
           Name: suggestion
         Engine: InnoDB
        Version: 10
     Row_format: Compact
           Rows: 44442324
 Avg_row_length: 152
    Data_length: 6759219200
Max_data_length: 0
   Index_length: 5125160960
      Data_free: 7340032
 Auto_increment: NULL
    Create_time: 2014-08-27 11:08:14
    Update_time: NULL
     Check_time: NULL
      Collation: latin1_german2_ci
       Checksum: NULL
 Create_options:
        Comment:
1 row in set (0.01 sec)

The explains you did:

mysql> EXPLAIN SELECT obj_id, flags, data, type FROM suggestion WHERE user_id='7723036' AND type IN ('newbie', 'group') AND rejected='n' AND flags=0 ORDER BY type DESC, created DESC;
+----+-------------+------------+-------+-------------------------------+---------+---------+------+------+-----------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+------------+-------+-------------------------------+---------+---------+------+------+-----------------------------+
| 1 | SIMPLE | suggestion | range | PRIMARY,user_id,type,rejected | PRIMARY | 5 | NULL | 62 | Using where; Using filesort |
+----+-------------+------------+-------+-------------------------------+---------+---------+------+------+-----------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT obj_id, flags, data, type FROM suggestion WHERE user_id='7723036' AND type IN ('newbie', 'group') AND rejected='n' AND flags=0 ORDER BY type DESC, created DESC LIMIT 50;
+----+-------------+------------+-------+-------------------------------+------+---------+------+----------+------------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+------------+-------+-------------------------------+------+---------+------+----------+------------------------------------+
| 1 | SIMPLE | suggestion | range | PRIMARY,user_id,type,rejected | type | 1 | NULL | 41129152 | Using index condition; Using where |
+----+-------------+------------+-------+-------------------------------+------+---------+------+----------+------------------------------------+
1 row in set (0.00 sec)

Excerpts from our my.cnf with all performance-related settings:

key_buffer_size = 4095M
max_allowed_packet = 16M
thread_cache_size = 50
table_open_cache = 20000
join_buffer_size = 16M
read_buffer_size = 12M
read_rnd_buffer_size = 32M
sort_buffer_size = 8M
tmp_table_size = 512M
max_heap_table_size = 512M
max_connections = 2000

query_cache_limit = 1M
query_cache_size = 128M
query_cache_type = 0

transaction-isolation = REPEATABLE-READ
innodb_lock_wait_timeout = 15
innodb_buffer_pool_size = 13G
innodb_log_file_size = 256M
innodb_log_buffer_size = 8M
innodb_flush_log_at_trx_commit = 2
innodb_thread_concurrency = 0
innodb_flush_method = O_DIRECT
innodb_file_per_table

I'll have a try whether I can create some test data which shows the same behaviour as our real data one of the next days.