Fix incorrect index selection when sort specified (#866)

It seems safe to assume that if a user specifies that
results should be sorted by a field, that field needs to exist
(but could be null) in the results returned.

In #816 we can only use an index if all its columns are
required to exist in the selector, so this improves
compatibility with the old behaviour by allowing sort
fields to be included in the index coverage check for
JSON indexes.

8 files changed, 93 insertions, 35 deletions

diff --git a/src/mango/src/mango_cursor.erl b/src/mango/src/mango_cursor.erl
index e0792b737..98b2d52bd 100644
--- a/src/mango/src/mango_cursor.erl
+++ b/src/mango/src/mango_cursor.erl
@@ -46,7 +46,7 @@
 
 create(Db, Selector0, Opts) ->
     Selector = mango_selector:normalize(Selector0),
-    UsableIndexes = mango_idx:get_usable_indexes(Db, Selector0, Opts),
+    UsableIndexes = mango_idx:get_usable_indexes(Db, Selector, Opts),
 
     {use_index, IndexSpecified} = proplists:lookup(use_index, Opts),
     case {length(UsableIndexes), length(IndexSpecified)} of
diff --git a/src/mango/src/mango_error.erl b/src/mango/src/mango_error.erl
index 4f8ae204d..4c55ef3f6 100644
--- a/src/mango/src/mango_error.erl
+++ b/src/mango/src/mango_error.erl
@@ -43,7 +43,7 @@ info(mango_cursor, {no_usable_index, selector_unsupported}) ->
     {
         400,
         <<"no_usable_index">>,
-        <<"There is no index available for this selector.">>
+        <<"The index specified with \"use_index\" is not usable for the query.">>
     };
 
 info(mango_json_bookmark, {invalid_bookmark, BadBookmark}) ->
diff --git a/src/mango/src/mango_idx.erl b/src/mango/src/mango_idx.erl
index c5f870d5b..4dd2e180d 100644
--- a/src/mango/src/mango_idx.erl
+++ b/src/mango/src/mango_idx.erl
@@ -20,7 +20,6 @@
 -export([
     list/1,
     recover/1,
-    for_sort/2,
 
     new/2,
     validate_new/2,
@@ -36,7 +35,7 @@
     def/1,
     opts/1,
     columns/1,
-    is_usable/2,
+    is_usable/3,
     start_key/2,
     end_key/2,
     cursor_mod/1,
@@ -57,9 +56,8 @@ list(Db) ->
     {ok, Indexes} = ddoc_cache:open(db_to_name(Db), ?MODULE),
     Indexes.
 
-get_usable_indexes(Db, Selector0, Opts) ->
-    Selector = mango_selector:normalize(Selector0),
 
+get_usable_indexes(Db, Selector, Opts) ->
     ExistingIndexes = mango_idx:list(Db),
     if ExistingIndexes /= [] -> ok; true ->
         ?MANGO_ERROR({no_usable_index, no_indexes_defined})
@@ -70,13 +68,17 @@ get_usable_indexes(Db, Selector0, Opts) ->
         ?MANGO_ERROR({no_usable_index, no_index_matching_name})
     end,
 
-    SortIndexes = mango_idx:for_sort(FilteredIndexes, Opts),
-    if SortIndexes /= [] -> ok; true ->
-        ?MANGO_ERROR({no_usable_index, missing_sort_index})
-    end,
+    SortFields = get_sort_fields(Opts),
+    UsableFilter = fun(I) -> is_usable(I, Selector, SortFields) end,
+    UsableIndexes0 = lists:filter(UsableFilter, FilteredIndexes),
+
+    case maybe_filter_by_sort_fields(UsableIndexes0, SortFields) of
+        {ok, SortIndexes} -> 
+            SortIndexes;
+        {error, no_usable_index} -> 
+            ?MANGO_ERROR({no_usable_index, missing_sort_index})
+    end.
 
-    UsableFilter = fun(I) -> mango_idx:is_usable(I, Selector) end,
-    lists:filter(UsableFilter, SortIndexes).
 
 recover(Db) ->
     {ok, DDocs0} = mango_util:open_ddocs(Db),
@@ -93,33 +95,38 @@ recover(Db) ->
     end, DDocs)}.
 
 
-for_sort(Indexes, Opts) ->
-    % If a sort was specified we have to find an index that
-    % can satisfy the request.
+get_sort_fields(Opts) ->
     case lists:keyfind(sort, 1, Opts) of
-        {sort, {SProps}} when is_list(SProps) ->
-            for_sort_int(Indexes, {SProps});
+        {sort, Sort} ->
+            mango_sort:fields(Sort);
         _ ->
-            Indexes
+            []
     end.
 
 
-for_sort_int(Indexes, Sort) ->
-    Fields = mango_sort:fields(Sort),
+maybe_filter_by_sort_fields(Indexes, []) ->
+    {ok, Indexes};
+
+maybe_filter_by_sort_fields(Indexes, SortFields) ->
     FilterFun = fun(Idx) ->
         Cols = mango_idx:columns(Idx),
         case {mango_idx:type(Idx), Cols} of
             {_, all_fields} ->
                 true;
             {<<"text">>, _} ->
-                sets:is_subset(sets:from_list(Fields), sets:from_list(Cols));
+                sets:is_subset(sets:from_list(SortFields), sets:from_list(Cols));
             {<<"json">>, _} ->
-                lists:prefix(Fields, Cols);
+                lists:prefix(SortFields, Cols);
             {<<"special">>, _} ->
-                lists:prefix(Fields, Cols)
+                lists:prefix(SortFields, Cols)
         end
     end,
-    lists:filter(FilterFun, Indexes).
+    case lists:filter(FilterFun, Indexes) of
+        [] ->
+            {error, no_usable_index};
+        FilteredIndexes ->
+            {ok, FilteredIndexes}
+    end.
 
 
 new(Db, Opts) ->
@@ -250,9 +257,9 @@ columns(#idx{}=Idx) ->
     Mod:columns(Idx).
 
 
-is_usable(#idx{}=Idx, Selector) ->
+is_usable(#idx{}=Idx, Selector, SortFields) ->
     Mod = idx_mod(Idx),
-    Mod:is_usable(Idx, Selector).
+    Mod:is_usable(Idx, Selector, SortFields).
 
 
 start_key(#idx{}=Idx, Ranges) ->
diff --git a/src/mango/src/mango_idx_special.erl b/src/mango/src/mango_idx_special.erl
index a8f94002b..12da1cbe5 100644
--- a/src/mango/src/mango_idx_special.erl
+++ b/src/mango/src/mango_idx_special.erl
@@ -20,7 +20,7 @@
     from_ddoc/1,
     to_json/1,
     columns/1,
-    is_usable/2,
+    is_usable/3,
     start_key/1,
     end_key/1
 ]).
@@ -63,7 +63,7 @@ columns(#idx{def=all_docs}) ->
     [<<"_id">>].
 
 
-is_usable(#idx{def=all_docs}, Selector) ->
+is_usable(#idx{def=all_docs}, Selector, _) ->
     Fields = mango_idx_view:indexable_fields(Selector),
     lists:member(<<"_id">>, Fields).
 
diff --git a/src/mango/src/mango_idx_text.erl b/src/mango/src/mango_idx_text.erl
index e00c241d2..e4ffc91db 100644
--- a/src/mango/src/mango_idx_text.erl
+++ b/src/mango/src/mango_idx_text.erl
@@ -22,7 +22,7 @@
     from_ddoc/1,
     to_json/1,
     columns/1,
-    is_usable/2,
+    is_usable/3,
     get_default_field_options/1
 ]).
 
@@ -125,7 +125,7 @@ columns(Idx) ->
     end.
 
 
-is_usable(Idx, Selector) ->
+is_usable(Idx, Selector, _) ->
     case columns(Idx) of
         all_fields ->
             true;
diff --git a/src/mango/src/mango_idx_view.erl b/src/mango/src/mango_idx_view.erl
index 4cb039c4a..8331683a0 100644
--- a/src/mango/src/mango_idx_view.erl
+++ b/src/mango/src/mango_idx_view.erl
@@ -20,7 +20,7 @@
     remove/2,
     from_ddoc/1,
     to_json/1,
-    is_usable/2,
+    is_usable/3,
     columns/1,
     start_key/1,
     end_key/1,
@@ -113,12 +113,17 @@ columns(Idx) ->
     [Key || {Key, _} <- Fields].
 
 
-is_usable(Idx, Selector) ->
-    % This index is usable if all of the columns are 
+is_usable(Idx, Selector, SortFields) ->
+    % 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)
+
+    % sort fields are required to exist in the results so 
+    % we don't need to check the selector for these
+    RequiredFields1 = ordsets:subtract(lists:usort(RequiredFields), lists:usort(SortFields)),
+
+    mango_selector:has_required_fields(Selector, RequiredFields1)
         andalso not is_text_search(Selector).
 
 
diff --git a/src/mango/src/mango_selector.erl b/src/mango/src/mango_selector.erl
index fe3998683..4ff36945a 100644
--- a/src/mango/src/mango_selector.erl
+++ b/src/mango/src/mango_selector.erl
@@ -609,7 +609,7 @@ has_required_fields([{[{Field, Cond}]} | Rest], RequiredFields) ->
         _ ->
             has_required_fields(Rest, lists:delete(Field, RequiredFields))
     end.
-    
+
 
 %%%%%%%% module tests below %%%%%%%%
 
diff --git a/src/mango/test/02-basic-find-test.py b/src/mango/test/02-basic-find-test.py
index a8725ffa8..72a4e3feb 100644
--- a/src/mango/test/02-basic-find-test.py
+++ b/src/mango/test/02-basic-find-test.py
@@ -222,6 +222,52 @@ class BasicFindTests(mango.UserDocsTests):
         docs2 = list(reversed(sorted(docs1, key=lambda d: d["age"])))
         assert docs1 is not docs2 and docs1 == docs2
 
+    def test_sort_desc_complex(self):
+        docs = self.db.find({
+            "company": {"$lt": "M"},
+            "$or": [
+                {"company": "Dreamia"},
+                {"manager": True}
+            ]
+        }, sort=[{"company":"desc"}, {"manager":"desc"}])
+        
+        companies_returned = list(d["company"] for d in docs)
+        desc_companies = sorted(companies_returned, reverse=True)
+        self.assertEqual(desc_companies, companies_returned)
+
+    def test_sort_with_primary_sort_not_in_selector(self):
+        try:
+            docs = self.db.find({
+                "name.last": {"$lt": "M"}
+            }, sort=[{"name.first":"desc"}])    
+        except Exception as e:
+            self.assertEqual(e.response.status_code, 400)
+            resp = e.response.json()
+            self.assertEqual(resp["error"], "no_usable_index")
+        else:
+            raise AssertionError("expected find error")
+
+    def test_sort_exists_true(self):
+        docs1 = self.db.find({"age": {"$gt": 0, "$exists": True}}, sort=[{"age":"asc"}])
+        docs2 = list(sorted(docs1, key=lambda d: d["age"]))
+        assert docs1 is not docs2 and docs1 == docs2
+
+    def test_sort_desc_complex_error(self):
+        try:
+            self.db.find({
+            "company": {"$lt": "M"},
+            "$or": [
+                {"company": "Dreamia"},
+                {"manager": True}
+            ]
+        }, sort=[{"company":"desc"}])
+        except Exception as e:
+            self.assertEqual(e.response.status_code, 400)
+            resp = e.response.json()
+            self.assertEqual(resp["error"], "no_usable_index")
+        else:
+            raise AssertionError("expected find error")
+
     def test_fields(self):
         selector = {"age": {"$gt": 0}}
         docs = self.db.find(selector, fields=["user_id", "location.address"])