Re: MDB indices operations (MIT Kerberos with OpenLDAP backend)

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

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&sekti
> > 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>