You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@couchdb.apache.org by wi...@apache.org on 2017/09/20 07:43:21 UTC
[couchdb] branch master updated: Fix json index selection (#816)
This is an automated email from the ASF dual-hosted git repository.
willholley pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/couchdb.git
The following commit(s) were added to refs/heads/master by this push:
new dae81be Fix json index selection (#816)
dae81be is described below
commit dae81befd57940d0777402b21c05a2e3c58014d7
Author: Will Holley <wi...@gmail.com>
AuthorDate: Wed Sep 20 08:43:19 2017 +0100
Fix json index selection (#816)
JSON index selection in Mango previously deemed an
index to be usable if a range scan on the first component
of its compound key could be generated from the query selector.
For instance, if I had an index:
[A, B]
is_usable would return true for the selector:
{"A": "foo"}
This is incorrect because JSON indexes only index documents that contain all
the fields in the index; null values are ok, but the field must be present.
That means that for the above selector, the index would implicitly include
only documents where B exists, missing documents where {"A":5} matched but
field B was not present.
This commit changes is_usable so that it only returns true if all the keys
in the index are required to exist by the selector. This means that in the
worst case e.g. none of the predicates can be used to generate a range query,
we should end up performing a full index scan, but this is still more
efficient than a full database scan.
We leave the generation of the optimal range for a given index as a separate
exercise - currently this happens after index selection.
Potentially we'd want to score indexes during index selection based on their
ability to restrict the result set, etc.
---
src/mango/src/mango_idx_view.erl | 11 +--
src/mango/src/mango_selector.erl | 110 +++++++++++++++++++++++++++++-
src/mango/test/03-operator-test.py | 6 +-
src/mango/test/05-index-selection-test.py | 74 +++++++++++++++++++-
src/mango/test/user_docs.py | 1 -
5 files changed, 191 insertions(+), 11 deletions(-)
diff --git a/src/mango/src/mango_idx_view.erl b/src/mango/src/mango_idx_view.erl
index d5dcd0c..7e9e646 100644
--- a/src/mango/src/mango_idx_view.erl
+++ b/src/mango/src/mango_idx_view.erl
@@ -114,11 +114,12 @@ columns(Idx) ->
is_usable(Idx, Selector) ->
- % This index is usable if at least the first column is
- % a member of the indexable fields of the selector.
- Columns = columns(Idx),
- Fields = indexable_fields(Selector),
- lists:member(hd(Columns), Fields) andalso not is_text_search(Selector).
+ % This index is usable if all of the columns are
+ % restricted by the selector such that they are required to exist
+ % and the selector is not a text search (so requires a text index)
+ RequiredFields = columns(Idx),
+ mango_selector:has_required_fields(Selector, RequiredFields)
+ andalso not is_text_search(Selector).
is_text_search({[]}) ->
diff --git a/src/mango/src/mango_selector.erl b/src/mango/src/mango_selector.erl
index bcf3472..fe39986 100644
--- a/src/mango/src/mango_selector.erl
+++ b/src/mango/src/mango_selector.erl
@@ -15,7 +15,8 @@
-export([
normalize/1,
- match/2
+ match/2,
+ has_required_fields/2
]).
@@ -566,3 +567,110 @@ match({[{Field, Cond}]}, Value, Cmp) ->
match({[_, _ | _] = _Props} = Sel, _Value, _Cmp) ->
erlang:error({unnormalized_selector, Sel}).
+
+
+% Returns true if Selector requires all
+% fields in RequiredFields to exist in any matching documents.
+
+% For each condition in the selector, check
+% whether the field is in RequiredFields.
+% If it is, remove it from RequiredFields and continue
+% until we match then all or run out of selector to
+% match against.
+
+% Empty selector
+has_required_fields({[]}, _) ->
+ false;
+
+% No more required fields
+has_required_fields(_, []) ->
+ true;
+
+% No more selector
+has_required_fields([], _) ->
+ false;
+
+has_required_fields(Selector, RequiredFields) when not is_list(Selector) ->
+ has_required_fields([Selector], RequiredFields);
+
+% We can "see" through $and operator. We ignore other
+% combination operators because they can't be used to restrict
+% an index.
+has_required_fields([{[{<<"$and">>, Args}]}], RequiredFields)
+ when is_list(Args) ->
+ has_required_fields(Args, RequiredFields);
+
+has_required_fields([{[{Field, Cond}]} | Rest], RequiredFields) ->
+ case Cond of
+ % $exists:false is a special case - this is the only operator
+ % that explicitly does not require a field to exist
+ {[{<<"$exists">>, false}]} ->
+ has_required_fields(Rest, RequiredFields);
+ _ ->
+ has_required_fields(Rest, lists:delete(Field, RequiredFields))
+ end.
+
+
+%%%%%%%% module tests below %%%%%%%%
+
+-ifdef(TEST).
+-include_lib("eunit/include/eunit.hrl").
+
+has_required_fields_basic_test() ->
+ RequiredFields = [<<"A">>],
+ Selector = {[{<<"A">>, <<"foo">>}]},
+ Normalized = normalize(Selector),
+ ?assertEqual(true, has_required_fields(Normalized, RequiredFields)).
+
+has_required_fields_basic_failure_test() ->
+ RequiredFields = [<<"B">>],
+ Selector = {[{<<"A">>, <<"foo">>}]},
+ Normalized = normalize(Selector),
+ ?assertEqual(false, has_required_fields(Normalized, RequiredFields)).
+
+has_required_fields_empty_selector_test() ->
+ RequiredFields = [<<"A">>],
+ Selector = {[]},
+ Normalized = normalize(Selector),
+ ?assertEqual(false, has_required_fields(Normalized, RequiredFields)).
+
+has_required_fields_exists_false_test() ->
+ RequiredFields = [<<"A">>],
+ Selector = {[{<<"A">>,{[{<<"$exists">>, false}]}}]},
+ Normalized = normalize(Selector),
+ ?assertEqual(false, has_required_fields(Normalized, RequiredFields)).
+
+has_required_fields_and_true_test() ->
+ RequiredFields = [<<"A">>],
+ Selector = {[{<<"$and">>,
+ [
+ {[{<<"A">>, <<"foo">>}]},
+ {[{<<"B">>, <<"foo">>}]}
+ ]
+ }]},
+ Normalized = normalize(Selector),
+ ?assertEqual(true, has_required_fields(Normalized, RequiredFields)).
+
+has_required_fields_and_false_test() ->
+ RequiredFields = [<<"A">>, <<"C">>],
+ Selector = {[{<<"$and">>,
+ [
+ {[{<<"A">>, <<"foo">>}]},
+ {[{<<"B">>, <<"foo">>}]}
+ ]
+ }]},
+ Normalized = normalize(Selector),
+ ?assertEqual(false, has_required_fields(Normalized, RequiredFields)).
+
+has_required_fields_or_test() ->
+ RequiredFields = [<<"A">>],
+ Selector = {[{<<"$or">>,
+ [
+ {[{<<"A">>, <<"foo">>}]},
+ {[{<<"B">>, <<"foo">>}]}
+ ]
+ }]},
+ Normalized = normalize(Selector),
+ ?assertEqual(false, has_required_fields(Normalized, RequiredFields)).
+
+-endif.
\ No newline at end of file
diff --git a/src/mango/test/03-operator-test.py b/src/mango/test/03-operator-test.py
index 8637526..1af39f2 100644
--- a/src/mango/test/03-operator-test.py
+++ b/src/mango/test/03-operator-test.py
@@ -26,8 +26,8 @@ class OperatorTests:
"manager": True,
"favorites": {"$all": ["Lisp", "Python"]}
})
- self.assertEqual(len(docs), 4)
- user_ids = [2,12,9,14]
+ self.assertEqual(len(docs), 3)
+ user_ids = [2,12,9]
self.assertUserIds(user_ids, docs)
def test_all_non_array(self):
@@ -124,7 +124,7 @@ class OperatorTests:
"manager": True,
"favorites": {"$in": ["Ruby", "Python"]}
})
- self.assertUserIds([2,6,7,9,11,12,14], docs)
+ self.assertUserIds([2,6,7,9,11,12], docs)
def test_nin_operator_array(self):
docs = self.db.find({
diff --git a/src/mango/test/05-index-selection-test.py b/src/mango/test/05-index-selection-test.py
index 2fb0a40..ee0d604 100644
--- a/src/mango/test/05-index-selection-test.py
+++ b/src/mango/test/05-index-selection-test.py
@@ -23,7 +23,7 @@ class IndexSelectionTests(mango.UserDocsTests):
user_docs.add_text_indexes(klass.db, {})
def test_basic(self):
- resp = self.db.find({"name.last": "A last name"}, explain=True)
+ resp = self.db.find({"age": 123}, explain=True)
self.assertEqual(resp["index"]["type"], "json")
def test_with_and(self):
@@ -92,6 +92,78 @@ class IndexSelectionTests(mango.UserDocsTests):
else:
raise AssertionError("bad find")
+ def test_uses_all_docs_when_fields_do_not_match_selector(self):
+ # index exists on ["company", "manager"] but not ["company"]
+ # so we should fall back to all docs (so we include docs
+ # with no "manager" field)
+ selector = {
+ "company": "Pharmex"
+ }
+ docs = self.db.find(selector)
+ self.assertEqual(len(docs), 1)
+ self.assertEqual(docs[0]["company"], "Pharmex")
+ self.assertNotIn("manager", docs[0])
+
+ resp_explain = self.db.find(selector, explain=True)
+ self.assertEqual(resp_explain["index"]["type"], "special")
+
+ def test_uses_all_docs_when_selector_doesnt_require_fields_to_exist(self):
+ # as in test above, use a selector that doesn't overlap with the index
+ # due to an explicit exists clause
+ selector = {
+ "company": "Pharmex",
+ "manager": {"$exists": False}
+ }
+ docs = self.db.find(selector)
+ self.assertEqual(len(docs), 1)
+ self.assertEqual(docs[0]["company"], "Pharmex")
+ self.assertNotIn("manager", docs[0])
+
+ resp_explain = self.db.find(selector, explain=True)
+ self.assertEqual(resp_explain["index"]["type"], "special")
+
+ def test_uses_index_when_no_range_or_equals(self):
+ # index on ["manager"] should be valid because
+ # selector requires "manager" to exist. The
+ # selector doesn't narrow the keyrange so it's
+ # a full index scan
+ selector = {
+ "manager": {"$exists": True}
+ }
+ docs = self.db.find(selector)
+ self.assertEqual(len(docs), 14)
+
+ resp_explain = self.db.find(selector, explain=True)
+ self.assertEqual(resp_explain["index"]["type"], "json")
+
+
+ def test_reject_use_index_invalid_fields(self):
+ # index on ["company","manager"] which should not be valid
+ ddocid = "_design/a0c425a60cf3c3c09e3c537c9ef20059dcef9198"
+ selector = {
+ "company": "Pharmex"
+ }
+ try:
+ self.db.find(selector, use_index=ddocid)
+ except Exception, e:
+ self.assertEqual(e.response.status_code, 400)
+ else:
+ raise AssertionError("did not reject bad use_index")
+
+ def test_reject_use_index_sort_order(self):
+ # index on ["company","manager"] which should not be valid
+ ddocid = "_design/a0c425a60cf3c3c09e3c537c9ef20059dcef9198"
+ selector = {
+ "company": {"$gt": None},
+ "manager": {"$gt": None}
+ }
+ try:
+ self.db.find(selector, use_index=ddocid, sort=[{"manager":"desc"}])
+ except Exception, e:
+ self.assertEqual(e.response.status_code, 400)
+ else:
+ raise AssertionError("did not reject bad use_index")
+
# This doc will not be saved given the new ddoc validation code
# in couch_mrview
def test_manual_bad_view_idx01(self):
diff --git a/src/mango/test/user_docs.py b/src/mango/test/user_docs.py
index 9896e55..02ffe9f 100644
--- a/src/mango/test/user_docs.py
+++ b/src/mango/test/user_docs.py
@@ -493,7 +493,6 @@ DOCS = [
},
"company": "Pharmex",
"email": "faithhess@pharmex.com",
- "manager": True,
"favorites": [
"Erlang",
"Python",
--
To stop receiving notification emails like this one, please contact
['"commits@couchdb.apache.org" <co...@couchdb.apache.org>'].