Подскажите, как оптимизировать поиск по полю VARCHAR(25)
Имеется таблица parts
 
CREATE TABLE `parts` (
  `id` int(11) NOT NULL auto_increment,
  `sclad` int(11) NOT NULL default '0',
  `code` varchar(25) NOT NULL,
  `cros` varchar(25) default NULL,
  `price` float NOT NULL,
  `count` int(11) NOT NULL default '1',
  `date` timestamp NOT NULL default CURRENT_TIMESTAMP on update CURRENT_TIMESTAMP,
  PRIMARY KEY  (`id`),
  KEY `sclad` (`sclad`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8
Записей порядка 2млн.
И таблица 
sclad CREATE TABLE IF NOT EXISTS `sclad` (
  `id` int(11) NOT NULL auto_increment,
  `title` varchar(255) NOT NULL,
  `address` text,
  `deliv` varchar(40) NOT NULL default '0',
  `sumdeliv` varchar(50) NOT NULL default '0',
  `notvisible` int(11) NOT NULL default '0',
  PRIMARY KEY  (`id`),
) ENGINE=InnoDB  DEFAULT CHARSET=utf8
Осуществляется поиск с присоединением доп. таблицы: 
SELECT 
 `parts`.`id`,
 `parts`.`sclad`,
 `parts`.`code`,
 `parts`.`cros`,  
 `parts`.`price`,
 `parts`.`count`,
 `sclad`.`title` `sclad`,
 `sclad`.`deliv`,
 `sclad`.`sumdeliv` 
FROM `parts` INNER JOIN `sclad` 
ON (`parts`.`sclad` = `sclad`.`id`) 
WHERE (`parts`.`cros` IN ('CODE_1',...,'CONE_N') OR `parts`.`code` IN ('CODE_1',...,'CONE_N') OR `parts`.`cros`='CONE_C') AND `sclad`.`notvisible`=0  ORDER BY `parts`.`price` DESC LIMIT 500
где 'CODE_1',...,'CONE_N' - искомые ключи
количество ключей может быть от одного до 20
поиск по 5 ключам проходит за время 5 сек.
поиск по 15 ключам проходит за время 9 сек.
мне и заказчику это кажется плохим результатом
подскажите, как можно ускорить?