summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAndrew Tridgell <tridge@samba.org>2009-06-01 22:03:20 +1000
committerAndrew Tridgell <tridge@samba.org>2009-06-01 22:03:20 +1000
commit73c8566d957af8c823a48912b66aae71b002259b (patch)
treee97cbb3a12dc703cc20091c592e7c8122544aa8b
parenta0edb50552090341760c9dfcf27a71df8100e1a5 (diff)
downloadsamba-73c8566d957af8c823a48912b66aae71b002259b.tar.gz
samba-73c8566d957af8c823a48912b66aae71b002259b.tar.bz2
samba-73c8566d957af8c823a48912b66aae71b002259b.zip
use the unique flag on ldb attributes to optimise & clauses
When a attribute is marked unique we know that if we find a match it will be the only possible match. This means that in a list of subtrees connected by an &, it is best to first load the index values for the unique entries, as if they find something then we know we won't have to look any further. This helps with searches like this: (&(objectclass=user)(samaccountname=tridge)) the old code would first have loaded the very large index for the objectclass=user attribute, and then loaded the single entry for samaccountname=tridge. Now we load the samaccountname=tridge entry first, notice that it gives us a single result, and stop, thereby skipping the load of the objectclass=user index record completely.
-rw-r--r--source4/lib/ldb/ldb_tdb/ldb_index.c118
1 files changed, 72 insertions, 46 deletions
diff --git a/source4/lib/ldb/ldb_tdb/ldb_index.c b/source4/lib/ldb/ldb_tdb/ldb_index.c
index 300cf7c5e9..fab60cb125 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_index.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_index.c
@@ -796,6 +796,18 @@ static int ltdb_index_dn_not(struct ldb_module *module,
return LDB_ERR_OPERATIONS_ERROR;
}
+
+static bool ltdb_index_unique(struct ldb_context *ldb,
+ const char *attr)
+{
+ const struct ldb_schema_attribute *a;
+ a = ldb_schema_attribute_by_name(ldb, attr);
+ if (a->flags & LDB_ATTR_FLAG_UNIQUE_INDEX) {
+ return true;
+ }
+ return false;
+}
+
/*
AND two index results
*/
@@ -806,7 +818,7 @@ static int ltdb_index_dn_and(struct ldb_module *module,
{
struct ldb_context *ldb;
unsigned int i;
- int ret;
+ int ret, pass;
ldb = ldb_module_get_ctx(module);
@@ -814,57 +826,71 @@ static int ltdb_index_dn_and(struct ldb_module *module,
list->dn = NULL;
list->count = 0;
- for (i=0;i<tree->u.list.num_elements;i++) {
- struct dn_list *list2;
- int v;
-
- list2 = talloc(module, struct dn_list);
- if (list2 == NULL) {
- return LDB_ERR_OPERATIONS_ERROR;
- }
-
- v = ltdb_index_dn(module, tree->u.list.elements[i], index_list, list2);
-
- if (v == LDB_ERR_NO_SUCH_OBJECT) {
- /* 0 && X == 0 */
- talloc_free(list->dn);
- talloc_free(list2);
- return LDB_ERR_NO_SUCH_OBJECT;
- }
-
- if (v != LDB_SUCCESS && v != LDB_ERR_NO_SUCH_OBJECT) {
- talloc_free(list2);
- continue;
- }
-
- if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
- ret = LDB_SUCCESS;
- talloc_free(list->dn);
- list->dn = talloc_move(list, &list2->dn);
- list->count = list2->count;
- } else {
- if (list_intersect(ldb, list, list2) == -1) {
- talloc_free(list2);
+ for (pass=0;pass<=1;pass++) {
+ /* in the first pass we only look for unique simple
+ equality tests, in the hope of avoiding having to look
+ at any others */
+ bool only_unique = pass==0?true:false;
+
+ for (i=0;i<tree->u.list.num_elements;i++) {
+ struct dn_list *list2;
+ int v;
+ bool is_unique = false;
+ const struct ldb_parse_tree *subtree = tree->u.list.elements[i];
+
+ if (subtree->operation == LDB_OP_EQUALITY &&
+ ltdb_index_unique(ldb, subtree->u.equality.attr)) {
+ is_unique = true;
+ }
+ if (is_unique != only_unique) continue;
+
+ list2 = talloc(module, struct dn_list);
+ if (list2 == NULL) {
return LDB_ERR_OPERATIONS_ERROR;
}
- }
-
- talloc_free(list2);
-
- if (list->count == 0) {
- talloc_free(list->dn);
- return LDB_ERR_NO_SUCH_OBJECT;
- }
+
+ v = ltdb_index_dn(module, subtree, index_list, list2);
- if (list->count == 1) {
- /* it isn't worth loading the next part of the tree */
- break;
+ if (v == LDB_ERR_NO_SUCH_OBJECT) {
+ /* 0 && X == 0 */
+ talloc_free(list->dn);
+ talloc_free(list2);
+ return LDB_ERR_NO_SUCH_OBJECT;
+ }
+
+ if (v != LDB_SUCCESS && v != LDB_ERR_NO_SUCH_OBJECT) {
+ talloc_free(list2);
+ continue;
+ }
+
+ if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
+ ret = LDB_SUCCESS;
+ talloc_free(list->dn);
+ list->dn = talloc_move(list, &list2->dn);
+ list->count = list2->count;
+ } else {
+ if (list_intersect(ldb, list, list2) == -1) {
+ talloc_free(list2);
+ return LDB_ERR_OPERATIONS_ERROR;
+ }
+ }
+
+ talloc_free(list2);
+
+ if (list->count == 0) {
+ talloc_free(list->dn);
+ return LDB_ERR_NO_SUCH_OBJECT;
+ }
+
+ if (list->count == 1) {
+ /* it isn't worth loading the next part of the tree */
+ return ret;
+ }
}
- }
-
+ }
return ret;
}
-
+
/*
AND index results and ONE level special index
*/