[389-devel] RFC: New Design: Fine Grained ID List Size

[Howard Chu]

Rich Megginson wrote:
> On 09/12/2013 07:08 PM, David Boreham wrote:
>> > On 9/11/2013 11:41 AM, Howard Chu wrote:
>>> >>
>>> >> Just out of curiosity, why is keeping a count per key a problem? If
>>> >> you're using BDB duplicate key support, can't you just use
>>> >> cursor->c_count() to get this? I.e., BDB already maintains key counts
>>> >> internally, why not leverage that?

>> > afaik you need to pass the DB_RECNUM flag at DB creation time to get
>> > record counting behavior, and it imposes a performance and concurrency
>> > penalty on writes. Also afaik 389DS does not set that flag except on
>> > VLV indexes (which need it, and coincidentally were the original
>> > reason for the feature being added to BDB).

> I'm using bdb 4.7 on RHEL 6.
> Looking at the code, it appears the dbc->count method for btree is
> __bamc_count() in bt_cursor.c.  I'm not sure, but it looks as though
> this function has to iterate each page counting the duplicates on each
> page, which makes it a non-starter.  Unless I'm mistaken, it doesn't
> look as though it keeps a counter on each update, then simply returns
> the counter.  I don't see any code which would make the behavior
> different depending on if DB_RECNUM is used when the database is created.

Ah totally forgot about that, it's been a couple years since I looked inside 
that code. LMDB updates record counts on every write op so returning the count 
is zero-cost. (Ironically we don't use this fact to optimize filter evaluation 
order in OpenLDAP. Probably should...) Also due to the fact that writing a 
leaf page requires every page up to the root to be updated (copy-on-write 
design), updating the counts also comes "for free" since the root page had to 
be updated anyway. (Or put another way, LMDB writes are already slow by 
design; updating the counters doesn't make them any slower.)

-- 
   -- Howard Chu
   CTO, Symas Corp.           http://www.symas.com
   Director, Highland Sun     http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP  http://www.openldap.org/project/