https://bugs.openldap.org/show_bug.cgi?id=10526

Issue ID: 10526 Summary: back-mdb: mdb_idl_intersection is O(ID-gap), not O(n), when a short candidate list is ANDed with a range Product: OpenLDAP Version: 2.5.20 Hardware: All OS: Linux Status: UNCONFIRMED Keywords: needs_review Severity: normal Priority: --- Component: backends Assignee: bugs@openldap.org Reporter: choeger@open-xchange.com Target Milestone: ---

Created attachment 1157 --> https://bugs.openldap.org/attachment.cgi?id=1157&action=edit the patch above

---------------------------------------------------------------------------- Note

The below report including the patch has been generated by Claude Opus 4.8. I built packages based on the OpenLDAP-LTB project version v2.5.20 and verified in our problematic production deployment.

This refers to the following thread: https://lists.openldap.org/hyperkitty/list/openldap-technical@openldap.org/t...

End Note ----------------------------------------------------------------------------

SUMMARY ------- AND-filter searches can be orders of magnitude slower than the size of their result set warrants. mdb_idl_intersection() falls back to a generic element-at-a-time merge whose cost is proportional to the distance in ID space between candidate IDs, not to the number of candidates. When one operand is a range (any indexed term matching more than the IDL range threshold, e.g. a common objectClass) and the other is a short list of IDs that are widely separated, the merge walks the range one ID at a time across the entire gap.

This is common in practice: filters of the form (&(objectClass=X)(someAttr=val)...) hit it whenever someAttr matches a small number of entries whose IDs happen to be far apart and objectClass=X is stored as a range that does not fully cover that span.

ENVIRONMENT ----------- - OpenLDAP 2.5.19, slapd back-mdb. - ~4.6M entries. An attribute is indexed eq and a given value normally matches exactly one entry. A common objectClass value matches ~2,000,000 entries and is therefore stored as an IDL range (it exceeds MDB_idl_db_max; see servers/slapd/back-mdb/idl.c:467, "No room, convert to a range").

SYMPTOM ------- Query: (&(objectClass=<common>)(<almost-unique-attr>=<value>)(<attr>=*)) The filter resolves to a single entry in all cases.

- When <almost-unique-attr>=<value> matches ONE entry: the search is very fast. - When it matches TWO entries whose IDs are far apart (here 1759457 and 2731413, a gap of ~972,000), the same search becomes roughly 20x slower, even though the AND still yields a single entry.

perf shows nearly all CPU in mdb_idl_next() and mdb_idl_intersection(). Enabling LDAP_DEBUG_FILTER and inspecting the per-term candidate counts confirms the broad term is a range; gdb in mdb_idl_intersection shows idmin/idmax equal to the two widely separated IDs.

Neither index_hash64 nor dropping the substring index changes the timing; the cost is not in the index key lookups, it is in the candidate intersection.

ROOT CAUSE ---------- In servers/slapd/back-mdb/idl.c, mdb_idl_intersection() has fast paths for both-ranges, for idmin==idmax, and for "range fully covers list". Anything that misses those falls into a generic merge:

cursora = cursorb = idmin; ida = mdb_idl_first( a, &cursora ); idb = mdb_idl_first( b, &cursorb ); cursorc = 0; while( ida <= idmax || idb <= idmax ) { if( ida == idb ) { a[++cursorc] = ida; ida = mdb_idl_next( a, &cursora ); idb = mdb_idl_next( b, &cursorb ); } else if ( ida < idb ) { ida = mdb_idl_next( a, &cursora ); } else { idb = mdb_idl_next( b, &cursorb ); } }

For a range, mdb_idl_next() returns ++(*cursor), i.e. consecutive integers. So when b is a range that does not fully cover list a (the "range fully covers list" shortcut is missed because the non-matching list member lies outside the range bounds), the loop advances idb one integer at a time from idmin to idmax. With the two matches ~972,000 apart, that is ~972,000 iterations per search.

The single-match case is fast only because it lands on the idmin==idmax or "range fully covers list" shortcut; it has nothing to do with the index.

The same loop is also O(gap) for the list-vs-list case (a populous list ANDed with a short, widely-spread list): it walks the populous list across the gap.

mdb_idl_intersection() is reached for every non-first term of an AND filter via list_candidates() in servers/slapd/back-mdb/filterindex.c.

REPRODUCTION (without specific data) ------------------------------------ 1. Load a DB where some indexed attribute value V matches more than MDB_idl_db_max entries (so V is stored as a range), and where the range's [lo,hi] does not span the whole DB. 2. Pick another indexed attribute A and two entries that share a value W on A, such that one of them is NOT in V's range and their IDs are far apart. 3. Time (&(A=W)) vs (&(V)(A=W)) repeatedly. The second is dramatically slower despite returning fewer (or equal) entries.

A standalone harness that extracts the real 2.5.19 IDL routines, cross-checks a fixed mdb_idl_intersection against brute-force set intersection, and benchmarks the pathology is attached (idl_intersection_test.c).

PROPOSED FIX ------------ mdb_idl_intersection() never needs to iterate a range. After the existing "range fully covers list" shortcut:

- If b is a range, the result is just the members of list a that fall within [first,last]: iterate the (bounded) list, test each against the bounds. O(|a|) instead of O(range width).

- If both a and b are lists, keep the sorted merge but, when the cursors diverge, binary-search (mdb_idl_search) the lagging list forward to the other's current value rather than stepping one element at a time. Each catch-up becomes O(log n) instead of O(gap).

Result ordering (ascending) and the a[0] count convention are preserved, as is the swap/copy-back behaviour. The in-place writes are safe: the write index (cursorc, number of matches) never exceeds the read index.

Patch against OPENLDAP_REL_ENG_2_5_19 (applies cleanly to RE25 and master HEAD as well); also attached as mdb-idl-intersection.patch:

--- a/servers/slapd/back-mdb/idl.c +++ b/servers/slapd/back-mdb/idl.c @@ -759,23 +759,49 @@ goto done; }

- /* Fine, do the intersection one element at a time. - * First advance to idmin in both IDLs. + /* If b is a range (and does not fully cover a, handled above), the + * intersection is just the elements of list a that fall within the + * range bounds. Walk the (bounded) list, never the (potentially huge) + * range: O(|a|), not O(range width). */ - cursora = cursorb = idmin; - ida = mdb_idl_first( a, &cursora ); - idb = mdb_idl_first( b, &cursorb ); - cursorc = 0; + if ( MDB_IDL_IS_RANGE( b ) ) { + ID lo = MDB_IDL_RANGE_FIRST( b ); + ID hi = MDB_IDL_RANGE_LAST( b ); + cursorc = 0; + for ( ida = mdb_idl_first( a, &cursora ); + ida != NOID; + ida = mdb_idl_next( a, &cursora ) ) { + if ( ida < lo ) + continue; + if ( ida > hi ) + break; + a[++cursorc] = ida; + } + a[0] = cursorc; + goto done; + }

- while( ida <= idmax || idb <= idmax ) { - if( ida == idb ) { + /* Both a and b are lists. Sorted-merge intersection, but when the two + * cursors diverge, binary-search the lagging list forward to the other's + * current value instead of stepping one element at a time. This keeps a + * large gap in one list (e.g. two widely separated matches intersected + * against a populous list) from forcing a linear scan of the other list + * across the whole gap: each catch-up is O(log n) rather than O(gap). + */ + cursora = mdb_idl_search( a, idmin ); + cursorb = mdb_idl_search( b, idmin ); + cursorc = 0; + while ( cursora <= a[0] && cursorb <= b[0] ) { + ida = a[cursora]; + idb = b[cursorb]; + if ( ida == idb ) { a[++cursorc] = ida; - ida = mdb_idl_next( a, &cursora ); - idb = mdb_idl_next( b, &cursorb ); + cursora++; + cursorb++; } else if ( ida < idb ) { - ida = mdb_idl_next( a, &cursora ); + cursora = mdb_idl_search( a, idb ); } else { - idb = mdb_idl_next( b, &cursorb ); + cursorb = mdb_idl_search( b, ida ); } } a[0] = cursorc;

TESTING ------- Using the attached harness (the patched function is byte-for-byte the shipped code):

- Correctness: 400,000 randomized trials (two seeds) over zero/list/range operands of varied sizes and gaps, in both argument orders, cross-checked against brute-force set intersection. Zero mismatches.

- The reported case, list {1759457, 2731413} intersected with a 2,000,000-entry range [1 .. 2731412] that does not cover the upper member, 1200 iterations:

original: 2.54 s, 1,166,348,400 mdb_idl_next calls, result count = 1 fixed: ~0 s, 1,200 mdb_idl_next calls, result count = 1

- Single-value baseline (original): ~0 s, 0 mdb_idl_next calls, confirming the original is fast only for the single-match case.