Resolves: #447353

Summary: RFE: search optimization and single character substring searches
Description: extended the substring key to have 3 types:
* begin (e.g., *^a)
* middle (e.g., *abc)
* end (e.g., *xy$)
* Usage: turn an index object to extensibleobject and set an integer value as
follows:
* dn: cn=sn, cn=index, cn=userRoot, cn=ldbm database, cn=plugins, cn=config
* objectClass: extensibleObject
* nsSubStrBegin: 2
* nsSubStrMiddle: 3
* nsSubStrEnd: 2
* [...]

10 files changed, 372 insertions, 128 deletions

diff --git a/ldap/servers/plugins/syntaxes/string.c b/ldap/servers/plugins/syntaxes/string.c
index 315610d8..c9477cce 100644
--- a/ldap/servers/plugins/syntaxes/string.c
+++ b/ldap/servers/plugins/syntaxes/string.c
@@ -50,10 +50,12 @@
 #include <unistd.h>
 #endif
 
+#define MAX_VAL(x,y)                    ((x)>(y)?(x):(y))
+
 static int string_filter_approx( struct berval *bvfilter,
 	Slapi_Value **bvals, Slapi_Value **retVal );
 static void substring_comp_keys( Slapi_Value ***ivals, int *nsubs, char *str,
-	int prepost, int syntax );
+	int prepost, int syntax, char *comp_buf, int substrlen );
 
 int
 string_filter_ava( struct berval *bvfilter, Slapi_Value **bvals, int syntax,
@@ -294,7 +296,7 @@ string_filter_sub( Slapi_PBlock *pb, char *initial, char **any, char *final,
 	for ( j = 0; bvals[j] != NULL; j++ ) {
 		int	tmprc;
 		size_t	len;
-                const struct berval *bvp = slapi_value_get_berval(bvals[j]);
+		const struct berval *bvp = slapi_value_get_berval(bvals[j]);
 
 		len = bvp->bv_len;
 		if ( len < sizeof(buf) ) {
@@ -392,8 +394,53 @@ string_values2keys( Slapi_PBlock *pb, Slapi_Value **bvals,
 		/* XXX should remove duplicates! XXX */
 		Slapi_Value *bvdup;
 		const struct berval *bvp;
-		char buf[SUBLEN+1];
+		char *buf;
 		int i;
+		int *substrlens = NULL;
+		int localsublens[3] = {SUBBEGIN, SUBMIDDLE, SUBEND};/* default values */
+		int maxsublen;
+		/*
+ 		 * Substring key has 3 types:
+		 * begin (e.g., *^a)
+		 * middle (e.g., *abc)
+		 * end (e.g., *xy$)
+		 *
+		 * the each has its own key length, which can be configured as follows:
+ 		 * Usage: turn an index object to extensibleobject and 
+ 		 *        set an integer value for each.
+ 		 * dn: cn=sn, cn=index, cn=userRoot, cn=ldbm database, cn=plugins, 
+		 *  cn=config
+ 		 * objectClass: extensibleObject
+ 		 * nsSubStrBegin: 2
+ 		 * nsSubStrMiddle: 3
+ 		 * nsSubStrEnd: 2
+ 		 * [...]
+ 		 * 
+ 		 * By default, begin == 2, middle == 3, end == 2 (defined in syntax.h)
+		 */
+
+		/* If nsSubStrLen is specified in each index entry,
+		   respect the length for the substring index key length.
+		   Otherwise, the deafult value SUBLEN is used */
+		slapi_pblock_get(pb, SLAPI_SYNTAX_SUBSTRLENS, &substrlens);
+
+		if (NULL == substrlens) {
+			substrlens = localsublens;
+		}
+		if (0 == substrlens[INDEX_SUBSTRBEGIN]) {
+			substrlens[INDEX_SUBSTRBEGIN] = SUBBEGIN;
+		}
+		if (0 == substrlens[INDEX_SUBSTRMIDDLE]) {
+			substrlens[INDEX_SUBSTRMIDDLE] = SUBMIDDLE;
+		}
+		if (0 == substrlens[INDEX_SUBSTREND]) {
+			substrlens[INDEX_SUBSTREND] = SUBEND;
+		}
+		maxsublen = MAX_VAL(substrlens[INDEX_SUBSTRBEGIN], substrlens[INDEX_SUBSTRMIDDLE]);
+		maxsublen = MAX_VAL(maxsublen, substrlens[INDEX_SUBSTREND]);
+
+		buf = (char *)slapi_ch_calloc(1, maxsublen + 1);
+
 		nsubs = 0;
 		for ( bvlp = bvals; bvlp && *bvlp; bvlp++ ) {
 			/*
@@ -407,11 +454,11 @@ string_values2keys( Slapi_PBlock *pb, Slapi_Value **bvals,
 			 * the only downside is that we allocate more space than
 			 * we really need.
 			 */
-			nsubs += slapi_value_get_length(*bvlp) - SUBLEN + 3;
+			nsubs += slapi_value_get_length(*bvlp) - substrlens[INDEX_SUBSTRMIDDLE] + 3;
 		}
+		nsubs += substrlens[INDEX_SUBSTRMIDDLE] * 2 - substrlens[INDEX_SUBSTRBEGIN] - substrlens[INDEX_SUBSTREND];
 		*ivals = (Slapi_Value **) slapi_ch_calloc( (nsubs + 1), sizeof(Slapi_Value *) );
 
-		buf[SUBLEN] = '\0';
 		n = 0;
 
 		bvdup= slapi_value_new(); 
@@ -423,39 +470,42 @@ string_values2keys( Slapi_PBlock *pb, Slapi_Value **bvals,
 			bvp = slapi_value_get_berval(bvdup);
 
 			/* leading */
-			if ( bvp->bv_len > SUBLEN - 2 ) {
+			if ( bvp->bv_len > substrlens[INDEX_SUBSTRBEGIN] - 2 ) {
 				buf[0] = '^';
-				for ( i = 0; i < SUBLEN - 1; i++ ) {
+				for ( i = 0; i < substrlens[INDEX_SUBSTRBEGIN] - 1; i++ ) {
 					buf[i + 1] = bvp->bv_val[i];
 				}
+				buf[substrlens[INDEX_SUBSTRBEGIN]] = '\0';
 				(*ivals)[n] = slapi_value_new_string(buf);
 				n++;
 			}
 
 			/* any */
 			for ( p = bvp->bv_val;
-			    p < (bvp->bv_val + bvp->bv_len - SUBLEN + 1);
+			    p < (bvp->bv_val + bvp->bv_len - substrlens[INDEX_SUBSTRMIDDLE] + 1);
 			    p++ ) {
-				for ( i = 0; i < SUBLEN; i++ ) {
+				for ( i = 0; i < substrlens[INDEX_SUBSTRMIDDLE]; i++ ) {
 					buf[i] = p[i];
 				}
-				buf[SUBLEN] = '\0';
+				buf[substrlens[INDEX_SUBSTRMIDDLE]] = '\0';
 				(*ivals)[n] = slapi_value_new_string(buf);
 				n++;
 			}
 
 			/* trailing */
-			if ( bvp->bv_len > SUBLEN - 2 ) {
-				p = bvp->bv_val + bvp->bv_len - SUBLEN + 1;
-				for ( i = 0; i < SUBLEN - 1; i++ ) {
+			if ( bvp->bv_len > substrlens[INDEX_SUBSTREND] - 2 ) {
+				p = bvp->bv_val + bvp->bv_len - substrlens[INDEX_SUBSTREND] + 1;
+				for ( i = 0; i < substrlens[INDEX_SUBSTREND] - 1; i++ ) {
 					buf[i] = p[i];
 				}
-				buf[SUBLEN - 1] = '$';
+				buf[substrlens[INDEX_SUBSTREND] - 1] = '$';
+				buf[substrlens[INDEX_SUBSTREND]] = '\0';
 				(*ivals)[n] = slapi_value_new_string(buf);
 				n++;
 			}
 		}
 		slapi_value_free(&bvdup);
+		slapi_ch_free_string(&buf);
 		}
 		break;
 	}
@@ -548,6 +598,25 @@ string_assertion2keys_sub(
 )
 {
 	int		nsubs, i, len;
+	int *substrlens = NULL;
+	int localsublens[3] = {SUBBEGIN, SUBMIDDLE, SUBEND};/* default values */
+	int maxsublen;
+	char	*comp_buf = NULL;
+
+	slapi_pblock_get(pb, SLAPI_SYNTAX_SUBSTRLENS, &substrlens);
+
+	if (NULL == substrlens) {
+		substrlens = localsublens;
+	}
+	if (0 == substrlens[INDEX_SUBSTRBEGIN]) {
+		substrlens[INDEX_SUBSTRBEGIN] = SUBBEGIN;
+	}
+	if (0 == substrlens[INDEX_SUBSTRMIDDLE]) {
+		substrlens[INDEX_SUBSTRMIDDLE] = SUBMIDDLE;
+	}
+	if (0 == substrlens[INDEX_SUBSTREND]) {
+		substrlens[INDEX_SUBSTREND] = SUBEND;
+	}
 
 	*ivals = NULL;
 
@@ -561,8 +630,8 @@ string_assertion2keys_sub(
 	nsubs = 0;
 	if ( initial != NULL ) {
 		value_normalize( initial, syntax, 0 /* do not trim leading blanks */ );
-		if ( strlen( initial ) > SUBLEN - 2 ) {
-			nsubs += strlen( initial ) - SUBLEN + 2;
+		if ( strlen( initial ) > substrlens[INDEX_SUBSTRBEGIN] - 2 ) {
+			nsubs += strlen( initial ) - substrlens[INDEX_SUBSTRBEGIN] + 2;
 		} else {
 			initial = NULL;	/* save some work later */
 		}
@@ -570,14 +639,14 @@ string_assertion2keys_sub(
 	for ( i = 0; any != NULL && any[i] != NULL; i++ ) {
 		value_normalize( any[i], syntax, 0 /* do not trim leading blanks */ );
 		len = strlen( any[i] );
-		if ( len >= SUBLEN ) {
-			nsubs += len - SUBLEN + 1;
+		if ( len >= substrlens[INDEX_SUBSTRMIDDLE] ) {
+			nsubs += len - substrlens[INDEX_SUBSTRMIDDLE] + 1;
 		}
 	}
 	if ( final != NULL ) {
 		value_normalize( final, syntax, 0 /* do not trim leading blanks */ );
-		if ( strlen( final ) > SUBLEN - 2 ) {
-			nsubs += strlen( final ) - SUBLEN + 2;
+		if ( strlen( final ) > substrlens[INDEX_SUBSTREND] - 2 ) {
+			nsubs += strlen( final ) - substrlens[INDEX_SUBSTREND] + 2;
 		} else {
 			final = NULL; /* save some work later */
 		}
@@ -592,21 +661,29 @@ string_assertion2keys_sub(
 	 */
 
 	*ivals = (Slapi_Value **) slapi_ch_malloc( (nsubs + 1) * sizeof(Slapi_Value *) );
+	
+	maxsublen = MAX_VAL(substrlens[INDEX_SUBSTRBEGIN], substrlens[INDEX_SUBSTRMIDDLE]);
+	maxsublen = MAX_VAL(maxsublen, substrlens[INDEX_SUBSTREND]);
 
 	nsubs = 0;
+	comp_buf = (char *)slapi_ch_malloc(maxsublen + 1);
 	if ( initial != NULL ) {
-		substring_comp_keys( ivals, &nsubs, initial, '^', syntax );
+		substring_comp_keys( ivals, &nsubs, initial, '^', syntax,
+							 comp_buf, substrlens[INDEX_SUBSTRBEGIN] );
 	}
 	for ( i = 0; any != NULL && any[i] != NULL; i++ ) {
-		if ( strlen( any[i] ) < SUBLEN ) {
+		if ( strlen( any[i] ) < substrlens[INDEX_SUBSTRMIDDLE] ) {
 			continue;
 		}
-		substring_comp_keys( ivals, &nsubs, any[i], 0, syntax );
+		substring_comp_keys( ivals, &nsubs, any[i], 0, syntax,
+							 comp_buf, substrlens[INDEX_SUBSTRMIDDLE] );
 	}
 	if ( final != NULL ) {
-		substring_comp_keys( ivals, &nsubs, final, '$', syntax );
+		substring_comp_keys( ivals, &nsubs, final, '$', syntax,
+							 comp_buf, substrlens[INDEX_SUBSTREND] );
 	}
 	(*ivals)[nsubs] = NULL;
+	slapi_ch_free_string(&comp_buf);
 
 	return( 0 );
 }
@@ -617,12 +694,15 @@ substring_comp_keys(
     int			*nsubs,
     char		*str,
     int			prepost,
-    int			syntax
+    int			syntax,
+	char		*comp_buf,
+	int			substrlen
 )
 {
     int     i, len;
     char    *p;
-    char    buf[SUBLEN + 1];
+
+	PR_ASSERT(NULL != comp_buf);
 
     LDAPDebug( LDAP_DEBUG_TRACE, "=> substring_comp_keys (%s) %d\n",
         str, prepost, 0 );
@@ -632,37 +712,37 @@ substring_comp_keys(
     /* prepend ^ for initial substring */
     if ( prepost == '^' )
     {
-		buf[0] = '^';
-		for ( i = 0; i < SUBLEN - 1; i++ )
+		comp_buf[0] = '^';
+		for ( i = 0; i < substrlen - 1; i++ )
 		{
-			buf[i + 1] = str[i];
+			comp_buf[i + 1] = str[i];
 		}
-		buf[SUBLEN] = '\0';
-		(*ivals)[*nsubs] = slapi_value_new_string(buf);
+		comp_buf[substrlen] = '\0';
+		(*ivals)[*nsubs] = slapi_value_new_string(comp_buf);
 		(*nsubs)++;
     }
 
-    for ( p = str; p < (str + len - SUBLEN + 1); p++ )
+    for ( p = str; p < (str + len - substrlen + 1); p++ )
     {
-		for ( i = 0; i < SUBLEN; i++ )
+		for ( i = 0; i < substrlen; i++ )
 		{
-			buf[i] = p[i];
+			comp_buf[i] = p[i];
 		}
-		buf[SUBLEN] = '\0';
-		(*ivals)[*nsubs] = slapi_value_new_string(buf);
+		comp_buf[substrlen] = '\0';
+		(*ivals)[*nsubs] = slapi_value_new_string(comp_buf);
 		(*nsubs)++;
     }
 
 	if ( prepost == '$' )
 	{
-		p = str + len - SUBLEN + 1;
-		for ( i = 0; i < SUBLEN - 1; i++ )
+		p = str + len - substrlen + 1;
+		for ( i = 0; i < substrlen - 1; i++ )
 		{
-			buf[i] = p[i];
+			comp_buf[i] = p[i];
 		}
-		buf[SUBLEN - 1] = '$';
-		buf[SUBLEN] = '\0';
-		(*ivals)[*nsubs] = slapi_value_new_string(buf);
+		comp_buf[substrlen - 1] = '$';
+		comp_buf[substrlen] = '\0';
+		(*ivals)[*nsubs] = slapi_value_new_string(comp_buf);
 		(*nsubs)++;
     }
 
diff --git a/ldap/servers/slapd/back-ldbm/back-ldbm.h b/ldap/servers/slapd/back-ldbm/back-ldbm.h
index 2af305fe..6dcca5b4 100644
--- a/ldap/servers/slapd/back-ldbm/back-ldbm.h
+++ b/ldap/servers/slapd/back-ldbm/back-ldbm.h
@@ -346,6 +346,34 @@ typedef struct dblayer_private_env dblayer_private_env;
 typedef struct idl_private idl_private;
 typedef struct attrcrypt_private attrcrypt_private;
 
+/*
+ * Special attribute for an index entry 
+ * Usage: turn an index object to extensibleobject and 
+ *        set an integer value for each
+ * dn: cn=sn, cn=index, cn=userRoot, cn=ldbm database, cn=plugins, cn=config
+ * objectClass: extensibleObject
+ * nsSubStrBegin: 2
+ * nsSubStrMiddle: 3
+ * nsSubStrEnd: 2
+ * [...]
+ * 
+ * By default, the minimum key length triplets of substring index is 2, 3, 2.
+ * The length is changed by setting this nsSubStrLen value.
+ *
+ * Note: If any of the key length value is modified, the index file needs
+ * to be regenerated.  Otherwise, the index file is going to have mixed
+ * key length.
+ * To change the key length,
+ * 1) stop the server, 2) run db2index -t <attr>, 3) start the server.
+ */
+#define INDEX_ATTR_SUBSTRBEGIN	"nsSubStrBegin"
+#define INDEX_ATTR_SUBSTRMIDDLE	"nsSubStrMiddle"
+#define INDEX_ATTR_SUBSTREND	"nsSubStrEnd"
+
+#define INDEX_SUBSTRBEGIN	0
+#define INDEX_SUBSTRMIDDLE	1
+#define INDEX_SUBSTREND		2
+
 
 /* for the cache of attribute information (which are indexed, etc.) */
 struct attrinfo {
@@ -382,6 +410,10 @@ struct attrinfo {
 											specify an ORDERING matching rule, or the index
 											configuration must define an ORDERING matching rule.
 										 */
+	int	*ai_substr_lens;	/* if the attribute nsSubStrXxx is specivied in
+							 * an index instance (dse.ldif), the substr key 
+							 * len value(s) are stored here.  If not specified, 
+							 * the default length triplet is 2, 3, 2.
 };
 
 #define MAXDBCACHE	20
diff --git a/ldap/servers/slapd/back-ldbm/index.c b/ldap/servers/slapd/back-ldbm/index.c
index 92e973ce..49c8eda2 100644
--- a/ldap/servers/slapd/back-ldbm/index.c
+++ b/ldap/servers/slapd/back-ldbm/index.c
@@ -1830,8 +1830,13 @@ index_addordel_values_ext_sv(
         Slapi_Value	**esubvals = NULL;
         Slapi_Value	**substresult = NULL;
         Slapi_Value   **origvals = NULL;
-        slapi_call_syntax_values2keys_sv( ai->ai_plugin, vals, &ivals, 
-                                          LDAP_FILTER_SUBSTRINGS );
+		Slapi_PBlock		pipb;
+
+		/* prepare pblock to pass ai_substr_lens */
+		pblock_init( &pipb );
+		slapi_pblock_set( &pipb, SLAPI_SYNTAX_SUBSTRLENS, ai->ai_substr_lens );
+        slapi_call_syntax_values2keys_sv_pb( ai->ai_plugin, vals, &ivals, 
+                                          LDAP_FILTER_SUBSTRINGS, &pipb );
 
         origvals = ivals;
         /* delete only: if the attribute has multiple values,
@@ -1840,8 +1845,8 @@ index_addordel_values_ext_sv(
          * then get rid of them from the being deleted values
          */
         if ( evals != NULL ) {
-            slapi_call_syntax_values2keys_sv( ai->ai_plugin, evals, &esubvals, 
-                                              LDAP_FILTER_SUBSTRINGS );
+            slapi_call_syntax_values2keys_sv_pb( ai->ai_plugin, evals,
+							&esubvals, LDAP_FILTER_SUBSTRINGS, &pipb );
             substresult = valuearray_minus_valuearray( ai->ai_plugin, ivals, esubvals );
             ivals = substresult;
             valuearray_free( &esubvals );
diff --git a/ldap/servers/slapd/back-ldbm/ldbm_attr.c b/ldap/servers/slapd/back-ldbm/ldbm_attr.c
index 28b79f19..520bca91 100644
--- a/ldap/servers/slapd/back-ldbm/ldbm_attr.c
+++ b/ldap/servers/slapd/back-ldbm/ldbm_attr.c
@@ -50,14 +50,6 @@ struct attrinfo *
 attrinfo_new()
 {
     struct attrinfo *p= (struct attrinfo *)slapi_ch_calloc(1, sizeof(struct attrinfo));
-	p->ai_type= 0;
-	p->ai_indexmask= 0;
-	p->ai_plugin= NULL;
-	p->ai_index_rules= NULL;
-	p->ai_dblayer= NULL;
-        p->ai_dblayer_count = 0;
-	p->ai_idl= NULL;
-	p->ai_key_cmp_fn = NULL;
     return p;
 }
 
@@ -156,6 +148,25 @@ ainfo_get(
 }
 
 void
+_set_attr_substrlen(int index, char *str, int **substrlens)
+{
+	char *p = NULL;
+	/* nsSubStrXxx=<VAL> is passed; 
+	   set it to the attribute's plugin */
+	p = strchr(str, '=');
+	if (NULL != p) {
+		long sublen = strtol(++p, (char **)NULL, 10);
+		if (sublen > 0) {	/* 0 is not acceptable */
+			if (NULL == *substrlens) {
+				*substrlens = (int *)slapi_ch_calloc(1, 
+												sizeof(int) * INDEX_SUBSTRLEN);
+			}
+			(*substrlens)[index] = sublen;
+		}
+	}
+}
+
+void
 attr_index_config(
     backend *be,
     char		*fname,
@@ -172,6 +183,8 @@ attr_index_config(
 	char	**index_rules = NULL;
 	struct attrinfo	*a;
 	int return_value = -1;
+	char    *p;
+	int *substrlens = NULL;
 
 	attrs = str2charray( argv[0], "," );
 	if ( argc > 1 ) {
@@ -189,34 +202,29 @@ attr_index_config(
 		attrsyntax_oid = slapi_ch_strdup(plugin_syntax2oid(a->ai_plugin));
 		if ( argc == 1 ) {
 			a->ai_indexmask = (INDEX_PRESENCE | INDEX_EQUALITY |
-			    INDEX_APPROX | INDEX_SUB);
+				INDEX_APPROX | INDEX_SUB);
 		} else {
 			a->ai_indexmask = 0;
 			for ( j = 0; indexes[j] != NULL; j++ ) {
-				if ( strncasecmp( indexes[j], "pres", 4 )
-				    == 0 ) {
+				if ( strncasecmp( indexes[j], "pres", 4 ) == 0 ) {
 					a->ai_indexmask |= INDEX_PRESENCE;
-				} else if ( strncasecmp( indexes[j], "eq", 2 )
-				    == 0 ) {
+				} else if ( strncasecmp( indexes[j], "eq", 2 ) == 0 ) {
 					a->ai_indexmask |= INDEX_EQUALITY;
-				} else if ( strncasecmp( indexes[j], "approx",
-				    6 ) == 0 ) {
+				} else if ( strncasecmp( indexes[j], "approx", 6 ) == 0 ) {
 					a->ai_indexmask |= INDEX_APPROX;
-				} else if ( strncasecmp( indexes[j], "sub", 3 )
-				    == 0 ) {
+				} else if ( strncasecmp( indexes[j], "sub", 3 ) == 0 ) {
 					a->ai_indexmask |= INDEX_SUB;
-				} else if ( strncasecmp( indexes[j], "none", 4 )
-				    == 0 ) {
+				} else if ( strncasecmp( indexes[j], "none", 4 ) == 0 ) {
 					if ( a->ai_indexmask != 0 ) {
 						LDAPDebug(LDAP_DEBUG_ANY,
 							"%s: line %d: index type \"none\" cannot be combined with other types\n",
-						    fname, lineno, 0);
+							fname, lineno, 0);
 					}
 					a->ai_indexmask = INDEX_OFFLINE; /* note that the index isn't available */
 				} else {
 					LDAPDebug(LDAP_DEBUG_ANY,
 						"%s: line %d: unknown index type \"%s\" (ignored)\n",
-					    fname, lineno, indexes[j]);
+						fname, lineno, indexes[j]);
 					LDAPDebug(LDAP_DEBUG_ANY,
 						"valid index types are \"pres\", \"eq\", \"approx\", or \"sub\"\n",
 						0, 0, 0);
@@ -227,53 +235,66 @@ attr_index_config(
 			j = 0;
 			if (index_rules != NULL) for (; index_rules[j] != NULL; ++j);
 			if (j > 0) { /* there are some candidates */
-			    char** official_rules = (char**)
-			      slapi_ch_malloc ((j + 1) * sizeof (char*));
-			    size_t k = 0;
-			    for (j = 0; index_rules[j] != NULL; ++j) {
-				/* Check that index_rules[j] is an official OID */
-				char* officialOID = NULL;
-				IFP mrINDEX = NULL;
-				Slapi_PBlock* pb = slapi_pblock_new();
-				if (!slapi_pblock_set (pb, SLAPI_PLUGIN_MR_OID, index_rules[j]) &&
-				    !slapi_pblock_set (pb, SLAPI_PLUGIN_MR_TYPE, a->ai_type) &&
-				    !slapi_mr_indexer_create (pb) &&
-				    !slapi_pblock_get (pb, SLAPI_PLUGIN_MR_INDEX_FN, &mrINDEX) &&
-				    mrINDEX != NULL &&
-				    !slapi_pblock_get (pb, SLAPI_PLUGIN_MR_OID, &officialOID) &&
-				    officialOID != NULL) {
-				    if (!strcasecmp (index_rules[j], officialOID)) {
-					official_rules[k++] = slapi_ch_strdup (officialOID);
-				    } else {
-					char* preamble = slapi_ch_smprintf("%s: line %d", fname, lineno);
-					LDAPDebug (LDAP_DEBUG_ANY, "%s: use \"%s\" instead of \"%s\" (ignored)\n",
-						   preamble, officialOID, index_rules[j] );
-					slapi_ch_free((void**)&preamble);
-				    }
-				} else if (!slapi_matchingrule_is_ordering(index_rules[j], attrsyntax_oid)) {
-				    LDAPDebug (LDAP_DEBUG_ANY, "%s: line %d: "
-					       "unknown or invalid matching rule \"%s\" in index configuration (ignored)\n",
-					       fname, lineno, index_rules[j] );
-				} else { /* assume builtin and use compare fn provided by syntax plugin */
-				    need_compare_fn = 1;
+				char** official_rules =
+						(char**)slapi_ch_malloc ((j + 1) * sizeof (char*));
+				size_t k = 0;
+				for (j = 0; index_rules[j] != NULL; ++j) {
+					/* Check that index_rules[j] is an official OID */
+					char* officialOID = NULL;
+					IFP mrINDEX = NULL;
+					Slapi_PBlock* pb = slapi_pblock_new();
+					if (!slapi_pblock_set (pb, SLAPI_PLUGIN_MR_OID, index_rules[j]) &&
+						!slapi_pblock_set (pb, SLAPI_PLUGIN_MR_TYPE, a->ai_type) &&
+						!slapi_mr_indexer_create (pb) &&
+						!slapi_pblock_get (pb, SLAPI_PLUGIN_MR_INDEX_FN, &mrINDEX) &&
+						mrINDEX != NULL &&
+						!slapi_pblock_get (pb, SLAPI_PLUGIN_MR_OID, &officialOID) &&
+						officialOID != NULL) {
+						if (!strcasecmp (index_rules[j], officialOID)) {
+						official_rules[k++] = slapi_ch_strdup (officialOID);
+						} else {
+						char* preamble = slapi_ch_smprintf("%s: line %d", fname, lineno);
+						LDAPDebug (LDAP_DEBUG_ANY, "%s: use \"%s\" instead of \"%s\" (ignored)\n",
+							   preamble, officialOID, index_rules[j] );
+						slapi_ch_free((void**)&preamble);
+						}
+					} else if (p =
+							   strstr(index_rules[j], INDEX_ATTR_SUBSTRBEGIN)) {
+						_set_attr_substrlen(INDEX_SUBSTRBEGIN, index_rules[j],
+											&substrlens);
+					} else if (p =
+							   strstr(index_rules[j], INDEX_ATTR_SUBSTRMIDDLE)) {
+						_set_attr_substrlen(INDEX_SUBSTRMIDDLE, index_rules[j],
+											&substrlens);
+					} else if (p =
+							   strstr(index_rules[j], INDEX_ATTR_SUBSTREND)) {
+						_set_attr_substrlen(INDEX_SUBSTREND, index_rules[j],
+											&substrlens);
+					} else if (!slapi_matchingrule_is_ordering(index_rules[j], attrsyntax_oid)) {
+						LDAPDebug (LDAP_DEBUG_ANY, "%s: line %d: "
+							   "unknown or invalid matching rule \"%s\" in index configuration (ignored)\n",
+							   fname, lineno, index_rules[j] );
+					} else { /* assume builtin and use compare fn provided by syntax plugin */
+						need_compare_fn = 1;
+					}
+					{/* It would improve speed to save the indexer, for future use.
+						But, for simplicity, we destroy it now: */
+						IFP mrDESTROY = NULL;
+						if (!slapi_pblock_get (pb, SLAPI_PLUGIN_DESTROY_FN, &mrDESTROY) &&
+						mrDESTROY != NULL) {
+						mrDESTROY (pb);
+						}
+					}
+					slapi_pblock_destroy (pb);
 				}
-				{/* It would improve speed to save the indexer, for future use.
-				    But, for simplicity, we destroy it now: */
-				    IFP mrDESTROY = NULL;
-				    if (!slapi_pblock_get (pb, SLAPI_PLUGIN_DESTROY_FN, &mrDESTROY) &&
-					mrDESTROY != NULL) {
-					mrDESTROY (pb);
-				    }
+				official_rules[k] = NULL;
+				a->ai_substr_lens = substrlens;
+				if (k > 0) {
+					a->ai_index_rules = official_rules;
+					a->ai_indexmask |= INDEX_RULES;
+				} else {
+					slapi_ch_free((void**)&official_rules);
 				}
-				slapi_pblock_destroy (pb);
-			    }
-			    official_rules[k] = NULL;
-			    if (k > 0) {
-				a->ai_index_rules = official_rules;
-				a->ai_indexmask |= INDEX_RULES;
-			    } else {
-				slapi_ch_free((void**)&official_rules);
-			    }
 			}
 		}
 
@@ -283,7 +304,7 @@ attr_index_config(
 		if (0 != return_value) {
 			/* fatal error, exit */
 			LDAPDebug(LDAP_DEBUG_ANY,"%s: line %d:Fatal Error: Failed to initialize attribute structure\n",
-			    fname, lineno, 0);
+				fname, lineno, 0);
 			exit( 1 );
 		}
 
@@ -300,24 +321,24 @@ attr_index_config(
 		if (need_compare_fn) {
 			int rc = plugin_call_syntax_get_compare_fn( a->ai_plugin, &a->ai_key_cmp_fn );
 			if (rc != LDAP_SUCCESS) {
-			    LDAPDebug(LDAP_DEBUG_ANY,
-				      "The attribute [%s] does not have a valid ORDERING matching rule\n",
-				      a->ai_type, 0, 0);
+				LDAPDebug(LDAP_DEBUG_ANY,
+					  "The attribute [%s] does not have a valid ORDERING matching rule\n",
+					  a->ai_type, 0, 0);
 				a->ai_key_cmp_fn = NULL;
 			}
 		}
 
 		if ( avl_insert( &inst->inst_attrs, a, ainfo_cmp, ainfo_dup ) != 0 ) {
 			/* duplicate - existing version updated */
-            attrinfo_delete(&a);
+			attrinfo_delete(&a);
 		}
 	}
 	charray_free( attrs );
 	if ( indexes != NULL ) {
-	    charray_free( indexes );
+		charray_free( indexes );
 	}
 	if ( index_rules != NULL ) {
-	    charray_free( index_rules );
+		charray_free( index_rules );
 	}
 }
 
diff --git a/ldap/servers/slapd/back-ldbm/ldbm_index_config.c b/ldap/servers/slapd/back-ldbm/ldbm_index_config.c
index df8e0dda..f86d7aa9 100644
--- a/ldap/servers/slapd/back-ldbm/ldbm_index_config.c
+++ b/ldap/servers/slapd/back-ldbm/ldbm_index_config.c
@@ -122,7 +122,7 @@ static char *attrinfo2ConfMatchingRules (struct attrinfo *pai)
 /* used by the two callbacks below, to parse an index entry into something
  * awkward that we can pass to attr_index_config().
  */
-#define MAX_TMPBUF      256
+#define MAX_TMPBUF      1024
 #define ZCAT_SAFE(_buf, _x1, _x2) do { \
     if (strlen(_buf) + strlen(_x1) + strlen(_x2) + 2 < MAX_TMPBUF) { \
         strcat(_buf, _x1); \
@@ -170,18 +170,71 @@ static int ldbm_index_parse_entry(ldbm_instance *inst, Slapi_Entry *e,
         arglist[argc++] = slapi_ch_strdup(tmpBuf);
     }
 
+    tmpBuf[0] = 0;
     /* Get the list of matching rules from the entry. */
     if (0 == slapi_entry_attr_find(e, "nsMatchingRule", &attr)) {
         for (i = slapi_attr_first_value(attr, &sval); i != -1;
              i = slapi_attr_next_value(attr, i, &sval)) {
             attrValue = slapi_value_get_berval(sval);
             if (0 == i) {
-                tmpBuf[0] = 0;
                 ZCAT_SAFE(tmpBuf, "", attrValue->bv_val);
             } else {
                 ZCAT_SAFE(tmpBuf, ",", attrValue->bv_val);
             }
         }
+    }
+
+    /* Get the substr begin length. note: pick the first value. */
+    if (0 == slapi_entry_attr_find(e, INDEX_ATTR_SUBSTRBEGIN, &attr)) {
+        i = slapi_attr_first_value(attr, &sval);
+        if (-1 != i) {
+            attrValue = slapi_value_get_berval(sval);
+            if (0 == tmpBuf[0]) {
+                PR_snprintf(tmpBuf, MAX_TMPBUF, "%s=%s",
+                            INDEX_ATTR_SUBSTRBEGIN,  attrValue->bv_val);
+            } else {
+                int tmpbuflen = strlen(tmpBuf);
+                char *p = tmpBuf + tmpbuflen;
+                PR_snprintf(p, MAX_TMPBUF - tmpbuflen, ",%s=%s",
+                            INDEX_ATTR_SUBSTRBEGIN,  attrValue->bv_val);
+            }
+        }
+    }
+
+    /* Get the substr middle length. note: pick the first value. */
+    if (0 == slapi_entry_attr_find(e, INDEX_ATTR_SUBSTRMIDDLE, &attr)) {
+        i = slapi_attr_first_value(attr, &sval);
+        if (-1 != i) {
+            attrValue = slapi_value_get_berval(sval);
+            if (0 == tmpBuf[0]) {
+                PR_snprintf(tmpBuf, MAX_TMPBUF, "%s=%s",
+                            INDEX_ATTR_SUBSTRMIDDLE,  attrValue->bv_val);
+            } else {
+                int tmpbuflen = strlen(tmpBuf);
+                char *p = tmpBuf + tmpbuflen;
+                PR_snprintf(p, MAX_TMPBUF - tmpbuflen, ",%s=%s",
+                            INDEX_ATTR_SUBSTRMIDDLE,  attrValue->bv_val);
+            }
+        }
+    }
+
+    /* Get the substr end length. note: pick the first value. */
+    if (0 == slapi_entry_attr_find(e, INDEX_ATTR_SUBSTREND, &attr)) {
+        i = slapi_attr_first_value(attr, &sval);
+        if (-1 != i) {
+            attrValue = slapi_value_get_berval(sval);
+            if (0 == tmpBuf[0]) {
+                PR_snprintf(tmpBuf, MAX_TMPBUF, "%s=%s",
+                            INDEX_ATTR_SUBSTREND,  attrValue->bv_val);
+            } else {
+                int tmpbuflen = strlen(tmpBuf);
+                char *p = tmpBuf + tmpbuflen;
+                PR_snprintf(p, MAX_TMPBUF - tmpbuflen, ",%s=%s",
+                            INDEX_ATTR_SUBSTREND,  attrValue->bv_val);
+            }
+        }
+    }
+    if (0 != tmpBuf[0]) {
         arglist[argc++] = slapi_ch_strdup(tmpBuf);
     }
 
diff --git a/ldap/servers/slapd/pblock.c b/ldap/servers/slapd/pblock.c
index 987b2476..b6076b35 100644
--- a/ldap/servers/slapd/pblock.c
+++ b/ldap/servers/slapd/pblock.c
@@ -1059,6 +1059,9 @@ slapi_pblock_get( Slapi_PBlock *pblock, int arg, void *value )
 		}
 		(*(IFP *)value) = pblock->pb_plugin->plg_syntax_compare;
 		break;
+	case SLAPI_SYNTAX_SUBSTRLENS:
+		(*(int **)value) = pblock->pb_substrlens;
+		break;
 
 	/* controls we know about */
 	case SLAPI_MANAGEDSAIT:
@@ -2298,12 +2301,15 @@ slapi_pblock_set( Slapi_PBlock *pblock, int arg, void *value )
 		}
 		pblock->pb_plugin->plg_syntax_compare = (IFP) value;
 		break;
-        case SLAPI_ENTRY_PRE_OP:
-                pblock->pb_pre_op_entry = (Slapi_Entry *) value;
-                break;
-        case SLAPI_ENTRY_POST_OP:
-                pblock->pb_post_op_entry = (Slapi_Entry *) value;
-                break;
+	case SLAPI_SYNTAX_SUBSTRLENS:
+		pblock->pb_substrlens = (int *) value;
+		break;
+	case SLAPI_ENTRY_PRE_OP:
+		pblock->pb_pre_op_entry = (Slapi_Entry *) value;
+		break;
+	case SLAPI_ENTRY_POST_OP:
+		pblock->pb_post_op_entry = (Slapi_Entry *) value;
+		break;
 
 	/* target address for all operations */
 	case SLAPI_TARGET_ADDRESS:
diff --git a/ldap/servers/slapd/plugin_syntax.c b/ldap/servers/slapd/plugin_syntax.c
index 2034e5c4..cb3cde9f 100644
--- a/ldap/servers/slapd/plugin_syntax.c
+++ b/ldap/servers/slapd/plugin_syntax.c
@@ -309,6 +309,38 @@ slapi_call_syntax_values2keys_sv(
 	return( rc );
 }
 
+/*
+ * almost identical to slapi_call_syntax_values2keys_sv except accepting 
+ * pblock to pass some info such as substrlen.
+ */
+int
+slapi_call_syntax_values2keys_sv_pb(
+    void			*vpi,
+    Slapi_Value		**vals,
+    Slapi_Value		***ivals,
+    int				ftype,
+	Slapi_PBlock	*pb
+)
+{
+	int					rc;
+	struct slapdplugin	*pi = vpi;
+
+	LDAPDebug( LDAP_DEBUG_FILTER, "=> slapi_call_syntax_values2keys\n",
+	    0, 0, 0 );
+
+	slapi_pblock_set( pb, SLAPI_PLUGIN, vpi );
+
+	*ivals = NULL;
+	rc = -1;	/* means no values2keys function */
+	if ( pi != NULL && pi->plg_syntax_values2keys != NULL ) {
+		rc = pi->plg_syntax_values2keys( pb, vals, ivals, ftype );
+	}
+
+	LDAPDebug( LDAP_DEBUG_FILTER,
+	    "<= slapi_call_syntax_values2keys %d\n", rc, 0, 0 );
+	return( rc );
+}
+
 SLAPI_DEPRECATED int
 slapi_call_syntax_assertion2keys_ava( /* JCM SLOW FUNCTION */
     void		*vpi,
diff --git a/ldap/servers/slapd/schema.c b/ldap/servers/slapd/schema.c
index b8e154af..c96a1efd 100644
--- a/ldap/servers/slapd/schema.c
+++ b/ldap/servers/slapd/schema.c
@@ -456,7 +456,7 @@ slapi_entry_schema_check( Slapi_PBlock *pb, Slapi_Entry *e )
   int i, oc_count = 0;
   int unknown_class = 0;
   char errtext[ BUFSIZ ];
-  PRUint32 schema_flags;
+  PRUint32 schema_flags = 0;
 
   /* smart referrals are not allowed in Directory Lite */
   if ( config_is_slapd_lite() ) {
diff --git a/ldap/servers/slapd/slap.h b/ldap/servers/slapd/slap.h
index 3241af71..dea64a2f 100644
--- a/ldap/servers/slapd/slap.h
+++ b/ldap/servers/slapd/slap.h
@@ -1444,8 +1444,18 @@ typedef struct slapi_pblock {
 	/* For password policy control */
 	int		pb_pwpolicy_ctrl;
 	void	*pb_vattr_context;      /* hold the vattr_context for roles/cos */
+
+	int		*pb_substrlens; /* user specified minimum substr search key lengths:
+							 * nsSubStrBegin, nsSubStrMiddle, nsSubStrEnd
+							 */
 } slapi_pblock;
 
+/* index if substrlens */
+#define INDEX_SUBSTRBEGIN	0
+#define INDEX_SUBSTRMIDDLE	1
+#define INDEX_SUBSTREND		2
+#define INDEX_SUBSTRLEN		3	/* size of the substrlens */
+
 /* The referral element */
 typedef struct ref {
      char          *ref_dn;       /* The DN of the entry that contains the referral */
diff --git a/ldap/servers/slapd/slapi-plugin.h b/ldap/servers/slapd/slapi-plugin.h
index 0782c471..56959b3d 100644
--- a/ldap/servers/slapd/slapi-plugin.h
+++ b/ldap/servers/slapd/slapi-plugin.h
@@ -891,6 +891,8 @@ char * slapi_ch_smprintf(const char *fmt, ...)
  */
 int slapi_call_syntax_values2keys_sv( void *vpi, Slapi_Value **vals,
 	Slapi_Value ***ivals, int ftype );
+int slapi_call_syntax_values2keys_sv_pb( void *vpi, Slapi_Value **vals,
+	Slapi_Value ***ivals, int ftype, Slapi_PBlock *pb );
 int slapi_call_syntax_assertion2keys_ava_sv( void *vpi, Slapi_Value *val,
 	Slapi_Value ***ivals, int ftype );
 int slapi_call_syntax_assertion2keys_sub_sv( void *vpi, char *initial,
@@ -1582,6 +1584,9 @@ typedef struct slapi_plugindesc {
 #define SLAPI_PLUGIN_SYNTAX_FLAGS		707
 #define SLAPI_PLUGIN_SYNTAX_COMPARE		708
 
+/* user defined substrlen; not stored in slapdplugin, but pblock itself */
+#define SLAPI_SYNTAX_SUBSTRLENS	709
+
 /* ACL plugin functions and arguments */
 #define SLAPI_PLUGIN_ACL_INIT			730
 #define SLAPI_PLUGIN_ACL_SYNTAX_CHECK		731