I've just committed a big bunch of improvements to back-sql, contributed by
Sam Drake and Raj Damani from TimesTen Performance Software.
It is available through CVS (HEAD branch).
Summary of changes is cited below. In brief - this eliminates most of known
deficiencies of back-sql, and is expected to boost out-of-box performance by
SEVERAL TIMES !
The patch will undergo some cosmetic changes later, when I return from
vacation, but it should be ready to test. Rajen kindly agreed to answer all
questions asked about this patch on openldap-devel and -software lists, and
provide bugfixes (if any will be needed). All those will be committed when I
Big thanks to Sam and Raj,
----- Original Message -----
From: "Rajen Damani" <email@example.com>
Sent: Saturday, July 28, 2001 2:52 AM
Subject: Back-sql improvements
> Hello Dmitry,
> My name is Raj Damani and I work with Sam Drake at TimesTen Performance
> Software. Sam had made bunch of improvements to OpenLDAP a while ago. I
> recently made the same changes to latest OpenLDAP 2.0.11 source. We would
> like to send those changes to you. (email below describes all those
> I was wondering, how I should submit these changes. I can send you the
> entire upgraded (back-sql) files that include all improvements via email.
> If this does not work for you, please let me know how we can submit these
> -Raj Damani
> TimesTen Performance Software
> -----Original Message-----
> From: Sam Drake [mailto:firstname.lastname@example.org]
> Sent: Saturday, April 07, 2001 10:40 PM
> To: 'email@example.com'
> 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
> changes asap, but it may take a couple of days.
> The performance numbers quoted in this report were seen at my location
> 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
> 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
> 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
> 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
> 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.
> 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.