Hello Quanah,

thanks for your answer.

Does a mdb_equality_candidates log message mean, that adding indices will improve the search?

The particular use-case is the OpenLDAP backend of MIT Kerberos and the indices it needs for this query, as discussed at https://github.com/krb5/krb5/pull/974#issuecomment-531167854. The debug output of OpenLDAP, when there is no objectClass eq index, but a krbPrincipal eq index, is:

Sep 13 09:09:03 mail slapd[14296]: 5d7b5caf conn=1117 op=7 SRCH base="cn=X.NET,cn=krbContainer" scope=2 deref=0 filter="(&(|(objectClass=krbPrincipalAux)(objectClass=krbPrincipal))(krbPrincipalName=krbtgt/X.NET@X.NET))" Sep 13 09:09:03 mail slapd[14296]: 5d7b5caf conn=1117 op=7 SRCH attr=krbprincipalname krbcanonicalname objectclass krbprincipalkey krbmaxrenewable age krbmaxticketlife krbticketflags krbprincipalexpiration krbticketpolicyreference krbUpEnabled krbpwdpolicyreference krbpasswordexpiration krbLastFailedAuth krbLoginFailedCount krbLastSuccessfulAuth krbLastPwdChange krbLastAdminUnlock krbPrincipalAuthInd krbExtraData krbObjectReferences krbAllowedToDelegateTo krbPwdHistory Sep 13 09:09:03 mail slapd[14296]: 5d7b5caf <= mdb_equality_candidates: (objectClass) not indexed Sep 13 09:09:03 mail slapd[14296]: 5d7b5caf conn=1117 op=7 SEARCH RESULT tag=101 err=0 nentries=1 text=

Does it need one index on objectClass, one index on krbPrincipal, or both?

If no mdb_candidate output can be triggered, does it mean, that creating an index is pointless?

Moreover, it is not clear when changing the oldDbIndex on a database regenerates the index, and when running slapindex is necessary.

My reading of https://www.openldap.org/doc/admin24/tuning.html , Section 21.3.2. “What to watch out for”, is that the output “mdb_equality_candidates” means inefficient searches.

But a different interpretation is possible:

This equality_candidates may be targeted at the simple case, where the search filter is just one equality test, and where an index could significantly reduce the number of candidates to be loaded and checked. For a krb5 LDAP KDB get_principal operation, the filter expression is (&(|(objectclass=krbprincipalaux)(objectclass=krbprincipal))(krbprincipalname=...)), so the objectClass equality test is intersected with a krbPrincipalName equality test.

If the Kerberos LDAP DB is large and isn't shared with a lot of other LDAP data, almost every object in the database will match one of the objectClass equality tests, but only one will match the krbPrincipalName test. In that scenario, an objectClass index is useless, as it doesn't reduce the number of candidates significantly, while the krbPrincipalName index is useful. In fact, it is possible for the objectClass index to slow down the search, relative to having only a krbPrincipalName index--slapd might have to read in a large list of krbprincipal objects, then intersect that with a one-element list of objects matching the krbPrincipalName. While that would be much faster than loading and checking every principal object, it would still be O(n) in space and time rather than O(1).

On Thu, 2019-09-19 at 09:23 -0700, Quanah Gibson-Mount wrote:

--On Wednesday, September 18, 2019 2:41 PM +0000 Дилян Палаузов dpa-openldap@aegee.org wrote:

...

Hello,

https://www.openldap.org/software/man.cgi?query=slapd-mdb&apropos=0&... on=0&manpath=OpenLDAP+2.4-Release&format=html (man slapd-mdb) is not clear about indices.

Is olcDbIndex A eq olcDbIndex B eq the same as olcDbIndex A,B eq and is the latter the same as oldDbIndex B,A eq ? In the SQL word these are different things and while Postgresql is supposed to handle "index A,B" and "index B,A" as equivalent, it does not, so a query has to be tuned to make use of existing indices.

LDAP is not SQL.

All of these are equivalent:

index A eq index B eq

OR

index A,B eq

OR

index B,A eq

OR

index default eq index A index B

OR

index default eq index A,B

OR

index default eq index B,A

In all of the above cases, "A" will have an equality index created for that attribute, and "B" wil have an equality index created for that attribute. There are is no concept of "combined" indices for two attributes.

--Quanah

--

Quanah Gibson-Mount Product Architect Symas Corporation Packaged, certified, and supported LDAP solutions powered by OpenLDAP: http://www.symas.com