I'm using ApacheDS 2.0.0-M16. I made "cn" an index, imported my own schema and then imported a bunch of data (4000 entries) based partially on the own schema.
After importing was finished I did a number of searches. The searches for "(cn=foo)" and "(cn=foo*)" were very fast (msecs) as expected but the search for "(cn=*foo)" was very slow (seconds). Is this a known issue or can it be improved?