How to break table into two without losing performance?
OPTION #1 : Use INT UNSIGNED instead of BIGINT

If the fields will not exceed 4,294,967,295, change them to INT UNSIGNED

ALTER TABLE part1
    MODIFY COLUMN id     INT UNSIGNED NOT NULL AUTO_INCREMENT,
    MODIFY COLUMN first  INT UNSIGNED NOT NULL,
    MODIFY COLUMN second INT UNSIGNED NOT NULL;
ALTER TABLE part2
    MODIFY COLUMN link  INT UNSIGNED NOT NULL,
    MODIFY COLUMN third INT UNSIGNED NOT NULL;


Smaller datatypes, especially for JOIN keys, will make the same query go faster.

If the fields will not exceed 16,777,215, useMEDIUMINT UNSIGNED for even smaller columns.

OPTION #2 : Use a Bigger Join Buffer

Add this to my.cnf

[mysqld]
join_buffer_size = 16M


Then, login to MySQL and run

mysql&gt; SET GLOBAL join_buffer_size = 1024 * 1024 * 16;


MySQL restart not needed.

See MySQL Documentation about join_buffer_size

OPTION #3 : Make sure link is indexed

Since you have a FOREIGN KEY reference, this is a rather moot point. If you do not have the FOREIGN KEY, make sure link is indexed:

ALTER TABLE part2 ADD UNIQUE KEY (link);


Give it a Try !!!

UPDATE 2014-08-22 17:13 EDT

I created my own version of the Sample Data using this:

DROP DATABASE IF EXISTS GILI; CREATE DATABASE GILI;
USE GILI
create table original 
(
    id mediumint unsigned not null auto_increment,
    first mediumint unsigned not null,
    second mediumint unsigned not null,
    third mediumint unsigned not null,
    primary key (id)
);
create table part1 like original;
alter table part1 drop column third;
create table part2 select third from original;
alter table part2 add link mediumint unsigned not null first;
alter table part2 add primary key (link);
insert into original (first,second,third) values (1,2,3);
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into original (first,second,third) select first,second,third from original;
insert into part1 (id,first,second) select id,first,second from original;
insert into part2 (link,third) select id,third from original;
select count(1) from (select * from original) A;
select count(1) from (select * from part1 inner join part2 on part1.id = part2.link) A;


Results are roughly the same as yours: About 3x's slower. The, I read your stackoverflow link. Then I got to thinking: Look at the sample we used. We basically pushed MySQL to its limit to join 1M rows with 1M rows. This is the worst-case equi-join scenario. All things considered, the performance is pretty good.

I remember my college days where I had to create a two-dimensional array using linked lists to construct a sparse array. If a node did not exist in a particular coordinate, the default value for the array was defined as zero in the app. Then, imagine this. Creating a 1000x1000 sparse array where all 1000000 (1 million) coordinates had a nonzero value represented. Now, you had at least 2.002 million pointers mapping all adjacent nodes. This is in additional to the 1 million 4-byte integers for the data. Fetching a single value out of it required more CPU for navigation than the retrieval of the actual data.

Doing a INNER JOIN of 1M rows from part1 to part2 where part2 has absolutely every key requires more resources for navigation (temp table creation, key comparison, value population). Denormalizing can sometimes be demorializing if the right side of a LEFT JOIN isn't very sparse or the left side of the LEFT JOIN is huge. In your case, separating the original into part1 and part2 buys you nothing if they have to be frequently referenced together and in bulk. In other words, separating columns that do not form repeating groups isn't true normalization.

The 3 options I gave would do a world of good for part1 and fetching part2 on a row by row basis.

Think about the following cases:


you only need some of the rows from part1

do you trust the MySQL Query Optimizer
do you refactor the query to get a cross section to part1 before joining to part2 ?
do you retrieve from part2 only one row at a time ?

Using a LEFT JOIN and learning there is no part2 for a given part1

set default value in the app for part2 ?
populate part2 for that part1 ?



Giving more consideration to how you plan to retrieve data, how much data you need in a single query, and how you structure the query will become the determining factor as your seek good performance.

EPILOGUE

You are not going to get better performance because of the cost to make the JOIN happen. It's like trying to turn lead into gold (Theoretically possible, practically and financially impossible).

Your best bet is to leave the table in its original state.