1) Никогда не пиши SELECT *. Перечисляй все имена полей
2) Построй индекс по полю, по которому ищешь

3) Используй полнотекстовый индекс
4) Если структура данных позволяет, откажись от поиска LIKE и делай вместо этого поиск по полю int.
Пример:
Имеем таблицу c записями о том, какие платежи поступали от покупателей
CREATE TABLE payments
(
id int not null auto_increment,
name varchar(255),
amount int,
primary key(id)
);
INSERT INTO payments(name, amount) VALUES ('Ivan', '1200');
INSERT INTO payments(name, amount) VALUES ('Peter', '800');
INSERT INTO payments(name, amount) VALUES ('Boris', '1600');
INSERT INTO payments(name, amount) VALUES ('Ivan', '5600');
Вместо поиска типа
SELECT * FROM payments WHERE name = 'Ivan';
Сделать:
CREATE TABLE users
(
id int not null auto_increment,
name varchar(255),
primary key(id)
);
INSERT INTO users(name) VALUES ('Ivan');
INSERT INTO users(name) VALUES ('Peter');
INSERT INTO users(name) VALUES ('Boris');

CREATE TABLE payments
(
id int not null auto_increment,
user_id int not null,
amount int,
primary key(id)
);
INSERT INTO payments(user_id, amount) VALUES (1, '1200');
INSERT INTO payments(user_id, amount) VALUES (2, '800');
INSERT INTO payments(user_id, amount) VALUES (3, '1600');
INSERT INTO payments(user_id, amount) VALUES (1, '5600');

И выбирать
SELECT * FROM payments WHERE user_id = '1';

Нет, это абсолютно разные вещи.