yo he solucionado problemas similares pero siempre ha sido afinando los query's o haciendo tuning, deberias publicar los querys y aca los vemos....
waiting for querys...
pero no has posteado ningun query solo has posteado la sentenceia para crear el indice...
*que base de datos usas?
*el campo ag_tlf puede repetirce en mas de una agenda?
*el campo ag_tlf necesariamente debe ser varchar2? (supongo que si pues es un telefono no?)
Hasta donde tengo entendido las consultas SELECT que devuelven todos los campos se optimizan reemplazando el "*" por el nombre de cada campo.