ldb + samdb perfs and ideas for perf improvement

[simo]

On Mon, 2013-01-07 at 00:22 -0800, Matthieu Patou wrote:
> 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

A few q.s about patches

In ldb_compare_base_one you use this function:
get_num_char_uptoposition() that does not skip escaped chars, so if you
have a \, you might count it as one component when in fact there is
none.
I guess the point is that if they have *more* text then it already is at
least one level, well that would be true if the 'optimization' weren't
buggy in the first place.

You could have attrname=foo,dc=bar and name=foo,dc=bar as the 2 DNs, and
this function would return the wrong answer. It would tell you they have
the same base when in fact they do not. We should fix that not build on
this error to also return that there is one more component and match a
onelevel that does not exist.

What signatures 'changed' in "ldb: increase version due to signature
changes" ?
Also you increase the version again a few patches later, please increase
it once only, if really necessary.

In general I like the direction you are going, but haven't had time to
finely inspect all patches yet.

Simo.

-- 
Simo Sorce
Samba Team GPL Compliance Officer <simo at samba.org>
Principal Software Engineer at Red Hat, Inc. <simo at redhat.com>