Bug #74078 join of large table to small table is slow if small table has less than 7 rows
Submitted: 25 Sep 2014 16:15 Modified: 16 Oct 2014 19:49
Reporter: Jeroen van den Hoed Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S5 (Performance)
Version:5.6.19/5.5/5.7 OS:Linux (Ubuntu 14)
Assigned to: CPU Architecture:Any

[25 Sep 2014 16:15] Jeroen van den Hoed
Description:
I have a simple query joining a large table (>250K rows) to a small table (just 1 row) . All the records in the large table refer to this 1 record in the small table. My real world tables and query are more complicated, but this illustrates my issue well enough.

SELECT t1.id, t1.name, t2.id, t2.name FROM t1, t2 WHERE t1.t2_id=t2.id ORDER BY t1.id LIMIT 0,10;

The query runs relatively slow (0.19s). Using EXPLAIN I know the tables are joined in an suboptimal order (Using temporary; Using filesort Using where; Using join buffer (Block Nested Loop)).

But when I add at least 6 other records to the small table (making a total of 7 rows), the query runs fast (0.00s) and uses the primary keys. Adding 5 record won't do it.

I'm running 5.6.19-0ubuntu0.14.04.1 on a x86_64 with persistent statistics turned ON. I've tried analyze/optimize table, and increasing the sample pages vars (innodb_stats_persistent_sample_pages, innodb_stats_sample_pages, innodb_stats_transient_sample_pages), but to no avail. Myisam does not have this problem; only Innodb has. Removing the "ORDER BY t1.id" from the query makes the query fast.

I've posted this issue earlier to http://forums.mysql.com/read.php?22,620920,620920#msg-620920 and got advised to report this as a bug. This bug might be similar/the same to http://bugs.mysql.com/bug.php?id=41873

Thank you for reading,
Jeroen

How to repeat:
#create the large table
CREATE TABLE t1 (id int(11) NOT NULL AUTO_INCREMENT, name varchar(255) NOT NULL, t2_id int(11) NOT NULL, PRIMARY KEY (id)) ENGINE=InnoDB DEFAULT CHARSET=utf8;

#create the small table
CREATE TABLE t2 (id int(11) NOT NULL AUTO_INCREMENT, name varchar(255) NOT NULL, PRIMARY KEY (id)) ENGINE=InnoDB DEFAULT CHARSET=utf8;

#insert 1 record in the small table
INSERT INTO t2 (name) VALUES ('small table');

#insert 262144 records in the large table; we do this by inserting 1 record and exponentially duplicating the records 18 times
INSERT INTO t1 (name, t2_id) VALUES ('large table', 1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);

#we now have 262144 identical rows in t1

#run the join query; this runs relatively slow; 0.19s
SELECT t1.id, t1.name, t2.id, t2.name FROM t1, t2 WHERE t1.t2_id=t2.id ORDER BY t1.id LIMIT 0,10;
+----+-------------+----+-------------+
| id | name | id | name |
+----+-------------+----+-------------+
| 1 | large table | 1 | small table |
| 2 | large table | 1 | small table |
| 3 | large table | 1 | small table |
| 4 | large table | 1 | small table |
| 6 | large table | 1 | small table |
| 7 | large table | 1 | small table |
| 8 | large table | 1 | small table |
| 9 | large table | 1 | small table |
| 13 | large table | 1 | small table |
| 14 | large table | 1 | small table |
+----+-------------+----+-------------+
20 rows in set (0.19 sec)

#run explain; the primary keys are NOT used
EXPLAIN SELECT t1.id, t1.name, t2.id, t2.name FROM t1, t2 WHERE t1.t2_id=t2.id ORDER BY t1.id LIMIT 0,10;
+----+-------------+-------+------+---------------+------+---------+------+--------+----------------------------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+------+--------+----------------------------------------------------+
| 1 | SIMPLE | t1 | ALL | NULL | NULL | NULL | NULL | 262010 | Using temporary; Using filesort |
| 1 | SIMPLE | t2 | ALL | PRIMARY | NULL | NULL | NULL | 1 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------+---------------+------+---------+------+--------+----------------------------------------------------+
2 rows in set (0.00 sec)

#add 6 more records to the small table
INSERT INTO t2 (name) VALUES ('small table');
INSERT INTO t2 (name) VALUES ('small table');
INSERT INTO t2 (name) VALUES ('small table');
INSERT INTO t2 (name) VALUES ('small table');
INSERT INTO t2 (name) VALUES ('small table');
INSERT INTO t2 (name) VALUES ('small table');

#run the query again; now it is fast; 0.00s
SELECT t1.id, t1.name, t2.id, t2.name FROM t1, t2 WHERE t1.t2_id=t2.id ORDER BY t1.id LIMIT 0,10;
+----+-------------+----+-------------+
| id | name | id | name |
+----+-------------+----+-------------+
| 1 | large table | 1 | small table |
| 2 | large table | 1 | small table |
| 3 | large table | 1 | small table |
| 4 | large table | 1 | small table |
| 6 | large table | 1 | small table |
| 7 | large table | 1 | small table |
| 8 | large table | 1 | small table |
| 9 | large table | 1 | small table |
| 13 | large table | 1 | small table |
| 14 | large table | 1 | small table |
+----+-------------+----+-------------+
10 rows in set (0.00 sec)

#run explain; the primary keys are used
EXPLAIN SELECT t1.id, t1.name, t2.id, t2.name FROM t1, t2 WHERE t1.t2_id=t2.id ORDER BY t1.id LIMIT 0,20;
+----+-------------+-------+--------+---------------+---------+---------+---------------+------+-------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+--------+---------------+---------+---------+---------------+------+-------+
| 1 | SIMPLE | t1 | index | NULL | PRIMARY | 4 | NULL | 20 | NULL |
| 1 | SIMPLE | t2 | eq_ref | PRIMARY | PRIMARY | 4 | test.t1.t2_id | 1 | NULL |
+----+-------------+-------+--------+---------------+---------+---------+---------------+------+-------+
2 rows in set (0.00 sec)

mysql> SHOW TABLE STATUS;
+------+--------+---------+------------+--------+----------------+-------------+-----------------+--------------+-----------+----------------+---------------------+-------------+------------+-----------------+----------+----------------+---------+
| Name | Engine | Version | Row_format | Rows   | Avg_row_length | Data_length | Max_data_length | Index_length | Data_free | Auto_increment | Create_time         | Update_time | Check_time | Collation       | Checksum | Create_options | Comment |
+------+--------+---------+------------+--------+----------------+-------------+-----------------+--------------+-----------+----------------+---------------------+-------------+------------+-----------------+----------+----------------+---------+
| t1   | InnoDB |      10 | Compact    | 262010 |             42 |    11026432 |               0 |            0 |         0 |         393198 | 2014-09-23 17:20:20 | NULL        | NULL       | utf8_general_ci |     NULL |                |         |
| t2   | InnoDB |      10 | Compact    |      1 |          16384 |       16384 |               0 |            0 |         0 |              2 | 2014-09-23 17:20:21 | NULL        | NULL       | utf8_general_ci |     NULL |                |         |
+------+--------+---------+------------+--------+----------------+-------------+-----------------+--------------+-----------+----------------+---------------------+-------------+------------+-----------------+----------+----------------+---------+
2 rows in set (0.00 sec)

mysql> SHOW VARIABLES LIKE 'innodb%';
+------------------------------------------+------------------------+
| Variable_name                            | Value                  |
+------------------------------------------+------------------------+
| innodb_adaptive_flushing                 | ON                     |
| innodb_adaptive_flushing_lwm             | 10                     |
| innodb_adaptive_hash_index               | ON                     |
| innodb_adaptive_max_sleep_delay          | 150000                 |
| innodb_additional_mem_pool_size          | 8388608                |
| innodb_api_bk_commit_interval            | 5                      |
| innodb_api_disable_rowlock               | OFF                    |
| innodb_api_enable_binlog                 | OFF                    |
| innodb_api_enable_mdl                    | OFF                    |
| innodb_api_trx_level                     | 0                      |
| innodb_autoextend_increment              | 64                     |
| innodb_autoinc_lock_mode                 | 1                      |
| innodb_buffer_pool_dump_at_shutdown      | OFF                    |
| innodb_buffer_pool_dump_now              | OFF                    |
| innodb_buffer_pool_filename              | ib_buffer_pool         |
| innodb_buffer_pool_instances             | 8                      |
| innodb_buffer_pool_load_abort            | OFF                    |
| innodb_buffer_pool_load_at_startup       | OFF                    |
| innodb_buffer_pool_load_now              | OFF                    |
| innodb_buffer_pool_size                  | 134217728              |
| innodb_change_buffer_max_size            | 25                     |
| innodb_change_buffering                  | all                    |
| innodb_checksum_algorithm                | innodb                 |
| innodb_checksums                         | ON                     |
| innodb_cmp_per_index_enabled             | OFF                    |
| innodb_commit_concurrency                | 0                      |
| innodb_compression_failure_threshold_pct | 5                      |
| innodb_compression_level                 | 6                      |
| innodb_compression_pad_pct_max           | 50                     |
| innodb_concurrency_tickets               | 5000                   |
| innodb_data_file_path                    | ibdata1:12M:autoextend |
| innodb_data_home_dir                     |                        |
| innodb_disable_sort_file_cache           | OFF                    |
| innodb_doublewrite                       | ON                     |
| innodb_fast_shutdown                     | 1                      |
| innodb_file_format                       | Antelope               |
| innodb_file_format_check                 | ON                     |
| innodb_file_format_max                   | Antelope               |
| innodb_file_per_table                    | ON                     |
| innodb_flush_log_at_timeout              | 1                      |
| innodb_flush_log_at_trx_commit           | 1                      |
| innodb_flush_method                      |                        |
| innodb_flush_neighbors                   | 1                      |
| innodb_flushing_avg_loops                | 30                     |
| innodb_force_load_corrupted              | OFF                    |
| innodb_force_recovery                    | 0                      |
| innodb_ft_aux_table                      |                        |
| innodb_ft_cache_size                     | 8000000                |
| innodb_ft_enable_diag_print              | OFF                    |
| innodb_ft_enable_stopword                | ON                     |
| innodb_ft_max_token_size                 | 84                     |
| innodb_ft_min_token_size                 | 3                      |
| innodb_ft_num_word_optimize              | 2000                   |
| innodb_ft_result_cache_limit             | 2000000000             |
| innodb_ft_server_stopword_table          |                        |
| innodb_ft_sort_pll_degree                | 2                      |
| innodb_ft_total_cache_size               | 640000000              |
| innodb_ft_user_stopword_table            |                        |
| innodb_io_capacity                       | 200                    |
| innodb_io_capacity_max                   | 2000                   |
| innodb_large_prefix                      | OFF                    |
| innodb_lock_wait_timeout                 | 50                     |
| innodb_locks_unsafe_for_binlog           | OFF                    |
| innodb_log_buffer_size                   | 8388608                |
| innodb_log_compressed_pages              | ON                     |
| innodb_log_file_size                     | 50331648               |
| innodb_log_files_in_group                | 2                      |
| innodb_log_group_home_dir                | ./                     |
| innodb_lru_scan_depth                    | 1024                   |
| innodb_max_dirty_pages_pct               | 75                     |
| innodb_max_dirty_pages_pct_lwm           | 0                      |
| innodb_max_purge_lag                     | 0                      |
| innodb_max_purge_lag_delay               | 0                      |
| innodb_mirrored_log_groups               | 1                      |
| innodb_monitor_disable                   |                        |
| innodb_monitor_enable                    |                        |
| innodb_monitor_reset                     |                        |
| innodb_monitor_reset_all                 |                        |
| innodb_old_blocks_pct                    | 37                     |
| innodb_old_blocks_time                   | 1000                   |
| innodb_online_alter_log_max_size         | 134217728              |
| innodb_open_files                        | 2000                   |
| innodb_optimize_fulltext_only            | OFF                    |
| innodb_page_size                         | 16384                  |
| innodb_print_all_deadlocks               | OFF                    |
| innodb_purge_batch_size                  | 300                    |
| innodb_purge_threads                     | 1                      |
| innodb_random_read_ahead                 | OFF                    |
| innodb_read_ahead_threshold              | 56                     |
| innodb_read_io_threads                   | 4                      |
| innodb_read_only                         | OFF                    |
| innodb_replication_delay                 | 0                      |
| innodb_rollback_on_timeout               | OFF                    |
| innodb_rollback_segments                 | 128                    |
| innodb_sort_buffer_size                  | 1048576                |
| innodb_spin_wait_delay                   | 6                      |
| innodb_stats_auto_recalc                 | ON                     |
| innodb_stats_method                      | nulls_equal            |
| innodb_stats_on_metadata                 | OFF                    |
| innodb_stats_persistent                  | ON                     |
| innodb_stats_persistent_sample_pages     | 100                    |
| innodb_stats_sample_pages                | 100                    |
| innodb_stats_transient_sample_pages      | 100                    |
| innodb_status_output                     | OFF                    |
| innodb_status_output_locks               | OFF                    |
| innodb_strict_mode                       | OFF                    |
| innodb_support_xa                        | ON                     |
| innodb_sync_array_size                   | 1                      |
| innodb_sync_spin_loops                   | 30                     |
| innodb_table_locks                       | ON                     |
| innodb_thread_concurrency                | 0                      |
| innodb_thread_sleep_delay                | 10000                  |
| innodb_undo_directory                    | .                      |
| innodb_undo_logs                         | 128                    |
| innodb_undo_tablespaces                  | 0                      |
| innodb_use_native_aio                    | ON                     |
| innodb_use_sys_malloc                    | ON                     |
| innodb_version                           | 5.6.19                 |
| innodb_write_io_threads                  | 4                      |
+------------------------------------------+------------------------+
119 rows in set (0.00 sec)
[7 Oct 2014 21:49] Miguel Solorzano
C:\dbs>c:\dbs\5.6\bin\mysql -uroot --port=3560 --debug-info --prompt="mysql 5.6 > "
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.6.22 Source distribution

Copyright (c) 2000, 2014, Oracle and/or its affiliates. All rights reserved.

Oracle is a registered trademark of Oracle Corporation and/or its
affiliates. Other names may be trademarks of their respective
owners.

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql 5.6 > CREATE DATABASE h;
Query OK, 1 row affected (0.01 sec)

mysql 5.6 > use h
Database changed
mysql 5.6 > CREATE TABLE t1 (id int(11) NOT NULL AUTO_INCREMENT, name varchar(255) NOT NULL, t2_id int(11) NOT NULL, PRIMARY KEY (id)) ENGINE=InnoDB DEFAULT CHARSET=utf8;
Query OK, 0 rows affected (0.27 sec)

mysql 5.6 > CREATE TABLE t2 (id int(11) NOT NULL AUTO_INCREMENT, name varchar(255) NOT NULL, PRIMARY KEY (id)) ENGINE=InnoDB DEFAULT CHARSET=utf8;
Query OK, 0 rows affected (0.23 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.03 sec)

mysql 5.6 > INSERT INTO t1 (name, t2_id) VALUES ('large table', 1);
Query OK, 1 row affected (0.02 sec)

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 1 row affected (0.02 sec)
Records: 1  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 2 rows affected (0.05 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 4 rows affected (0.03 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 8 rows affected (0.02 sec)
Records: 8  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 16 rows affected (0.03 sec)
Records: 16  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 32 rows affected (0.02 sec)
Records: 32  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 64 rows affected (0.06 sec)
Records: 64  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 128 rows affected (0.03 sec)
Records: 128  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 256 rows affected (0.06 sec)
Records: 256  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 512 rows affected (0.17 sec)
Records: 512  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 1024 rows affected (0.16 sec)
Records: 1024  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 2048 rows affected (0.23 sec)
Records: 2048  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 4096 rows affected (0.45 sec)
Records: 4096  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 8192 rows affected (0.91 sec)
Records: 8192  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 16384 rows affected (0.28 sec)
Records: 16384  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 32768 rows affected (0.80 sec)
Records: 32768  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 65536 rows affected (1.33 sec)
Records: 65536  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 131072 rows affected (2.33 sec)
Records: 131072  Duplicates: 0  Warnings: 0

mysql 5.6 > SELECT t1.id, t1.name, t2.id, t2.name FROM t1, t2 WHERE t1.t2_id=t2.id ORDER BY t1.id LIMIT 0,10;
+----+-------------+----+-------------+
| id | name        | id | name        |
+----+-------------+----+-------------+
|  1 | large table |  1 | small table |
|  2 | large table |  1 | small table |
|  3 | large table |  1 | small table |
|  4 | large table |  1 | small table |
|  6 | large table |  1 | small table |
|  7 | large table |  1 | small table |
|  8 | large table |  1 | small table |
|  9 | large table |  1 | small table |
| 13 | large table |  1 | small table |
| 14 | large table |  1 | small table |
+----+-------------+----+-------------+
10 rows in set (0.53 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.03 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.05 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.05 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.03 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.05 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.03 sec)

mysql 5.6 > SELECT t1.id, t1.name, t2.id, t2.name FROM t1, t2 WHERE t1.t2_id=t2.id ORDER BY t1.id LIMIT 0,10;
+----+-------------+----+-------------+
| id | name        | id | name        |
+----+-------------+----+-------------+
|  1 | large table |  1 | small table |
|  2 | large table |  1 | small table |
|  3 | large table |  1 | small table |
|  4 | large table |  1 | small table |
|  6 | large table |  1 | small table |
|  7 | large table |  1 | small table |
|  8 | large table |  1 | small table |
|  9 | large table |  1 | small table |
| 13 | large table |  1 | small table |
| 14 | large table |  1 | small table |
+----+-------------+----+-------------+
10 rows in set (0.00 sec)
[7 Oct 2014 22:01] Miguel Solorzano
C:\dbs>c:\dbs\5.6\bin\mysql -uroot --port=3560 --debug-info --prompt="mysql 5.6 > "
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.6.22 Source distribution

Copyright (c) 2000, 2014, Oracle and/or its affiliates. All rights reserved.

Oracle is a registered trademark of Oracle Corporation and/or its
affiliates. Other names may be trademarks of their respective
owners.

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql 5.6 > CREATE DATABASE q;
Query OK, 1 row affected (0.00 sec)

mysql 5.6 > USE q
Database changed
mysql 5.6 > CREATE TABLE t1 (id int(11) NOT NULL AUTO_INCREMENT, name varchar(255) NOT NULL, t2_id int(11) NOT NULL, PRIMARY KEY (id)) ENGINE=InnoDB DEFAULT CHARSET=utf8;
Query OK, 0 rows affected (0.37 sec)

mysql 5.6 > CREATE TABLE t2 (id int(11) NOT NULL AUTO_INCREMENT, name varchar(255) NOT NULL, PRIMARY KEY (id)) ENGINE=InnoDB DEFAULT CHARSET=utf8;
Query OK, 0 rows affected (0.34 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.04 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.03 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.03 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.05 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.03 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.03 sec)

mysql 5.6 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.03 sec)

mysql 5.6 > INSERT INTO t1 (name, t2_id) VALUES ('large table', 1);
Query OK, 1 row affected (0.03 sec)

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 1 row affected (0.02 sec)
Records: 1  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 2 rows affected (0.08 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 4 rows affected (0.04 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 8 rows affected (0.03 sec)
Records: 8  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 16 rows affected (0.03 sec)
Records: 16  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 32 rows affected (0.02 sec)
Records: 32  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 64 rows affected (0.02 sec)
Records: 64  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 128 rows affected (0.04 sec)
Records: 128  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 256 rows affected (0.06 sec)
Records: 256  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 512 rows affected (0.15 sec)
Records: 512  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 1024 rows affected (0.13 sec)
Records: 1024  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 2048 rows affected (0.21 sec)
Records: 2048  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 4096 rows affected (0.37 sec)
Records: 4096  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 8192 rows affected (1.05 sec)
Records: 8192  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 16384 rows affected (0.25 sec)
Records: 16384  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 32768 rows affected (0.97 sec)
Records: 32768  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 65536 rows affected (1.15 sec)
Records: 65536  Duplicates: 0  Warnings: 0

mysql 5.6 > INSERT INTO t1 (name, t2_id) (SELECT name, t2_id FROM t1);
Query OK, 131072 rows affected (2.51 sec)
Records: 131072  Duplicates: 0  Warnings: 0

mysql 5.6 > SELECT t1.id, t1.name, t2.id, t2.name FROM t1, t2 WHERE t1.t2_id=t2.id ORDER BY t1.id LIMIT 0,10;
+----+-------------+----+-------------+
| id | name        | id | name        |
+----+-------------+----+-------------+
|  1 | large table |  1 | small table |
|  2 | large table |  1 | small table |
|  3 | large table |  1 | small table |
|  4 | large table |  1 | small table |
|  6 | large table |  1 | small table |
|  7 | large table |  1 | small table |
|  8 | large table |  1 | small table |
|  9 | large table |  1 | small table |
| 13 | large table |  1 | small table |
| 14 | large table |  1 | small table |
+----+-------------+----+-------------+
10 rows in set (0.00 sec)

mysql 5.6 > delete from t2 where id >= 2;
Query OK, 6 rows affected (0.02 sec)

mysql 5.6 > SELECT t1.id, t1.name, t2.id, t2.name FROM t1, t2 WHERE t1.t2_id=t2.id ORDER BY t1.id LIMIT 0,10;
+----+-------------+----+-------------+
| id | name        | id | name        |
+----+-------------+----+-------------+
|  1 | large table |  1 | small table |
|  2 | large table |  1 | small table |
|  3 | large table |  1 | small table |
|  4 | large table |  1 | small table |
|  6 | large table |  1 | small table |
|  7 | large table |  1 | small table |
|  8 | large table |  1 | small table |
|  9 | large table |  1 | small table |
| 13 | large table |  1 | small table |
| 14 | large table |  1 | small table |
+----+-------------+----+-------------+
10 rows in set (0.55 sec)
[7 Oct 2014 22:07] Miguel Solorzano
Same behavior since 5.1:

mysql 5.1 > SELECT t1.id, t1.name, t2.id, t2.name FROM t1, t2 WHERE t1.t2_id=t2.id ORDER BY t1.id LIMIT 0,10;
+----+-------------+----+-------------+
| id | name        | id | name        |
+----+-------------+----+-------------+
|  1 | large table |  1 | small table |
|  2 | large table |  1 | small table |
|  3 | large table |  1 | small table |
|  4 | large table |  1 | small table |
|  6 | large table |  1 | small table |
|  7 | large table |  1 | small table |
|  8 | large table |  1 | small table |
|  9 | large table |  1 | small table |
| 13 | large table |  1 | small table |
| 14 | large table |  1 | small table |
+----+-------------+----+-------------+
10 rows in set (1.65 sec)

mysql 5.1 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.05 sec)

mysql 5.1 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.03 sec)

mysql 5.1 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.03 sec)

mysql 5.1 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.02 sec)

mysql 5.1 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.01 sec)

mysql 5.1 > INSERT INTO t2 (name) VALUES ('small table');
Query OK, 1 row affected (0.03 sec)

mysql 5.1 > SELECT t1.id, t1.name, t2.id, t2.name FROM t1, t2 WHERE t1.t2_id=t2.id ORDER BY t1.id LIMIT 0,10;
+----+-------------+----+-------------+
| id | name        | id | name        |
+----+-------------+----+-------------+
|  1 | large table |  1 | small table |
|  2 | large table |  1 | small table |
|  3 | large table |  1 | small table |
|  4 | large table |  1 | small table |
|  6 | large table |  1 | small table |
|  7 | large table |  1 | small table |
|  8 | large table |  1 | small table |
|  9 | large table |  1 | small table |
| 13 | large table |  1 | small table |
| 14 | large table |  1 | small table |
+----+-------------+----+-------------+
10 rows in set (0.01 sec)

mysql 5.1 > SHOW VARIABLES LIKE "%VERSION%";
+-------------------------+---------------------+
| Variable_name           | Value               |
+-------------------------+---------------------+
| protocol_version        | 10                  |
| version                 | 5.1.74-Win X64      |
| version_comment         | Source distribution |
| version_compile_machine | unknown             |
| version_compile_os      | Win64               |
+-------------------------+---------------------+
5 rows in set (0.00 sec)

Thank you for the bug report.
[8 Oct 2014 7:45] Øystein Grøvlen
The reason the optimizer chooses a non-optimal plan is that it does not take into account that choosing join buffering will require sorting the entire result.
A work-around is to turn of join buffering.  In 5.6 you can do this with
set optimizer_switch="block_nested_loop=off'

In 5.5, I do not think there is any way to turn off join buffering, but you can use an optimizer hint to get the optimal plan: 
"... FROM t1 FORCE INDEX(PRIMARY), t2 ..."
[16 Oct 2014 19:49] Jeroen van den Hoed
Hi Miguel & Øystein, thank you for your comments. I know I could use optimizer hints, but I do not like to put that kind of logic in my applications. I will look into block_nested_loop. Are there any negative consequences to turning this variable off?

Could the behaviour of this choosen plan be changed in a coming version of mysql (without the use of hints and optimizer switches)?

Thank you, Jeroen