[389-devel] RFC: New Design: Fine Grained ID List Size

[David Boreham]

On 9/6/2013 3:05 PM, Rich Megginson wrote:
> Please review and comment:
>
> http://port389.org/wiki/Design/Fine_Grained_ID_List_Size

This looks interesting. I suppose this is similar to a SQL database's 
concept of index statistics, and also query hints supplied by the 
client. Perhaps more of a "server index hint".

This may already been discussed, but in reading through the design doc, 
I was wondering about having the query planner (such as there is one in 
the DS) take note of the index hints prior to executing any lookups. 
This is similar to a SQL database's behavior executing such a query, 
when it sees index statistics that indicate low cardinality. To expand:

I seem to recall that there is already code to avoid looking up a low 
cardinality index, if and only if the intersection predicates are 
ordered suitably, by checking the id list size between index lookups. 
Thus, if there is a filter for uid=foo & objectclass=bar (apologies for 
not using the wacky LDAP string filter syntax...), then if only one hit 
is seen from the uid=foo lookup, the objectclass=bar lookup is skipped. 
If that's still the case, then the example "bad" search would become 
good if the client were to re-order the predicates. Of course often the 
client can not be modified, so:

My thought is to add that functionality to the server -- the client can 
then submit filters without regard to the internal workings of the 
server. The server checks the predicates against Rich's new index hints, 
and can therefore make the correct ordering itself. The benefit would be 
that no additional index lookup would be done, vs one that meets the id 
limit pertaining to the index, and the administrator only has to know 
that the index has low cardinality. A further "refinement" would be to 
make a tool that populates the hint data based on analysis of the index 
content, a la SQL "UPDATE STATISTICS".

Hopefully this makes sense. Apologies if it has already been considered.