CODEWITHSUNDEEP
phpldap
IlludiumPu36
IlludiumPu36

Reputation: 4304

LDAP - optimising filter

How can I optimise the following LDAP filter to remove the duplication in the code?

(|(&(cn=PATH*)(cn=*2013*)(|(cn=*_S1_*)(cn=*_1_*)))(&(cn=MICR*)(cn=*2013*)(|(cn=*_S1_*)(cn=*_1_*))))

Upvotes: 0

Views: 108

Answers (1)

mr.spuratic
mr.spuratic

Reputation: 10127

In general, the single most important thing you can do to optimise is to make sure the correct indexes are in place on the LDAP server. This doesn't help simplify an actual filter though... This problem is (almost) simple boolean expression simplification.

Firstly, convert from LDAP filter prefix notation to infix notation (some example algorithms). I'm using place-holder symbols for the filter items:

a  cn=PATH*
b  cn=*2013*
c  cn=*_S1_*
d  cn=*_1_*
e  cn=MICR*

So this prefix-notation filter

(|(&(a)(b)(|(c)(d)))(&(e)(b)(|(c)(d))))

becomes this infix notation filter:

 (a&b&(c|d))|(e&b&(c|d))

And then use any normal boolean expression optimiser/simplifier, I'm lazy so I'll let Wolfram do it.

Now fish out the simplest minimal form result, the DNF or CNF forms are only and and or operations, these can be readily used as LDAP filters (anything without ⊻ "xor" is likely good). The CNF is clearly simpler here:

DNF   (a ∧ b ∧ c) ∨ (a ∧ b ∧ d) ∨ (b ∧ c ∧ e) ∨ (b ∧ d ∧ e)
CNF   (a ∨ e) ∧ b ∧ (c ∨ d)

("∧" is "and", "∨" is "or")

Turning it back into a prefix filter and substituting the symbols you get:

(& (| (cn=PATH*)(cn=MICR*) )
   (cn=*2013*)
   (| (cn=*_S1_*)(cn=*_1_*) )
)

There is one last trivial optimisation, you can merge some types of sub-string matches without using operators when they don't overlap:

(& (| (cn=PATH*2013*)(cn=MICR*2013*))
   (| (cn=*_S1_*)(cn=*_1_*))
)

If you need to do this programmatically for arbitrary filters you can readily find code to perform prefix/infix conversion, and boolean expression optimisation in PHP, these are common problems in parsers and expression evaluation.

I suspect you'll need to special-case merging terms with prefix/infix/suffix strings when you have zero or one of each, I'm not aware of a name for such a process. You'll need it to be aware of the LDAP attribute= syntax in any case.

Upvotes: 1

Related Questions