Índices sobre columnas VARCHAR

[dre]

Hola, estoy creando una base de datos para guardar la información de los logs de un servidor web. Hay una tabla que almacena la información para cada acceso: nº de bytes transferidos, código resultado de la operación, hora, etc... el caso es que también guardo las URL en un campo VARCHAR de tamaño 2000. Creé índices para acelerar las consultas ya que es una BD bastante gorda (ahora mismo tiene más de 43 millones de registros) y tampoco es imprescindible que haga consultas instantáneas (un retardo de un par de segundos es aceptable), pero sí es necesario que responda en un periodo de tiempo razonable. Bueno, pues para los índices sobre campos numéricos y fechas va como la seda, pero cuando consulto campos de texto como el de las urls o las ips, se comporta de una forma muy extraña incluso haciendo búsquedas casi idénticas. Por ejemplo, a esta consulta:

select * from REQUESTS where DATE_TIME>"2006-05-05 00:00:00" and DATE_TIME>"2006-05-06 00:00:00" and URL like "/index.php?pagina=%"

Responde relativamente rápido. Sin embargo, si le añado unos carácteres más al criterio de la url, de esta forma:

select * from REQUESTS where DATE_TIME>"2006-05-05 00:00:00" and DATE_TIME>"2006-05-06 00:00:00" and URL like "/index.php?pagina=noticias%"

Se queda ahí un buen rato haciendo la consulta. La tabla está definida de esta forma:

CREATE TABLE 'logs'.'REQUESTS' (
'SESSION' varchar(20) NOT NULL default '',
'DATE_TIME' datetime NOT NULL default '0000-00-00 00:00:00',
'URL' varchar(2000) NOT NULL default '',
'RETURN_CODE' smallint(5) unsigned NOT NULL default '0',
'BYTES' bigint(20) NOT NULL default '0',
'REFERRER' varchar(2000) NOT NULL default '',
KEY 'SESSIONS_ID' ('SESSION'),
KEY 'index_date' ('DATE_TIME'),
KEY 'index_url' ('URL'(1000)),
KEY 'index_referrer' ('REFERRER'(1000)),
)

Supongo que será algo relacionado con el funcionamiento interno de los índices que desconozco, pero la verdad es que no tengo ni idea, no tengo mucha experiencia en bases de datos. A ver si alguien sabe decirme algo, un saludo.