MDB indices operations (MIT Kerberos with OpenLDAP backend)

[Дилян Палаузов <dpa-openldap@aegee.org>]

Hello,

https://www.openldap.org/software/man.cgi?query=slapd-mdb&apropos=0&sektion=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.

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 one index
on "first objectClass, then krbPrincipal"?

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).

Regards
  Дилян