Below worked for me:
Stop slapd:
$ sudo /etc/init.d/slapd stop
Modify config to include additional indexes
$ sudo nano /etc/ldap/slapd.d/cn\=config/olcDatabase\=\{1\}hdb.ldif
Find
olcDbIndex: objectclass eq
olcDbIndex: entryCSN eq
olcDbIndex: entryUUID eq
olcDbIndex: uid eq
olcDbIndex: memberUid eq
Replace with
olcDbIndex: objectClass eq,pres
olcDbIndex: ou,cn,sn,mail,givenname eq,pres,sub
olcDbIndex: uidNumber,gidNumber,memberUid eq,pres
olcDbIndex: loginShell eq,pres
olcDbIndex: uniqueMember eq,pres
olcDbIndex: uid pres,sub,eq
olcDbIndex: displayName pres,sub,eq
olcDbIndex: sambaSID eq
olcDbIndex: sambaPrimaryGroupSID eq
olcDbIndex: sambaDomainName eq
olcDbIndex: sambaGroupType eq
olcDbIndex: sambaSIDList eq
Save.
Index:
$ sudo slapindex
WARNING!
Runnig as root!
There's a fair chance slapd will fail to start.
Check file permissions!
Fix permissions
$ sudo chown openldap:openldap -R /var/lib/ldap*
Restart slapd
$ sudo /etc/init.d/slapd start