[Date Prev][Date Next] [Chronological] [Thread] [Top]

Back-sql improvements - please test

Hello, all!

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

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,

WBW, Dmitry

----- Original Message -----
From: "Rajen Damani" <
To: <
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
> changes).
> 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
> changes.
> Thanks.
> -Raj Damani
> TimesTen Performance Software
> -----Original Message-----
> From: Sam Drake [mailto:drake@timesten.com]
> Sent: Saturday, April 07, 2001 10:40 PM
> To:
> 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
>    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.