Bug 464854 - ldapsearch with size limit (-z) doesn't work with OR filter and range search
Summary: ldapsearch with size limit (-z) doesn't work with OR filter and range search
Keywords:
Status: CLOSED CURRENTRELEASE
Alias: None
Product: 389
Classification: Retired
Component: Directory Server
Version: 1.1.1
Hardware: All
OS: Linux
medium
medium
Target Milestone: ---
Assignee: Noriko Hosoi
QA Contact: Chandrasekar Kannan
URL:
Whiteboard:
Depends On:
Blocks: 249650 FDS1.2.0
TreeView+ depends on / blocked
 
Reported: 2008-09-30 20:46 UTC by xili
Modified: 2015-01-04 23:34 UTC (History)
4 users (show)

Fixed In Version: 8.1
Doc Type: Bug Fix
Doc Text:
Clone Of:
Environment:
Last Closed: 2009-04-29 23:06:51 UTC


Attachments (Terms of Use)
cvs diff ldapserver/ldap/servers/slapd/back-ldbm/filterindex.c (1.67 KB, patch)
2009-01-09 18:40 UTC, Noriko Hosoi
no flags Details | Diff
Revised: cvs diff ldapserver/ldap/servers/slapd/back-ldbm/filterindex.c (1.84 KB, patch)
2009-01-09 21:01 UTC, Noriko Hosoi
no flags Details | Diff
cvs commit message (1.02 KB, text/plain)
2009-01-09 21:34 UTC, Noriko Hosoi
no flags Details

Description xili 2008-09-30 20:46:26 UTC
I am having a problem with the following command:

ldapsearch -z 10 ... (&(attr1=val1)(|(attr2=val21)(attr2=val22))(attr3>=val3))

The command returns successfully with 0 entry. I know there are entries in my database matching the search criteria. And if I remove "-z 10" option, all the entries matching the search criteria return. More interestingly, if I switch the order of the search filter:

ldapsearch -z 10 ... (&(attr1=val1)(attr3>=val3)(|(attr2=val21)(attr2=val22)))

It returns 10 entries. After looking at the fedora-ds-base code, I found the following:

Range search ">=" or "<=" calls index_range_read() function, which has the following code:

if (!is_and)
{
       slapi_pblock_get(pb, SLAPI_SEARCH_SIZELIMIT, &sizelimit);
}

When filter is not AND, client side size limit is used to filter candidates. I don't understand why client side size limit is used on server side to filter the candidates in the first place.

Now "is_and" is set in list_candidates() every time when it is called and it is called for AND and OR filters. So if I have a filter like this:

(&(attr1=val1)(|(attr2=val21)(attr2=val22))(attr3>=val3))

Since OR "|" is after AND "&", "is_and" is false when index_range_read() is called, size limit is used and if the candidates within the size limit don't satisfy the whole search criteria, no record is returned from the search. The code doesn't seem to understand OR is only for "(|(attr2=val21)(attr2=val22))" part of the filter.

However, if I switch the filter order to:

(&(attr1=val1)(attr3>=val3)(|(attr2=val21)(attr2=val22)))

Now "is_and" is true when index_range_read() is called, thus no size limit is used and the records satisfy the search criteria are returned.

Comment 1 Noriko Hosoi 2009-01-09 18:35:26 UTC
Thanks.  I could reproduce the problem.

Create a test ldif file with dbgen.pl
$ dbgen.pl -o /path/to/example10k.ldif -n 10000
Import it
$ ldif2db -n userRoot -i /path/to/example10k.ldif
Start the server
$ start-slapd

Run the following command
$ ldapsearch -D 'cn=Directory Manager' -w <pw> -b "dc=example,dc=com" "(&(l=Boston)(|(ou=Payroll)(ou=Accounting))(roomNumber>=9700))" dn roomNumber l ou
It returns 7 entries.

$ ldapsearch -D 'cn=Directory Manager' -w <pw> -b "dc=example,dc=com" -z 5 "(&(l=Boston)(|(ou=Payroll)(ou=Accounting))(roomNumber>=9700))" dn roomNumber l ou
It returns no entries.
Expected result: returns 5 entries

Problem description:
SIZELIMIT is checked in index_range_read to eliminate the unnecessary data retrieval.  But when the filter contains a range search which is connected by AND, then we should not do sizelimit.  There was a bug in the function which sets is_and.  The flag should have been cleared only when the function set it to 1.  Instead, it was cleared each time the function is called.  It let index_range_read stop reading when it reaches sizelimit even though it should not have.

Comment 2 Noriko Hosoi 2009-01-09 18:40:21 UTC
Created attachment 328581 [details]
cvs diff ldapserver/ldap/servers/slapd/back-ldbm/filterindex.c

Fix Description: list_candidates sets SLAPI_SEARCH_IS_AND to 1 in pblock when the filter starts with AND.  This function is recursively called and the IS_AND info should be passed to the descendent candidates functions.  The IS_AND flag is cleared only by the function which sets it to 1.

Comment 3 Noriko Hosoi 2009-01-09 21:01:44 UTC
Created attachment 328591 [details]
Revised: cvs diff ldapserver/ldap/servers/slapd/back-ldbm/filterindex.c

Thanks to Nathan for pointing out the flaw in my previous proposal.  It had a bug in the nested AND case.  Inner AND was clearing "is_and", which should not have.  It was fixed in this new proposal.

Comment 4 Noriko Hosoi 2009-01-09 21:34:37 UTC
Created attachment 328594 [details]
cvs commit message

Reviewed by Nathan (Thank you!!)

Checked in into CVS HEAD.

Comment 5 Jenny Severance 2009-03-30 20:14:41 UTC
fix verified DS 8.1 - RHEL 5

[root@jennyv2 slapd-jennyv2]# ldapsearch -x -h `hostname` -p 389 -D "cn=Directory Manager" -w Secret123 -b "dc=example, dc=com" "(&(l=Boston)(|(ou=Payroll)(ou=Accounting))(roomNumber>=9700))" dn roomNumber l
# extended LDIF
#
# LDAPv3
# base <dc=example, dc=com> with scope subtree
# filter: (&(l=Boston)(|(ou=Payroll)(ou=Accounting))(roomNumber>=9700))
# requesting: dn roomNumber l 
#

# EGeadah724, Accounting, example.com
dn: uid=EGeadah724, ou=Accounting, dc=example,dc=com
roomNumber: 9803
l: Boston

# ASteinbac2444, Accounting, example.com
dn: uid=ASteinbac2444, ou=Accounting, dc=example,dc=com
roomNumber: 9723
l: Boston

# VPendergr4204, Payroll, example.com
dn: uid=VPendergr4204, ou=Payroll, dc=example,dc=com
roomNumber: 9960
l: Boston

# SJuskevic5677, Accounting, example.com
dn: uid=SJuskevic5677, ou=Accounting, dc=example,dc=com
roomNumber: 9765
l: Boston

# MKneese6357, Accounting, example.com
dn: uid=MKneese6357, ou=Accounting, dc=example,dc=com
roomNumber: 9980
l: Boston

# EGrossutt7059, Accounting, example.com
dn: uid=EGrossutt7059, ou=Accounting, dc=example,dc=com
roomNumber: 9845
l: Boston

# SSkillen8191, Accounting, example.com
dn: uid=SSkillen8191, ou=Accounting, dc=example,dc=com
roomNumber: 9839
l: Boston

# search result
search: 2
result: 0 Success

# numResponses: 8
# numEntries: 7
[root@jennyv2 slapd-jennyv2]# ldapsearch -x -h `hostname` -p 389 -D "cn=Directory Manager" -w Secret123 -b "dc=example, dc=com" -z 5 "(&(l=Boston)(|(ou=Payroll)(ou=Accounting))(roomNumber>=9700))" dn roomNumber l
# extended LDIF
#
# LDAPv3
# base <dc=example, dc=com> with scope subtree
# filter: (&(l=Boston)(|(ou=Payroll)(ou=Accounting))(roomNumber>=9700))
# requesting: dn roomNumber l 
#

# EGeadah724, Accounting, example.com
dn: uid=EGeadah724, ou=Accounting, dc=example,dc=com
roomNumber: 9803
l: Boston

# ASteinbac2444, Accounting, example.com
dn: uid=ASteinbac2444, ou=Accounting, dc=example,dc=com
roomNumber: 9723
l: Boston

# VPendergr4204, Payroll, example.com
dn: uid=VPendergr4204, ou=Payroll, dc=example,dc=com
roomNumber: 9960
l: Boston

# SJuskevic5677, Accounting, example.com
dn: uid=SJuskevic5677, ou=Accounting, dc=example,dc=com
roomNumber: 9765
l: Boston

# MKneese6357, Accounting, example.com
dn: uid=MKneese6357, ou=Accounting, dc=example,dc=com
roomNumber: 9980
l: Boston

# search result
search: 2
result: 4 Size limit exceeded

# numResponses: 6
# numEntries: 5

Comment 6 Chandrasekar Kannan 2009-04-29 23:06:51 UTC
An advisory has been issued which should help the problem
described in this bug report. This report is therefore being
closed with a resolution of ERRATA. For more information
on therefore solution and/or where to find the updated files,
please follow the link below. You may reopen this bug report
if the solution does not work for you.

http://rhn.redhat.com/errata/RHEA-2009-0455.html


Note You need to log in before you can comment on or make changes to this bug.