Re: (ITS#7743) bdb_idl_intersection() seems to expand the search candidates unnecessarily

[hyc@symas.com]

nishino-yoshinori@mxc.nes.nec.co.jp wrote:
> Full_Name: Yoshinori Nishino
> Version: 2.4.37
> OS: RedHatEL 5.5
> URL: ftp://ftp.openldap.org/incoming/
> Submission from: (NULL) (210.143.35.12)
>
>
> Dear sir,
>
>   OS:Red Hat Enterprise Linux 5.5(x86) (2.6.18-194.el5)
>   Version: 2.4.37 + BDB 4.4.20
>
> In our environment, the issue occurs that the ldapsearch command using the
> following filter always took about 15?`30 seconds.

> The response of the ldapsearch command becomes faster by modifying idl.c like
> that:
>
>    1087          /* If a range completely covers the list, the result is
>
>    1088           * just the list. If idmin to idmax is contiguous, just
>
>    1089           * turn it into a range.
>
>    1090           */
>    1091          if ( BDB_IDL_IS_RANGE( b )
>
>    1092                  && BDB_IDL_RANGE_FIRST( b ) <= BDB_IDL_RANGE_FIRST( a )
>
>    1093                  && BDB_IDL_RANGE_LAST( b ) >= BDB_IDL_RANGE_LAST( a ) )
> {
>    1094                  /* if (idmax - idmin + 1 == a[0])
>
>    1095                  {
>
>    1096                          a[0] = NOID;
>
>    1097                          a[1] = idmin;
>
>    1098                          a[2] = idmax;
>
>    1099                  }  */
>
>    1100                  goto done;
>
>    1101          }
>
> By the aforementioned modification, the search candidate set becomes (list-type:
> the number of elements=298, minID=296,maxID=858689).
>
> I think the line 1094-1099 part of idl.c seems to be a bug.
> The part seems to be implemented in order to just make "ids[]" smaller.
> If the reason is so, would you please consider fixing idl.c?

This is certainly no bug in idl_intersection(), it is an optimization that 
makes subsequent intersection operations faster. As such, your suggested fix 
is wrong.

If you want to suggest a fix, you should look at idl_union() instead.

-- 
   -- Howard Chu
   CTO, Symas Corp.           http://www.symas.com
   Director, Highland Sun     http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP  http://www.openldap.org/project/