Choose index based on fields match (#469)

* Choose index based on Prefix and FieldRange

First choose the index with the lowest difference between its 
Prefix and the FieldRanges. If that is equal, then
choose the index with the least number of 
fields in the index. If we still cannot break the tie, 
then choose alphabetically based on ddocId.
Return the first element's Index and IndexRanges.

2 files changed, 128 insertions, 13 deletions

diff --git a/src/mango/src/mango_cursor_view.erl b/src/mango/src/mango_cursor_view.erl
index 2918a2d08..ffa5ec168 100644
--- a/src/mango/src/mango_cursor_view.erl
+++ b/src/mango/src/mango_cursor_view.erl
@@ -110,7 +110,11 @@ composite_indexes(Indexes, FieldRanges) ->
     lists:foldl(fun(Idx, Acc) ->
         Cols = mango_idx:columns(Idx),
         Prefix = composite_prefix(Cols, FieldRanges),
-        [{Idx, Prefix} | Acc]
+        % Calcuate the difference between the FieldRanges/Selector
+        % and the Prefix. We want to select the index with a prefix
+        % that is as close to the FieldRanges as possible
+        PrefixDifference = length(FieldRanges) - length(Prefix),
+        [{Idx, Prefix, PrefixDifference} | Acc]
     end, [], Indexes).
 
 
@@ -125,29 +129,40 @@ composite_prefix([Col | Rest], Ranges) ->
     end.
 
 
-% Low and behold our query planner. Or something.
-% So stupid, but we can fix this up later. First
-% pass: Sort the IndexRanges by (num_columns, idx_name)
-% and return the first element. Yes. Its going to
-% be that dumb for now.
+% The query planner
+% First choose the index with the lowest difference between its 
+% Prefix and the FieldRanges. If that is equal, then
+% choose the index with the least number of 
+% fields in the index. If we still cannot break the tie, 
+% then choose alphabetically based on ddocId.
+% Return the first element's Index and IndexRanges.
 %
 % In the future we can look into doing a cached parallel
 % reduce view read on each index with the ranges to find
 % the one that has the fewest number of rows or something.
 choose_best_index(_DbName, IndexRanges) ->
-    Cmp = fun({A1, A2}, {B1, B2}) ->
-        case length(A2) - length(B2) of
+    Cmp = fun({IdxA, _PrefixA, PrefixDifferenceA}, {IdxB, _PrefixB, PrefixDifferenceB}) ->
+        case PrefixDifferenceA - PrefixDifferenceB of
             N when N < 0 -> true;
             N when N == 0 ->
-                % This is a really bad sort and will end
-                % up preferring indices based on the
-                % (dbname, ddocid, view_name) triple
-                A1 =< B1;
+                ColsLenA = length(mango_idx:columns(IdxA)),
+                ColsLenB = length(mango_idx:columns(IdxB)),
+                case ColsLenA - ColsLenB of
+                    M when M < 0 -> 
+                        true;
+                    M when M == 0 ->
+                        % We have no other way to choose, so at this point 
+                        % select the index based on (dbname, ddocid, view_name) triple
+                        IdxA =< IdxB;
+                    _ -> 
+                        false
+                end;
             _ ->
                 false
         end
     end,
-    hd(lists:sort(Cmp, IndexRanges)).
+    {SelectedIndex, SelectedIndexRanges, _} = hd(lists:sort(Cmp, IndexRanges)),
+    {SelectedIndex, SelectedIndexRanges}.
 
 
 handle_message({meta, _}, Cursor) ->
diff --git a/src/mango/test/12-use-correct-index.py b/src/mango/test/12-use-correct-index.py
new file mode 100644
index 000000000..f1eaf5fe8
--- /dev/null
+++ b/src/mango/test/12-use-correct-index.py
@@ -0,0 +1,100 @@
+# Licensed under the Apache License, Version 2.0 (the "License"); you may not
+# use this file except in compliance with the License. You may obtain a copy of
+# the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+# License for the specific language governing permissions and limitations under
+# the License.
+
+import mango
+import copy
+
+DOCS = [
+    {
+        "_id": "_design/my-design-doc",
+    },
+    {
+        "_id": "54af50626de419f5109c962f",
+        "user_id": 0,
+        "age": 10,
+        "name": "Jimi",
+        "location": "UK",
+        "number": 4
+    },
+    {
+        "_id": "54af50622071121b25402dc3",
+        "user_id": 1,
+        "age": 12,
+        "name": "Eddie",
+        "location": "ZAR",
+        "number": 2
+    },
+    {
+        "_id": "54af50622071121b25402dc6",
+        "user_id": 1,
+        "age": 6,
+        "name": "Harry",
+        "location": "US",
+        "number":8
+    },
+    {
+        "_id": "54af50622071121b25402dc9",
+        "name": "Eddie",
+        "occupation": "engineer",
+        "number":7
+    },
+]
+
+class ChooseCorrectIndexForDocs(mango.DbPerClass):
+    def setUp(self):
+        self.db.recreate()
+        self.db.save_docs(copy.deepcopy(DOCS))
+
+    def test_choose_index_with_one_field_in_index(self):
+        self.db.create_index(["name", "age", "user_id"], ddoc="aaa")
+        self.db.create_index(["name"], ddoc="zzz")
+        explain = self.db.find({"name": "Eddie"}, explain=True)
+        assert explain["index"]["ddoc"] == '_design/zzz'
+
+    def test_choose_index_with_two(self):
+        self.db.create_index(["name", "age", "user_id"], ddoc="aaa")
+        self.db.create_index(["name", "age"], ddoc="bbb")
+        self.db.create_index(["name"], ddoc="zzz")
+        explain = self.db.find({"name": "Eddie", "age":{"$gte": 12}}, explain=True)
+        assert explain["index"]["ddoc"] == '_design/bbb'
+
+    def test_choose_index_alphabetically(self):
+        self.db.create_index(["name", "age", "user_id"], ddoc="aaa")
+        self.db.create_index(["name", "age", "location"], ddoc="bbb")
+        self.db.create_index(["name"], ddoc="zzz")
+        explain = self.db.find({"name": "Eddie", "age": {"$gte": 12}}, explain=True)
+        assert explain["index"]["ddoc"] == '_design/aaa'
+
+    def test_choose_index_most_accurate(self):
+        self.db.create_index(["name", "location", "user_id"], ddoc="aaa")
+        self.db.create_index(["name", "age", "user_id"], ddoc="bbb")
+        self.db.create_index(["name"], ddoc="zzz")
+        explain = self.db.find({"name": "Eddie", "age": {"$gte": 12}}, explain=True)
+        assert explain["index"]["ddoc"] == '_design/bbb'
+    
+    def test_choose_index_most_accurate_in_memory_selector(self):
+        self.db.create_index(["name", "location", "user_id"], ddoc="aaa")
+        self.db.create_index(["name", "age", "user_id"], ddoc="bbb")
+        self.db.create_index(["name"], ddoc="zzz")
+        explain = self.db.find({"name": "Eddie", "number": {"$lte": 12}}, explain=True)
+        assert explain["index"]["ddoc"] == '_design/zzz'
+
+    def test_chooses_idxA(self):
+        DOCS2 = [
+            {"a":1, "b":1, "c":1},
+            {"a":1000, "d" : 1000, "e": 1000}
+        ]
+        self.db.save_docs(copy.deepcopy(DOCS2))
+        self.db.create_index(["a", "b", "c"])
+        self.db.create_index(["a", "d", "e"])
+        explain = self.db.find({"a": {"$gt": 0}, "b": {"$gt": 0}, "c": {"$gt": 0}}, explain=True)
+        assert explain["index"]["def"]["fields"] == [{'a': 'asc'}, {'b': 'asc'}, {'c': 'asc'}]