firstyear / 389-ds-base

Forked from 389-ds-base 6 years ago
Clone

0355f62 Ticket 49372 - filter optimisation improvements for common queries

30 files Authored by William Brown 4 years ago, Committed by firstyear 4 years ago,
30 files changed. 808 lines added. 218 lines removed.
Makefile.am
file modified
+1 -0
dirsrvtests/tests/suites/filter/basic_filter_test.py
file modified
+15 -10
dirsrvtests/tests/suites/filter/complex_filters_test.py
file modified
+21 -4
dirsrvtests/tests/suites/filter/filter_logic_test.py
file modified
+103 -6
dirsrvtests/tests/suites/filter/filter_test.py
file modified
+2 -5
dirsrvtests/tests/suites/filter/rfc3673_all_oper_attrs_test.py
file modified
+51 -35
ldap/admin/src/scripts/ns-slapd-gdb.py
file modified
+70 -1
ldap/schema/01core389.ldif
file modified
+1 -0
ldap/servers/slapd/back-ldbm/filterindex.c
file modified
+32 -18
ldap/servers/slapd/back-ldbm/idl_set.c
file modified
+15 -3
ldap/servers/slapd/back-ldbm/ldbm_modrdn.c
file modified
+6 -1
ldap/servers/slapd/back-ldbm/ldbm_search.c
file modified
+63 -63
ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
file modified
+3 -3
ldap/servers/slapd/back-ldbm/vlv_srch.c
file modified
+14 -17
ldap/servers/slapd/dse.c
file modified
+9 -0
ldap/servers/slapd/filter.c
file modified
+200 -33
ldap/servers/slapd/filterentry.c
file modified
+21 -11
ldap/servers/slapd/libglobs.c
file modified
+30 -0
ldap/servers/slapd/pblock.c
file modified
+12 -0
ldap/servers/slapd/pblock_v3.h
file modified
+14 -0
ldap/servers/slapd/plugin_internal_op.c
file modified
+3 -0
ldap/servers/slapd/plugin_syntax.c
file modified
+6 -6
ldap/servers/slapd/proto-slap.h
file modified
+2 -0
ldap/servers/slapd/result.c
file modified
+16 -2
ldap/servers/slapd/search.c
file modified
+3 -0
ldap/servers/slapd/slap.h
file modified
+2 -0
ldap/servers/slapd/slapi-private.h
file modified
+6 -0
test/libslapd/filter/optimise.c
file added
+83
test/libslapd/test.c
file modified
+1 -0
test/test_slapd.h
file modified
+3 -0
    Ticket 49372 - filter optimisation improvements for common queries
    
    Bug Description:  Due to the way we apply indexes to searches
    and the presence of the "filter test threshold" there are a number
    of queries which can be made faster if they understood the internals
    of our idl_set and index mechanisms. However, instead of expecting
    application authors to do this, we should provide it.
    
    Fix Description:  In the server we have some cases we want to
    achieve, and some to avoid:
    
    * If a union has an unindexed candidate, we throw away all work
      and return an ALLIDS idls.
    * In an intersection, if we have an idl that is less than
      filter test threshold, we return immediately that idl
      rather than accessing all others, and perform a filter
      test.
    
    Knowing these two properties, we can now look at improving filters
    for queries.
    
    In a common case, SSSD will give us a query which is a union of
    host cn and sudoHost rules. However, the sudoHost rules are
    substring searchs that are not able to be indexed - thus the whole
    filter becomes an unindexed search. IE:
    
    (|(cn=a)(cn=b)(cn= ....)(sudoHost=[*]*))
    
    So in this case we want to move the substring to the first query
    so that if it's un-indexed, we fail immediately with ALLIDS rather
    than opening the cn index.
    
    For intersection, we often see:
    
    (&(objectClass=account)(objectClass=posixAccount)(uid=william))
    
    The issue here is that the idls for account and posixAccount both
    may contain 100,000 items. Even with idl lookthrough limits, until
    we start to read these, we don't know if we will exceed that.
    
    A better query is:
    
    (&(uid=william)(objectClass=account)(objectClass=posixAccount))
    
    Because the uid=william index will contain a single item, this
    put's us below filter test threshold, and we will not open the
    objectClass indexes.
    
    In fact, in an intersection, it is almost always better to perform
    simple equalities first:
    
    (&(uid=william)(modifyTimestamp>=...)(sn=br*)(objectClass=posixAccount))
    
    In most other cases, we will not greatly benefit from re-arrangement
    due to the size of the idls involved we won't hit filter test. IE
    
    (&(modifyTimestamp>=...)(sn=br*)(objectClass=posixAccount))
    
    Would not be significantly better despite and possible arrangement
    without knowing the content of sn.
    
    So in summary, our rules for improving queries are:
    
    * unions-with-substrings should have substrings *first*
    * intersection-with-equality should have all non-objectclass
      equality filters *first*.
    
    https://pagure.io/389-ds-base/issue/49372
    https://pagure.io/389-ds-base/issue/50073
    
    Author: wibrown
    
    Original Review by: lkrispen, mreynolds (Thanks!)
    Review by: mreynolds (Thanks!)
    
        
file modified
+1 -0
file modified
+1 -0
file modified
+9 -0
file modified
+200 -33
file modified
+30 -0
file modified
+12 -0
file modified
+16 -2
file modified
+3 -0
file modified
+2 -0
file modified
+1 -0
file modified
+3 -0