The sudo code is pretty much the same on RHEL-7 and RHEL8, since it is quite fast on RHEL-7 I wonder if there was any change in ldb (the library that we use for cache database) that would diminish the index performance. Tomas, I think you have some internal knowledge of ldb, can you please check?
In RHEL7 we have version 1.5, in RHEL8 there is 2.6. The difference is significant but at first glance I do not see any obvious reasons why it is slower. In 2.6 is an option that allows to increase in-memory cache for indexes and that may help during update (it does not explain why it is so much slower now) but the commit message mentions huge performance penalty if the cache is small and hence not used. Unfortunately there is no way to set this option in SSSD configuration currently. I may run some experiments if we obtain the cache files, or we can create a scratch build with this memory cache option set to higher value just for the sake of investigation.