Add general extensible matching support and integerBitAndMatch
and integerBitOrMatch enhancement (ITS#1302 + minor changes)
from Luke Howard <lukeh@padl.com>.

Allow dn.base=""

Open databases using WRCREAT not READER.

There is no TLSProtocol option.

Move Cyrus SASL initializing forward

More updates.

Add additional types to lber-types.

Misc Update

Skip over the "dn:" prefix when passing a DN to dn_normalize().

Remove redundant call of SSL_set_info_callback, to allow users
to override it in the SSL_CTX.

Fix NEW_LGGING typo

Password-hash doesn't support UNIX, KERBEROS, SASL schemes.

Minor cleanup

Add dnnolocking warning

Remove -r

Minor rework of *text = textbuf fix

Apply ACLs to front end objects (root DSE, subschema) consistently

Use parens for clarity

Add DB 3.3 support...
  likely needs work on NT4 (but so did old code)

Fix -H ldaps:// crashes due to rework of TLS code

Changed get_listener_addresses() to not use getaddrinfo() for PF_LOCAL

fix bug in '%' escaping in substitution pattern compile

Fix db1 error and add kerberos comment

Update kerberos flags

Need to set error text pointer sooner in entry_schema_check(), or Debug() will SEGV

fix malformed test

fix a reference to volative memory in back-ldbm/passwd.c that caused garbage messages to be returned to ldappasswd

add limits stuff to back-ldap

cleanup limits stuff in back-meta

allow multiple limits setting on one global/per backend config line

more intuitive special limits configuration

enforces detailed search limits

A big bunch of improvements, contributed by Sam Drake and Raj Damani.
Summary of changes is cited below.
The patch still needs some cosmetic changes to be made, but is ready for testing.

-----Original Message-----
From: Sam Drake [mailto:drake@timesten.com]
Sent: Saturday, April 07, 2001 10:40 PM
To: 'mitya@seismic.ru'
Cc: openldap-devel@OpenLDAP.org
Subject: RE: Slapd frontend performance issues

FYI, here is a short description of the changes I made.  I'll package up the
changes asap, but it may take a couple of days.

The performance numbers quoted in this report were seen at my location with
a 100,000 object database ... the slower numbers I mentioned earlier were
reported by a customer with a 1,000,000 object database.

I also can't explain the very poor performance I saw with OpenLDAP and LDBM
with a 100,000 object database.

...Sam Drake / TimesTen Performance Software

----------

Work Performed

OpenLDAP 2.0.9, including back-sql, was built successfully on Solaris
8 using gcc.  The LDAP server itself, slapd, passed all tests bundled
with OpenLDAP.  OpenLDAP was built using Sleepycat LDBM release 3.1.17
as the "native" storage manager.

The experimental back-sql facility in slapd was also built
successfully.  It was built using Oracle release 8.1.7 and the Oracle
ODBC driver and ODBC Driver Manager from Merant.  Rudimentary testing
was performed with the data and examples provided with back-sql, and
back-sql was found to be functional.

Slapd and back-sql were then tested with TimesTen, using TimesTen
4.1.1.  Back-sql was not immediately functional with TimesTen due to a
number of SQL limitations in the TimesTen product.

Functional issues encountered were:

1. Back-sql issued SELECT statements including the construct,
   "UPPER(?)".  While TimesTen supports UPPER, it does not support the
   use of parameters as input to builtin functions.  Back-sql was
   modified to convert the parameter to upper case prior to giving it
   to the underlying database ... a change that is appropriate for all
   databases.

2. Back-sql issued SELECT statements using the SQL CONCAT function.
   TimesTen does not support this function.  Back-sql was modified to
   concatentate the necessary strings itself (in "C" code) prior to
   passing the parameters to SQL.  This change is also appropriate for
   all databases, not just TimesTen.

Once these two issues were resolved, back-sql could successfully
process LDAP searches using the sample data and examples provided with
back-sql.

While performance was not measured at this point, numerous serious
performance problems were observed with the back-sql code and the
generated SQL.  In particular:

1. In the process of implementing an LDAP search, back-sql will
   generate and execute a SQL query for all object classes stored in
   back-sql.  During the source of generating each SQL query, it is
   common for back-sql to determine that a particular object class can
   not possibly have any members satisfying the search.  For example,
   this can occur if the query searches an attribute of the LDAP
   object that does not exist in the SQL schema.  In this case,
   back-sql would generate and issue the SQL query anyway, including a
   clause such as "WHERE 1=0" in the generated SELECT.  The overhead
   of parsing, optimizing and executing the query is non-trivial, and
   the answer (the empty set) is known in advance. Solution: Back-sql
   was modified to stop executing a SQL query when it can be
   predetermined that the query will return no rows.

2. Searches in LDAP are fundamentally case-insensitive ("abc" is equal
   to "aBc").  However, in SQL this is not normally the case.
   Back-sql thus generated SQL SELECT statements including clauses of
   the form, "WHERE UPPER(attribute) = 'JOE'".  Even if an index is
   defined on the attribute in the relational database, the index can
   not be used to satisfy the query, as the index is case sensitive.
   The relational database then is forced to scan all rows in the
   table in order to satisfy the query ... an expensive and
   non-scalable proposition.  Solution: Back-sql was modified to allow
   the schema designer to add additional "upper cased" columns to the
   SQL schema.  These columns, if present, contain an upper cased
   version of the "standard" field, and will be used preferentially
   for searching.  Such columns can be provided for all searchable
   columns, some columns, or no columns.  An application using
   database "triggers" or similar mechanisms can automatically
   maintain these upper cased columns when the standard column is
   changed.

3. In order to implement the hierarchical nature of LDAP object
   hierarchies, OpenLDAP uses suffix searches in SQL.  For example, to
   find all objects in the subtree "o=TimesTen,c=us", a SQL SELECT
   statement of the form, "WHERE UPPER(dn) LIKE '%O=TIMESTEN,C=US'"
   would be employed.  Aside from the UPPER issue discussed above, a
   second performance problem in this query is the use of suffix
   search.  In TimesTen (and most relational databases), indexes can
   be used to optimize exact-match searches and prefix searches.
   However, suffix searches must be performed by scanning every row in
   the table ... an expensive and non-scalable proposition.  Solution:
   Back-sql was modified to optionally add a new "dn_ru" column to the
   ldap_entries table.  This additional column, if present, contains a
   byte-reversed and upper cased version of the DN.  This allows
   back-sql to generate indexable prefix searches.  This column is
   also easily maintained automatically through the use of triggers.

Results

A simple database schema was generated holding the LDAP objects and
attributes specified by our customer.  An application was written to
generate test databases.  Both TimesTen and Oracle 8.1.7 were
populated with 100,000 entry databases.

Load Times

Using "slapadd" followed by "slapindex", loading and indexing 100,000
entries in an LDBM database ran for 19 minutes 10 seconds.

Using a C++ application that used ODBC, loading 100,000 entries into
a disk based RDBMS took 17 minutes 53 seconds.

Using a C++ application that used ODBC, loading 100,000 entries into
TimesTen took 1 minute 40 seconds.

Search Times

The command, "timex timesearch.sh '(cn=fname210100*)'" was used to
test search times.  This command issues the same LDAP search 4000
times over a single LDAP connection.  Both the client and server
(slapd) were run on the same machine.

With TimesTen as the database, 4000 queries took 14.93 seconds, for a
rate of 267.9 per second.

With a disk based RDBMS as the database, 4000 queries took 77.79 seconds,
for a
rate of 51.42 per second.

With LDBM as the database, 1 query takes 76 seconds, or 0.076 per
second.  Something is clearly broken.

Fix bug introduced during TLS rework

Add some addl. logging

fix a couple of typos; schemacheck was duplicated

add global, per backend and per op_ndn time/size soft, hard and to-be-checked limits (exploited by back-ldbm); see slapd.conf(5) for details

Add user schema I-D

Replaced with ldap-opattrs/features I-Ds

Update drafts to latest revs

Update to rev 04

Updates for back-bdb testing

fix typo; try to delete dn2id in case of late failure

added acl check for added/removed rdn attrs

Fix typo

Clean up

Last changes should have been #ifdef

Fix basic operations

Fix slapadd crash when only a subset of databases have been initialized.
Likely should have a general solution to this.

fixes another assert in case of subtle error (schema failure while applying rdn changes)

fixes ITS#1261 (abort on modrdn with new dn already existing)

Add no attrs clarification

fixed some memory allocation nonsense

Fixed a tiny typo/spelling error

fix typo

regex-based per op_ndn time/size limits

exploits regex-based per op_ndn time/size limits

handle regex-based per op_ndn time/size limits

Remove compare root dse task, in development

Remove assert(0)

Removed duplicate code by replacing case-Exact/Ignore-Filter/Indexer and
case-Exact/Ignore-Substrings-Match/Filter/Indexer with common code for
the caseExact and caseIgnore cases

Making the approx multistring code default. Leaving the old code for now,
but can really be removed.

Misc cleanup of asserts

Made approxMatch/Indexer/Filter all do Unicode cannonical normalization
followed by stripping of characters with 8th bit set. The normalization
is needed to make exact match imply approx match.

ITS#1274 fix

To be consistent, should assert that ld is valid.

suffix option; allows partial replication of a database

Misc. updates

Misc updates

Rework single-value check

Add an improved single value constraint check.

added extra check to suffix param of replica entry

misc updates, constification, deprecation...

Misc cleanup

Misc updates

LDAPext I-D updates

Fix typo

fix up UTF8MATCH

Use DN normalize

We shouldn't need UTF8oncasecmp() and UTF8casechr() anymore, removing
them.

Minor cleanup

Zap old DN code

Make some additional UTF8 public
Remove lint

Zap !UTF8MATCH code

Back out DN changes, needs more work

unifdef -DMULTIATTRVAL_RDN

Added the suffix=<dn> parameter to replica config directive
to allow selective replication of subtrees of a single database.
Multiple occurrences allow the same replica to handle different
subtrees

Reworked again the caching in case of failure.
Now operations that set the status of an entry to CREATING (add.c, modrdn.c)
need to set it to COMMIT, by calling cache_entry_commit, before returning
the entry itself, otherwise the entry is removed from the cache
and its private data is freed.
Should fix crashes due to add failures as in ITS#1245

Reworked API of nextid; e_private gets destroyed separately from the entry in case add fails (should fix ITS#1245)

Made caseExactMatch() use Unicode normalization

Made caseIgnoreSubstringsMatch and caseExactSubstringsMatch use proper
Unicode cannonical normalization

Prevent ldbm_sync from being called by ldbm_cache_close when the new
dbsync configuration is in use, which was preventing the performance
gains of this mode.

Fixed UTF8 encoding checks for substrings assertions

Fix ITS#1239:
slapadd core-dumps when destroying db's env (Sleepycat 3.2.9) (ITS#1239)
Only call ldbm_shutdown_env if the database has been opened, ie. when
li->li_dbenv != NULL.  Would appear any time a shutdown occurred and
not all LDBM databases were opened.

Fixed bug in caseExactSubstringsIndexer() and caseIgnoreSubstringsIndexer().
UTF8 normalization must be done before we compute number of keys since
string length might increase.

Extend assertion value syntax checks to some other cases.  Needs to
be applied to substrings assertions as well.

Fix typo in disallow logging

Fixed segfault in caseIgnoreFilter when assertion value has bad UTF8 coding

reworked slapd_mods_free into mimic to avoid extra obj linking into tools

This is the skeleton of back-monitor, the slapd monitoring backend.
The old monitoring stuff has been removed; the new backend is
enabled by using --enable-monitor at configure time and requires

database monitor

in slapd.conf to be activated.  At present it implements a subset
of the old monitoring options, and it should be extendable to
a number of different subsystems.  The search operation has been
implementd; it does not honor abandon or size/time limits, though.
The compare and the abandon operations are planned.

Copyright Pierangelo Masarati <ando@sys-net.it>; the code is provided
AS IS with NO GUARANTEE.  It can be used and distributed under the
conditions stated by the OpenLDAP Public License.