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

RE: address look-up performance and a filterindex.c patch



Looks like a good find. I'm committing this patch.

  -- Howard Chu
  Chief Architect, Symas Corp.       Director, Highland Sun
  http://www.symas.com               http://highlandsun.com/hyc  
  Symas: Premier OpenSource Development and Support

> -----Original Message-----
> From: owner-openldap-devel@OpenLDAP.org
> [mailto:owner-openldap-devel@OpenLDAP.org]On Behalf Of Jonghyuk Choi
> Sent: Wednesday, January 02, 2002 2:39 PM
> To: openldap-devel@OpenLDAP.org
> Subject: address look-up performance and a filterindex.c patch
> 
> 
> The DirectoryMark address look-up scenario mimics a situation where
> multiple
> clients ask general address look-up queries. Each client thread sends a
> sequence of
> requests of the following mix :
> 
> - exact match on emailAddress :     28%
> - CN wildcard search :        24%
> - exact match on given name :       16%
> - exact match on SN :          8%
> - exact match on CN :         16%
> - not found :                  8%
> - bind :    as anonymous, every 5 requests
> 
> In the experimental run, the throughput of back-bdb happened to be
> siginificanlty lower than that of back-ldbm.
> 
> # of Clients : 8, # of Threads / Clients : 2
> Run Time : 5 minutes
> 
> DirectoryMark Results
> - back-ldbm
>       Number of Transactions  : 170,812
>       Min Time (ms)           :       0
>       Max Time (ms)           :   8,607
>       Average Time (ms) :      27
>       Standard Dev. (ms)      :      14
>       DirectoryMark           :     561.9 operations / second
> - back-bdb
>       Number of Transactions  :     511
>       Min Time (ms)           :       1
>       Max Time (ms)           : 153,428
>       Average Time (ms) :  13,137
>       Standard Dev. (ms)      :  13,207
>       DirectoryMark           :       1.2 operations / second
> 
> When examining back-bdb traces, I found that search_candidates() returns
> all entries when searching for non-existent entries.
> Because slapd should loop through all entries to vainly find matching
> entries,
> 8% of the searches seem to result in the drastic performance degradation
> as shown above.
> 
> The following is a possible patch to make ids empty in such cases (please
> examine) :
> 
> *** filterindex.c.org         Wed Jan  2 17:14:24 2002
> --- filterindex.c.jhchoi      Wed Jan  2 17:24:29 2002
> *************** presence_candidates(
> *** 229,239 ****
>             return 0;
>       }
> 
>       rc = bdb_key_read( be, db, NULL, &prefix, ids );
> 
>       if( rc == DB_NOTFOUND ) {
>             rc = 0;
> -
>       } else if( rc != LDAP_SUCCESS ) {
>             Debug( LDAP_DEBUG_TRACE,
>                   "<= bdb_presense_candidates: key read failed (%d)\n",
> --- 235,247 ----
>             return 0;
>       }
> 
> +
>       rc = bdb_key_read( be, db, NULL, &prefix, ids );
> 
> +
>       if( rc == DB_NOTFOUND ) {
> +           BDB_IDL_ZERO( ids );
>             rc = 0;
>       } else if( rc != LDAP_SUCCESS ) {
>             Debug( LDAP_DEBUG_TRACE,
>                   "<= bdb_presense_candidates: key read failed (%d)\n",
> *************** equality_candidates(
> *** 316,325 ****
>             return 0;
>       }
> 
>       for ( i= 0; keys[i].bv_val != NULL; i++ ) {
>             rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
> 
> !           if( rc != LDAP_SUCCESS ) {
>                   Debug( LDAP_DEBUG_TRACE,
>                         "<= bdb_equality_candidates key read failed (%d)
> \n",
>                         rc, 0, 0 );
> --- 324,339 ----
>             return 0;
>       }
> 
> +
>       for ( i= 0; keys[i].bv_val != NULL; i++ ) {
>             rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
> 
> !           if (rc == DB_NOTFOUND) {
> !                 BDB_IDL_ZERO( ids );
> !                 rc = 0;
> !                 break;
> !           }
> !           else if( rc != LDAP_SUCCESS ) {
>                   Debug( LDAP_DEBUG_TRACE,
>                         "<= bdb_equality_candidates key read failed (%d)
> \n",
>                         rc, 0, 0 );
> *************** approx_candidates(
> *** 424,430 ****
>       for ( i= 0; keys[i].bv_val != NULL; i++ ) {
>             rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
> 
> !           if( rc != LDAP_SUCCESS ) {
>                   Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates key
> read failed (%d)\n",
>                         rc, 0, 0 );
>                   break;
> --- 440,450 ----
>       for ( i= 0; keys[i].bv_val != NULL; i++ ) {
>             rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
> 
> !           if( rc == DB_NOTFOUND ) {
> !                 BDB_IDL_ZERO( ids );
> !                 rc = 0;
> !                 break;
> !           } else if( rc != LDAP_SUCCESS ) {
>                   Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates key
> read failed (%d)\n",
>                         rc, 0, 0 );
>                   break;
> *************** substring_candidates(
> *** 523,529 ****
>       for ( i= 0; keys[i].bv_val != NULL; i++ ) {
>             rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
> 
> !           if( rc != LDAP_SUCCESS ) {
>                   Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates key
> read failed (%d)\n",
>                         rc, 0, 0 );
>                   break;
> --- 543,553 ----
>       for ( i= 0; keys[i].bv_val != NULL; i++ ) {
>             rc = bdb_key_read( be, db, NULL, &keys[i], tmp );
> 
> !           if( rc == DB_NOTFOUND ) {
> !                 BDB_IDL_ZERO( ids );
> !                 rc = 0;
> !                 break;
> !           } else if( rc != LDAP_SUCCESS ) {
>                   Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates key
> read failed (%d)\n",
>                         rc, 0, 0 );
>                   break;
> 
> 
> 
> The DirectoryMark Results with the patch is :
> -back-bdb
>       Number of Transactions  :  57,298
>       Min Time (ms)           :       0
>       Max Time (ms)           :  13,985
>       Average Time (ms) :      83
>       Standard Dev. (ms)      :      46
>       DirectoryMark           :     189.7 operations / second
> 
> 
> ------------------------
> Jong Hyuk Choi
> IBM Thomas J. Watson Research Center - Enterprise Linux Group
> P. O. Box 218, Yorktown Heights, NY 10598
> email: jongchoi@us.ibm.com
> (phone) 914-945-3979    (fax) 914-945-4425   TL: 862-3979
>