search practice

[Piotr Wadas <pwadas@jewish.org.pl>]

Hello,
Using openldap 2.3.35.

I have some simpleString like "aaaBBBcccDDDeeeFFF", and I want
to find entries, in which a specified attribute "mySearchAttr"
has values like

entry 1:
mySearchAttr=aaaBBBcccDD

entry 2:
mySearchAttr=aa

entry 3:
mySearchAttr=aaaBBBc

entry 4:
mySearchAttr=aaaBBBcccDDDeeeFFF

and example entries which should NOT be covered by search:

entry 5:
mySearchAttr=aaaBBBcccDDDeeeFFFgggHHH

entry 6:
mySearchAttr=XXXyyyZZZaaaBBBcccDDDeeeFFFxxxYYYzzz

entry 7:
mySearchAttr=XXXyyyZZZaaaBBBcccXXXyyyZZZ

and so on. 
In other words, I want to find all entries having
a value of mySearchAttr attribute starting with
the same characters as simpleString, and shorter than or
equal to simpleString. 

What would be best practice to do such search? I imagined
three versions:

a. iterate over simpleString from 0 to strlen(simpleString) - 1, 
and do a search for 
"mySearchAttr=a", then for "mySearchAttr=aa", ..., 
then for "mySearchAttr=aaaBBBcccDDD" and so on until
end of simpleString is reached. But this would be
probably inefficient, regarding number of searches.

b. iterate over simpleString from 0 to strlen(simpleString) -1,
and build a really long filter from all partial strings, like

(|(mySearchAttr=a)(mySearchAttr=aa)(mySearchAttr=aaa)...)

but the string may be even 100+ characters long, so filter
would have 100+ conditions in it, which also seems not so well).

c. find all entries which have (myAttrSearch=*), sort by myAttrSearch,
and then iterate over search result, to extract final set of entries,
which have myAttrSearch matching all partial strings of simpleString.
But actually I don't even need to know all strings, I need
only the first one found.

On one hand - simpleString may be long. on the other hand - number
of entries (c) may hundreds, or even thousands of entries,
and all partial strings of simpleString should be compared to each
value of mySearchAttr attribute.

Finally I search for mySearchAtt=*, then I sort, next I iterate
over search result, and for each entry, and each attribute value,
next if the value is shorter than or equal to simpleString, I iterate over 
all partial strings (starting from left), and matching by some strcasecmp 
- all of this until the first is found. Even some regex value
matching wouldn't be solution for "aa", ..., "aaaBBB",...

Any hints ? Actually mySearchAttr keeps for me some filesystem object name
string. Knowing some fsobject name like /some/dir/subfileordir, I want 
to find all entries, which are related to objects _above_ my fsobject 
in filesystem directory tree. I have no special characters in directory 
and file names, only letters, digits and slashes. This actually
is used to check some fs directory access permissions - to determine
whether access to /some/sub/dir/or/file should be granted, I need
to make sure, that there's no above object which restricts access,
it should work like http access control.

Isn't there really some filter to cover this? Did I miss something
trivial? :)

Regards,
Piotr