This is an automated email from the git hooks/post-receive script.
mreynolds pushed a commit to branch master
in repository 389-ds-base.
commit 14a10a34b3ff10d5146d73e67aa54c8945cfa37d
Author: Mark Reynolds <mreynolds@redhat.com>
Date: Fri Aug 24 16:24:21 2018 -0400
Revert "Ticket 49372 - filter optimisation improvements for common queries"
This reverts commit 4cd1a24b3ce88968ff5f9a2b87efdc84dee176da.
---
.../suites/filter/rfc3673_all_oper_attrs_test.py | 5 +-
ldap/admin/src/scripts/ns-slapd-gdb.py | 70 -------
ldap/servers/slapd/back-ldbm/ldbm_modrdn.c | 7 +-
ldap/servers/slapd/back-ldbm/ldbm_search.c | 79 +++++---
ldap/servers/slapd/back-ldbm/proto-back-ldbm.h | 6 +-
ldap/servers/slapd/back-ldbm/vlv_srch.c | 23 ++-
ldap/servers/slapd/dse.c | 7 -
ldap/servers/slapd/filter.c | 203 ++++-----------------
ldap/servers/slapd/index_subsystem.c | 4 -
ldap/servers/slapd/slapi-private.h | 1 -
10 files changed, 104 insertions(+), 301 deletions(-)
diff --git a/dirsrvtests/tests/suites/filter/rfc3673_all_oper_attrs_test.py b/dirsrvtests/tests/suites/filter/rfc3673_all_oper_attrs_test.py
index e61ece1..7cb15fd 100644
--- a/dirsrvtests/tests/suites/filter/rfc3673_all_oper_attrs_test.py
+++ b/dirsrvtests/tests/suites/filter/rfc3673_all_oper_attrs_test.py
@@ -148,12 +148,9 @@ def test_search_basic(topology_st, test_user, user_aci, add_attr,
else:
expected_attrs = sorted(oper_attr_list)
- log.info("suffix: %s filter: %s" % (search_suffix, search_filter))
entries = topology_st.standalone.search_s(search_suffix, ldap.SCOPE_BASE,
'(objectclass=*)',
search_filter)
- log.info("results: %s" % entries)
- assert len(entries) > 0
found_attrs = sorted(entries[0].data.keys())
if add_attr == '*':
@@ -162,7 +159,7 @@ def test_search_basic(topology_st, test_user, user_aci, add_attr,
assert all(attr in found_attrs
for attr in ['objectClass', expected_attrs[0]])
else:
- assert set(expected_attrs).issubset(set(found_attrs))
+ assert cmp(found_attrs, expected_attrs) == 0
if __name__ == '__main__':
diff --git a/ldap/admin/src/scripts/ns-slapd-gdb.py b/ldap/admin/src/scripts/ns-slapd-gdb.py
index eb99a6f..3273d43 100644
--- a/ldap/admin/src/scripts/ns-slapd-gdb.py
+++ b/ldap/admin/src/scripts/ns-slapd-gdb.py
@@ -16,22 +16,9 @@
import itertools
import re
-from enum import IntEnum
-
import gdb
from gdb.FrameDecorator import FrameDecorator
-class LDAPFilter(IntEnum):
- PRESENT = 0x87
- APPROX = 0xa8
- LE = 0xa6
- GE = 0xa5
- SUBSTRINGS = 0xa4
- EQUALITY = 0xa3
- NOT = 0xa2
- OR = 0xa1
- AND = 0xa0
-
class DSAccessLog (gdb.Command):
"""Display the Directory Server access log."""
def __init__ (self):
@@ -127,64 +114,7 @@ class DSIdleFilter():
frame_iter = map(DSIdleFilterDecorator, frame_iter)
return frame_iter
-class DSFilterPrint (gdb.Command):
- """Display a filter's contents"""
- def __init__ (self):
- super (DSFilterPrint, self).__init__ ("ds-filter-print", gdb.COMMAND_DATA)
-
- def display_filter(self, filter_element, depth=0):
- pad = " " * depth
- # Extract the choice, that determines what we access next.
- f_choice = filter_element['f_choice']
- f_un = filter_element['f_un']
- f_flags = filter_element['f_flags']
- if f_choice == LDAPFilter.PRESENT:
- print("%s(%s=*) flags:%s" % (pad, f_un['f_un_type'], f_flags))
- elif f_choice == LDAPFilter.APPROX:
- print("%sAPPROX ???" % pad)
- elif f_choice == LDAPFilter.LE:
- print("%sLE ???" % pad)
- elif f_choice == LDAPFilter.GE:
- print("%sGE ???" % pad)
- elif f_choice == LDAPFilter.SUBSTRINGS:
- f_un_sub = f_un['f_un_sub']
- value = f_un_sub['sf_initial']
- print("%s(%s=%s*) flags:%s" % (pad, f_un_sub['sf_type'], value, f_flags))
- elif f_choice == LDAPFilter.EQUALITY:
- f_un_ava = f_un['f_un_ava']
- value = f_un_ava['ava_value']['bv_val']
- print("%s(%s=%s) flags:%s" % (pad, f_un_ava['ava_type'], value, f_flags))
- elif f_choice == LDAPFilter.NOT:
- print("%sNOT ???" % pad)
- elif f_choice == LDAPFilter.OR:
- print("%s(| flags:%s" % (pad, f_flags))
- filter_child = f_un['f_un_complex'].dereference()
- self.display_filter(filter_child, depth + 4)
- print("%s)" % pad)
- elif f_choice == LDAPFilter.AND:
- # Our child filter is in f_un_complex.
- print("%s(& flags:%s" % (pad, f_flags))
- filter_child = f_un['f_un_complex'].dereference()
- self.display_filter(filter_child, depth + 4)
- print("%s)" % pad)
- else:
- print("Corrupted filter, no such value %s" % f_choice)
-
- f_next = filter_element['f_next']
- if f_next != 0:
- self.display_filter(f_next.dereference(), depth)
-
- def invoke (self, arg, from_tty):
- # Select our program state
- gdb.newest_frame()
- cur_frame = gdb.selected_frame()
- # We are given the name of a filter, so we need to look up that symbol.
- filter_val = cur_frame.read_var(arg)
- filter_root = filter_val.dereference()
- self.display_filter(filter_root)
-
DSAccessLog()
DSBacktrace()
DSIdleFilter()
-DSFilterPrint()
diff --git a/ldap/servers/slapd/back-ldbm/ldbm_modrdn.c b/ldap/servers/slapd/back-ldbm/ldbm_modrdn.c
index 71e2a8f..b9a092c 100644
--- a/ldap/servers/slapd/back-ldbm/ldbm_modrdn.c
+++ b/ldap/servers/slapd/back-ldbm/ldbm_modrdn.c
@@ -2072,13 +2072,8 @@ moddn_get_children(back_txn *ptxn,
* being moved */
strcpy(filterstr, "objectclass=*");
filter = slapi_str2filter(filterstr);
- /*
- * We used to set managedSAIT here, but because the subtree create
- * referral step is now in build_candidate_list, we can trust the filter
- * we provide here is exactly as we provide it IE no referrals involved.
- */
candidates = subtree_candidates(pb, be, slapi_sdn_get_ndn(dn_parentdn),
- parententry, filter,
+ parententry, filter, 1 /* ManageDSAIT */,
NULL /* allids_before_scopingp */, &err);
slapi_filter_free(filter, 1);
}
diff --git a/ldap/servers/slapd/back-ldbm/ldbm_search.c b/ldap/servers/slapd/back-ldbm/ldbm_search.c
index 966131c..7f3600e 100644
--- a/ldap/servers/slapd/back-ldbm/ldbm_search.c
+++ b/ldap/servers/slapd/back-ldbm/ldbm_search.c
@@ -32,7 +32,7 @@
/* prototypes */
static int build_candidate_list(Slapi_PBlock *pb, backend *be, struct backentry *e, const char *base, int scope, int *lookup_returned_allidsp, IDList **candidates);
static IDList *base_candidates(Slapi_PBlock *pb, struct backentry *e);
-static IDList *onelevel_candidates(Slapi_PBlock *pb, backend *be, const char *base, Slapi_Filter *filter, int *lookup_returned_allidsp, int *err);
+static IDList *onelevel_candidates(Slapi_PBlock *pb, backend *be, const char *base, struct backentry *e, Slapi_Filter *filter, int managedsait, int *lookup_returned_allidsp, int *err);
static back_search_result_set *new_search_result_set(IDList *idl, int vlv, int lookthroughlimit);
static void delete_search_result_set(Slapi_PBlock *pb, back_search_result_set **sr);
static int can_skip_filter_test(Slapi_PBlock *pb, struct slapi_filter *f, int scope, IDList *idl);
@@ -959,25 +959,13 @@ build_candidate_list(Slapi_PBlock *pb, backend *be, struct backentry *e, const c
break;
case LDAP_SCOPE_ONELEVEL:
- /* modify the filter to be: (&(parentid=idofbase)(|(originalfilter)(objectclass=referral))) */
- filter = create_onelevel_filter(filter, e, managedsait);
- /* Now optimise the filter for use */
- slapi_filter_optimise(filter);
-
- *candidates = onelevel_candidates(pb, be, base, filter, lookup_returned_allidsp, &err);
- /* Give the optimised filter back to search filter for free */
- slapi_pblock_set(pb, SLAPI_SEARCH_FILTER, filter);
+ *candidates = onelevel_candidates(pb, be, base, e, filter, managedsait,
+ lookup_returned_allidsp, &err);
break;
case LDAP_SCOPE_SUBTREE:
- /* make (|(originalfilter)(objectclass=referral)) */
- filter = create_subtree_filter(filter, managedsait);
- /* Now optimise the filter for use */
- slapi_filter_optimise(filter);
-
- *candidates = subtree_candidates(pb, be, base, e, filter, lookup_returned_allidsp, &err);
- /* Give the optimised filter back to search filter for free */
- slapi_pblock_set(pb, SLAPI_SEARCH_FILTER, filter);
+ *candidates = subtree_candidates(pb, be, base, e, filter, managedsait,
+ lookup_returned_allidsp, &err);
break;
default:
@@ -1036,15 +1024,15 @@ base_candidates(Slapi_PBlock *pb __attribute__((unused)), struct backentry *e)
* non-recursively when done with the returned filter.
*/
static Slapi_Filter *
-create_referral_filter(Slapi_Filter *filter)
+create_referral_filter(Slapi_Filter *filter, Slapi_Filter **focref, Slapi_Filter **forr)
{
char *buf = slapi_ch_strdup("objectclass=referral");
- Slapi_Filter *focref = slapi_str2filter(buf);
- Slapi_Filter *forr = slapi_filter_join(LDAP_FILTER_OR, filter, focref);
+ *focref = slapi_str2filter(buf);
+ *forr = slapi_filter_join(LDAP_FILTER_OR, filter, *focref);
slapi_ch_free((void **)&buf);
- return forr;
+ return *forr;
}
/*
@@ -1058,20 +1046,20 @@ create_referral_filter(Slapi_Filter *filter)
* This function is exported for the VLV code to use.
*/
Slapi_Filter *
-create_onelevel_filter(Slapi_Filter *filter, const struct backentry *baseEntry, int managedsait)
+create_onelevel_filter(Slapi_Filter *filter, const struct backentry *baseEntry, int managedsait, Slapi_Filter **fid2kids, Slapi_Filter **focref, Slapi_Filter **fand, Slapi_Filter **forr)
{
Slapi_Filter *ftop = filter;
char buf[40];
if (!managedsait) {
- ftop = create_referral_filter(filter);
+ ftop = create_referral_filter(filter, focref, forr);
}
sprintf(buf, "parentid=%lu", (u_long)(baseEntry != NULL ? baseEntry->ep_id : 0));
- Slapi_Filter *fid2kids = slapi_str2filter(buf);
- Slapi_Filter *fand = slapi_filter_join(LDAP_FILTER_AND, ftop, fid2kids);
+ *fid2kids = slapi_str2filter(buf);
+ *fand = slapi_filter_join(LDAP_FILTER_AND, ftop, *fid2kids);
- return fand;
+ return *fand;
}
/*
@@ -1082,16 +1070,38 @@ onelevel_candidates(
Slapi_PBlock *pb,
backend *be,
const char *base,
+ struct backentry *e,
Slapi_Filter *filter,
+ int managedsait,
int *lookup_returned_allidsp,
int *err)
{
+ Slapi_Filter *fid2kids = NULL;
+ Slapi_Filter *focref = NULL;
+ Slapi_Filter *fand = NULL;
+ Slapi_Filter *forr = NULL;
+ Slapi_Filter *ftop = NULL;
IDList *candidates;
- candidates = filter_candidates(pb, be, base, filter, NULL, 0, err);
+ /*
+ * modify the filter to be something like this:
+ *
+ * (&(parentid=idofbase)(|(originalfilter)(objectclass=referral)))
+ */
+
+ ftop = create_onelevel_filter(filter, e, managedsait, &fid2kids, &focref, &fand, &forr);
+
+ /* from here, it's just like subtree_candidates */
+ candidates = filter_candidates(pb, be, base, ftop, NULL, 0, err);
*lookup_returned_allidsp = slapi_be_is_flag_set(be, SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST);
+ /* free up just the filter stuff we allocated above */
+ slapi_filter_free(fid2kids, 0);
+ slapi_filter_free(fand, 0);
+ slapi_filter_free(forr, 0);
+ slapi_filter_free(focref, 0);
+
return (candidates);
}
@@ -1106,12 +1116,12 @@ onelevel_candidates(
* This function is exported for the VLV code to use.
*/
Slapi_Filter *
-create_subtree_filter(Slapi_Filter *filter, int managedsait)
+create_subtree_filter(Slapi_Filter *filter, int managedsait, Slapi_Filter **focref, Slapi_Filter **forr)
{
Slapi_Filter *ftop = filter;
if (!managedsait) {
- ftop = create_referral_filter(filter);
+ ftop = create_referral_filter(filter, focref, forr);
}
return ftop;
@@ -1128,9 +1138,13 @@ subtree_candidates(
const char *base,
const struct backentry *e,
Slapi_Filter *filter,
+ int managedsait,
int *allids_before_scopingp,
int *err)
{
+ Slapi_Filter *focref = NULL;
+ Slapi_Filter *forr = NULL;
+ Slapi_Filter *ftop = NULL;
IDList *candidates;
PRBool has_tombstone_filter;
int isroot = 0;
@@ -1139,8 +1153,13 @@ subtree_candidates(
Operation *op = NULL;
PRBool is_bulk_import = PR_FALSE;
+ /* make (|(originalfilter)(objectclass=referral)) */
+ ftop = create_subtree_filter(filter, managedsait, &focref, &forr);
+
/* Fetch a candidate list for the original filter */
- candidates = filter_candidates_ext(pb, be, base, filter, NULL, 0, err, allidslimit);
+ candidates = filter_candidates_ext(pb, be, base, ftop, NULL, 0, err, allidslimit);
+ slapi_filter_free(forr, 0);
+ slapi_filter_free(focref, 0);
/* set 'allids before scoping' flag */
if (NULL != allids_before_scopingp) {
diff --git a/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h b/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
index 6d772cd..f8b86d9 100644
--- a/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
+++ b/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
@@ -568,9 +568,9 @@ int bedse_add_index_entry(int argc, char **argv);
/*
* ldbm_search.c
*/
-Slapi_Filter *create_onelevel_filter(Slapi_Filter *filter, const struct backentry *e, int managedsait);
-Slapi_Filter *create_subtree_filter(Slapi_Filter *filter, int managedsait);
-IDList *subtree_candidates(Slapi_PBlock *pb, backend *be, const char *base, const struct backentry *e, Slapi_Filter *filter, int *allids_before_scopingp, int *err);
+Slapi_Filter *create_onelevel_filter(Slapi_Filter *filter, const struct backentry *e, int managedsait, Slapi_Filter **fid2kids, Slapi_Filter **focref, Slapi_Filter **fand, Slapi_Filter **forr);
+Slapi_Filter *create_subtree_filter(Slapi_Filter *filter, int managedsait, Slapi_Filter **focref, Slapi_Filter **forr);
+IDList *subtree_candidates(Slapi_PBlock *pb, backend *be, const char *base, const struct backentry *e, Slapi_Filter *filter, int managedsait, int *allids_before_scopingp, int *err);
void search_set_tune(struct ldbminfo *li, int val);
int search_get_tune(struct ldbminfo *li);
int compute_lookthrough_limit(Slapi_PBlock *pb, struct ldbminfo *li);
diff --git a/ldap/servers/slapd/back-ldbm/vlv_srch.c b/ldap/servers/slapd/back-ldbm/vlv_srch.c
index 0c09cb8..c4c0875 100644
--- a/ldap/servers/slapd/back-ldbm/vlv_srch.c
+++ b/ldap/servers/slapd/back-ldbm/vlv_srch.c
@@ -93,8 +93,13 @@ vlvSearch_reinit(struct vlvSearch *p, const struct backentry *base)
p->vlv_slapifilter = slapi_str2filter(p->vlv_filter);
filter_normalize(p->vlv_slapifilter);
/* make (&(parentid=idofbase)(|(originalfilter)(objectclass=referral))) */
- p->vlv_slapifilter = create_onelevel_filter(p->vlv_slapifilter, base, 0 /* managedsait */);
- slapi_filter_optimise(p->vlv_slapifilter);
+ {
+ Slapi_Filter *fid2kids = NULL;
+ Slapi_Filter *focref = NULL;
+ Slapi_Filter *fand = NULL;
+ Slapi_Filter *forr = NULL;
+ p->vlv_slapifilter = create_onelevel_filter(p->vlv_slapifilter, base, 0 /* managedsait */, &fid2kids, &focref, &fand, &forr);
+ }
}
/*
@@ -168,16 +173,22 @@ vlvSearch_init(struct vlvSearch *p, Slapi_PBlock *pb, const Slapi_Entry *e, ldbm
/* make (&(parentid=idofbase)(|(originalfilter)(objectclass=referral))) */
{
- p->vlv_slapifilter = create_onelevel_filter(p->vlv_slapifilter, e, 0 /* managedsait */);
- slapi_filter_optimise(p->vlv_slapifilter);
+ Slapi_Filter *fid2kids = NULL;
+ Slapi_Filter *focref = NULL;
+ Slapi_Filter *fand = NULL;
+ Slapi_Filter *forr = NULL;
+ p->vlv_slapifilter = create_onelevel_filter(p->vlv_slapifilter, e, 0 /* managedsait */, &fid2kids, &focref, &fand, &forr);
+ /* jcm: fid2kids, focref, fand, and forr get freed when we free p->vlv_slapifilter */
CACHE_RETURN(&inst->inst_cache, &e);
}
} break;
case LDAP_SCOPE_SUBTREE: {
/* make (|(originalfilter)(objectclass=referral))) */
/* No need for scope-filter since we apply a scope test before the filter test */
- p->vlv_slapifilter = create_subtree_filter(p->vlv_slapifilter, 0 /* managedsait */);
- slapi_filter_optimise(p->vlv_slapifilter);
+ Slapi_Filter *focref = NULL;
+ Slapi_Filter *forr = NULL;
+ p->vlv_slapifilter = create_subtree_filter(p->vlv_slapifilter, 0 /* managedsait */, &focref, &forr);
+ /* jcm: focref and forr get freed when we free p->vlv_slapifilter */
} break;
}
}
diff --git a/ldap/servers/slapd/dse.c b/ldap/servers/slapd/dse.c
index e61e9d9..151c8ae 100644
--- a/ldap/servers/slapd/dse.c
+++ b/ldap/servers/slapd/dse.c
@@ -1635,13 +1635,6 @@ dse_search(Slapi_PBlock *pb) /* JCM There should only be one exit point from thi
*/
isrootdse = slapi_sdn_isempty(basesdn);
- /*
- * Now optimise the filter for use: note that unlike ldbm_search,
- * because we don't change the outer filter container, we don't need
- * to set back into pb.
- */
- slapi_filter_optimise(filter);
-
switch (scope) {
case LDAP_SCOPE_BASE: {
Slapi_Entry *baseentry = NULL;
diff --git a/ldap/servers/slapd/filter.c b/ldap/servers/slapd/filter.c
index 87ec0de..393a4dc 100644
--- a/ldap/servers/slapd/filter.c
+++ b/ldap/servers/slapd/filter.c
@@ -29,6 +29,7 @@ static int get_extensible_filter(BerElement *ber, mr_filter_t *);
static int get_filter_internal(Connection *conn, BerElement *ber, struct slapi_filter **filt, char **fstr, int maxdepth, int curdepth, int *subentry_dont_rewrite, int *has_tombstone_filter, int *has_ruv_filter);
static int tombstone_check_filter(Slapi_Filter *f);
static int ruv_check_filter(Slapi_Filter *f);
+static void filter_optimize(Slapi_Filter *f);
/*
@@ -74,12 +75,7 @@ get_filter(Connection *conn, BerElement *ber, int scope, struct slapi_filter **f
slapi_filter_to_string(*filt, logbuf, logbufsize));
}
- /*
- * Filter optimise has been moved to the onelevel/subtree candidate dispatch.
- * this is because they inject referrals or other business, that we can optimise
- * and improve.
- */
- /* filter_optimize(*filt); */
+ filter_optimize(*filt);
if (NULL != logbuf) {
slapi_log_err(SLAPI_LOG_DEBUG, "get_filter", " after optimize: %s\n",
@@ -862,22 +858,19 @@ slapi_filter_join_ex(int ftype, struct slapi_filter *f1, struct slapi_filter *f2
if (add_to->f_list->f_choice == LDAP_FILTER_NOT) {
add_this->f_next = add_to->f_list;
add_to->f_list = add_this;
+ filter_compute_hash(add_to);
+ return_this = add_to;
} else {
/* find end of list, add the filter */
for (fjoin = add_to->f_list; fjoin != NULL; fjoin = fjoin->f_next) {
if (fjoin->f_next == NULL) {
fjoin->f_next = add_this;
+ filter_compute_hash(add_to);
+ return_this = add_to;
break;
}
}
}
- /*
- * Make sure we sync the filter flags. The origin filters may have flags
- * we still need on the outer layer!
- */
- add_to->f_flags |= add_this->f_flags;
- filter_compute_hash(add_to);
- return_this = add_to;
} else {
fjoin = (struct slapi_filter *)slapi_ch_calloc(1, sizeof(struct slapi_filter));
fjoin->f_choice = ftype;
@@ -890,8 +883,6 @@ slapi_filter_join_ex(int ftype, struct slapi_filter *f1, struct slapi_filter *f2
fjoin->f_list = f1;
f1->f_next = f2;
}
- /* Make sure any flags that were set move to the outer parent */
- fjoin->f_flags |= f1->f_flags | f2->f_flags;
filter_compute_hash(fjoin);
return_this = fjoin;
}
@@ -1536,175 +1527,47 @@ ruv_check_filter(Slapi_Filter *f)
return 0; /* Not a RUV filter */
}
-/*
- * To help filter optimise we break out the list manipulation
- * code.
- */
-
-static void
-filter_prioritise_element(Slapi_Filter **list, Slapi_Filter **head, Slapi_Filter **tail, Slapi_Filter **f_prev, Slapi_Filter **f_cur) {
- if (*f_prev != NULL) {
- (*f_prev)->f_next = (*f_cur)->f_next;
- } else if (*list == *f_cur) {
- *list = (*f_cur)->f_next;
- }
- if (*head == NULL) {
- *head = *f_cur;
- *tail = *f_cur;
- (*f_cur)->f_next = NULL;
- } else {
- (*f_cur)->f_next = *head;
- *head = *f_cur;
- }
-}
-
-static void
-filter_merge_subfilter(Slapi_Filter **list, Slapi_Filter **f_prev, Slapi_Filter **f_cur, Slapi_Filter **f_next) {
- /* Cut our current AND/OR out */
- if (*f_prev != NULL) {
- (*f_prev)->f_next = (*f_cur)->f_next;
- } else if (*list == *f_cur) {
- *list = (*f_cur)->f_next;
- }
- (*f_next) = (*f_cur)->f_next;
-
- /* Look ahead to the end of our list, without the f_cur. */
- Slapi_Filter *f_cur_tail = *list;
- while (f_cur_tail->f_next != NULL) {
- f_cur_tail = f_cur_tail->f_next;
- }
- /* Now append our descendant into the tail */
- f_cur_tail->f_next = (*f_cur)->f_list;
- /* Finally free the remainder */
- slapi_filter_free(*f_cur, 0);
-}
-
-/* slapi_filter_optimise
+/* filter_optimize
* ---------------
- * takes a filter and optimises it for fast evaluation
- *
- * Optimisations are:
- * * In OR conditions move substrings early to promote fail-fast of unindexed types
- * * In AND conditions move eq types (that are not objectClass) early to promote triggering threshold shortcut
- * * In OR conditions, merge all direct child OR conditions into the list. (|(|(a)(b))) == (|(a)(b))
- * * in AND conditions, merge all direct child AND conditions into the list. (&(&(a)(b))) == (&(a)(b))
- *
- * In the case of the OR and AND merges, we remove the inner filter because the outer one may have flags set.
- *
- * In the future this could be backend dependent.
+ * takes a filter and optimizes it for fast evaluation
+ * currently this merely ensures that any AND or OR
+ * does not start with a NOT sub-filter if possible
*/
-void
-slapi_filter_optimise(Slapi_Filter *f)
+static void
+filter_optimize(Slapi_Filter *f)
{
- /*
- * Today tombstone searches RELY on filter ordering
- * and a filter test threshold quirk. We need to avoid
- * touching these cases!!!
- */
- if (f == NULL || (f->f_flags & SLAPI_FILTER_TOMBSTONE) != 0) {
+ if (!f)
return;
- }
switch (f->f_choice) {
case LDAP_FILTER_AND:
- /* Move all equality searches to the head. */
- /* Merge any direct descendant AND queries into us */
- {
- Slapi_Filter *f_prev = NULL;
- Slapi_Filter *f_cur = NULL;
- Slapi_Filter *f_next = NULL;
-
- Slapi_Filter *f_op_head = NULL;
- Slapi_Filter *f_op_tail = NULL;
-
- f_cur = f->f_list;
- while(f_cur != NULL) {
-
- switch(f_cur->f_choice) {
- case LDAP_FILTER_AND:
- filter_merge_subfilter(&(f->f_list), &f_prev, &f_cur, &f_next);
- f_cur = f_next;
- break;
- case LDAP_FILTER_EQUALITY:
- if (strcasecmp(f_cur->f_avtype, "objectclass") != 0) {
- f_next = f_cur->f_next;
- /* Cut it out */
- filter_prioritise_element(&(f->f_list), &f_op_head, &f_op_tail, &f_prev, &f_cur);
- /* Don't change previous, because we remove this f_cur */
- f_cur = f_next;
- break;
- } else {
- /* Move along */
- f_prev = f_cur;
- f_cur = f_cur->f_next;
- }
- break;
- default:
- /* Move along */
- f_prev = f_cur;
- f_cur = f_cur->f_next;
+ case LDAP_FILTER_OR: {
+ /* first optimize children */
+ filter_optimize(f->f_list);
+
+ /* optimize this */
+ if (f->f_list->f_choice == LDAP_FILTER_NOT) {
+ Slapi_Filter *f_prev = 0;
+ Slapi_Filter *f_child = 0;
+
+ /* grab a non not filter to place at start */
+ for (f_child = f->f_list; f_child != 0; f_child = f_child->f_next) {
+ if (f_child->f_choice != LDAP_FILTER_NOT) {
+ /* we have a winner, do swap */
+ if (f_prev)
+ f_prev->f_next = f_child->f_next;
+ f_child->f_next = f->f_list;
+ f->f_list = f_child;
break;
}
- }
- if (f_op_head != NULL) {
- f_op_tail->f_next = f->f_list;
- f->f_list = f_op_head;
+ f_prev = f_child;
}
}
- /* finally optimize children */
- slapi_filter_optimise(f->f_list);
-
- break;
-
- case LDAP_FILTER_OR:
- /* Move all substring searches to the head. */
- {
- Slapi_Filter *f_prev = NULL;
- Slapi_Filter *f_cur = NULL;
- Slapi_Filter *f_next = NULL;
-
- Slapi_Filter *f_op_head = NULL;
- Slapi_Filter *f_op_tail = NULL;
-
- f_cur = f->f_list;
- while(f_cur != NULL) {
-
- switch(f_cur->f_choice) {
- case LDAP_FILTER_OR:
- filter_merge_subfilter(&(f->f_list), &f_prev, &f_cur, &f_next);
- f_cur = f_next;
- break;
- case LDAP_FILTER_APPROX:
- case LDAP_FILTER_GE:
- case LDAP_FILTER_LE:
- case LDAP_FILTER_SUBSTRINGS:
- f_next = f_cur->f_next;
- /* Cut it out */
- filter_prioritise_element(&(f->f_list), &f_op_head, &f_op_tail, &f_prev, &f_cur);
- /* Don't change previous, because we remove this f_cur */
- f_cur = f_next;
- break;
- default:
- /* Move along */
- f_prev = f_cur;
- f_cur = f_cur->f_next;
- break;
- }
- }
- if (f_op_head != NULL) {
- f_op_tail->f_next = f->f_list;
- f->f_list = f_op_head;
- }
- }
- /* finally optimize children */
- slapi_filter_optimise(f->f_list);
-
- break;
-
+ }
default:
- slapi_filter_optimise(f->f_next);
+ filter_optimize(f->f_next);
break;
}
}
diff --git a/ldap/servers/slapd/index_subsystem.c b/ldap/servers/slapd/index_subsystem.c
index 7d7e1b7..97cb7b4 100644
--- a/ldap/servers/slapd/index_subsystem.c
+++ b/ldap/servers/slapd/index_subsystem.c
@@ -191,10 +191,6 @@ index_subsys_assign_filter_decoders(Slapi_PBlock *pb)
char *subsystem = "index_subsys_assign_filter_decoders";
char logbuf[1024];
- if (!theCache) {
- return rc;
- }
-
/* extract the filter */
slapi_pblock_get(pb, SLAPI_SEARCH_FILTER, &f);
if (f) {
diff --git a/ldap/servers/slapd/slapi-private.h b/ldap/servers/slapd/slapi-private.h
index 837ca8e..d93693b 100644
--- a/ldap/servers/slapd/slapi-private.h
+++ b/ldap/servers/slapd/slapi-private.h
@@ -383,7 +383,6 @@ void ndn_cache_get_stats(uint64_t *hits, uint64_t *tries, uint64_t *size, uint64
int filter_flag_is_set(const Slapi_Filter *f, unsigned char flag);
char *slapi_filter_to_string(const Slapi_Filter *f, char *buffer, size_t bufsize);
char *slapi_filter_to_string_internal(const struct slapi_filter *f, char *buf, size_t *bufsize);
-void slapi_filter_optimise(Slapi_Filter *f);
/* operation.c */
--
To stop receiving notification emails like this one, please contact
the administrator of this repository.
_______________________________________________
389-commits mailing list -- 389-commits@lists.fedoraproject.org
To unsubscribe send an email to 389-commits-leave@lists.fedoraproject.org
Fedora Code of Conduct: https://getfedora.org/code-of-conduct.html
List Guidelines: https://fedoraproject.org/wiki/Mailing_list_guidelines
List Archives: https://lists.fedoraproject.org/archives/list/389-commits@lists.fedoraproject.org/message/SOQJZIHZJFCAJWLMSNFVACKRW46I4OEO/
No comments:
Post a Comment