Re: [389-devel] RFC: New Design: Fine Grained ID List Size
Rich Megginson wrote: On 09/12/2013 07:08 PM, David Boreham wrote: On 9/11/2013 11:41 AM, Howard Chu wrote: Just out of curiosity, why is keeping a count per key a problem? If you're using BDB duplicate key support, can't you just use cursor-c_count() to get this? I.e., BDB already maintains key counts internally, why not leverage that? afaik you need to pass the DB_RECNUM flag at DB creation time to get record counting behavior, and it imposes a performance and concurrency penalty on writes. Also afaik 389DS does not set that flag except on VLV indexes (which need it, and coincidentally were the original reason for the feature being added to BDB). I'm using bdb 4.7 on RHEL 6. Looking at the code, it appears the dbc-count method for btree is __bamc_count() in bt_cursor.c. I'm not sure, but it looks as though this function has to iterate each page counting the duplicates on each page, which makes it a non-starter. Unless I'm mistaken, it doesn't look as though it keeps a counter on each update, then simply returns the counter. I don't see any code which would make the behavior different depending on if DB_RECNUM is used when the database is created. Ah totally forgot about that, it's been a couple years since I looked inside that code. LMDB updates record counts on every write op so returning the count is zero-cost. (Ironically we don't use this fact to optimize filter evaluation order in OpenLDAP. Probably should...) Also due to the fact that writing a leaf page requires every page up to the root to be updated (copy-on-write design), updating the counts also comes for free since the root page had to be updated anyway. (Or put another way, LMDB writes are already slow by design; updating the counters doesn't make them any slower.) -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/ -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel
Re: [389-devel] RFC: New Design: Fine Grained ID List Size
On 09/12/2013 07:08 PM, David Boreham wrote: On 9/11/2013 11:41 AM, Howard Chu wrote: Just out of curiosity, why is keeping a count per key a problem? If you're using BDB duplicate key support, can't you just use cursor-c_count() to get this? I.e., BDB already maintains key counts internally, why not leverage that? afaik you need to pass the DB_RECNUM flag at DB creation time to get record counting behavior, and it imposes a performance and concurrency penalty on writes. Also afaik 389DS does not set that flag except on VLV indexes (which need it, and coincidentally were the original reason for the feature being added to BDB). I'm using bdb 4.7 on RHEL 6. Looking at the code, it appears the dbc-count method for btree is __bamc_count() in bt_cursor.c. I'm not sure, but it looks as though this function has to iterate each page counting the duplicates on each page, which makes it a non-starter. Unless I'm mistaken, it doesn't look as though it keeps a counter on each update, then simply returns the counter. I don't see any code which would make the behavior different depending on if DB_RECNUM is used when the database is created. -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel
Re: [389-devel] RFC: New Design: Fine Grained ID List Size
On 09/13/2013 02:39 PM, David Boreham wrote:
On 9/13/2013 2:18 PM, Rich Megginson wrote:
On 09/12/2013 07:08 PM, David Boreham wrote:
On 9/11/2013 11:41 AM, Howard Chu wrote:
Just out of curiosity, why is keeping a count per key a problem? If
you're using BDB duplicate key support, can't you just use
cursor-c_count() to get this? I.e., BDB already maintains key
counts internally, why not leverage that?
afaik you need to pass the DB_RECNUM flag at DB creation time to get
record counting behavior, and it imposes a performance and
concurrency penalty on writes. Also afaik 389DS does not set that
flag except on VLV indexes (which need it, and coincidentally were
the original reason for the feature being added to BDB).
I'm using bdb 4.7 on RHEL 6.
Looking at the code, it appears the dbc-count method for btree is
__bamc_count() in bt_cursor.c. I'm not sure, but it looks as though
this function has to iterate each page counting the duplicates on
each page, which makes it a non-starter. Unless I'm mistaken, it
doesn't look as though it keeps a counter on each update, then simply
returns the counter. I don't see any code which would make the
behavior different depending on if DB_RECNUM is used when the
database is created.
The DB_RECNUM count feature is not accessed via dbc-count() but
through the dbc-c_get() call, passing DB_GET_RECNO, positioning at
the last key. You do also need to use nested btrees for it to count
the dups, afaik (but we're doing that in the DS indexes already I
believe).
I wrote a small bdbtest.py script which uses the python bdb interface.
https://github.com/richm/scripts/blob/master/bdbtest.py
This creates an env, opens a db with
bsddb.db.DB_DUPSORT|bsddb.db.DB_RECNUM, adds several non-dup and dup
records, opens a cursor and iterates them. This is the output:
open dbenv in /var/tmp/dbtest
open db /var/tmp/dbtest/dbtest.db4
no txn records
key=key0 val=data0
extra=('', '\x01\x00\x00\x00')
snip
key=key9 val=data9
extra=('', '\n\x00\x00\x00')
key=multikey val=multidata0
extra=('', '\x0b\x00\x00\x00')
snip
key=multikey val=multidata9
extra=('', '\x0b\x00\x00\x00')
The extra is the str() output of cur.get(bsddb.db.DB_GET_RECNO)
So for all of the dup records, the recno is the same '\b' == 11?
I'm probably missing something, but how do I use this to get the number
of duplicates?
--
389-devel mailing list
389-devel@lists.fedoraproject.org
https://admin.fedoraproject.org/mailman/listinfo/389-devel
--
389-devel mailing list
389-devel@lists.fedoraproject.org
https://admin.fedoraproject.org/mailman/listinfo/389-devel
Re: [389-devel] RFC: New Design: Fine Grained ID List Size
On 09/12/2013 07:39 AM, thierry bordaz wrote: On 09/10/2013 04:35 PM, Ludwig Krispenz wrote: On 09/10/2013 04:29 PM, Rich Megginson wrote: On 09/10/2013 01:47 AM, Ludwig Krispenz wrote: On 09/09/2013 07:19 PM, Rich Megginson wrote: On 09/09/2013 02:27 AM, Ludwig Krispenz wrote: On 09/07/2013 05:02 AM, David Boreham wrote: On 9/6/2013 8:49 PM, Nathan Kinder wrote: This is a good idea, and it is something that we discussed briefly off-list. The only downside is that we need to change the index format to keep a count of ids for each key. Implementing this isn't a big problem, but it does mean that the existing indexes need to be updated to populate the count based off of the contents (as you mention above). I don't think you need to do this (I certainly wasn't advocating doing so). The statistics state is much the same as that proposed in Rich's design. In fact you could probably just use that same information. My idea is more about where and how you use the information. All you need is something associated with each index that says not much point looking here if you're after something specific, move along, look somewhere else instead. This is much the same information as don't use a high scan limit here. In the short term, we are looking for a way to be able to improve performance for specific search filters that are not possible to modify on the client side (for whatever reason) while leaving the index file format exactly as it is. I still feel that there is potentially great value in keeping a count of ids per key so we can optimize things on the server side automatically without the need for complex index configuration on the administrator's part. I think we should consider this for an additional future enhancement. I'm saying the same thing. Keeping a cardinality count per key is way more than I'm proposing, and I'm not sure how useful that would be anyway, unless you want to do OLAP in the DS ;) we have the cardinality of the key in old-idl and this makes some searches where parts of the filter are allids fast. I'm late in the discussion, but I think Rich's proposal is very promising to address all the problems related to allids in new-idl. We could then eventually rework filter ordering based on these configurations. Right now we only have a filter ordering based on index type and try to postpone = or similar filter as they are known to be costly, but this could be more elaborate. An alternative would be to have some kind of index lookup caching. In the example in ticket 47474 the filter is ((|(objectClass=organizationalPerson)(objectClass=inetOrgPerson)(objectClass=organization)(objectClass=organizationalUnit)(objectClass=groupOf Names)(objectClass=groupOfUniqueNames)(objectClass=group))(c3sUserID=EndUser078458)) and probably only the c3sUserID=x part will change, if we cache the result for the ((|(objectClass=... part, even if it is expensive, it would be done only once. Thanks everyone for the comments. I have added Noriko's suggestion: http://port389.org/wiki/Design/Fine_Grained_ID_List_Size David, Ludwig: Does the current design address your concerns, and/or provide the necessary first step for further refinements? yes, the topic of filter reordering or caching could be looked at independently. Just one concern abou the syntax: nsIndexIDListScanLimit: maxsize[:indextype][:flag[,flag...]][:value[,value...]] since everything is optional, how do you decide if in nsIndexIDListScanLimit: 6:eq:AND AND is a value or a flag ? and as it defines limits for specific keys, could the attributname reflect this, eg nsIndexKeyIDListScanLimit or nsIndexKeyScanLimit or ... ? Thanks, yes, it is ambiguous. I think it may have to use keyword=value, so something like this: nsIndexIDListScanLimit: limit=NNN [type=eq[,sub]] [flags=ADD[,OR]] [values=val[,val...]] That should be easy to parse for both humans and machines. For values, will have to figure out a way to have escapes (e.g. if a value contains a comma or an escape character). Was thinking of using LDAP escapes (e.g. \, or \032) they should be treated as in filters and normalized, in the config it should be the string representation according to the attributetype Hi, I was wondering if this configuration attribute at the index level, could not also be implemented at the bind-base level. It could be - it would be more difficult to do - you would have to have the nsIndexIDListScanLimit attribute specified in the user entry, and it would have to specify the attribute type e.g. dn: uid=admin, nsIndexIDListScanLimit: limit= attr=objectclass type=eq value=inetOrgPerson Or perhaps a new attribute - nsIndexIDListScanLimit should be not operational for use in nsIndex, but should be operational for use in a user entry. If an application use to bind with a given entry, it could use its own limitations put for example into operational
Re: [389-devel] RFC: New Design: Fine Grained ID List Size
On 09/12/2013 04:40 PM, Rich Megginson wrote: On 09/12/2013 07:39 AM, thierry bordaz wrote: On 09/10/2013 04:35 PM, Ludwig Krispenz wrote: On 09/10/2013 04:29 PM, Rich Megginson wrote: On 09/10/2013 01:47 AM, Ludwig Krispenz wrote: On 09/09/2013 07:19 PM, Rich Megginson wrote: On 09/09/2013 02:27 AM, Ludwig Krispenz wrote: On 09/07/2013 05:02 AM, David Boreham wrote: On 9/6/2013 8:49 PM, Nathan Kinder wrote: This is a good idea, and it is something that we discussed briefly off-list. The only downside is that we need to change the index format to keep a count of ids for each key. Implementing this isn't a big problem, but it does mean that the existing indexes need to be updated to populate the count based off of the contents (as you mention above). I don't think you need to do this (I certainly wasn't advocating doing so). The statistics state is much the same as that proposed in Rich's design. In fact you could probably just use that same information. My idea is more about where and how you use the information. All you need is something associated with each index that says not much point looking here if you're after something specific, move along, look somewhere else instead. This is much the same information as don't use a high scan limit here. In the short term, we are looking for a way to be able to improve performance for specific search filters that are not possible to modify on the client side (for whatever reason) while leaving the index file format exactly as it is. I still feel that there is potentially great value in keeping a count of ids per key so we can optimize things on the server side automatically without the need for complex index configuration on the administrator's part. I think we should consider this for an additional future enhancement. I'm saying the same thing. Keeping a cardinality count per key is way more than I'm proposing, and I'm not sure how useful that would be anyway, unless you want to do OLAP in the DS ;) we have the cardinality of the key in old-idl and this makes some searches where parts of the filter are allids fast. I'm late in the discussion, but I think Rich's proposal is very promising to address all the problems related to allids in new-idl. We could then eventually rework filter ordering based on these configurations. Right now we only have a filter ordering based on index type and try to postpone = or similar filter as they are known to be costly, but this could be more elaborate. An alternative would be to have some kind of index lookup caching. In the example in ticket 47474 the filter is ((|(objectClass=organizationalPerson)(objectClass=inetOrgPerson)(objectClass=organization)(objectClass=organizationalUnit)(objectClass=groupOf Names)(objectClass=groupOfUniqueNames)(objectClass=group))(c3sUserID=EndUser078458)) and probably only the c3sUserID=x part will change, if we cache the result for the ((|(objectClass=... part, even if it is expensive, it would be done only once. Thanks everyone for the comments. I have added Noriko's suggestion: http://port389.org/wiki/Design/Fine_Grained_ID_List_Size David, Ludwig: Does the current design address your concerns, and/or provide the necessary first step for further refinements? yes, the topic of filter reordering or caching could be looked at independently. Just one concern abou the syntax: nsIndexIDListScanLimit: maxsize[:indextype][:flag[,flag...]][:value[,value...]] since everything is optional, how do you decide if in nsIndexIDListScanLimit: 6:eq:AND AND is a value or a flag ? and as it defines limits for specific keys, could the attributname reflect this, eg nsIndexKeyIDListScanLimit or nsIndexKeyScanLimit or ... ? Thanks, yes, it is ambiguous. I think it may have to use keyword=value, so something like this: nsIndexIDListScanLimit: limit=NNN [type=eq[,sub]] [flags=ADD[,OR]] [values=val[,val...]] That should be easy to parse for both humans and machines. For values, will have to figure out a way to have escapes (e.g. if a value contains a comma or an escape character). Was thinking of using LDAP escapes (e.g. \, or \032) they should be treated as in filters and normalized, in the config it should be the string representation according to the attributetype Hi, I was wondering if this configuration attribute at the index level, could not also be implemented at the bind-base level. It could be - it would be more difficult to do - you would have to have the nsIndexIDListScanLimit attribute specified in the user entry, and it would have to specify the attribute type e.g. dn: uid=admin, nsIndexIDListScanLimit: limit= attr=objectclass type=eq value=inetOrgPerson Or perhaps a new attribute - nsIndexIDListScanLimit should be not operational for use in nsIndex, but should be operational for use in a user entry. Or it could be handled as a policy, like password policy, have a default one and the
Re: [389-devel] RFC: New Design: Fine Grained ID List Size
On 9/9/2013 11:19 AM, Rich Megginson wrote: Thanks everyone for the comments. I have added Noriko's suggestion: http://port389.org/wiki/Design/Fine_Grained_ID_List_Size David, Ludwig: Does the current design address your concerns, and/or provide the necessary first step for further refinements? Looks good to me. -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel
Re: [389-devel] RFC: New Design: Fine Grained ID List Size
On 9/11/2013 11:41 AM, Howard Chu wrote: Just out of curiosity, why is keeping a count per key a problem? If you're using BDB duplicate key support, can't you just use cursor-c_count() to get this? I.e., BDB already maintains key counts internally, why not leverage that? afaik you need to pass the DB_RECNUM flag at DB creation time to get record counting behavior, and it imposes a performance and concurrency penalty on writes. Also afaik 389DS does not set that flag except on VLV indexes (which need it, and coincidentally were the original reason for the feature being added to BDB). -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel
Re: [389-devel] RFC: New Design: Fine Grained ID List Size
On 09/09/2013 07:19 PM, Rich Megginson wrote: On 09/09/2013 02:27 AM, Ludwig Krispenz wrote: On 09/07/2013 05:02 AM, David Boreham wrote: On 9/6/2013 8:49 PM, Nathan Kinder wrote: This is a good idea, and it is something that we discussed briefly off-list. The only downside is that we need to change the index format to keep a count of ids for each key. Implementing this isn't a big problem, but it does mean that the existing indexes need to be updated to populate the count based off of the contents (as you mention above). I don't think you need to do this (I certainly wasn't advocating doing so). The statistics state is much the same as that proposed in Rich's design. In fact you could probably just use that same information. My idea is more about where and how you use the information. All you need is something associated with each index that says not much point looking here if you're after something specific, move along, look somewhere else instead. This is much the same information as don't use a high scan limit here. In the short term, we are looking for a way to be able to improve performance for specific search filters that are not possible to modify on the client side (for whatever reason) while leaving the index file format exactly as it is. I still feel that there is potentially great value in keeping a count of ids per key so we can optimize things on the server side automatically without the need for complex index configuration on the administrator's part. I think we should consider this for an additional future enhancement. I'm saying the same thing. Keeping a cardinality count per key is way more than I'm proposing, and I'm not sure how useful that would be anyway, unless you want to do OLAP in the DS ;) we have the cardinality of the key in old-idl and this makes some searches where parts of the filter are allids fast. I'm late in the discussion, but I think Rich's proposal is very promising to address all the problems related to allids in new-idl. We could then eventually rework filter ordering based on these configurations. Right now we only have a filter ordering based on index type and try to postpone = or similar filter as they are known to be costly, but this could be more elaborate. An alternative would be to have some kind of index lookup caching. In the example in ticket 47474 the filter is ((|(objectClass=organizationalPerson)(objectClass=inetOrgPerson)(objectClass=organization)(objectClass=organizationalUnit)(objectClass=groupOf Names)(objectClass=groupOfUniqueNames)(objectClass=group))(c3sUserID=EndUser078458)) and probably only the c3sUserID=x part will change, if we cache the result for the ((|(objectClass=... part, even if it is expensive, it would be done only once. Thanks everyone for the comments. I have added Noriko's suggestion: http://port389.org/wiki/Design/Fine_Grained_ID_List_Size David, Ludwig: Does the current design address your concerns, and/or provide the necessary first step for further refinements? yes, the topic of filter reordering or caching could be looked at independently. Just one concern abou the syntax: nsIndexIDListScanLimit: maxsize[:indextype][:flag[,flag...]][:value[,value...]] since everything is optional, how do you decide if in nsIndexIDListScanLimit: 6:eq:AND AND is a value or a flag ? and as it defines limits for specific keys, could the attributname reflect this, eg nsIndexKeyIDListScanLimit or nsIndexKeyScanLimit or ... ? -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel
Re: [389-devel] RFC: New Design: Fine Grained ID List Size
On 09/10/2013 04:29 PM, Rich Megginson wrote: On 09/10/2013 01:47 AM, Ludwig Krispenz wrote: On 09/09/2013 07:19 PM, Rich Megginson wrote: On 09/09/2013 02:27 AM, Ludwig Krispenz wrote: On 09/07/2013 05:02 AM, David Boreham wrote: On 9/6/2013 8:49 PM, Nathan Kinder wrote: This is a good idea, and it is something that we discussed briefly off-list. The only downside is that we need to change the index format to keep a count of ids for each key. Implementing this isn't a big problem, but it does mean that the existing indexes need to be updated to populate the count based off of the contents (as you mention above). I don't think you need to do this (I certainly wasn't advocating doing so). The statistics state is much the same as that proposed in Rich's design. In fact you could probably just use that same information. My idea is more about where and how you use the information. All you need is something associated with each index that says not much point looking here if you're after something specific, move along, look somewhere else instead. This is much the same information as don't use a high scan limit here. In the short term, we are looking for a way to be able to improve performance for specific search filters that are not possible to modify on the client side (for whatever reason) while leaving the index file format exactly as it is. I still feel that there is potentially great value in keeping a count of ids per key so we can optimize things on the server side automatically without the need for complex index configuration on the administrator's part. I think we should consider this for an additional future enhancement. I'm saying the same thing. Keeping a cardinality count per key is way more than I'm proposing, and I'm not sure how useful that would be anyway, unless you want to do OLAP in the DS ;) we have the cardinality of the key in old-idl and this makes some searches where parts of the filter are allids fast. I'm late in the discussion, but I think Rich's proposal is very promising to address all the problems related to allids in new-idl. We could then eventually rework filter ordering based on these configurations. Right now we only have a filter ordering based on index type and try to postpone = or similar filter as they are known to be costly, but this could be more elaborate. An alternative would be to have some kind of index lookup caching. In the example in ticket 47474 the filter is ((|(objectClass=organizationalPerson)(objectClass=inetOrgPerson)(objectClass=organization)(objectClass=organizationalUnit)(objectClass=groupOf Names)(objectClass=groupOfUniqueNames)(objectClass=group))(c3sUserID=EndUser078458)) and probably only the c3sUserID=x part will change, if we cache the result for the ((|(objectClass=... part, even if it is expensive, it would be done only once. Thanks everyone for the comments. I have added Noriko's suggestion: http://port389.org/wiki/Design/Fine_Grained_ID_List_Size David, Ludwig: Does the current design address your concerns, and/or provide the necessary first step for further refinements? yes, the topic of filter reordering or caching could be looked at independently. Just one concern abou the syntax: nsIndexIDListScanLimit: maxsize[:indextype][:flag[,flag...]][:value[,value...]] since everything is optional, how do you decide if in nsIndexIDListScanLimit: 6:eq:AND AND is a value or a flag ? and as it defines limits for specific keys, could the attributname reflect this, eg nsIndexKeyIDListScanLimit or nsIndexKeyScanLimit or ... ? Thanks, yes, it is ambiguous. I think it may have to use keyword=value, so something like this: nsIndexIDListScanLimit: limit=NNN [type=eq[,sub]] [flags=ADD[,OR]] [values=val[,val...]] That should be easy to parse for both humans and machines. For values, will have to figure out a way to have escapes (e.g. if a value contains a comma or an escape character). Was thinking of using LDAP escapes (e.g. \, or \032) they should be treated as in filters and normalized, in the config it should be the string representation according to the attributetype -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel
Re: [389-devel] RFC: New Design: Fine Grained ID List Size
On 09/07/2013 05:02 AM, David Boreham wrote: On 9/6/2013 8:49 PM, Nathan Kinder wrote: This is a good idea, and it is something that we discussed briefly off-list. The only downside is that we need to change the index format to keep a count of ids for each key. Implementing this isn't a big problem, but it does mean that the existing indexes need to be updated to populate the count based off of the contents (as you mention above). I don't think you need to do this (I certainly wasn't advocating doing so). The statistics state is much the same as that proposed in Rich's design. In fact you could probably just use that same information. My idea is more about where and how you use the information. All you need is something associated with each index that says not much point looking here if you're after something specific, move along, look somewhere else instead. This is much the same information as don't use a high scan limit here. In the short term, we are looking for a way to be able to improve performance for specific search filters that are not possible to modify on the client side (for whatever reason) while leaving the index file format exactly as it is. I still feel that there is potentially great value in keeping a count of ids per key so we can optimize things on the server side automatically without the need for complex index configuration on the administrator's part. I think we should consider this for an additional future enhancement. I'm saying the same thing. Keeping a cardinality count per key is way more than I'm proposing, and I'm not sure how useful that would be anyway, unless you want to do OLAP in the DS ;) we have the cardinality of the key in old-idl and this makes some searches where parts of the filter are allids fast. I'm late in the discussion, but I think Rich's proposal is very promising to address all the problems related to allids in new-idl. We could then eventually rework filter ordering based on these configurations. Right now we only have a filter ordering based on index type and try to postpone = or similar filter as they are known to be costly, but this could be more elaborate. An alternative would be to have some kind of index lookup caching. In the example in ticket 47474 the filter is ((|(objectClass=organizationalPerson)(objectClass=inetOrgPerson)(objectClass=organization)(objectClass=organizationalUnit)(objectClass=groupOf Names)(objectClass=groupOfUniqueNames)(objectClass=group))(c3sUserID=EndUser078458)) and probably only the c3sUserID=x part will change, if we cache the result for the ((|(objectClass=... part, even if it is expensive, it would be done only once. -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel
Re: [389-devel] RFC: New Design: Fine Grained ID List Size
Rich Megginson wrote: Please review and comment: http://port389.org/wiki/Design/Fine_Grained_ID_List_Size -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel Hi Rich, A nice design! It looks promising to solve the sticky problems. Can I add a request -- a flag or something to the value to switch the behaviour? E.g., nsIndexIDListScanLimit: maxsize[:indextype]/[:flags]/[:value[,value...]] The flags could be KEYWORD_1|KEYWORD_2|... By default, no flags. I only have one use case for now, but we may want to apply the scan limit only when the specific filter is in AND, i.e., ((objectclass=inetorgperson)(uid=UserA)), but not to the standalone filter (objectclass=inetorgperson). This could be useful when DB stores millions of inetorgperson's as well as millions of other objectclasses. But not useful at all, if 99% of the entries are inetorgperson. So, for example, the keyword could be ANDONLY...? Thanks, --noriko -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel
Re: [389-devel] RFC: New Design: Fine Grained ID List Size
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. -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel
Re: [389-devel] RFC: New Design: Fine Grained ID List Size
On 9/6/2013 8:49 PM, Nathan Kinder wrote: This is a good idea, and it is something that we discussed briefly off-list. The only downside is that we need to change the index format to keep a count of ids for each key. Implementing this isn't a big problem, but it does mean that the existing indexes need to be updated to populate the count based off of the contents (as you mention above). I don't think you need to do this (I certainly wasn't advocating doing so). The statistics state is much the same as that proposed in Rich's design. In fact you could probably just use that same information. My idea is more about where and how you use the information. All you need is something associated with each index that says not much point looking here if you're after something specific, move along, look somewhere else instead. This is much the same information as don't use a high scan limit here. In the short term, we are looking for a way to be able to improve performance for specific search filters that are not possible to modify on the client side (for whatever reason) while leaving the index file format exactly as it is. I still feel that there is potentially great value in keeping a count of ids per key so we can optimize things on the server side automatically without the need for complex index configuration on the administrator's part. I think we should consider this for an additional future enhancement. I'm saying the same thing. Keeping a cardinality count per key is way more than I'm proposing, and I'm not sure how useful that would be anyway, unless you want to do OLAP in the DS ;) -- 389-devel mailing list 389-devel@lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/389-devel
