agilizar busqueda en bd paradox

[solrak]

tengo aprox 40 tablas paradox de mas de 2 millones de registros, utilizo DBE, delphi 7, la cuestion es si alguien tiene sugerencias de como agilizar las busquedas, ya que en 10 tablas utilizando un query para cada una y haciendo una consulta comun select * form tabla where nombre=valor and paterno=valor and materno=valor tarda aprox 6 minutos (nota uso select * porque necesito mostrar todos los campos)