Fwd: Regression: ldb performance with indexes

[Douglas Bagnall]

On 28/05/24 23:56, Andreas Schneider via samba-technical wrote:
> On Tuesday, 14 May 2024 16:31:53 GMT+2 Andreas Schneider via samba-technical
> wrote:
>>> Using a red black tree doesn't solve the issue:
>>>
>>> $ bash repro_dev_ldb.sh 10000 indexes
>>> RED BLACK TREE
>>> RED BLACK TREE
>>> RED BLACK TREE
>>> Added 2 records successfully
>>> RED BLACK TREE
>>> Added 10000 records successfully
>>>
>>> real    0m9.299s
>>> user    0m9.212s
>>> sys     0m0.263s
>>>
>>> https://git.samba.org/?p=asn/samba.git;a=shortlog;h=refs/heads/asn-ldb
>>
>> The thing is that those subtrees have 4 entries, with 10000 entries we walk
>> 4x10000 so 40000.
>>
>> This needs to be optimized. As dbwrap_rbt is similar to tdb we share the
>> same problems. Those could be removed if a real rbtree is used.
>>
>> So someone with more ldb knowlege should look into this. I dunno if we
>> always need all those 4 entries and are then overwriting stuff or if we
>> always traverse those 4 entries but don't have too if we found the one we
>> need.
>>
>> With two rbtrees we could just push nodes from one tree to another. It is
>> just pointer that should be fast. Allocating memory and traversing is
>> probably what makes it so extremely slow.
> 
> Andrew,
> 
> any comments?

I might be able to look at it soon.

Douglas