Slow respons when seaching for givenname

["Jarle Tvedten" <jarle.tvedten@ttyl.com>]

Hi

I have a openldap directory containing 1000000 (1 million) entries.
I use the following lines in slapd.conf to index the directory:
index   cn,mail,sn,gn           pres,eq,sub
index objectClass               eq

One-level search using attributes cn,mail and sn is done within 2 seconds.
Search for givenname (gn=*someone) and (gn=someone) goes well(within a
couple of seconds), but search for (gn=someone*) takes very long to
complete(more than one hour).

I have tried to re-index the directory but that did not help much.
I am using openldap 2.1.3, on a Sparc machine running SunOS 5.7(2.7).

Any help would be nice.

thanks in advance,

Jarle Tvedten