ldb + samdb perfs and ideas for perf improvement

[Matthieu Patou]

Hello all,

As some are already aware I started a task on performance
improvements on ldb and by side effect on samdb as well (or more
exactly on ldb_modules used by samdb).
The work in progress result of this is located at 
http://git.samba.org/mat/?p=mat/samba.git;a=shortlog;h=refs/heads/ldb_perfs
It pass make tests, there is some stuff to fix in it like checking
for null pointers retuned by talloc and also limiting the size of
the talloc_pool but you should get an idea of it. I tried and think
managed to not break ldb ABI if I did well let me know I'm pretty
sure I can work around.

I started my worked based on callgrind trace from Thomas Manniger
and continued by using a couple of python script to reproduce what I
think are typical searches, that is to say:

1) doing a search that will use a not really selective index on a
subtree that is in turn selective, thus causing the index to return
a lot of entries by the search itself not so much. This kind of
search didn't happen too often with the default provision but is
very likely to happen if you start to partition the users partition,
for instance if you have CN=<dept>,CN=Users,DC=domain,DC=tld
where dept can be sales, finances, hr, engineering, it ... and do a
search like '(objectclass=users)',
base="CN=IT,CN=Users,DC=domain,DC=tld" you will hit a not very
selective index but after you will not have a lot entries in IT
(relatively speaking to the number of total users). Based on my
experience of IT manager this is scheme is a pretty frequent one and
admins tends to think that doing search in subcontainers help the
server to do quick search (hint: it was not true).

2) doing a search that will use a not really selective index on the
DN of a partition (DC=domain,DC=tld, or
DC=Configuration,DC=domain,DC=tld, ...) with also a criteria on a
non indexed attribute (at least from ldb-tdb point of view). This
kind of search is *very* frequent in real life ie.
(&(objectclass=user)(mail=mat*)). This kind of search usually
returns not a lot of objects and not a lot of attributes.

3) doing a search that returns a lot of objects with one attribute

4) doing a basedn search returning a couple of attributes, this kind
of search is present a lot in the samdb and is not too much
influenced by indexes as (for the moment) samdb is indexed by DNs.

I've been mainly changing:

* doing the scope filtering before unpacking the object, this impact
searches like 1) and has a huge impact on performance (200%/300%
speed gain just this alone) as we don't have to unmarshall most of
the object and just talloc_free them a couple of seconds after.

* indexing (including onelevel indexing) to use DNs stored in the
case folded form already, the reason for this is that as tdb's key
are DNs in the case folded we can save quite a lot of time at search
by not doing the case folding of DNs returned by an index and just
marking them already casefolded, it requires to store the DN in a
casefolded form and offset part of the cost to the write operation
(but usually the database has much more read than writes), this has
an influence in 1), 2), and to some extent 3 but the cost of search
callbacks reduce the impact of this change

* filtering attributes not needed for the search criteria or for the
requested attributes, so that they are not talloced to be removed
just a couple of microsecond after the complete filtering.
This impact searches 1) 2) and 4)

* reworking the operational module to avoid a double loop search to
be done on every single attribute of every single entry returned by
a search, this has an influence on search 3)

For search 1) I have 600/700% of increase with a index of 1300
objects but with only 1 object matching the scope with one
attribute, that's impressive but it's definitely not the most
frequent query.
For search 2) I have 500/550% of increase with an index of 1300
objects but with only 1 object with criteria on indexed attribute
and a non indexed criteria
For search 3) I have 100%/130% of increase
For search 4) I have 100%/130% of increase

I have also achieved a ~20% improvement on make test TESTS=samba4 (tests 
that can be impacted ihmo by improvements in ldb/dsdb) with some very 
long tests like samba4.rpc.samr.large-dc.two or 
samba4.ldap.secdesc.python  being improved from 30% to 50%.

Thomas, can you try those patches but not on the database you have in 
production, before doing test performance you have to reindex the 
database so that the new indexing scheme is used (for the moment 
no-autoupgrade): samba-tool dbcheck --reindex

Matthieu.