Issue 8868 - Inefficiency when processing certain search filters
Summary: Inefficiency when processing certain search filters
Status: VERIFIED FIXED
Alias: None
Product: OpenLDAP
Classification: Unclassified
Component: slapd (show other issues)
Version: 2.4.46
Hardware: All All
: --- normal
Target Milestone: ---
Assignee: OpenLDAP project
URL:
Keywords:
: 7743 (view as issue list)
Depends on:
Blocks:
 
Reported: 2018-06-21 20:25 UTC by Quanah Gibson-Mount
Modified: 2020-09-03 11:47 UTC (History)
1 user (show)

See Also:

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this issue.
Description Quanah Gibson-Mount 2018-06-21 20:25:00 UTC 
Full_Name: Quanah Gibson-Mount
Version: 2.4.46
OS: Linux
URL: ftp://ftp.openldap.org/incoming/
Submission from: (NULL) (47.208.148.239)


Certain search filters are not processed efficiently in the back-{bhm}db code
base.

An example is:

"(|(&(subscriberid=1)(objectClass=XYZ))(&(subscriberid=2)(objectClass=XYZ)))"

In this situation, the contiguous list of possibilities for the objectClass
result gets turned into a range, causing each entry to be examined as a match. 
This significantly increases CPU load and causes a delay in returning the
result.  Re-arranging the search in the following manner bypasses this issue:

(&(objectClass=XYZ)(|(subscriberid=1)(subscriberid=2)))"

General timing with back-mdb:

.477 seconds for the expensive search
.020 seconds for the optimized search

For back-bdb, the timing was:
.665 seconds for the expensive search
.020 seconds for the optimized search
Comment 1 Howard Chu 2018-06-21 23:32:52 UTC 
changed notes
changed state Open to Test
moved from Incoming to Software Bugs
Comment 2 Quanah Gibson-Mount 2018-07-03 23:41:32 UTC 
changed notes
changed state Test to Release
Comment 3 OpenLDAP project 2018-12-19 17:20:28 UTC 
fixed in master
fixed in RE24 (2.4.47)
Comment 4 Quanah Gibson-Mount 2018-12-19 17:20:28 UTC 
changed notes
changed state Release to Closed
Comment 5 Howard Chu 2020-09-03 11:47:18 UTC 
*** Issue 7743 has been marked as a duplicate of this issue. ***