ldap/servers/slapd/back-ldbm/back-ldbm.h | 5 ++-
ldap/servers/slapd/back-ldbm/idl.c | 7 ++++
ldap/servers/slapd/back-ldbm/index.c | 39 ++++++++++++++++++-------
ldap/servers/slapd/back-ldbm/ldbm_config.c | 23 ++++++++++++++
ldap/servers/slapd/back-ldbm/ldbm_config.h | 1
ldap/servers/slapd/back-ldbm/proto-back-ldbm.h | 1
ldap/servers/slapd/back-ldbm/start.c | 9 +++++
ldap/servers/slapd/back-ldbm/vlv.c | 8 -----
8 files changed, 75 insertions(+), 18 deletions(-)
New commits:
commit 0a54aa676341b7f5f1056373a5067a69cbe54b89
Author: Noriko Hosoi <nhosoi(a)redhat.com>
Date: Tue Nov 13 18:01:57 2012 -0800
Trac Ticket #519 - Search with a complex filter including range search is slow
https://fedorahosted.org/389/ticket/519
Bug description: If a filter contains a range search, the
search retrieves one ID per one idl_fetch and merge it to
the idlist using idl_union, which is slow especially when
the range search result size is large.
Fix description: When the idlist size is larger than nsslapd-
lookthroughlimit, the range search returns ALLID (default
value of nsslapd-lookthroughlimit is 5000). Then, the range
search filter is evaluated before returning to the client.
If the default value of nsslapd-lookthroughlimit can be used,
the search elapsed time is much shorter than generating a
complete idlist in index_range_read_ext. Since the nsslapd-
lookthroughlimit is shared among all the search operations,
larger value might be required for other cases. To have its
own control, this patch introduces a new config parameter
nsslapd-rangelookthroughlimit for the range search.
Also, this patch replaced idl_union in index_range_read_ext
with idl_append_extend and sort the idlist at the end. It
improves the range search, but it is still slower than just
returning ALLID for the large range search.
(cherry picked from commit f026ef0447b18994e0e9b847698703436e874f84)
diff --git a/ldap/servers/slapd/back-ldbm/back-ldbm.h
b/ldap/servers/slapd/back-ldbm/back-ldbm.h
index fb45a9f..aed57cf 100644
--- a/ldap/servers/slapd/back-ldbm/back-ldbm.h
+++ b/ldap/servers/slapd/back-ldbm/back-ldbm.h
@@ -210,7 +210,6 @@ typedef unsigned short u_int16_t;
#define DEFAULT_DBCACHE_SIZE 1000000
#define DEFAULT_MODE 0600
#define DEFAULT_ALLIDSTHRESHOLD 4000
-#define DEFAULT_LOOKTHROUGHLIMIT 5000
#define DEFAULT_IDL_TUNE 1
#define DEFAULT_SEARCH_TUNE 0
#define DEFAULT_IMPORT_INDEX_BUFFER_SIZE 0
@@ -650,6 +649,8 @@ struct ldbminfo {
int li_pagedallidsthreshold;
int li_reslimit_pagedlookthrough_handle;
int li_reslimit_pagedallids_handle; /* allids aka idlistscan */
+ int li_rangelookthroughlimit;
+ int li_reslimit_rangelookthrough_handle;
};
/* li_flags could store these bits defined in ../slapi-plugin.h
@@ -819,6 +820,8 @@ typedef struct _back_search_result_set
/* Name of attribute type used for binder-based look through limit */
#define LDBM_LOOKTHROUGHLIMIT_AT "nsLookThroughLimit"
/* Name of attribute type used for binder-based look through limit */
+#define LDBM_RANGELOOKTHROUGHLIMIT_AT "nsRangeSearchLookThroughLimit"
+/* Name of attribute type used for binder-based look through limit */
#define LDBM_ALLIDSLIMIT_AT "nsIDListScanLimit"
/* Name of attribute type used for binder-based look through simple paged limit */
#define LDBM_PAGEDLOOKTHROUGHLIMIT_AT "nsPagedLookThroughLimit"
diff --git a/ldap/servers/slapd/back-ldbm/idl.c b/ldap/servers/slapd/back-ldbm/idl.c
index 5d467bd..58736f8 100644
--- a/ldap/servers/slapd/back-ldbm/idl.c
+++ b/ldap/servers/slapd/back-ldbm/idl.c
@@ -1620,3 +1620,10 @@ make_cont_key( DBT *contkey, DBT *key, ID id )
sprintf( contkey->dptr, "%c%s%lu", CONT_PREFIX, (char *)key->dptr,
(u_long)id );
contkey->dsize = strlen( contkey->dptr ) + 1;
}
+
+int
+idl_sort_cmp(const void *x, const void *y)
+{
+ return *(ID *)x - *(ID *)y;
+}
+
diff --git a/ldap/servers/slapd/back-ldbm/index.c b/ldap/servers/slapd/back-ldbm/index.c
index a5c6ac5..5948717 100644
--- a/ldap/servers/slapd/back-ldbm/index.c
+++ b/ldap/servers/slapd/back-ldbm/index.c
@@ -1236,6 +1236,7 @@ index_range_read_ext(
time_t curtime, stoptime, optime;
int timelimit = -1;
back_search_result_set *sr = NULL;
+ int isroot = 0;
if (!pb) {
LDAPDebug(LDAP_DEBUG_ANY, "index_range_read: NULL pblock\n",
@@ -1270,11 +1271,11 @@ index_range_read_ext(
if (sr != NULL) {
/* the normal case */
lookthrough_limit = sr->sr_lookthroughlimit;
- } else {
- int isroot = 0;
- slapi_pblock_get( pb, SLAPI_REQUESTOR_ISROOT, &isroot );
- if (!isroot) {
- lookthrough_limit = li->li_lookthroughlimit;
+ }
+ slapi_pblock_get( pb, SLAPI_REQUESTOR_ISROOT, &isroot );
+ if (!isroot) {
+ if (lookthrough_limit > li->li_rangelookthroughlimit) {
+ lookthrough_limit = li->li_rangelookthroughlimit;
}
}
@@ -1478,7 +1479,7 @@ index_range_read_ext(
/* exit the loop when we either run off the end of the table,
* fail to read a key, or read a key that's out of range.
*/
- IDList *tmp, *tmp2;
+ IDList *tmp;
/*
char encbuf [BUFSIZ];
LDAPDebug( LDAP_DEBUG_FILTER, " cur_key=%s(%li bytes)\n",
@@ -1549,10 +1550,22 @@ index_range_read_ext(
encoded(&cur_key, encbuf), (long)cur_key.dsize);
}
} else {
- tmp2 = idl_union( be, idl, tmp );
- idl_free( idl );
- idl_free( tmp );
- idl = tmp2;
+ /* idl tmp only contains one id */
+ /* append it at the end here; sort idlist at the end */
+ if (ALLIDS(tmp)) {
+ idl_free(idl);
+ idl = tmp;
+ } else {
+ ID id;
+ for (id = idl_firstid(tmp); id != NOID; id = idl_nextid(tmp, id)) {
+ *err = idl_append_extend(&idl, id);
+ if (*err) {
+ ldbm_nasty("index_range_read - failed to generate
idlist",
+ 1097, *err);
+ }
+ }
+ idl_free(tmp);
+ }
if (ALLIDS(idl)) {
LDAPDebug(LDAP_DEBUG_TRACE, "index_range_read hit an allids
value\n",
0, 0, 0);
@@ -1601,6 +1614,12 @@ error:
dblayer_release_index_file( be, ai, db );
+ /* sort idl */
+ if (idl && !ALLIDS(idl)) {
+ qsort((void *)&idl->b_ids[0], idl->b_nids,
+ (size_t)sizeof(ID), idl_sort_cmp);
+ }
+
LDAPDebug( LDAP_DEBUG_TRACE, "<= index_range_read(%s,%s) %lu
candidates\n",
type, prefix, (u_long)IDL_NIDS(idl) );
return( idl );
diff --git a/ldap/servers/slapd/back-ldbm/ldbm_config.c
b/ldap/servers/slapd/back-ldbm/ldbm_config.c
index d0664eb..232af54 100644
--- a/ldap/servers/slapd/back-ldbm/ldbm_config.c
+++ b/ldap/servers/slapd/back-ldbm/ldbm_config.c
@@ -187,6 +187,28 @@ static int ldbm_config_pagedlookthroughlimit_set(void *arg, void
*value, char *e
return retval;
}
+static void *ldbm_config_rangelookthroughlimit_get(void *arg)
+{
+ struct ldbminfo *li = (struct ldbminfo *) arg;
+
+ return (void *) ((uintptr_t)(li->li_rangelookthroughlimit));
+}
+
+static int ldbm_config_rangelookthroughlimit_set(void *arg, void *value, char *errorbuf,
int phase, int apply)
+{
+ struct ldbminfo *li = (struct ldbminfo *) arg;
+ int retval = LDAP_SUCCESS;
+ int val = (int) ((uintptr_t)value);
+
+ /* Do whatever we can to make sure the data is ok. */
+
+ if (apply) {
+ li->li_rangelookthroughlimit = val;
+ }
+
+ return retval;
+}
+
static void *ldbm_config_mode_get(void *arg)
{
struct ldbminfo *li = (struct ldbminfo *) arg;
@@ -1341,6 +1363,7 @@ static config_info ldbm_config[] = {
{CONFIG_ENTRYRDN_NOANCESTORID, CONFIG_TYPE_ONOFF, "off",
&ldbm_config_entryrdn_noancestorid_get, &ldbm_config_entryrdn_noancestorid_set, 0
/* no show */},
{CONFIG_PAGEDLOOKTHROUGHLIMIT, CONFIG_TYPE_INT, "0",
&ldbm_config_pagedlookthroughlimit_get, &ldbm_config_pagedlookthroughlimit_set,
CONFIG_FLAG_ALWAYS_SHOW|CONFIG_FLAG_ALLOW_RUNNING_CHANGE},
{CONFIG_PAGEDIDLISTSCANLIMIT, CONFIG_TYPE_INT, "0",
&ldbm_config_pagedallidsthreshold_get, &ldbm_config_pagedallidsthreshold_set,
CONFIG_FLAG_ALWAYS_SHOW|CONFIG_FLAG_ALLOW_RUNNING_CHANGE},
+ {CONFIG_RANGELOOKTHROUGHLIMIT, CONFIG_TYPE_INT, "5000",
&ldbm_config_rangelookthroughlimit_get, &ldbm_config_rangelookthroughlimit_set,
CONFIG_FLAG_ALWAYS_SHOW|CONFIG_FLAG_ALLOW_RUNNING_CHANGE},
{NULL, 0, NULL, NULL, NULL, 0}
};
diff --git a/ldap/servers/slapd/back-ldbm/ldbm_config.h
b/ldap/servers/slapd/back-ldbm/ldbm_config.h
index 36b8f60..a5830e3 100644
--- a/ldap/servers/slapd/back-ldbm/ldbm_config.h
+++ b/ldap/servers/slapd/back-ldbm/ldbm_config.h
@@ -85,6 +85,7 @@ struct config_info {
#define CONFIG_INSTANCE "nsslapd-instance"
#define CONFIG_LOOKTHROUGHLIMIT "nsslapd-lookthroughlimit"
+#define CONFIG_RANGELOOKTHROUGHLIMIT "nsslapd-rangelookthroughlimit"
#define CONFIG_PAGEDLOOKTHROUGHLIMIT "nsslapd-pagedlookthroughlimit"
#define CONFIG_IDLISTSCANLIMIT "nsslapd-idlistscanlimit"
#define CONFIG_PAGEDIDLISTSCANLIMIT "nsslapd-pagedidlistscanlimit"
diff --git a/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
b/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
index be4120a..48b3164 100644
--- a/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
+++ b/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
@@ -235,6 +235,7 @@ int idl_is_allids(IDList *idl);
int idl_append(IDList *idl, ID id);
int idl_append_extend(IDList **idl, ID id);
void idl_insert(IDList **idl, ID id);
+int idl_sort_cmp(const void *x, const void *y);
/*
* idl_delete - delete an id from an id list.
* returns 0 id deleted
diff --git a/ldap/servers/slapd/back-ldbm/start.c b/ldap/servers/slapd/back-ldbm/start.c
index 0f42bed..4276c3b 100644
--- a/ldap/servers/slapd/back-ldbm/start.c
+++ b/ldap/servers/slapd/back-ldbm/start.c
@@ -116,6 +116,15 @@ ldbm_back_start( Slapi_PBlock *pb )
return SLAPI_FAIL_GENERAL;
}
+ /* lookthrough limit for the rangesearch */
+ if ( slapi_reslimit_register( SLAPI_RESLIMIT_TYPE_INT,
+ LDBM_RANGELOOKTHROUGHLIMIT_AT,
&li->li_reslimit_rangelookthrough_handle )
+ != SLAPI_RESLIMIT_STATUS_SUCCESS ) {
+ LDAPDebug( LDAP_DEBUG_ANY, "start: Resource limit registration failed for
rangelookthroughlimit\n",
+ 0, 0, 0 );
+ return SLAPI_FAIL_GENERAL;
+ }
+
/* If the db directory hasn't been set yet, we need to set it to
* the default. */
if (NULL == li->li_directory || '\0' == li->li_directory[0]) {
diff --git a/ldap/servers/slapd/back-ldbm/vlv.c b/ldap/servers/slapd/back-ldbm/vlv.c
index 7172104..39d16bf 100644
--- a/ldap/servers/slapd/back-ldbm/vlv.c
+++ b/ldap/servers/slapd/back-ldbm/vlv.c
@@ -1048,12 +1048,6 @@ vlv_build_candidate_list_byvalue( struct vlvIndex* p, DBC *dbc,
PRUint32 length,
return si;
}
-static int
-vlv_idl_sort_cmp(const void *x, const void *y)
-{
- return *(ID *)x - *(ID *)y;
-}
-
/* build a candidate list (IDL) from a VLV index, given the starting index
* and the ending index (as an inclusive list).
* returns 0 on success, or an LDAP error code.
@@ -1111,7 +1105,7 @@ int vlv_build_idl(PRUint32 start, PRUint32 stop, DB *db, DBC *dbc,
if (dosort)
{
qsort((void *)&idl->b_ids[0], idl->b_nids,
- (size_t)sizeof(ID), vlv_idl_sort_cmp);
+ (size_t)sizeof(ID), idl_sort_cmp);
}
*candidates = idl;