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.

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 d5dcd0c07..7e9e6464c 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 bcf347201..fe3998683 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 863752682..1af39f205 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 2fb0a405b..ee0d604c3 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 9896e5596..02ffe9ffc 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",