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 f026ef0447b18994e0e9b847698703436e874f84
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.
diff --git a/ldap/servers/slapd/back-ldbm/back-ldbm.h
b/ldap/servers/slapd/back-ldbm/back-ldbm.h
index 39fd950..6536664 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
@@ -817,6 +818,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 4227055..65fca7c 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 daf6d05..40fa325 100644
--- a/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
+++ b/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
@@ -241,6 +241,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 cf68bb3..3131661 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;