ldb speed

[tridge at samba.org]

Simo,

As we've discussed previously, ldb is currently way too slow. The
LOCAL-DBSPEED test is a simple way to demonstrate this - it tests both
ldb and tdb for the example of a sidmap style database (something like
what winbind_idmap.tdb currently holds). 

In LOCAL-DBSPEED compiled with optimisation, each ldb search takes
about 45 usec on my test machine. The equivalent tdb fetch takes about
8 usec. It's even worse if you factor out the system overhead of
locking. With locking disabled a tdb fetch takes about 3 usec, whereas
a ldb search takes around 40 usec.

So we're losing about 37 usec per search on
packing/unpacking/validation/dns etc in ldb. More specifically the
breakdown is roughly:

	7 usec/op in ldb_dn_explode
	8 usec/op in ldb_dn_linearize
	6 usec/op in tdb_fetch
	3 usec/op in ltdb_unpack_data
	9 usec/op in ldb_dn_string_compose
	7 usec ltdb_lock_read/ltdb_unlock_read

I think we can eliminate most of this overhead with a bit of work.

The most obvious place to start is with the DN manipulation code. If
you look at the work done in something like ldb_dn_explode() then you
should see that most of the work is not needed most of the time. The
reason is that it spends an awful lot of time and effort carefully
validating the input it has, carefully checking that attribute names
are valid, parsing potentially escaped strings etc.

This work is arguably appropriate for DNs given to us by external
users of the ldb API when we are going to store that DN in our
database, but it is not needed at all for a ldb_search() call, and is
certainly not needed when parsing a DN that is stored in our
underlying tdb.

Say that a user gave us a DN in a ldb_search() call with a invalid
atribute name as part of one component. The search will not find any
results, as our database will not contain any records with a DN that
matches, so carefully checking the DN components for validity just
isn't necessary.

Similarly, when parsing a DN from our tdb, that DN could only have
been stored in that tdb via a add operation or a DN rename operation,
so it is only necessary to validate the DN on an add or
rename. Validating it on read is pointless.

Next, we should think about the format of a DN. Originally in ldb a DN
was a char* string. This format was used both in the on-disk format
and in the API. It meant we never had to convert a DN from one format
to another. 

As I understand it, the change to the ldb_dn structure format was
needed to allow us to correctly handle some of the semantics of
ldap. Could we support all those semantics with a char* format? I
think we could.

There is a lot more room for optimisation in other parts of ldb, but
fixing the current struct ldb_dn is the main thing. I'd suggest we try
the following strategy to start with.

 1) make 'struct ldb_dn' a private structure to ldb_dn.c. Keep it in
    the API for now, but make it an opaque structure as far as the
    rest of our code is concerned. That will involve adding some
    public routines to extract properties of a 'struct ldb_dn' to
    allow us to fix up the (very few!) external bits of code that
    currently look inside a struct ldb_dn

 2) once we've made it an internal only structure, we can start
    changing its shape. It could become as simple as a 'char*'
    internally, or could retain some flags, or even a broken out array
    that gets created on demand.

 3) make sure we differentiate between callers where input needs to be
    validated and callers where it does not need validation.

Sound OK?

Cheers, Tridge