#47474 Ordering of ANDed search terms in filter can negatively impact search etimes
Closed: wontfix None Opened 10 years ago by chrisunger.

I have a particular search that can take 6 times longer depending upon the order of the AND'ed search terms in the filter. The following search is generated by
CA's SiteMinder Policy Server software and takes an etime of 6 milliseconds to be processed by 389 DS (1.2.11.21).

base="ou=c3sUserProduct,ou=CAS,ou=Commerce,o=cas.org" scope=2 filter="(&(|(objectClass=organizationalPerson)(objectClass=inetOrgPerson)(objectClass=organization)(objectClass=organizationalUnit)(objectClass=groupOf
Names)(objectClass=groupOfUniqueNames)(objectClass=group))(c3sUserID=EndUser0000078458))" attrs="objectClass"

However, if I reverse the AND‘ed (“&”) terms in that search filter where the more restrictive term (c3sUserID=EndUser0000078458) is first, then 389 DS returns the same results with an etime of 1 millisecond. Our current SUN
Directory Server instance, returns those search results in 1 millisecond
regardless of how the terms are ordered.

NOTE: There are over 2 million entries in the 389 and SUN DS instances.

Can 389 DS be changed to ensure that search performance is consistent
regardless of the order of the AND'ed filter terms?


email exchanges between myself and Rich Megginson
389bug.txt

I think this is an effect of old-idl vs new-idl. With new-idl it takes much more index accesses to determine that an index value is allids.
If the filter order is changed and the first filter component only returns less than 10 ids (filter threshold) then the second component isn't used in lookup - and it is faster

For reference, there are two fixes to allow the usage and tuning of old-idl: tickets #47326 and #47372
Both fixes are only in the main branch.

Can you provide the following information about the ID list sizes for these index keys?

{{{
for attr in organizationalPerson inetOrgPerson organization organizationalUnit groupOfNames groupOfUniqueNames group ; do
dbscan -n -f /var/lib/dirsrv/slapd-*/db/userRoot/objectclass.db4 -k "=$attr"
done
}}}

Do you have any searches that just use one of these objectclass filters, such as

'(&(objectclass=group)(cn=mygroupname))'

I think the fix for https://fedorahosted.org/389/ticket/47504 will also help your problem, but I just want to make sure the problem is that one or more of these search filters singly has too large an ID list, and that it is not all of them in concert.

Replying to [comment:5 rmeggins]:

Can you provide the following information about the ID list sizes for these index keys?

{{{
for attr in organizationalPerson inetOrgPerson organization organizationalUnit groupOfNames groupOfUniqueNames group ; do
dbscan -n -f /var/lib/dirsrv/slapd-*/db/userRoot/objectclass.db4 -k "=$attr"
done
}}}

'''''Here is the output from those dbscan commands:

'''''=organizationalperson 1636395
=inetorgperson 928969
=organization 1
=organizationalunit 138
Can't find key '=groupofnames
=groupofuniquenames 86731
Can't find key '=group'

Do you have any searches that just use one of these objectclass filters, such as

'(&(objectclass=group)(cn=mygroupname))'

'''''No.

I think the fix for https://fedorahosted.org/389/ticket/47504 will also help your problem, but I just want to make sure the problem is that one or more of these search filters singly has too large an ID list, and that it is not all of them in concert.

Thanks. Would you be able to try out the patches in https://fedorahosted.org/389/ticket/47504?

Please try out the new build with the fix for ​https://fedorahosted.org/389/ticket/47504

I would like to close this ticket if possible.

Metadata Update from @rmeggins:
- Issue set to the milestone: N/A

7 years ago

389-ds-base is moving from Pagure to Github. This means that new issues and pull requests
will be accepted only in 389-ds-base's github repository.

This issue has been cloned to Github and is available here:
- https://github.com/389ds/389-ds-base/issues/811

If you want to receive further updates on the issue, please navigate to the github issue
and click on subscribe button.

Thank you for understanding. We apologize for all inconvenience.

Metadata Update from @spichugi:
- Issue close_status updated to: wontfix (was: Fixed)

3 years ago

Login to comment on this ticket.

Metadata