CVS log for servers/slapd/back-sql/search.c

Up to [OpenLDAP] / servers / slapd / back-sql

Request diff between arbitrary revisions

Keyword substitution: kv
Default branch: MAIN

Happy New Year

s/producer/provider

noop commit: cleanup 0 -> REP_RESULT in SlapReply

(blind) support for long long keys (ITS#6617; needs ITS#6622 patch)

improve ID logging when arbitrary key is set (almost blind fix; compiles in both cases)

happy belated New Year

blind fix to ITS#6163

(blindly) allow to build with BACKSQL_ARBITRARY_KEY defined (ITS#6100).  Please note that this disables paged results support

cleanup (related to ITS#5760)

Update copyright notices

Happy New Year (belated)

fix declarations of buffers for numeric strings; other related cleanup

ITS#5191 do all pagedresult control parsing in the frontend, don't
re-parse in the backend. Keep track of pagedresult controls and state
in backglue.

re-fix previous commit

fix tree delete error handling

add support for tree delete along with minor fixes (portions ITS#3497)

rework connections so that they get cached on a per-thread basis (ITS#5095)

more on ITS#4868

Fallout from ITS#4986 - remove unused param of select_backend()

add support for pagedResults to back-sql (ITS#4888)

fix subtree shortcut (ITS#4856)

happy new year

ITS#4768 more be_add fallout

Entry/Attribute struct caching, to minimize malloc fragmentation
Note: this breaks LDAP_COMP_MATCH and SLAP_ZONE_MALLOC. But they
were probably broken already anyway.

don't sigsegv if has_ldapinfo_dn_ru is erroneously defined; return a (more) meaningful error

handle computed filters the best it can (ITS#4604)

unifdef -DSLAP_ACL_HONOR_DISCLOSE
unifdef -DSLAP_ACL_HONOR_MANAGE
unifdef -DSLAP_OVERLAY_ACCESS
unifdef -DSLAP_ORDERED_PRETTYNORM
unifdef -DSLAP_AUTHZ_SYNTAX
Move LDAP_COLLECTIVE_ATTRIBUTES, LDAP_COMP_MATCH, and LDAP_SYNC_TIMESTAMP
back behind LDAP_DEVEL (as these either too experimental or not yet
implemented).

Happy new year!

fix various memory leaks and handling issues

Remove some unnecessary #ifdefs

use LDAP_SIZELIMIT_EXCEEDED; rework the return values of slap_send_search_entry(); silence a few warnings

cleanup filter escaping

check sizelimit in frontend (ITS#4213)

always set sr_flags before sending an entry

use lutil_ato*() whenever appropriate

fix size limit count (ITS#4181)

use pooled memory whenever appropriate

don't leak entry/referrals in case of reference

remove unnecessary data from search_info

cleanup candidate list in case of abandon, even if it occurs while selecting candidates

cleanup candidate list in case of abandon

use operation slab for column binding

assert expects int. (int)<nonnull ptr/long> can be 0. Use assert(arg!=0/NULL).

make aliasing and aliasing quotes configurable

fix previous commit

work around syncprov interoperation issues; minor cleanup

honor abandon/cancel (ITS#3551)

fix ITS#3551

(blind) improvement of column name aliasing

fix compare; more manageDSAit cleanup

fix different issues with referrals in searches; remove unused tests; cleanup referrals in tests so that they don't get chased; improve schema checking in modrdn and updates in general; minor cleanup

fix several schema checking issues; add rename specific statement for entry renaming without losing ID (helps e.g. in renaming referrals, otherwise referential integrity would prevent del/add because of referenced stuff in ldap_referrals and ldap_entry_objclasses); referrals need schemacheck off otherwise objectClass chain is invalid (they need to be attached to another objectClass by now; will address this later)

fixes for ITS#3480,3485,3489; implementation of DISCLOSE access for all operations (ITS#3472); ITS#3432.4; added value validate/pretty when applicable (see comments and #defines in back-sql.h)

address ITS#3472/3480/3488/3489

condition compilation of DISCLOSE checking (there's more to do)

plug memory leak: bsi_attrs member
use tmpmemctx for bsi_attrs (should be used more for temporaries)
fix ITS#3480: allow to fetch all attrs or provide hints
fixed access check to entry for rename
TODO: fetch entries for access checking in selected code portions (e.g. rename)

fix couple of bugs in recent 'disclose' commits; prepare for sending matchedDN when appropriate; note ITS#3480 access control issues

honor 'disclose' ACL on searchBase/compare/referral/matched (ITS#3472 and comments on -devel)

minor naming cleanup; improvements to DN mapping layer; major docs update

mostly copyright cleanup; removal of unnecessary headers

Happy New Year!

More cr statements

apply patches 1,2,3,5,8 (with changes) from ITS#3432)

more on DN munging; now works for all operations

fix DN munging; also fix potential error when logging incomplete deletes

fix user/operational mix of attribute request

essential support for refreshOnly syncrepl

more on syncprov support

first round at enabling back-sql as LDAPsync provider

make unregistered known controls show up as undefined; move LDAPsync cid to frontend; some cleanup

wait until syncprov freezes

Merge op->o_sync_mode into op->o_sync

minor cleanup

add support for entryUUID and entryCSN operational attributes (entryUUID is honored in filters as well)

improve previous commit; consistently use dn/ndn; add support for LDAP_SCOPE_SUBORDINATE

add (and honor) a (configurable) baseObject to workaround ldap_entries view for RDBMSes that do not support UNION in views

cleanup naming; minor fixes

fix, rework and optimize search base; allow orphaned entries addition

multiple precision with BIGNUM/gmp/ulong

consistently check return value of BindParam*; rework macros to ease parameter binding; always add data length to string values (may need to specialize for integers)

improve candidate selection when filtering by objectClass

more definitive improvements; now write operations are consistent; plugged some more leaks/invalid frees; tests are more complete.  IBM db2 doesn't pass write test because the entries are written in a different order; need to write a script that sorts the results...

fix various issues; line up with new tests

handle referrals correctly; allow to add suffix entry; fix multiple values add bug; cleanup

allow to search for "auxiliary" objectClasses (i.e. those in ldap_entry_objclasses); allow to return all objectClasses including "auxiliary"; various cleanup

rework op/rs structures to deal with opeartional attributes

clarify no limits in (internal) searches

more cleanup

split objectClass and attributeType mapping (should cure ITS#3091: Sybase compatibility)

Added provisions for a layer between the backend and the ODBC
for further mucking with data.  This can be of use in ill situations
where not all the required massaging can be done on data with SQL
by means of stored procedures, but overlays are called too early
and cannot be used to make data non LDAP compliant.
- only support for bidirectional DN mucking is provided right now
- support for other values mucking is planned
- write is not completely tested yet
- the API could change quite often; don't rely too much on it

other cleanup has been added.

General improvements:
- There might be special cases that require the unique key to be a string
  (just ran into one); since this is not a generally useful change, it's
  hidden behind #defines.
- Added essential support for telephoneNumber match; the same infrastructure
  might be useful for other specialized matches (also regular matches should
  use it to handle multiple spaces and so!).
- Fixed dynamic backend initialization.
- Cleaned up search base DN normalization (works also if no uppercase function
  is available, using case exact matches).

reset SlapReply flags

move limits evaluation to frontend

allow search limits based on groups (ITS#2967)

make file names more slapd-ish; add attribute inheritance to search attributes; precompile uppercased search

cleanup

cleanup

honor attributeType inheritance as well

add extra level of parens only if required

don't search if the filter is invalid; search also if an attribute is undefined for that objectclass, the filter may succeed anyway

allow multiple attribute definitions; honor ldap_entry_objclasses in filter; major cleanup

honor objectclass inheritance in filters + some cleanup

don't try to decide if uppercase based on LDAP matching rules

Happy new year

notices and acknowledgements

fix format (ITS#2640?)

cleanup; improve error handling

clarify hasSubordinate filtering

use syntax and matching rules knowledge when preparing SQL filters (to reduce pseudo-normalization efforts and search candidate number)

more cleanup; small improvements

honor attributes request

fix backsql new API; use berbuf instead of berval

fix context memory and more cleanup

fix referrals return

more new API ... back-sql should be OK

more new API ...

Remove casts of AVL function pointers.

improve limits handling and consistency; return "Admin limit exceeded" instead of "Unwilling to perform"

remove #ifdef SLAP_FILTER_HASSUBORDINATES

fix hasSubordinate filtering; now it can be safely turned on

fix extendedMatch and approx hfilter andling; get rid of subtree_cond (argh, need to trim it from config and docs ...)

cleaner handling of unchecked limit support

- added the capability to filter based on hasSubordinate attribute
  to back-bdb, back-ldbm and back-sql (the latter with limitations);
- added handling of ":dn" attributes to extended rfc2254 filters
  and to matched value filter
- altered the behavior of get_mra() when a matching rule is given:
  now it checks whether it is compatible with the attribute syntax
  and, in case it is, the given mr is used.  In case of no type,
  the check is delayed when filtering

Final run of changes to back-sql; IBM db2 support has been tested.
Now related ITSes need be audited and possibly closed.

Enhancements:
  - re-styled code for better readability
  - upgraded backend API to reflect recent changes
  - LDAP schema is checked when loading SQL/LDAP mapping
  - AttributeDescription/ObjectClass pointers used for more efficient
    mapping lookup
  - bervals used where string length is required often
  - atomized write operations by committing at the end of each operation
    and defaulting connection closure to rollback
  - added LDAP access control to write operations
  - fully implemented modrdn (with rdn attrs change, deleteoldrdn,
    access check, parent/children check and more)
  - added parent access control, children control to delete operation
  - added structuralObjectClass operational attribute check and
    value return on search
  - added hasSubordinate operational attribute on demand
  - search limits are appropriately enforced
  - function backsql_strcat() has been made more efficient
  - concat function has been made configurable by means of a pattern
  - added config switches:
      - fail_if_no_mapping	write operations fail if there is no mapping
      - has_ldapinfo_dn_ru	overrides autodetect
      - concat_pattern		a string containing two '?' is used
				(note that "?||?" should be more portable
				than builtin function "CONCAT(?,?)")
      - strcast_func		cast of string constants in "SELECT DISTINCT					statements (needed by PostgreSQL)
      - upper_needs_cast	cast the argument of upper when required
				(basically when building dn substring queries)

Todo:
  - add security checks for SQL statements that can be injected (?)
  - re-test with previously supported RDBMs
  - replace dn_ru and so with normalized dn (no need for upper() and so
    in dn match)
  - implement a backsql_normalize() function to replace the upper()
    conversion routines
  - note that subtree deletion, subtree renaming and so could be easily
    implemented (rollback and consistency checks are available :)
  - implement "lastmod" and other operational stuff (ldap_entries table ?)

CHANGES:
- now all write operations appear to work correctly with PostgeSQL 7.0
- all write operations have been made transactional (atomic writes to
  entries are committed separately only in case of complete^1 success
  while all other operations are rolled-back by default)
- more cleanup and handling of exceptional conditions

TODO:
- deen to check with different databases and more up to date versions
  of both unixODBC and PostgreSQL.

^1: attribute add/modify/delete operations silently succeed if the
    appropriate add/delete proc does not exist for each attribute;
    this may be correct to hide undesired/unimplemented correspondence
    between LDAP and SQL databases; however, a more appropriate
    LDAP behavior would be a failure with LDAP_UNAVAILABLE if a
    single write operation cannot be executed for such reason

changes:
- re-style according to the style giudelines for better readability
- updated to recent frontend/backend API changes
- fixed a few quirks about normalization
- "optimized" a few memory allocation/string handling functions
- fixed a few quirks about add/modify (still have to look ad modrdn)

todo:
- there is still something broken (at least with PostgreSQL and IBM db2,
  the two RDBMS O have at hand) when adding
- move everything to struct bervals and try to save a few strlen
- try some LDAP/SQL syntax relation to use appropriate value bind if possible
- ...

ITS#1733 eliminate o_abandonmutex

Changed AttributeName back into an array instead of a linked list

Changed search attrs from struct berval ** to AttributeName *

Changed search attrs to struct berval **.
Use typedefs for all backend functions, to minimize work in future API
updates. (back-*/external.h will never need updating in the future.)

More struct berval DNs

Changed sai_dn, sai_ndn to struct berval. (Affects op->o_dn,o_ndn,
conn->c_dn,c_ndn, Access->a_dn_pat)

Moved AttributeDescription caching into main code:
   Changed AttributeDescription.{ad_cname,ad_lang} to struct berval everywhere
   Deleted ad_free() everywhere
   Added ad_mutex to init.c

The AttributeDescriptions are in a linked list hanging off of the
corresponding AttributeType.

finish the prefious fixes... it is really hard to commit a truly good patch without even a chance to check if it is compilable ;)

some cosmetics and minor problems fixed, pointed out by Mei-Hui Su (c++-style comments, newlines etc.)

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.

Add 'distinct' to sql search query to prevent duplicate entries in results (suggested by Mathieu Guillaume)

fix _stupid_ thing with toupper -> ldap_pvt_str2upper

fix ITS #855 (back-sql crashes with malformed filters),

also extend bind() to something less trivial (to support SIMPLE_AUTH mode)

fix case-insensitive matching
+
documentation cleanup & update

changes for 2.0-beta
including:
- fixes according to new API changes
- closing db connection in connection_destroy callback, not unbind
- support of new schema code, samples changed accordingly
- support for multiple objectclasses (to distinguish from unique objectclass-to-tables mapping)
- auto 'ref' attribute support
- samples now include illustrations of using these 2 features to make named referrals as described in ldapext-namedref draft

more to come:
- documentation update
- different improvements to be more close to native directory (after beta?)

Summary of changes:
- filter -> SQL translation bugfixes
- several memory leaks fixups
- improved configurability:
    - allows definition of  uppercasing function to support CIS matching on databases that do
    case sensitive compares (this fixes up Oracle issues, example updated)
    - allows more flexibility in stored procedures interface (different parameter order, optional return
      codes - see samples, and comments in backsql.h)
- synchronize function interfaces to recent changes in prototypes ("const" clauses etc.) made for all backends
  (those changes led to compile-time errors)

wrap sql *.c files with #ifdef SLAPD_SQL to facilate NT builds
without -DSLAPD_SQL

more back-sql files + rdbms_dependent samples

Import latest from devel

Import latest from devel including filter fixes

Update back-sql

Import experimental SQL from devel and associated configure
support.

First round of imports from HEAD

Search limit updates and other misc cleanup

Misc changes from HEAD

back-sql attribute handling

Sync with HEAD

Sync with HEAD

Sync with HEAD

Sync with HEAD

Suck in HEAD changes since 2.1alpha

Happy new year!

fix ITS#3488

import improvements from HEAD

Changes from HEAD, including
+       Fixed back-bdb ignore deadlock bug (ITS#3188)
+       Fixed back-bdb pagedResults no end cookie bug (ITS#3161)
+       Fixed back-bdb pagedResults clear controls bug (ITS#3182)
+       Fixed back-bdb pagedResults ignore control bug
+       Fixed slapd internal search limit bugs (ITS#3183)
+       Added slapd -l USER/DAEMON options (ITS#3187)
+       Build environments
+               Fixed back-sql trace build

From HEAD:
New module build stuff
updateref updates, new SHADOW DBFLAGS, etc.
paging control updates
limits updates
fixed duplicate value checks
fixed permissive modify
sasl auxprop propname changes
back-bdb "" suffix fixes
fixed back-bdb/ldbm approx non-indexing fixings
updated back-sql

Sync with HEAD

Sync with HEAD as of 14-March-2004

Sync with HEAD

Sync with HEAD

Sync with HEAD

Sync with (old) HEAD

Happy new year

Sync with HEAD

Changes from HEAD for beta

Happy new year! (belated)

fix subtree shortcut (ITS#4856)

happy new year

import small fixes from HEAD

Happy new year!

Sync with HEAD

Sync with HEAD

Sync with HEAD

Sync with HEAD

Sync with HEAD
Ready for release

Merge in recent changes to HEAD

Sync with HEAD

Sync with HEAD

Sync with HEAD

ITS#6758

Happy New Year!

Replace term "producer" with "provider".  "Provider" has a very specific meaning when it comes to replication.

ITS#6617

improve ID logging when arbitrary key is set

happy belated new year

ITS#6163

ITS#6100

ITS#5760
warnings fix

Update copyright for next release

Happy new year! (belated)

fix declarations of buffers for numeric strings; other related cleanup

ITS#5191
Fix paged results control handling

Sync with HEAD for OL 2.4.5

Quick merge: everything from HEAD

Sync with HEAD

Sync with HEAD

Sync with HEAD

New access_allowed()