Searching fileds using LIKE in tables with more than 500000 records.

I'm performing some tests on a big database.
This is the table I'm currently testing.

CREATE TABLE `subscribers` (
  `subscriber_id` int(11) NOT NULL auto_increment,
  `client_id` int(11) NOT NULL,
  `subscriber_fname` varchar(64) default NULL,
  `subscriber_lname` varchar(64) default NULL,
  `subscriber_email` varchar(128) default NULL,
  `subscriber_newsletters` text,
  `subscriber_date` datetime default NULL,
  PRIMARY KEY  (`subscriber_id`),
  KEY `subscriber_email` (`subscriber_email`),
  KEY `subscriber_fname` (`subscriber_fname`),
  KEY `subscriber_lname` (`subscriber_lname`)
)

The 3 fields I need to sort by are indexed.
I have imported 540000 randomly generated records. All emails look like this: "somerandomstring@mydomain.com"
I'm working on a search form and I'm searching the email field using LIKE. The problem is that I'm getting extremely different time depending on what I'm searching for.

Here are some examples:

SELECT *
FROM `subscribers`
WHERE `subscriber_email` LIKE '%mydomain.com%'
LIMIT 0 , 100

Showing rows 0 - 99 (100 total, Query took 0.0014 sec)

--------------------

SELECT *
FROM subscribers
WHERE `subscriber_email` LIKE '%fa11d41aa4%'
LIMIT 0 , 100

Showing rows 0 - 24 (25 total, Query took 2.4643 sec)

--------------------

SELECT subscriber_fname, subscriber_lname, subscriber_email, client_id, subscriber_id
FROM subscribers
WHERE subscriber_email LIKE "%mydomain.com%"
ORDER BY subscriber_fname ASC
LIMIT 0 , 100

Showing rows 0 - 99 (100 total, Query took 0.0018 sec)

--------------------

SELECT subscriber_fname, subscriber_lname, subscriber_email, client_id, subscriber_id
FROM subscribers
WHERE subscriber_email LIKE "%fa11d41aa4%"
ORDER BY subscriber_fname ASC
LIMIT 0 , 100

There are 25 rows corresponding to this query (fa11d41aa4@mydomain.com) - the query does not execute in 30 sec.
--------------------

SELECT *
FROM subscribers
WHERE `subscriber_email` LIKE '%nonexistingstring%'
LIMIT 0 , 100

MySQL returned an empty result set (i.e. zero rows). (Query took 2.2848 sec)
--------------------

I wonder why the execution time is so different depending on what I'm searching.

Thank youStart Free Trial