Q:

Please help me optimize a mysql search query

I have a query in MySql (5.1) InnoDB that searches in a table with parts. The table with parts contains about 500 000 rows. The search also joins two other tables tblcategory and tblheadcategory. I have a lot of users using this query and it makes my server almost crasch with the heavy load.
I know that a good way would be to use full-text search for this, and I hope we can change this to use it in the future. But as that is not possible with InnoDB I need a "quick" optimization to get it running for now. How should I optimize this and setup Index and other things to get this query to run as good as possible? 
This is the query:
SELECT tblpart.partid,tblpart.title,tblcategory.category,tblheadcategory.headcategory

FROM tblpart

INNER JOIN tblcategory ON tblpart.categoryid = tblcategory.categoryid
INNER JOIN tblheadcategory ON tblcategory.headcategoryid = tblheadcategory.headcategoryid

WHERE (tblpart.title LIKE '%bmw%' OR tblpart.description LIKE '%bmw%' OR tblpart.brand LIKE '%bmw%')

ORDER BY

tblpart.title='bmw' DESC,
tblcategory.category LIKE '%bmw%' DESC

LIMIT 50;

The tables:
CREATE TABLE `tblpart` (
    `partid` int(10) NOT NULL auto_increment,
    `userid` int(11) default '1',
    `categoryid` int(10) default '1',
    `title` varchar(100) default NULL,
    `brand` varchar(100) default NULL,
    `description` varchar(100) default NULL,
    PRIMARY KEY  (`partid`),
    KEY `userid` (`userid`),
    KEY `title` (`title`)
) ENGINE=InnoDB AUTO_INCREMENT=534007 DEFAULT CHARSET=utf8;

CREATE TABLE `tblcategory` (
    `categoryid` int(10) NOT NULL auto_increment,
    `category` varchar(255) default NULL,
    `headcategoryid` int(10) default NULL,
      PRIMARY KEY  (`categoryid`)
) ENGINE=InnoDB AUTO_INCREMENT=1261 DEFAULT CHARSET=utf8;

CREATE TABLE `tblheadcategory` (
    `headcategoryid` int(10) NOT NULL auto_increment,
    `headcategory` varchar(255) default NULL,
    PRIMARY KEY  (`headcategoryid`)
) ENGINE=InnoDB AUTO_INCREMENT=21 DEFAULT CHARSET=utf8;

EXPLAIN gives following: (Sorry, I can't figure out how to format it right)
id   select_type   table            type    possible_keys   key      key_len  ref                         rows        extra
1    SIMPLE        tblpart          ALL     NULL            NULL     NULL     NULL                        522905      Using where; Using temporary; Using filesort
1    SIMPLE        tblcategory      eq_ref  PRIMARY         PRIMARY  4        tblpart.categoryid          1
1    SIMPLE        tblheadcategory  eq_ref  PRIMARY         PRIMARY  4        tblcategory.headcategoryid  1 

UPDATE
From the suggestions I tried a FULLTEXT solution:
The new MyISAM table:
CREATE TABLE `tblpart_search` (
    `partid` int(11) NOT NULL AUTO_INCREMENT,
    `title` varchar(100) NOT NULL,
    `brand` varchar(100) DEFAULT NULL,
    `description` varchar(100) DEFAULT NULL,
    PRIMARY KEY (`partid`),
    FULLTEXT KEY `all` (`title`,`brand`,`description`)
) ENGINE=MyISAM AUTO_INCREMENT=359596 DEFAULT CHARSET=utf8;

Triggers:
DELIMITER ;;
CREATE TRIGGER `tblpart_insert_trigger` AFTER INSERT ON `tblpart` 
FOR EACH ROW INSERT INTO tblpart_search VALUES(NEW.partid,NEW.title,NEW.brand,NEW.description);;
DELIMITER ;

DELIMITER ;;
CREATE TRIGGER `tblpart_update_trigger` AFTER UPDATE ON `tblpart` 
FOR EACH ROW UPDATE tblpart_search SET tblpart_search.title=NEW.title,tblpart_search.brand=NEW.brand,tblpart_search.description=NEW.description WHERE tblpart_search.partid=NEW.partid;;
DELIMITER ;

DELIMITER ;;
CREATE TRIGGER `tblpart_delete_trigger` AFTER DELETE ON `tblpart` 
FOR EACH ROW DELETE FROM tblpart_search WHERE tblpart_search.partid=OLD.partid;;
DELIMITER ;

The new query:
SELECT tblpart.partid,tblpart.title,tblcategory.category,tblheadcategory.headcategory

FROM tblpart_search
INNER JOIN tblpart ON tblpart_search.partid = tblpart.partid
INNER JOIN tblcategory ON tblpart.categoryid = tblcategory.categoryid
INNER JOIN tblheadcategory ON tblcategory.headcategoryid = tblheadcategory.headcategoryid

WHERE MATCH (tblpart_search.title, tblpart_search.brand, tblpart_search.description) AGAINST ('bmw,car')
LIMIT 50;

A:

You cannot really optimize a query with leading wildcards (even with FULLTEXT searches).
The only thing you can do here is to split the query in three (on client side):
SELECT  tblpart.partid,tblpart.title,tblcategory.category,tblheadcategory.headcategory
FROM    tblpart
INNER JOIN
        tblcategory
ON      tblpart.categoryid = tblcategory.categoryid
INNER JOIN
        tblheadcategory
ON      tblcategory.headcategoryid = tblheadcategory.headcategoryid
WHERE   tblpart.title = 'bmw'
ORDER BY
        tblcategory.category LIKE '%bmw%' DESC
LIMIT 50

SELECT  tblpart.partid,tblpart.title,tblcategory.category,tblheadcategory.headcategory
FROM    tblpart
INNER JOIN
        tblcategory
ON      tblpart.categoryid = tblcategory.categoryid
INNER JOIN
        tblheadcategory
ON      tblcategory.headcategoryid = tblheadcategory.headcategoryid
WHERE   tblpart.title <> 'bmw'
        AND  (tblpart.title LIKE '%bmw%' OR tblpart.description LIKE '%bmw%' OR tblpart.brand LIKE '%bmw%')
        AND tblcategory.category LIKE '%bmw%'
LIMIT N

SELECT  tblpart.partid,tblpart.title,tblcategory.category,tblheadcategory.headcategory
FROM    tblpart
INNER JOIN
        tblcategory
ON      tblpart.categoryid = tblcategory.categoryid
INNER JOIN
        tblheadcategory
ON      tblcategory.headcategoryid = tblheadcategory.headcategoryid
WHERE   tblpart.title <> 'bmw'
        AND  (tblpart.title LIKE '%bmw%' OR tblpart.description LIKE '%bmw%' OR tblpart.brand LIKE '%bmw%')
        AND tblcategory.category NOT LIKE '%bmw%'
LIMIT N

and replace N in the last queries with 50 - records, where records is the number of records returned by the previous queries
The first query can be served with an index on title.
Update:
A FULLTEXT search can be implemented like this:
CREATE TABLE `tblpart_search` (
    `partid` int(11) NOT NULL AUTO_INCREMENT,
    `title` varchar(100) NOT NULL,
    `brand` varchar(100) DEFAULT NULL,
    `description` varchar(100) DEFAULT NULL,
    PRIMARY KEY (`partid`),
    FULLTEXT KEY `all` (`title`,`brand`,`description`)
) ENGINE=MyISAM AUTO_INCREMENT=359596 DEFAULT CHARSET=utf8;

Triggers:
DELIMITER ;;
CREATE TRIGGER `tblpart_insert_trigger` AFTER INSERT ON `tblpart` 
FOR EACH ROW INSERT INTO tblpart_search VALUES(NEW.partid,NEW.title,NEW.brand,NEW.description);;
DELIMITER ;

DELIMITER ;;
CREATE TRIGGER `tblpart_update_trigger` AFTER UPDATE ON `tblpart` 
FOR EACH ROW UPDATE tblpart_search SET tblpart_search.title=NEW.title,tblpart_search.brand=NEW.brand,tblpart_search.description=NEW.description WHERE tblpart_search.partid=NEW.partid;;
DELIMITER ;

DELIMITER ;;
CREATE TRIGGER `tblpart_delete_trigger` AFTER DELETE ON `tblpart` 
FOR EACH ROW DELETE FROM tblpart_search WHERE tblpart_search.partid=OLD.partid;;
DELIMITER ;

The new query:
SELECT tblpart.partid,tblpart.title,tblcategory.category,tblheadcategory.headcategory

FROM tblpart_search
INNER JOIN tblpart ON tblpart_search.partid = tblpart.partid
INNER JOIN tblcategory ON tblpart.categoryid = tblcategory.categoryid
INNER JOIN tblheadcategory ON tblcategory.headcategoryid = tblheadcategory.headcategoryid

WHERE MATCH (tblpart_search.title, tblpart_search.brand, tblpart_search.description) AGAINST ('+bmw +car' IN BOOLEAN MODE)
LIMIT 50;

Set ft_min_word_len to 3 or less so that it could index the 3-character words like 'BMW' and 'CAR'.

