https://bugs.openldap.org/show_bug.cgi?id=10526
--- Comment #10 from Carsten Höger choeger@open-xchange.com ---
Howard, thank you very much to take my report into account even though your policy prohibits AI generated reports! This issue is serious for us and working around it is painful and expensive.
(In reply to Howard Chu from comment #9)
Created attachment 1161 [details] Benchmark original vs binary search
Using your test as a starting point. This program first just generates the data 200000 times, to get a baseline cost of data generation. Only the case of two lists is being timed.
Then it times both the mdb_idl_intersection_orig and the mdb_idl_intersection_fixed. The _fixed version, using binary search, is slower.
You can also specify the number of iterations and seed as arguments, if desired.
The fix works at least in our environment (reduces load by factors, see graphs).
I confronted Claude with your analysis and here's the response:
------------------------------------------------------------------------------
Thanks for benchmarking it. Agreed -- for two comparably sized lists the binary-search merge is a net loss (I measure ~2.5x slower than the linear merge here as well), so that half should be dropped. It was a "while I'm here" change and doesn't pay for itself.
That benchmark only exercises list INT list, though; the reported case is list INT range, which it never constructs. In the original report objectClass=<value> matches ~2,000,000 entries, so that term is stored as a range, and the slow filter intersects the small almost_uniqe list against it. When the range does not fully cover the list (the non-matching member's ID lies outside [first,last], so the "range completely covers the list" shortcut is missed), the generic merge iterates the *range* one ID at a time via mdb_idl_next across the whole gap. With the two IDs ~972k apart that is ~10^6 mdb_idl_next calls per search:
almost_uniqe{1759457,2731413} INT objectClass range[1..2731412], 1200 searches: original: 1.52 s, 1.17e9 mdb_idl_next calls range trim: 0.00 s, 1.20e3 mdb_idl_next calls
That is the list-vs-range trim already present in your _fixed. So the minimal change is just that branch, with the linear list INT list merge left exactly as it is -- no change to the path the benchmark covers. Patch below (also attached). Cross-checked against brute-force set intersection over 400k randomized list/range trials in both argument orders: no mismatches.
--- a/servers/slapd/back-mdb/idl.c +++ b/servers/slapd/back-mdb/idl.c @@ -750,12 +750,24 @@ } }
- /* If a range completely covers the list, the result is - * just the list. + /* If b is a range, the intersection is just the elements of list a + * that fall within the range bounds. Never iterate the range itself: + * doing so walks one ID at a time across the whole [first,last] span, + * which is O(range width) rather than O(|a|). */ - if ( MDB_IDL_IS_RANGE( b ) - && MDB_IDL_RANGE_FIRST( b ) <= MDB_IDL_FIRST( a ) - && MDB_IDL_RANGE_LAST( b ) >= MDB_IDL_LLAST( a ) ) { + if ( MDB_IDL_IS_RANGE( b ) ) { + idmin = MDB_IDL_RANGE_FIRST( b ); + idmax = MDB_IDL_RANGE_LAST( b ); + if ( idmin <= MDB_IDL_FIRST( a ) && idmax >= MDB_IDL_LLAST( a ) ) + goto done; /* range completely covers the list */ + cursorc = 0; + cursora = idmin; + ida = mdb_idl_first( a, &cursora ); + while ( ida <= idmax ) { + a[++cursorc] = ida; + ida = mdb_idl_next( a, &cursora ); + } + a[0] = cursorc; goto done; }