Optimizing JOIN on two large tables with additional ORDER BY

Question

I have two tables that are pretty large (first table 5 mio. entries, second one also about that much rows.) The first table objects has a primary key objectID My second table search has a column searchID and a column objectID which references the objectID from the objects table.

What I want to to now is, to get all objects from my objects-table, where the objectIDs are in my search table with searchID = 1 The amount of rows for searchID 1 is pretty large - about two million entries. I indexed the table with a unique key for searchID/objectID combination. The query looks like this:

SELECT *
FROM objects
JOIN search
ON search.searchID = 1
AND objects.objectID = search.objectID

this query runs pretty fast. But only as long as I dont add a ORDER BY clause to order by the name or the title in the objects table. It seems that any index does not help. Is this problem unsolvable with an index? What index would I need?

EDIT: Table structure as requested

TABLE `objects` (
  `objectID` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `title` varchar(255) NOT NULL,
  PRIMARY KEY (`objectID`),
  KEY `name` (`name`),
  KEY `title` (`title`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8

TABLE `search` (
  `searchID` int(11) NOT NULL,
  `objectID` int(11) NOT NULL,
  UNIQUE KEY `searchID` (`searchID`,`objectID`)
) ENGINE=InnoDB 

EXPLAIN with ORDER BY:

id  select_type table   type    possible_keys   key key_len ref rows    Extra
1   SIMPLE  search      ref     searchID,objectID   searchID    4   const   1014549 Using index; Using temporary; Using filesort
1   SIMPLE  objects     eq_ref  PRIMARY         PRIMARY 4   db_test.search.objectID     1   Using index

EXPLAIN without ORDER BY:

id  select_type table   type    possible_keys       key         key_len ref rows    Extra
1   SIMPLE  search      ref     searchID,contactID  searchID    4   const   1014549 Using index
1   SIMPLE  contact     eq_ref  PRIMARY             PRIMARY 4   db_test.search.objectID     1   Using index

Answer 1

First of all your query is not very correct, proper versions should be:

SELECT *
FROM objects
INNER JOIN search
ON (objects.objectID = search.objectID and search.searchID = 1)

another version:

SELECT *
FROM objects
where objects.objectID in (
    select search.objectID from search where search.searchID = 1)

They are absolutely the same from logic point of view, but I'm not sure that mysql will execute them in the same way, so test both and select fastest one

next issue about indexes:

1. Do you really need to fetch * from table, maybe you can reduce to 1/2 columns?
2. Do you really need varchar(255)? Try to reduce to actual strings length
3. Create index on objects table: INDEXNAME (SORTCOLUMN, objectid, the rest of columns)
4. Change table types to innodb,
5. Increase sort_buffer_size and join_buffer_size

Now you can change your query to one of these (test both to select fastest)

SELECT *
FROM objects use index (INDEXNAME)
INNER JOIN search
ON (objects.objectID = search.objectID and search.searchID = 1)
order by SORTCOLUMN

or

SELECT *
FROM objects use index (INDEXNAME)
where objects.objectID in (
    select search.objectID from search where search.searchID = 1)
order by SORTCOLUMN

this is what I'm getting on test db (explain extended is the same for both queries):

id  type    table   type    pk  key key_len ref                             rows    filter  Extra
1   SIMPLE  objects index       srtcol  142                                 2091427 100.00  Using index
1   SIMPLE  search  eq_ref  sid sid     5   const,testhash.objects.objectID 1       100.00  Using index

NOTE: if you need to have such long strings (varchar 255) - you can make a trick: add integer column, set it value according to proper order and make ordering and index on this column

here is my tables to test:

CREATE TABLE `objects` (
  `objectID` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `sortcol` varchar(45) DEFAULT NULL,
  PRIMARY KEY (`objectID`),
  UNIQUE KEY `srtcol` (`sortcol`,`objectID`)
) ENGINE=InnoDB AUTO_INCREMENT=2490316 DEFAULT CHARSET=utf8;

CREATE TABLE `search` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `searchID` int(10) unsigned NOT NULL,
  `objectID` int(10) unsigned NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `sid` (`searchID`,`objectID`)
) ENGINE=InnoDB AUTO_INCREMENT=2162656 DEFAULT CHARSET=utf8;

each have approximately 2m random rows