(ITS#4888) Enhance back-sql with paged results

[adamson@cmu.edu]

Full_Name: Mark Adamson
Version: HEAD
OS: Solaris 2.8
URL: http://null.andrew.cmu.edu/openldap/sql_paged_results.patch
Submission from: (NULL) (128.2.234.24)


Here at Carnegie Mellon we had a need to use the LDAP_CONTROL_PAGEDRESULTS
control with the SQL backend. The patch to add this is not hard, and was mostly
copied from the back-bdb/search.c file.

http://null.andrew.cmu.edu/openldap/sql_paged_results.patch

The only challenge was the contents of the cookie that is used to maintain
state. The slap.h file defines the PagedResultsCookie type to be an unsigned
long, so I wanted to fit everything into that. The design idea was to keep the
ldap_entries.id value of the last returned entry in the cookie so that
subsequent searches could add a "AND ldap_entries.id > COOKIEVALUE" clause to
the SQL query. However, the gathering of candidate entries is done across all
objectClasses with avl_apply(), so if one OC returns an entry with a high
ldap_entries.id, objectClasses that come later in the AVL could miss entries.
  For this reason, I add the oc_map_id of the last returned entry to the cookie,
and I adjusted the avl_apply() call to run through the objectClasses in numeric
order. In this way, when subsequent pages of entries are requested, all of the
objectClasses that were completed by previous pages can be skipped for the new
page. When we get to the objectClass where the previous page left off, we take
the ldap_entries.id from the cookie and apply the above mentioned SQL clause.
  To fit both the oc_map_id and ldap_entries.id into a 32bit cookie, I had to
make a sacrifice. I took 6 bits and used them for oc_map_id and the remaining 26
bits for ldap_entries.id. This means max(oc_map_id) needs to be < 64 and
max(ldap_entries.id) needs to be < 134,217,728.  If the PagedResultsCookie type
is ever expanded to be a berval, we can store both oc_map_id and ldap_entries.id
in their full glory.
  Anyway, try it out. It's a quick patch.

  -Mark Adamson
   Carnegie Mellon University