A search for "(uid=12345)" on basedn "dc=example,dc=com" with a subtree scope returns much more quickly than the same filter and scope on basedn "ou=People,dc=example,dc=com".

To confirm this wasn't just a problem with my schema or configuration, I loaded Ubuntu 18 (slapd 2.4.45+dfsg-1ubuntu1), used ldctl to generate 100,000 inetOrgPerson records with uids from 00000 to 99999, loaded them in with ldapadd, then used ldctl to test performance of searches:

Both tests were scope subtree, 20 seconds, hitting the test server as fast as possible with randomly generated filters of "(uid=<random uid from 00000 to 99999>)".

basedn: dc=example,dc=com - 5455.30/sec - total: 109106 successful searches

basedn: ou=People,dc=example,dc=com - 198.80/sec - total: 3976 successful searches

Also, while testing against ou=People, the CPU load from slaps went through the roof.  It feels rather like the index isn’t being used when the base isn’t the root.  

I can provide the ldif of my test users and the parameters I used for ldctl tests if desired.

Thanks for any help you can offer,

Matthew